【NOIp】NOIp2015

爱被打了一巴掌 2023-08-17 16:49 40阅读 0赞

# NOIp 2015 #

### day 1 [T1 神奇的幻方][T1] ###

标签：模拟

code

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

1 #include<iostream>
     2 #include<cstdio>
     3 using namespace std;
     4 int a[40][40];
     5 int main(){
     6     int n,x[1600],y[1600];
     7     scanf("%d",&n);
     8     for(int i=0;i<=n;i++){
     9         a[0][i]=260408,a[i][0]=260408;
    10     }
    11     a[1][n/2+1]=1;
    12     x[1]=1,y[1]=n/2+1;
    13     for(int i=2;i<=n*n;i++){
    14         if(x[i-1]==1&&y[i-1]!=n){
    15             a[n][y[i-1]+1]=i;
    16             x[i]=n,y[i]=y[i-1]+1;
    17         }
    18         else if(y[i-1]==n&&x[i-1]!=1){
    19             a[x[i-1]-1][1]=i;
    20             x[i]=x[i-1]-1,y[i]=1;
    21         }
    22         else if(a[1][n]==i-1){
    23             a[2][n]=i;
    24             x[i]=2,y[i]=n;
    25         }
    26         else if(x[i-1]!=1&&y[i-1]!=n){
    27             if(a[x[i-1]-1][y[i-1]+1]==0){
    28                 a[x[i-1]-1][y[i-1]+1]=i;
    29                 x[i]=x[i-1]-1,y[i]=y[i-1]+1;
    30             }
    31             else{
    32                 a[x[i-1]+1][y[i-1]]=i;
    33                 x[i]=x[i-1]+1,y[i]=y[i-1];
    34             }
    35         }
    36     }
    37     for(int i=1;i<=n;i++)
    38     {
    39           for(int j=1;j<=n;j++){
    40             printf("%d ",a[i][j]);
    41         }
    42     printf("\n");
    43     }
    44     return 0;
    45 }

### day 1 [T2 信息传递][T2] ###

标签：图论，数据结构

两种做法

①并查集

code

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

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 namespace gengyf{
     4 #define ll long long
     5 const int inf=1e9+7;
     6 const int maxn=2e5+10;
     7 inline int read(){
     8     int x=0,f=1;
     9     char c=getchar();
    10     while(c<'0'||c>'9'){
         if(c=='-')f=-1;c=getchar();}
    11     while(c>='0'&&c<='9'){x=(x*10)+c-'0';c=getchar();}
    12     return x*f;
    13 }
    14 int fa[maxn],n,d[maxn],minn=inf;
    15 int get(int x){
    16     if(x!=fa[x]){
    17         int tmp=fa[x];
    18         fa[x]=get(fa[x]);
    19         d[x]+=d[tmp];
    20     }
    21     return fa[x];
    22 }
    23 void check(int x,int y){
    24     int a=get(x),b=get(y);
    25     if(a!=b){
    26         fa[a]=b;d[x]=d[y]+1;
    27     }
    28     else minn=min(minn,d[x]+d[y]+1);
    29 }
    30 int main(){
    31     n=read();
    32     for(int i=1;i<=n;i++){
    33         fa[i]=i;
    34     }
    35     for(int i=1;i<=n;i++){
    36         int x=read();
    37         check(i,x);
    38     }
    39     printf("%d",minn);
    40     return 0;
    41 }
    42 }
    43 signed main(){
    44   gengyf::main();
    45   return 0;
    46 }

T2.1

②拓扑排序

code

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

