社区讨论

本人蒟蒻刚学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 条回复,欢迎继续交流。

正在加载回复...