本文共 3629 字，大约阅读时间需要 12 分钟。
NOI2000的题吓死人啊。
一开始写了一个裸的搜索，发现样例跑的都有点吃力。然后弃疗了。
看完题解后觉得其实优化也不是很难想。
显然先枚举=+*。然后每一行之前没出现过的字符就暴力枚举对应的数字。
这样做不加剪枝是过不了的。
然后有一个显然的优化是，=+*这三个确定后一块块数字的位数也就确定了。
对于每一行，我们算出左右两边的可能的答案位数范围，然后判断有无交集，没有就不合法。
然后就能过了？
当然，还有一些，比如说当前搜下去不会对答案产生变动就剪枝。
其实还可以加上如从低位到高位搜，然后确定低位，不合法就剪枝。但感觉这个有点烦就没加。
#include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define rep(i,x,y) for(i=x;i<=y;i++)#define _rep(i,x,y) for(i=x;i>=y;i--)#define REP(i,x,y) for(int i=(x);i<=(y);i++)#define _REP(i,x,y) for(int i=(x);i>=(y);i--)#define CL(S,x) memset(S,x,sizeof(S))#define CP(S1,S2) memcpy(S1,S2,sizeof(S2))#define ALL(x,S) for(__typeof((v).end()) x=S.begin();x!=S.end();x++)#define pb push_back#define IN insert#define ER erase#define BE begin()#define ED end() #define LB lower_bound#define UB upper_bound#define mp make_pair#define fi first#define se second#define upmin(x,y) x=min(x,y)#define upmax(x,y) x=max(x,y)#define COUT(S,x) cout< < < < inline void read(T&x){bool fu=0;char c;for(c=getchar();c<=32;c=getchar());if(c=='-')fu=1,c=getchar();for(x=0;c>32;c=getchar())x=x*10+c-'0';if(fu)x=-x;};template inline void read(T&x,T&y){read(x);read(y);}template inline void read(T&x,T&y,T&z){read(x);read(y);read(z);}inline char getc(){char c;for(c=getchar();c<=32;c=getchar());return c;}typedef long long ll;typedef long double ld;typedef pair pii;const int inf=int(1e9);int T,n,i,j,k,l,p,c;char a[1111][13];int len[1111];int w[15];int cnt[13][1111];bool c2[15],c1[15];int lg2[(1<<10)+10];int ans[15];int st[15];bool mark[15];bool near[128][128];char eq,mul,add;bool sol;bool caneq(){ CL(c1,1); for(char c='a';c<='m';c++) rep(i,1,T) { bool can2=1; rep(j,1,len[i]) { if(j =0;}int cl(){ int i,tot=0; for(;mark[st[0]-1];st[0]--) st[st[0]-1]=st[st[0]-1]*st[st[0]]; rep(i,1,st[0])tot+=st[i];st[0]=0; return tot;}bool check(int d){ int i,j,k,la=-1,left=-1,right=-1;st[0]=0; rep(i,1,len[d]) { int c=w[a[d][i]-'a']; if(D(c)) if(D(la))st[st[0]]=st[st[0]]*10+c; else st[++st[0]]=c; else { if(st[0]==0)return 0; for(;mark[st[0]-1];st[0]--) st[st[0]-1]=st[st[0]-1]*st[st[0]]; if(c==-3)mark[st[0]]=1; else if(c==-1)left=cl(); else mark[st[0]]=0; } la=c; } right=cl(); return left==right;}void go(int d,int nl,int S) //dfs{ bool ppp=1;rep(i,0,12)if(!(ans[i]==w[i]||ans[i]==-200)){ppp=0;break;}if(ppp)return; if(d>T) { //rep(i,0,12) printf("%c : %d\n",'a'+i,w[i]);printf("end\n"); sol=1; rep(i,0,12)if(w[i]!=inf) { if(ans[i]==-100)ans[i]=w[i]; else if(ans[i]!=w[i])ans[i]=-200; } else ans[i]=-200; return; } else { if(nl>len[d]) { if(check(d)) go(d+1,1,S); return; } int cc=a[d][nl]-'a'; if(w[cc]==inf) { for(int S2=S;S2;S2-=S2&-S2) { int t=lg2[S2&-S2]; if(nl==1&&t==0&&w[a[d][2]-'a']>0)continue; w[cc]=t; go(d,nl+1,S-(S2&-S2)); w[cc]=inf; } } else go(d,nl+1,S); }}void print(){ int i; rep(i,0,12) if(ans[i]>=-3) { putchar('a'+i); if(ans[i]==-3)putchar('*'); else if(ans[i]==-2)putchar('+'); else if(ans[i]==-1)putchar('='); else putchar('0'+ans[i]); putchar('\n'); } if(!sol)printf("noway\n");}int g,lw[15],rw[15];void clw(int&L,int&R){L=R=0;for(;g;g--)upmax(L,lw[g]),R=max(rw[g],R)+(R>0);}bool predfs(){ int d,i,j,la,Llw,Lrw,Rlw,Rrw; rep(d,1,T){ g=0;la=-1; rep(i,1,len[d]){ int c=w[a[d][i]-'a']; if(c==inf){if(la<0)g++,lw[g]=rw[g]=0;lw[g]++;rw[g]++;} else{ if(g==0)return 0; for(;mark[g-1];g--) lw[g-1]+=lw[g]-1,rw[g-1]+=rw[g]; if(c==-3)mark[g]=1; else if(c==-2)mark[g]=0; else if(c==-1)clw(Llw,Lrw); } la=c; } clw(Rlw,Rrw); if(Lrw
转载于:https://www.cnblogs.com/oldmanren/p/3808583.html