社区讨论
本人蒟蒻刚学OI,请问开O2后全WA掉是怎么回事?
P1074[NOIP 2009 提高组] 靶形数独参与者 4已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @mi6xm76v
- 此快照首次捕获于
- 2025/11/20 12:29 4 个月前
- 此快照最后确认于
- 2025/11/20 12:29 4 个月前
我很菜所以只会暴搜,写完以后有70分,有一个点因为没特判无解WA的,还有5个点TLE。
然后我想先不管特判,直接开O2后看还会不会超时,结果所有点全部WA掉了。之前听说开了O2后如果代码不规范会出现这种问题,但我太蒻了还没发现哪里有问题。恳请各位大佬帮我看看到底是哪里出了问题。谢谢!
CPP#include<bits/stdc++.h>
using namespace std;
int mp[10][10],ans;
bool vis[3][10][10];//横,竖,九宫格
int score[10][10]=
{{0,0,0,0,0,0,0,0,0,0},
{0,6,6,6,6,6,6,6,6,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,9,10,9,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,6,6,6,6,6,6,6,6}};
struct line{
int num,id;
} l[10];
inline int read()
{
char ch=getchar();
int f=1,x=0;
while (ch<'0' || ch>'9')
{
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
inline int nine(int x,int y)
{
return (x-1)/3*3+(y-1)/3+1;
}
int dfs(int id,int y)
{
int x=l[id].id,mx=0;
for (int i=1;i<=9;i++)
{
int now=0;
if (vis[0][x][i] || vis[1][y][i] || vis[2][nine(x,y)][i]) continue;
now+=i*score[x][y];
vis[0][x][i]=1;
vis[1][y][i]=1;
vis[2][nine(x,y)][i]=1;
mp[x][y]=i;
int nxt=y;
while (mp[x][nxt]) nxt++;
if (nxt==10) //搜完
{
if (id==9) return now; //只能选一个,当前就是最大值
id++;
for (int j=1;j<=9;j++)
{
if (!mp[id][j])
{
now+=dfs(id,j);
break;
}
}
}
else now+=dfs(id,nxt);
vis[0][x][i]=0;
vis[1][y][i]=0;
vis[2][nine(x,y)][i]=0;
mp[x][y]=0;
mx=max(mx,now);
}
return mx;
}
inline bool cmp(line x,line y)
{
return x.num>y.num;
}
int main()
{
for (int i=1;i<=9;i++)
{
l[i].id=i;
for (int j=1;j<=9;j++)
{
mp[i][j]=read();
ans+=mp[i][j]*score[i][j];
l[i].num++;
vis[0][i][mp[i][j]]=1;
vis[1][j][mp[i][j]]=1;
vis[2][nine(i,j)][mp[i][j]]=1;
}
}
sort(l+1,l+10,cmp);
for (int i=1;i<=9;i++)
{
int id=l[i].id;
bool stat=0;
for (int j=1;j<=9;j++)
{
if (!mp[id][j])
{
ans+=dfs(i,j);
stat=1;
break;
}
}
if (stat) break;
}
printf("%d",ans);
//system("pause");
return 0;
}
回复
共 4 条回复,欢迎继续交流。
正在加载回复...