高中学OI很是失败，于是心里总是堵着，想要大学翻盘？
似乎大学可以搞ACM，然而要选拔，还要刷好多题。。（还有英语）
于是我要复出啦！
从水题开始，这次坚决不看题解，动脑仔细搞！
虽是水题。。但由于我现在人水了。。不能1A。。。
本集提要：全是搜索
poj1321 棋盘问题
看到这个题，第一反应IDDFS，又一想。。杀鸡焉用牛刀，查个重不就行了。
又一想，查你妹的重！！！这种题一定是玄学，然后瞎写了个没查重的，直接爆搜。
然后TLE，然后发现自己SB。然后：
横排，纵排不能有旗子且放旗子的顺序没规定-》直接从第一排往下放就行了，这样也不用查重。
然后直接DFS。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=10; char s[N][N]; bool vis[N]; int n,k,ans; void dfs(int ii,int cnt)//已经放了几个 并且在哪个右下 { if(cnt>=k){ans++;return;} for(int i=ii+1;i<=n;i++) for(int j=1;j<=n;j++) if(!vis[j]) { if(s[i][j]=='#') { vis[j]=1; dfs(i,cnt+1); vis[j]=0; } } } int main() { while(scanf("%d%d",&n,&k)) { memset(s,0,sizeof s); memset(vis,0,sizeof vis); if(n==-1&&k==-1)break; ans=0; for(int i=1;i<=n;i++)scanf("%s",s[i]+1); dfs(0,0); printf("%d\n",ans); } }
poj2251：
吓唬人的BFS。直接乱写一通，1A了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=35; int l,r,c; int dx[6]={1,0,-1,0,0,0}; int dy[6]={0,1,0,-1,0,0}; int dz[6]={0,0,0,0,1,-1}; char s[N][N][N]; bool judge(int z,int x,int y) { if(z<1||x<1||y<1||x>r||y>c||z>l)return 0; if(s[z][x][y]=='#')return 0; return 1; } struct pos { int z,x,y,cnt; pos(){}; pos(int a,int b,int c,int d){z=a,x=b,y=c,cnt=d;}; }; int bfs() { pos ss; for(int i=1;i<=l;i++) for(int j=1;j<=r;j++) for(int k=1;k<=c;k++) if(s[i][j][k]=='S') ss=pos(i,j,k,0),s[i][j][k]='#'; queue<pos>q;q.push(ss); while(!q.empty()) { pos now=q.front();q.pop(); //cout<<now.z<<" "<<now.x<<" "<<now.y<<" "<<now.cnt<<endl; for(int i=0;i<6;i++) { int z=now.z+dz[i]; int x=now.x+dx[i]; int y=now.y+dy[i]; if(judge(z,x,y)) { if(s[z][x][y]=='E')return now.cnt+1; if(s[z][x][y]=='#')continue; s[z][x][y]='#'; q.push(pos(z,x,y,now.cnt+1)); } } } return -1; } int main() { while(scanf("%d%d%d",&l,&r,&c)) { memset(s,0,sizeof s); if(l==0&&r==0&&c==0)return 0; for(int i=1;i<=l;i++) for(int j=1;j<=r;j++)scanf("%s",s[i][j]+1); int ans=bfs(); if(ans>0)printf("Escaped in %d minute(s).\n",ans); else puts("Trapped!"); } }
poj3278:
此题暴露出我的垃圾了。
第一波WA：会减到小于零的时候，这时候查重数组越界了。
第二波MLE：没剪枝，比答案大了就别再+和*2了。。。。（我真傻）
第三波WA：会有答案为0的情况。。我只在扩展出来的数中找答案。。没有考虑这一点
所以：hash时不如mod一个数，bfs时先判答案，搜索时动下脑子剪枝
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; int hash[20000005]; int n,k; queue<int>q; int bfs() { q.push(n);hash[n]=1; while(!q.empty()) { int now=q.front();q.pop(); if(now==k)return hash[now]-1;//真坑 有答案为0的 int a[3]; a[0]=a[1]=a[2]=-1; if(now<k)a[0]=now+1; a[1]=now-1; if(now<k)a[2]=now*2; for(int i=0;i<3;i++) if(a[i]>=0&&a[i]<20000000&&hash[a[i]]==0) { hash[a[i]]=hash[now]+1,q.push(a[i]); if(a[i]==k)return hash[a[i]]-1; } } return -1; } int main() { scanf("%d%d",&n,&k); cout<<bfs()<<endl; return 0; }
poj3279:
第一反应：这爆搜不了啊
第二反应：这不是高斯消元吗
插播，高斯消元解法是这样的：
我怎么一点也记不起来啊啊啊啊啊啊（回头补）
第三反应：哈哈哈枚举第一行
假设，第一行确定了的话，第二行只需要根据第一行是黑是白就能确定了
例如：要求全白，第一行是白黑白白 第二行第二个地方就得按一下！让它变白！
所以枚举第一行就行啦！
然后 WA。
然后再读题，题目要求，最小的按下次数！！！好。。加个计数器。。。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N=40; int m,n; int s[N][N]; int f[N][N]; int ans[N][N]; int out[N][N]; int mn,now; int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; void modify(int l,int i) { now++; f[l][i]=(f[l][i]+1)%2; for(int j=0;j<4;j++) { int xx=l+dx[j]; int yy=i+dy[j]; f[xx][yy]=(f[xx][yy]+1)%2; } } bool judge() { for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) if(f[i][j]==1)return 0; return 1; } void init(int t) { now=0; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++)f[i][j]=s[i][j]; memset(ans,0,sizeof ans); for(int i=n;i>=1;i--) { ans[1][i]=t%2,t/=2; if(ans[1][i]==1) modify(1,i); } } bool dfs(int l)//到了第几行 { if(now>mn)return 0; if(l==m+1) { if(judge())return 1; return 0; } for(int i=1;i<=n;i++) { if(f[l-1][i]==1) { modify(l,i); ans[l][i]=1; } } return dfs(l+1); } int main() { while(scanf("%d%d",&m,&n)!=EOF) { memset(s,0,sizeof s); memset(f,0,sizeof f); memset(ans,0,sizeof ans); mn=0x3f3f3f3f; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) scanf("%d",&s[i][j]); int mx=pow(2,n)-1; bool flag=0; for(int k=0;k<=mx;k++) { init(k); if(dfs(2)) { if(now<mn) { mn=now; for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) out[i][j]=ans[i][j]; } flag=1; } } } if(!flag) puts("IMPOSSIBLE"); else { for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) printf("%d ",out[i][j]); puts(""); } } } }
代码能力严重下降。。。。
本期节目就到这里。。下期预告：最短路