Luogu P1092 虫食算爆搜

心路历程：震惊，我竟然得了$90$分！！。。。康康数据。。。奥。。（忽然有了邪恶的卡数据的想法）

于是把$for(int \space i=0;i<n;++i)$改成了$for(int \space i=n-1;i>0;--i) $

然后，我$90$~

然后，我开了$O2$，$A$了$OvO$。。。

upd:然后第二天：可以再加个剪枝？

what，我A了？$41ms（without \space O2）or \space 33ms (with \space O2)$

(所以就当我的是正解了$qwq$)

我的思路很暴力：

我的思路很暴力：
由于最后一位没有进位，所以这一列的三个字母的关系是确定的，而不会像后面一样存在进位，所以就是暴力大枚举，对于竖式的每一列，枚举没用过的数，然后判一下这一列是否合法（记得要累积上一位的进位），合法的话，再判一下整个竖式所有已知数是否合法，合法接着搜，不合法枚举下一个。。。复杂度玄学。。。

又臭又长又慢的代码$qwq$

解释一下：$s[i][j]$是指第$i$行的第$j$个字母（已在$void\space gs()$中转化为数字，'A'对应$0$,'B'对应$1$,以此类推），$rw[x]$指x（已经转化为数字的字母）所代表的真正数字，$vis[x]$表示$x$有没有被使用过，$inc[i]$表示第$i$列有没有进位。

$90pts$

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<cctype>

#include<cstdlib>

#include<iomanip>

#include<vector>

#include<map>

#include<set>

#define ll long long

#define R register int

static char B[<<],*S=B,*D=B;

#define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<8,stdin),S==D)?EOF:*S++)

using namespace std;

inline int g() {

    R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;

    do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;

}

inline void gs(int* c) {

    register char ch; while(!isalpha(ch=getchar()));

    do *++c=int(ch-'A'); while(isalpha(ch=getchar()));

} int n,rw[],s[][],inc[];

bool vis[];

