首页 > 代码库 > CUGBACM_Summer_Tranning1 二进制枚举+模拟+离散化
CUGBACM_Summer_Tranning1 二进制枚举+模拟+离散化
整体感觉:这个组队赛收获还挺多的。自从期末考试以后已经有一个多月没有 做过组队赛了吧,可是这暑假第一次组队赛就找回了曾经的感觉。还挺不错的!继续努力!!
改进的地方:这次组队赛開始的时候题目比較难读懂,然后就感觉题目应该比較难吧,认为应该是区域赛难度的题目。尽管A题和B题自己都感觉能自己A的。可是可能对自己不太自信,所以让队友大帝敲了。要是当时自己敢敲一下的话,后续会更快的A掉吧。
A题:二进制枚举
题目链接:https://icpcarchive.ecs.baylor.edu/external/66/6661.pdf
事实上这题当时听宝一提醒。就知道能够用二进制枚举来做了。只是大帝也是二进制枚举。然后队友敲了好多代码才A。
我当时感觉用二进制枚举代码就十几行啊,在大帝怎么会写那么多代码呢。然后还以为自己的想法错了呢。刚才分析了下,由于n<20,所以复杂度也就10^6再乘以一个for循环二进制模拟数,最多也就10^7。3秒肯定过了,然后几分钟敲了下。耗时1009ms AC,要是题目是1s的话。能够机智一点AC。
#include<iostream> #include<cstdio> using namespace std; int main() { int n,k,s; while(scanf("%d%d%d",&n,&k,&s)&&(n||k||s)) { int sum1=0,i,j; for(i=2;i<(1<<(n+1));i++) { if(i&1) continue; int sum=0,ans=0; for(j=1;j<=n;j++) if(i&(1<<j)) sum+=j,ans++; if(sum==s&&ans==k) sum1++; } printf("%d\n",sum1); } return 0; }
B题:模拟
题目链接:https://icpcarchive.ecs.baylor.edu/external/66/6662.pdf
这题太逗了。今早一直做到如今,debug了好久,把之前写的全改了。反正不是光彩的一次高速写代码……怎样以逆向思维来想的话。它们的方向事实上都不用管了,假设他们在同一位置的话。就把它们的-1或者+1交换即可了,呀。刚開始没想到。
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; struct abc { int len,ans; }e[53]; int main() { int n,l; while(scanf("%d%d",&n,&l)&&(n||l)) { int i,j,ii,jj,sum=0,cnt=0; char str[3]; for(i=0;i<n;i++) { scanf("%s%d",str,&e[i].len); str[0]==‘R‘?e[i].ans=1:e[i].ans=-1; } while(cnt<n) { sum++; for(i=0;i<n;i++) e[i].len+=e[i].ans; for(i=0;i<n;i++) for(j=i+1;j<n;j++) if(e[i].len==e[j].len) swap(e[i].ans,e[j].ans); for(i=0;i<n;i++) if(e[i].len==l) ii=i+1,jj=sum,cnt++; for(i=0;i<n;i++) if(e[i].len==0) ii=i+1,jj=sum,cnt++; } printf("%d %d\n",jj,ii); } return 0; }
C题:离散化+DFS
题目链接:https://icpcarchive.ecs.baylor.edu/external/66/6663.pdf
思路:这题确实昨晚感觉看队友做的时候会了。可是也和队友debug了非常久,没想到如今做了,又犯相同的错误了,debug了两小时。晕……离散化完然后搜索后,题目的三个例子都过了,可是就是不知道为什么没过。检查了好久没有发现哪里错啊。又交了几发WA,最后试了自己想的例子:1 2 2 4 1。这个例子就错了。原因是离散化第一次的时候第一个纵坐标变成2了,然后第二次的时候又推断2==2?,然后是又变成4,所以变了2次。想要的数就变了。
就是这里错了,用个数组标记一下变一次即可了。
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int lenx,leny,vis[210][210],dist[4][2]= {0,1,1,0,0,-1,-1,0}; void dfs(int i,int j) { if(vis[i][j]||i<0||i>lenx*2+3||j<0||j>=leny*2+3) return ; vis[i][j]=1; for(int k=0; k<4; k++) { int ii=i+dist[k][0]; int jj=j+dist[k][1]; dfs(ii,jj); } } int main() { int n; while(scanf("%d",&n)&&n) { memset(vis,0,sizeof(vis)); int i,j,sum=0,a[153][5],v[55][5]={0},x[210],y[210]; for(i=0; i<n; i++) { scanf("%d%d%d%d",&a[i][0],&a[i][1],&a[i][2],&a[i][3]); x[i*2]=a[i][0],x[i*2+1]=a[i][2]; y[i*2]=a[i][1],y[i*2+1]=a[i][3]; } sort(x,x+n*2); sort(y,y+n*2); lenx=unique(x,x+n*2)-x; leny=unique(y,y+n*2)-y; for(i=0; i<n; i++) { for(j=0; j<lenx; j++) { if(a[i][0]==x[j]&&!v[i][0]) a[i][0]=j*2+2,v[i][0]=1; if(a[i][2]==x[j]&&!v[i][2]) a[i][2]=j*2+2,v[i][2]=1; } for(j=0; j<leny; j++) { if(a[i][1]==y[j]&&!v[i][1]) a[i][1]=j*2+2,v[i][1]=1; if(a[i][3]==y[j]&&!v[i][3]) a[i][3]=j*2+2,v[i][3]=1; } } for(i=0; i<n; i++) { for(j=a[i][0]; j<=a[i][2]; j++) vis[j][a[i][1]]=1,vis[j][a[i][3]]=1; for(j=a[i][3]; j<=a[i][1]; j++) vis[a[i][0]][j]=1,vis[a[i][2]][j]=1; } for(i=0; i<lenx*2+2; i++) for(j=0; j<leny*2+2; j++) if(!vis[i][j]) dfs(i,j),sum++; printf("%d\n",sum); } return 0; }
CUGBACM_Summer_Tranning1 二进制枚举+模拟+离散化