注册登录

【NOIp】NOIp2015

NOIp 2015

day 1 T1 神奇的幻方

标签：模拟

code

 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 }
知识兔T1

day 1 T2 信息传递

标签：图论，数据结构

两种做法

①并查集

 code 

 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

 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 斗地主

标签：模拟，搜索

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

code

  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 }
知识兔T3

day 2 T1 跳石头

标签：二分，贪心

code 

 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 }
知识兔T4

day 2 T2 子串

标签：dp

code 

 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 }
知识兔T5

day 2 T3 运输计划

标签：图论，树链剖分

code

  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 }
知识兔T6

题解怕不是咕了

计算机