1 #include <iostream>
     2 #include <set>
     3 #include <queue>
     4 #include <vector>
     5 #include <cmath>
     6 //#include <bits/stdc++.h>
     7 using namespace std;
     8 namespace gengyf{
     9 #define ll long long
    10 const int maxn=2e5+10;
    11 const int inf=1e9+7;
    12 inline int read(){
    13     int x=0,f=1;
    14     char c=getchar();
    15     while(c<'0'||c>'9'){
         if(c=='-')f=-1;c=getchar();}
    16     while(c>='0'&&c<='9'){x=(x*10)+c-'0';c=getchar();}
    17     return x*f;
    18 }
    19 int n;
    20 struct edge{
    21     int nxt,to;
    22 }e[maxn];
    23 int head[maxn],cnt;
    24 int in[maxn],vis[maxn],a[maxn];
    25 inline void add(int from,int to){
    26     e[++cnt].to=to;e[cnt].nxt=head[from];head[from]=cnt;
    27 }
    28 void topsort(){
    29     queue<int>q;
    30     for(int i=1;i<=n;i++){
    31         if(!in[i])q.push(i);
    32     }
    33     while(!q.empty()){
    34         int x=q.front();q.pop();
    35         for(int i=head[x];i;i=e[i].nxt){
    36             int y=e[i].to;
    37             --in[y];
    38             if(!in[y])q.push(y);
    39         }
    40     }
    41 }
    42 int dfs(int x){
    43     if(vis[x])return 0;
    44     vis[x]=1;
    45     for(int i=head[x];i;i=e[i].nxt){
    46         int y=e[i].to;
    47         return 1+dfs(y);
    48     }
    49     return 0;
    50 }
    51 int main(){
    52     n=read();
    53     for(int i=1;i<=n;i++){
    54         a[i]=read();add(i,a[i]);
    55         ++in[a[i]];
    56     }
    57     int ans=inf;
    58     topsort();
    59     for(int i=1;i<=n;i++){
    60         if(in[i]&&!vis[i]){
    61             ans=min(ans,dfs(i));
    62         }
    63     }
    64     printf("%d",ans);
    65     return 0;
    66 }
    67 }
    68 signed main(){
    69   gengyf::main();
    70   return 0;
    71 }

T2.2

### day 1 [T3 斗地主][T3] ###

标签：模拟，搜索

我已无力吐槽这175行的代码

code

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

