社区讨论

提供一个简洁的做法

P1092[NOIP 2004 提高组] 虫食算参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@locuwfjx
此快照首次捕获于
2023/10/30 20:08
2 年前
此快照最后确认于
2023/11/05 06:42
2 年前
查看原帖
(这个代码是我好几年前写的,由于没有剪枝一直T一个点,到今天开O2才过了
就是从右向坐一列列枚举这三位的字母是什么,如果和之前重复了就回溯
这里我是从大到小枚举的,这样枚举结束的标志就是-1
之所以要发题解,是因为代码中用了大量的goto,可以在这里看到goto的巧妙应用,极大地压缩了代码的长度
CPP
#include<cstdio>
#include<cstdlib>
int n,w[27],v[27];
char a[27],b[27],c[27];//w是ABCD..等字母分别对应的数字,v是0123..等数字是否已经被访问
void dfs(int u,int d) { //u是列编号,d是进位的数字
    if (u<0) { if (d==0) { for (int i=0;i<n;++i) printf("%d ",w[i]); exit(0); } return; }
    int x,y,z,t,&wa=w[a[u]],&wb=w[b[u]],&wc=w[c[u]];
    if ((x=wa)==-1) wa=n;
    xxx:
        if (x==-1) { do if (--wa<0) goto xx; while (v[wa]); v[wa]=1; }
        if ((y=wb)==-1) wb=n;
        yyy:
            if (y==-1) { do if (--wb<0) goto yy; while (v[wb]); v[wb]=1; }
                t=(wa+wb+d)%n;
                if ((z=wc)==-1&&!v[t]) v[t]=1,wc=t;
                    if (t==wc) dfs(u-1,(wa+wb+d)/n); //这里进入下一层递归
                if (z==-1&&wc!=-1) v[wc]=0,wc=-1;
            if (y==-1) { v[wb]=0; goto yyy; } // y==-1意味着当前层之前w[b[u]]这个字母之前没有被赋值,因而可以继续枚举它的值
        yy:
        if (x==-1) { v[wa]=0; goto xxx; } //同“y==-1”的注释
    xx:;
}
signed main() {
    scanf("%d%s%s%s",&n,a,b,c);
    for (int i=0;i<n;++i) a[i]-=65,b[i]-=65,c[i]-=65,w[i]=-1;
    dfs(n-1,0);
}

回复

2 条回复,欢迎继续交流。

正在加载回复...