【NOIp】NOIp2010

朴灿烈づ我的快乐病毒、 2023-08-17 16:49 100阅读 0赞

# NOIp2010 #

### [T1 机器翻译][T1] ###

标签：模拟，STL

两种做法，同一本质

1.依题意模拟

code

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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 }

T1.1

早期代码

2.发现题意就是个队列，STL水一波

code

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

T1.2

### [T2 乌龟棋][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

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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 关押罪犯][T3] ###

标签：图论，数据结构

两种做法

1.排序后并查集维护犯人之间的怨气值,依据"敌人的敌人是朋友"原则分配监狱

如果不可避免将两个互为敌人的罪犯分到一个监狱，就输出怨气值

code

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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 }

T3.1

早期代码

2.二分图

二分怨气值后黑白染色判断能否形成二分图，如果能就更新答案

code(有注释)

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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 }

T3.2

### [T4 引水入城][T4] ###

标签：搜索

把第一排每个点都dfs一遍，找到这个点能覆盖的底层点，看能不能覆盖完

如果不能直接返回

如果能覆盖完，可以发现每一个第一排的点覆盖的都是底层的一段区间，于是问题转化为最小区间覆盖，贪心或dp都可解

code

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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\n%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\n%d",f[m]);
    58         return 0;
    59     }
    60 }
    61 int main(){
    62     gengyf::main();
    63     return 0;
    64 }

--------------------

总结： 思维难度逐渐上升，有点NOIp的样子了，题目的多解也能够带来很大启发

![1658269-20190912081828535-1907472377.png][]

转载于:https://www.cnblogs.com/gengyf/p/11508171.html

[T1]: https://www.luogu.org/problem/P1540
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230809/27d2fd1d303a4d299f5d110096dca712.png
[T2]: https://www.luogu.org/problem/P1541
[T3]: https://www.luogu.org/problem/P1525
[T4]: https://www.luogu.org/problem/P1514
[1658269-20190912081828535-1907472377.png]: /images/20230809/24f39b811335464bbeb9de25e01c23d9.png