1 #include <bits/stdc++.h>
      2 using namespace std;
      3 namespace gengyf{
      4 #define ll long long
      5 inline int read(){
      6     int x=0,f=1;
      7     char c=getchar();
      8     while(c<'0'||c>'9'){
         if(c=='-')f=-1;c=getchar();}
      9     while(c>='0'&&c<='9'){x=(x*10)+c-'0';c=getchar();}
     10     return x*f;
     11 }
     12 int t,n,card[15],c,d,ans;
     13 inline void init(){
     14     memset(card,0,sizeof(card));
     15     for(int i=1;i<=n;i++){
     16         scanf("%d%d",&d,&c);
     17         if((d>=3)&&(d<=13))card[d-2]++;
     18         if(d==0)card[14]++;
     19         if(d==1)card[12]++;
     20         if(d==2)card[13]++;
     21     }
     22     ans=n;
     23 }
     24 inline int chupai(){
     25     int cnt[5],tmp[14],ret=0;
     26     memset(cnt,0,sizeof(cnt));
     27     for(int i=1;i<=14;i++){
     28         cnt[card[i]]++;
     29     }
     30     for(int i=1;i<=14;i++){
     31         tmp[i]=card[i];
     32     }
     33     if(cnt[4]&&(cnt[2]>2||cnt[3]>2)){
         //4带两队
     34         for(int i=1;i<=14;i++){
     35             if(tmp[i]==4){
     36                 for(int j=1;j<=14;j++){
     37                     if((j==i)||(tmp[j]!=2))continue;
     38                     if(tmp[i]<4)break;
     39                     for(int k=1;k<=14;k++){
     40                         if((k==j)||(k==i))continue;
     41                         if(tmp[k]==2){
     42                             tmp[i]-=4;tmp[j]-=2;
     43                             tmp[k]-=2;cnt[4]--;
     44                             ret++;break;
     45                         }
     46                     }
     47                 }
     48             }
     49         }
     50     }
     51     if(cnt[4]&&(cnt[2]||cnt[3]||(cnt[1]))){
         //4带2
     52         for(int i=1;i<=14;i++){
     53             if(tmp[i]==4){
     54                 for(int j=1;j<=14;j++){
     55                     if((j==i)||tmp[j]!=1)continue;
     56                     if(tmp[i]!=4)break;
     57                     for(int k=1;k<=14;k++){
     58                         if((k==j)||(k==i))continue;
     59                         if(tmp[k]==1){
     60                             tmp[i]-=4;tmp[j]--;tmp[k]--;
     61                             ret++;break;
     62                         }
     63                     }
     64                 }
     65             }
     66         }
     67     }
     68     if(cnt[4]&&(cnt[2]||cnt[3])){
         //4带一对
     69         for(int i=1;i<=14;i++){
     70             if(tmp[i]==4){
     71                 for(int j=1;j<=14;j++){
     72                     if(j==i)continue;
     73                     if(tmp[j]==2){
     74                         tmp[i]-=4;tmp[j]-=2;
     75                         ret++;cnt[4]--;
     76                         break;
     77                     }
     78                 }
     79             }
     80         }
     81     }
     82     for(int i=1;i<=14;i++){
     83         if(tmp[i]>=3){
     84             for(int j=1;j<=14;j++){
     85                 if(j==i)continue;
     86                 if(tmp[j]==2){
         //3带2
     87                     tmp[i]-=3;tmp[j]-=2;
     88                     ret++;break;
     89                 }
     90                 if(tmp[j]==1){
         //3带1
     91                     tmp[i]-=3;tmp[j]-=1;
     92                     ret++;break;
     93                 }
     94             }
     95         }
     96     }
     97     for(int i=1;i<=14;i++){
         //散牌
     98         if(tmp[i]==4){tmp[i]-=4;ret++;}
     99         else if(tmp[i]==3){tmp[i]-=3;ret++;}
    100         else if(tmp[i]==2){tmp[i]-=2;ret++;}
    101         else if(tmp[i]){tmp[i]--;ret++;}
    102     }
    103     return ret;
    104 }
    105 inline void dfs(int deep){
         //顺子
    106     if(deep>=ans)return ;
    107     for(int i=1;i<=14;i++){
    108         if(card[i])break;
    109         if(i==14){
    110             ans=deep;return ;
    111         }
    112     }
    113     int tmp=chupai();
    114     if(tmp+deep<ans)ans=tmp+deep;
    115     int cnt[15];
    116     memset(cnt,0,sizeof(cnt));
    117     for(int i=1;i<=14;i++){
    118         cnt[card[i]]++;
    119     }
    120     if(cnt[3]>=3){
         //三顺
    121         for(int i=1;i<=10;i++)
    122             for(int l=2;l<=12;l++)
    123                 for(int p=i;p<=l+i;p++){
    124                     if(card[p]<3||p>12)break;
    125                     else {
    126                         if(p==l+i){
    127                             for(int q=p-l;q<=p;q++)card[q]-=3;
    128                             cnt[3]-=l+1;dfs(deep+1);cnt[3]+=l+1;
    129                             for(int q=p-l;q<=p;q++)card[q]+=3;
    130                         }
    131                     }
    132         }
    133     }
    134     if(cnt[2]>=3){
         //对顺
    135         for(int i=1;i<=10;i++)
    136             for(int l=2;l<=12;l++)
    137                 for(int p=i;p<=l+i;p++){
    138                     if(card[p]<2||p>12)break;
    139                     else {
    140                         if(p==l+i){
    141                             for(int q=p-l;q<=p;q++)card[q]-=2;
    142                             cnt[2]-=l+1;dfs(deep+1);cnt[2]+=l+1;
    143                             for(int q=p-l;q<=p;q++)card[q]+=2;
    144                         }
    145                     }
    146         }
    147     }
    148     if(cnt[1]+cnt[2]+cnt[3]>5){
         //单顺
    149         for(int i=1;i<=10;i++)
    150             for(int l=4;l<=12;l++)
    151                 for(int p=i;p<=l+i;p++){
    152                     if(!card[p]||p>12)break;
    153                     else {
    154                         if(p==l+i){
    155                             for(int q=p-l;q<=p;q++)card[q]--;
    156                             dfs(deep+1);
    157                             for(int q=p-l;q<=p;q++)card[q]++;
    158                         }
    159                     }
    160                 }
    161     }
    162 }
    163 int main(){
    164     t=read();n=read();
    165     while(t--){
    166         init();dfs(0);
    167         printf("%d\n",ans);
    168     }
    169     return 0;
    170 }
    171 }
    172 signed main(){
    173   gengyf::main();
    174   return 0;
    175 }