inline void dfs(int x) {

    if(x==) {for(R i=;i<n;++i) printf("%d ",rw[i]); exit();} //print();

    if(rw[s[][x]]==-) {

        for(R i=n-;i>=;--i) if(!vis[i]) {

                rw[s[][x]]=i,vis[i]=true;

                if(rw[s[][x]]==-) {

                    for(R j=;j<n;++j) if(!vis[j]){

                        rw[s[][x]]=j,vis[j]=true;

                        if(rw[s[][x]]==-) {

                            rw[s[][x]]=(rw[s[][x]]+rw[s[][x]]+inc[x]);

                            if(rw[s[][x]]>=n) rw[s[][x]]%=n,inc[x-]=;

                            if(vis[rw[s[][x]]]) {rw[s[][x]]=-; inc[x-]=; goto ed2;}

                            vis[rw[s[][x]]]=true; dfs(x-); inc[x-]=; vis[rw[s[][x]]]=false; rw[s[][x]]=-;

                        } else {

                            if(rw[s[][x]]==(rw[s[][x]]+rw[s[][x]]+inc[x])%n) inc[x-]=(rw[s[][x]]+rw[s[][x]]+inc[x])/n,dfs(x-),inc[x-]=;

                        }

                        ed2: rw[s[][x]]=-,vis[j]=false;

                    }

                } else {

                    if(rw[s[][x]]==-) {

                        rw[s[][x]]=(rw[s[][x]]+rw[s[][x]]+inc[x]);

                        if(rw[s[][x]]>=n) rw[s[][x]]%=n,inc[x-]=;

                        if(vis[rw[s[][x]]]) {rw[s[][x]]=-; inc[x-]=; goto enddd;}

                        vis[rw[s[][x]]]=true; dfs(x-); inc[x-]=; vis[rw[s[][x]]]=false; rw[s[][x]]=-;

                    } else {

                        if(rw[s[][x]]==(rw[s[][x]]+rw[s[][x]]+inc[x])%n) inc[x-]=(rw[s[][x]]+rw[s[][x]]+inc[x])/n,dfs(x-),inc[x-]=;

                        else {inc[x-]=; }

                    } enddd:;

                } rw[s[][x]]=-,vis[i]=false;

        }

    } else {

        if(rw[s[][x]]==-) {

            for(R j=n-;j>=;--j) if(!vis[j]) {

                rw[s[][x]]=j,vis[j]=true;

                if(rw[s[][x]]==-) {

                    rw[s[][x]]=(rw[s[][x]]+rw[s[][x]]+inc[x]);

                    if(rw[s[][x]]>=n) rw[s[][x]]%=n,inc[x-]=;

                    if(vis[rw[s[][x]]]) {rw[s[][x]]=-; inc[x-]=; goto ed21;}

                    vis[rw[s[][x]]]=true; dfs(x-); inc[x-]=; vis[rw[s[][x]]]=false; rw[s[][x]]=-;

                } else {

                    if(rw[s[][x]]==(rw[s[][x]]+rw[s[][x]]+inc[x])%n) inc[x-]=(rw[s[][x]]+rw[s[][x]]+inc[x])/n,dfs(x-),inc[x-]=;

                } ed21: vis[j]=false;

            } rw[s[][x]]=-;

        } else {

            if(rw[s[][x]]==-) {

                rw[s[][x]]=(rw[s[][x]]+rw[s[][x]]+inc[x]);

                if(rw[s[][x]]>=n) rw[s[][x]]%=n,inc[x-]=;

                if(vis[rw[s[][x]]]) {rw[s[][x]]=-; inc[x-]=; goto end;}

                vis[rw[s[][x]]]=true; dfs(x-); inc[x-]=; vis[rw[s[][x]]]=false; rw[s[][x]]=-;

            } else {

                if(rw[s[][x]]==(rw[s[][x]]+rw[s[][x]]+inc[x])%n) inc[x-]=(rw[s[][x]]+rw[s[][x]]+inc[x])/n,dfs(x-),inc[x-]=;

            } end:;

        }

    }

}

signed main() {

    n=g(); for(R i=;i<=;++i) gs(s[i]);

    memset(rw,0xff,sizeof(rw)); dfs(n);

}

$100pts$

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<cctype>

#include<cstdlib>

#include<iomanip>

#include<vector>

#include<map>

#include<set>

#define ll long long

#define R register int

static char B[<<],*S=B,*D=B;

#define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<8,stdin),S==D)?EOF:*S++)

using namespace std;

inline int g() {

    R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;

    do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;

}

inline void gs(int* c) {

    register char ch; while(!isalpha(ch=getchar()));

    do *++c=int(ch-'A'); while(isalpha(ch=getchar()));

} int n,rw[],s[][],inc[];

bool vis[];

inline bool ck() {

    for(R i=;i<=n;++i) {

        if(rw[s[][i]]!=-&&(rw[s[][i]])!=-&&(rw[s[][i]])!=-)  {

            if(((rw[s[][i]])+(rw[s[][i]])+)%n!=(rw[s[][i]])&&((rw[s[][i]])+(rw[s[][i]]))%n!=rw[s[][i]]) return false;

        }

    } return true;

}

