NOIp2010
T1 机器翻译
标签：模拟，STL
两种做法，同一本质
1.依题意模拟
code
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,m,x,ans,l,r,a[1005],b[1005]; 4 int main() 5 { 6 cin>>m>>n; 7 l=0;r=0; 8 for (int i=1;i<=n;i++) 9 { 10 scanf("%d",&x); 11 if (a[x]==0) 12 { 13 ans++; 14 r++;b[r]=x;a[x]=1; 15 if (r>m) {l++;a[b[l]]=0;} 16 } 17 } 18 cout<<ans; 19 return 0; 20 }
早期代码
2.发现题意就是个队列，STL水一波
code
1 #include <bits/stdc++.h> 2 using namespace std; 3 namespace gengyf{ 4 inline int read(){ 5 int x=0,f=1;char s=getchar(); 6 while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} 7 while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} 8 return f*x; 9 } 10 int n,m,vis[1005],ans; 11 queue<int>q; 12 int main(){ 13 m=read();n=read(); 14 for(int i=1;i<=n;i++){ 15 int x=read(); 16 if(vis[x])continue; 17 if(q.size()>=m){ 18 int k=q.front();q.pop(); 19 vis[k]=0; 20 } 21 q.push(x);vis[x]=1;ans++; 22 } 23 printf("%d",ans); 24 return 0; 25 } 26 } 27 int main(){ 28 gengyf::main(); 29 return 0; 30 }
T2 乌龟棋
标签：dp
用每种卡片的数量表示状态
f[i][j][k][l]表示用第一种卡片i张，第二种j张，第三种k张，第四种l张时得到的分数
用卡片张数就能够算出当前位置
转移方程为
f[i][j][k][l]=max(f[i][j][k][l],f[i-1][j][k][l]+a[pos]) （pos=1+i+2*j+3*k+4*l） pos是当前位置，a[i]表示i位置的分数
j,k,l同理
code
1 #include <bits/stdc++.h> 2 using namespace std; 3 namespace gengyf{ 4 inline int read(){ 5 int x=0,f=1;char s=getchar(); 6 while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} 7 while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} 8 return x*f; 9 } 10 int n,m,a[400],tmp[5],st; 11 int f[50][50][50][50]; 12 int main() { 13 n=read();m=read(); 14 for(int i=1;i<=n;i++){ 15 a[i]=read(); 16 } 17 for(int i=1;i<=m;i++){ 18 int x; 19 x=read(); 20 tmp[x]++; 21 } 22 for(int i=0;i<=tmp[1];i++) 23 for(int j=0;j<=tmp[2];j++) 24 for(int k=0;k<=tmp[3];k++) 25 for(int l=0;l<=tmp[4];l++){ 26 st=1+i+j*2+k*3+l*4; 27 if(i)f[i][j][k][l]=max(f[i][j][k][l],f[i-1][j][k][l]+a[st]); 28 if(j)f[i][j][k][l]=max(f[i][j][k][l],f[i][j-1][k][l]+a[st]); 29 if(k)f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k-1][l]+a[st]); 30 if(l)f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k][l-1]+a[st]); 31 } 32 printf("%d",f[tmp[1]][tmp[2]][tmp[3]][tmp[4]]+a[1]); 33 return 0; 34 } 35 } 36 int main(){ 37 gengyf::main(); 38 return 0; 39 }
T3 关押罪犯
标签：图论，数据结构
两种做法
1.排序后并查集维护犯人之间的怨气值,依据"敌人的敌人是朋友"原则分配监狱
如果不可避免将两个互为敌人的罪犯分到一个监狱，就输出怨气值
code
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 struct node {int x,y,z;}; 5 node f[100005]; 6 int n,m,a[20005],b[20005],i; 7 inline bool cmp(node a,node b) 8 { 9 return a.z>b.z; 10 } 11 inline int find(int x) 12 { 13 if(a[x]==x) return x; 14 a[x]=find(a[x]); 15 return a[x]; 16 } 17 inline void merge(int x,int y) 18 { 19 x=find(a[x]); 20 y=find(a[y]); 21 a[x]=y; 22 } 23 inline bool check(int x,int y) 24 { 25 x=find(x); 26 y=find(y); 27 if(x==y) return true; 28 return false; 29 } 30 int main() 31 { 32 scanf("%d%d",&n,&m); 33 for(i=1;i<=n;i++) a[i]=i; 34 for(i=1;i<=m;i++) 35 scanf("%d%d%d",&f[i].x,&f[i].y,&f[i].z); 36 sort(f+1,f+m+1,cmp); 37 for(i=1;i<=m+1;i++) 38 { 39 if(check(f[i].x,f[i].y)) {printf("%d",f[i].z);break;} 40 else 41 { 42 if(!b[f[i].x]) b[f[i].x]=f[i].y; 43 else {merge(b[f[i].x],f[i].y);} 44 if(!b[f[i].y]) b[f[i].y]=f[i].x; 45 else {merge(b[f[i].y],f[i].x);} 46 } 47 } 48 return 0; 49 }
早期代码
2.二分图
二分怨气值后黑白染色判断能否形成二分图，如果能就更新答案
code(有注释)
1 #include <bits/stdc++.h> 2 using namespace std; 3 namespace gengyf{ 4 inline int read(){ 5 int x=0,f=1;char s=getchar(); 6 while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} 7 while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} 8 return f*x; 9 } 10 const int maxm=100010; 11 const int maxn=20010; 12 int n,m; 13 struct edge{ 14 int nxt,to,w; 15 }e[maxm*2]; 16 int head[maxn],cnt,l=0,r,color[maxn]; 17 void add(int from,int to,int w){ 18 e[++cnt].to=to;e[cnt].nxt=head[from]; 19 e[cnt].w=w;head[from]=cnt; 20 } 21 bool check(int x){ 22 queue<int>q; 23 memset(color,0,sizeof(color)); 24 for(int i=1;i<=n;i++){ 25 if(color[i])continue; 26 q.push(i);color[i]=1; 27 while(!q.empty()){ 28 int k=q.front();q.pop(); 29 for(int j=head[k];j;j=e[j].nxt){ 30 if(e[j].w>=x){ 31 if(!color[e[j].to]){//没染过色 32 color[e[j].to]=(color[k]==1?2:1); 33 q.push(e[j].to); 34 //涂上相反颜色入队 35 } 36 else if(color[e[j].to]==color[k])return 0; 37 //如果出现矛盾直接返回(不为二分图) 38 } 39 } 40 } 41 } 42 return 1; 43 } 44 int main(){ 45 n=read();m=read(); 46 for(int i=1;i<=m;i++){ 47 int u,v,w; 48 u=read();v=read();w=read(); 49 r=max(r,w); 50 add(u,v,w);add(v,u,w); 51 } 52 r++; 53 while(l+1<r){ 54 int mid=(l+r)>>1; 55 if(check(mid)){//染色法判断二分图如果可行就缩小范围 56 r=mid; 57 } 58 else l=mid; 59 } 60 printf("%d",l); 61 return 0; 62 } 63 } 64 int main(){ 65 gengyf::main(); 66 return 0; 67 }
T4 引水入城
标签：搜索
把第一排每个点都dfs一遍，找到这个点能覆盖的底层点，看能不能覆盖完
如果不能直接返回
如果能覆盖完，可以发现每一个第一排的点覆盖的都是底层的一段区间，于是问题转化为最小区间覆盖，贪心或dp都可解
code
1 #include <bits/stdc++.h> 2 using namespace std; 3 namespace gengyf{ 4 const int inf=1e9+7; 5 inline int read(){ 6 int x=0,f=1;char s=getchar(); 7 while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} 8 while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} 9 return f*x; 10 } 11 int a[550][550],v[550][550],vl[550],f[505]; 12 int block,cnt,ans,n,m; 13 struct node{ 14 int l,r; 15 }c[10005]; 16 void dfs(int x,int y,int k){ 17 v[x][y]=1; 18 if(x==n){ 19 vl[y]=1; 20 c[k].l=min(c[k].l,y); 21 c[k].r=max(c[k].r,y); 22 } 23 if(a[x][y]>a[x+1][y]&&!v[x+1][y]&&x!=n)dfs(x+1,y,k); 24 if(a[x][y]>a[x-1][y]&&!v[x-1][y]&&x!=1)dfs(x-1,y,k); 25 if(a[x][y]>a[x][y-1]&&!v[x][y-1]&&y!=1)dfs(x,y-1,k); 26 if(a[x][y]>a[x][y+1]&&!v[x][y+1]&&y!=m)dfs(x,y+1,k); 27 } 28 int main(){ 29 n=read();m=read(); 30 for(int i=1;i<=n;i++) 31 for(int j=1;j<=m;j++){ 32 a[i][j]=read(); 33 } 34 for(int i=1;i<=m;i++){ 35 c[i].l=f[i]=inf; 36 } 37 f[0]=0; 38 for(int i=1;i<=m;i++){ 39 if(a[1][i-1]<=a[1][i]&&a[1][i+1]<=a[1][i]){ 40 dfs(1,i,i); 41 } 42 memset(v,0,sizeof(v)); 43 } 44 for(int i=1;i<=m;i++){ 45 if(!vl[i])block++; 46 } 47 if(block){ 48 printf("0 %d",block); 49 return 0; 50 } 51 for(int i=1;i<=m;i++) 52 for(int j=1;j<=m;j++){ 53 if(i>=c[j].l&&i<=c[j].r){ 54 f[i]=min(f[i],f[c[j].l-1]+1); 55 } 56 } 57 printf("1 %d",f[m]); 58 return 0; 59 } 60 } 61 int main(){ 62 gengyf::main(); 63 return 0; 64 }
总结： 思维难度逐渐上升，有点NOIp的样子了，题目的多解也能够带来很大启发