### day 2 [T1 跳石头][T1 1] ###

标签：二分，贪心

code

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

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 namespace gengyf{
     4 #define ll long long
     5 const int maxn=5e4+10;
     6 inline int read(){
     7     int x=0,f=1;
     8     char c=getchar();
     9     while(c<'0'||c>'9'){
         if(c=='-')f=-1;c=getchar();}
    10     while(c>='0'&&c<='9'){x=(x*10)+c-'0';c=getchar();}
    11     return x*f;
    12 }
    13 int l,m,n,d[maxn],ans;
    14 int main(){
    15     l=read();n=read();m=read();
    16     for(int i=1;i<=n;i++){
    17         d[i]=read();
    18     }
    19     int le=0,ri=l;
    20     while(le<=ri){
    21         int mid=(ri+le)>>1;
    22         int now=0,s=0;
    23         for(int i=1;i<=n;i++){
    24             if(d[i]-d[now]<mid)
    25                     s++;
    26             else now=i;
    27         }
    28         if(s<=m){
    29             ans=mid;le=mid+1;
    30         }
    31         else ri=mid-1;
    32     }
    33     printf("%d",ans);
    34     return 0;
    35 }
    36 }
    37 signed main(){
    38   gengyf::main();
    39   return 0;
    40 }

### day 2 [T2 子串][T2 1] ###

标签：dp

code

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

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 namespace gengyf{
     4 #define ll long long
     5 const int maxn=2e5+10;
     6 const int mod=1e9+7;
     7 inline int read(){
     8     int x=0,f=1;
     9     char c=getchar();
    10     while(c<'0'||c>'9'){
         if(c=='-')f=-1;c=getchar();}
    11     while(c>='0'&&c<='9'){x=(x*10)+c-'0';c=getchar();}
    12     return x*f;
    13 }
    14 int n,m,K,f[2][210][210][2];
    15 char a[1010],b[1010];
    16 void dp(){
    17     f[0][0][0][0]=f[1][0][0][0]=1;
    18     for(int i=1;i<=n;i++){
    19         int now=i&1;
    20         for(int j=0;j<=m;j++)
    21             for(int k=0;k<=min(K,j);k++){
    22                 f[now][j][k][0]=(f[now^1][j][k][0]+f[now^1][j][k][1])%mod;
    23                 if(j<=0||a[i]!=b[j]){
    24                     f[now][j][k][1]=0;continue;
    25                 }
    26                 f[now][j][k][1]=f[now^1][j-1][k][1];
    27                 if(k>0){
    28                     f[now][j][k][1]=((f[now][j][k][1]+f[now^1][j-1][k-1][0])%mod+f[now^1][j-1][k-1][1])%mod;
    29                 }
    30             }
    31     }
    32 }
    33 int main(){
    34     n=read();m=read();K=read();
    35     scanf("%s%s",a+1,b+1);
    36     dp();
    37     printf("%d",(f[n&1][m][K][0]+f[n&1][m][K][1])%mod);
    38     return 0;
    39 }
    40 }
    41 signed main(){
    42   gengyf::main();
    43   return 0;
    44 }

### day 2 [T3 运输计划][T3 1] ###

标签：图论，树链剖分

code

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

