【NOIp】NOIp2015

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

NOIp 2015

day 1 T1 神奇的幻方

标签:模拟

code

ContractedBlock.gif ExpandedBlockStart.gif

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

T1

day 1 T2 信息传递

标签:图论,数据结构

两种做法

①并查集

code

ContractedBlock.gif ExpandedBlockStart.gif

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

T2.1

②拓扑排序

code

ContractedBlock.gif ExpandedBlockStart.gif

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

T2.2

day 1 T3 斗地主

标签:模拟,搜索

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

code

ContractedBlock.gif ExpandedBlockStart.gif

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

T3

day 2 T1 跳石头

标签:二分,贪心

code

ContractedBlock.gif ExpandedBlockStart.gif

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

T4

day 2 T2 子串

标签:dp

code

ContractedBlock.gif ExpandedBlockStart.gif

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

T5

day 2 T3 运输计划

标签:图论,树链剖分

code

ContractedBlock.gif ExpandedBlockStart.gif

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

T6


1658269-20190926170505742-1603326851.png

题解怕不是咕了

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

发表评论

表情:
评论列表 (有 0 条评论,168人围观)

还没有评论,来说两句吧...

相关阅读

    相关 2015年底总结

    时间过的好快,一年又过了,回顾这一年,经历了很多,成长了很多,今天对2015做一个简单的总结,同时展望一下未来![吐舌头][tongue.gif]。 在14年总结中,今年的重

    相关 2015 -> 2016

    2015年。 2015年前几个月,一直住在三亚,每天过着老年人般的生活。每天吃饭睡觉看电视遛弯游泳,生活倒也惬意。 4月份开始,从三亚一路开车回到上海,开开停停,最后享受了

    相关 2015年终总结

    又到了年末,从两年前开始,每到年末我都会写个总结,目的是至少要给自己一个交待,不要活得糊里糊涂的,总结的内容不外乎就是这一年来自己的工作、生活情况,然后设定新年的目标,以更好的