inline void dfs(int x) {

    if(x==) if(!inc[]){for(R i=;i<n;++i) printf("%d ",rw[i]); exit();} //print();

        else return ;

    if(rw[s[][x]]==-) {

        for(R i=n-;i>=;--i) if(!vis[i]) {

                rw[s[][x]]=i,vis[i]=true;

                if(rw[s[][x]]==-) {

                    for(R j=;j<n;++j) if(!vis[j]){

                        rw[s[][x]]=j,vis[j]=true;

                        if(rw[s[][x]]==-) {

                            rw[s[][x]]=(rw[s[][x]]+rw[s[][x]]+inc[x]);

                            if(rw[s[][x]]>=n) rw[s[][x]]%=n,inc[x-]=;

                            if(vis[rw[s[][x]]]||!ck()) {rw[s[][x]]=-; inc[x-]=; goto ed2;}

                            vis[rw[s[][x]]]=true; dfs(x-); inc[x-]=; vis[rw[s[][x]]]=false; rw[s[][x]]=-;

                        } else {

                            if(rw[s[][x]]==(rw[s[][x]]+rw[s[][x]]+inc[x])%n&&ck()) inc[x-]=(rw[s[][x]]+rw[s[][x]]+inc[x])/n,dfs(x-),inc[x-]=;

                        }

                        ed2: rw[s[][x]]=-,vis[j]=false;

                    }

                }

                else {

                    if(rw[s[][x]]==-) {

                        rw[s[][x]]=(rw[s[][x]]+rw[s[][x]]+inc[x]);

                        if(rw[s[][x]]>=n) rw[s[][x]]%=n,inc[x-]=;

                        if(vis[rw[s[][x]]]||!ck()) {rw[s[][x]]=-; inc[x-]=; goto enddd;}

                        vis[rw[s[][x]]]=true; dfs(x-); inc[x-]=; vis[rw[s[][x]]]=false; rw[s[][x]]=-;

                    } else {

                        if(rw[s[][x]]==(rw[s[][x]]+rw[s[][x]]+inc[x])%n&&ck()) inc[x-]=(rw[s[][x]]+rw[s[][x]]+inc[x])/n,dfs(x-),inc[x-]=;

                        else {inc[x-]=; }

                    } enddd:;

                } rw[s[][x]]=-,vis[i]=false;

        }

    } else {

        if(rw[s[][x]]==-) {

            for(R j=n-;j>=;--j) if(!vis[j]) {

                rw[s[][x]]=j,vis[j]=true;

                if(rw[s[][x]]==-) {

                    rw[s[][x]]=(rw[s[][x]]+rw[s[][x]]+inc[x]);

                    if(rw[s[][x]]>=n) rw[s[][x]]%=n,inc[x-]=;

                    if(vis[rw[s[][x]]]||!ck()) {rw[s[][x]]=-; inc[x-]=; goto ed21;}

                    vis[rw[s[][x]]]=true; dfs(x-); inc[x-]=; vis[rw[s[][x]]]=false; rw[s[][x]]=-;

                } else {

                    if(rw[s[][x]]==(rw[s[][x]]+rw[s[][x]]+inc[x])%n&&ck()) inc[x-]=(rw[s[][x]]+rw[s[][x]]+inc[x])/n,dfs(x-),inc[x-]=;

                } ed21: vis[j]=false;

            } rw[s[][x]]=-;

        } else {

            if(rw[s[][x]]==-) {

                rw[s[][x]]=(rw[s[][x]]+rw[s[][x]]+inc[x]);

                if(rw[s[][x]]>=n) rw[s[][x]]%=n,inc[x-]=;

                if(vis[rw[s[][x]]]||!ck()) {rw[s[][x]]=-; inc[x-]=; goto end;}

                vis[rw[s[][x]]]=true; dfs(x-); inc[x-]=; vis[rw[s[][x]]]=false; rw[s[][x]]=-;

            } else {

                if(rw[s[][x]]==(rw[s[][x]]+rw[s[][x]]+inc[x])%n&&ck()) inc[x-]=(rw[s[][x]]+rw[s[][x]]+inc[x])/n,dfs(x-),inc[x-]=;

            } end:;

        }

    }

}

signed main() {

#ifdef JACK

    freopen("NOIPAK++.in","r",stdin);

#endif

    n=g(); for(R i=;i<=;++i) gs(s[i]);

    memset(rw,0xff,sizeof(rw)); dfs(n);

}

2019.06.06

巴特西

Luogu P1092 虫食算爆搜

最新文章

热门文章

巴特西

Luogu P1092 虫食算 爆搜

最新文章

热门文章

Luogu P1092 虫食算爆搜