1 //
      2 //  main.cpp
      3 //  bzoj
      4 //
      5 //  Created by gengyf on 2019/7/22.
      6 //  Copyright © 2019 yifan Geng. All rights reserved.
      7 //
      8 
      9 #include <bits/stdc++.h>
     10 using namespace std;
     11 namespace gengyf{
     12 #define maxn 300010
     13 #define mod 10007
     14     inline int read(){
     15         int f=1,x=0;char s=getchar();
     16         while(!isdigit(s)){
         if(s=='-')f=-1;s=getchar();}
     17         while(isdigit(s)){x=x*10+s-'0';s=getchar();}
     18         return x*f;
     19     }
     20     int n,m;
     21     struct edge{
     22         int nxt,to,w;
     23     }e[maxn*2];
     24     struct node{
     25         int u,v,dis,lc;
     26     }l[maxn*2];
     27     int head[maxn],cnt,k,deep[maxn],dis[maxn],dfn[maxn];
     28     int fa[maxn][25],f[maxn][25],tmp[maxn],vis[maxn],sum;
     29     void add(int from,int to,int w){
     30         e[++cnt].to=to;e[cnt].w=w;
     31         e[cnt].nxt=head[from];head[from]=cnt;
     32     }
     33     void dfs(int x,int pa,int dep){
     34         k++;
     35         dfn[k]=x;
     36         deep[x]=dep;
     37         vis[x]=1;
     38         for(int i=1;i<25;i++){
     39             fa[x][i]=fa[fa[x][i-1]][i-1];
     40         }
     41         for(int i=head[x];i;i=e[i].nxt){
     42             int to=e[i].to;
     43             if(!vis[to]){
     44                 fa[to][0]=x;
     45                 dis[to]=dis[x]+e[i].w;
     46                 dfs(to,x,dep+1);
     47             }
     48         }
     49     }
     50     int lca(int x,int y){
     51         if(deep[x]<deep[y])
     52             swap(x,y);
     53         int t=deep[x]-deep[y];
     54         for(int i=0;i<25;i++){
     55             if((1<<i)&t)x=fa[x][i];
     56         }
     57         if(x==y)return x;
     58         for(int i=24;i>=0;i--){
     59             if(fa[x][i]!=fa[y][i]){
     60                 x=fa[x][i];y=fa[y][i];
     61             }
     62         }
     63         return fa[x][0];
     64         
     65     }
     66     bool check(int x){
     67         int cnt=0,ans=0;
     68         memset(tmp,0,sizeof(tmp));
     69         for(int i=1;i<=m;i++){
     70             if(l[i].dis>x){
     71                 tmp[l[i].u]++;
     72                 tmp[l[i].v]++;
     73                 tmp[l[i].lc]-=2;
     74                 ans=max(ans,l[i].dis-x);
     75                 cnt++;
     76             }
     77         }
     78         if(cnt==0)return true;
     79         for(int i=n;i>=1;i--){
     80             tmp[fa[dfn[i]][0]]+=tmp[dfn[i]];
     81         }
     82         for(int i=2;i<=n;i++) {
     83             if(tmp[i]==cnt&&dis[i]-dis[fa[i][0]]>=ans) return true;
     84         }
     85         return false;
     86     }
     87     signed main(){
     88         n=read();m=read();
     89         for(int i=1;i<=n-1;i++){
     90             int u,v,w;
     91             u=read();v=read();w=read();
     92             add(u,v,w);add(v,u,w);
     93             sum+=w;
     94         }
     95         dis[1]=0;
     96         dfs(1,0,1);
     97         for(int i=1;i<=m;i++){
     98             l[i].u=read();l[i].v=read();
     99             l[i].lc=lca(l[i].u,l[i].v);
    100             l[i].dis=dis[l[i].u]+dis[l[i].v]-2*dis[l[i].lc];
    101         }
    102         int l=0,r=sum;
    103         int mid;
    104         while(l<r){
    105             mid=(l+r)>>1;
    106             if(check(mid)) r=mid;
    107             else l=mid+1;
    108         }
    109         printf("%d",l);
    110         return 0;
    111     }
    112 }
    113 signed main() {
    114     gengyf::main();
    115     return 0;
    116 }

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

![1658269-20190926170505742-1603326851.png][]

题解怕不是咕了

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

[T1]: https://www.luogu.com.cn/problem/P2615
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230809/827f71c9f10744c2a768f860dc8d7d9e.png
[T2]: https://www.luogu.com.cn/problem/P2661
[T3]: https://www.luogu.com.cn/problem/P2668
[T1 1]: https://www.luogu.com.cn/problem/P2678
[T2 1]: https://www.luogu.com.cn/problem/P2679
[T3 1]: https://www.luogu.com.cn/problem/P2680
[1658269-20190926170505742-1603326851.png]: /images/20230809/1c50bbf7c8514ec5b607887a11a31aff.png