题目来自 ICPC Japan IISF 2018
输入一串数字，寻找里面小于等于这些数字平均值的个数。
一张正方形的方格纸，只能从左往右，从上往下折叠，折叠t次后有q次询问，每次询问给出的是最终状态下方格的坐标（左下角为(0,0)），代表在这个地方扎个洞，问你把方格纸展开后有多少个洞。每次询问是独立的
输入n，m，t，q（n代表的是宽度、m代表的是高度，t是折叠次数，q是询问次数），对于t次折叠，输入op、p（op==1，表示把左边的p列折到右边；op==2，表示把下边的p行折到上边），对于q次询问，输入x，y（x代表列，y代表行）
直接模拟即可。但是要注意2*p可能会大于原来的宽度或高度
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,m,t,q,mp[100][100],bp[100][100],k; 4 int main() 5 { 6 // freopen("in.txt","r",stdin); 7 while(1) 8 { 9 scanf("%d%d%d%d",&m,&n,&t,&q); 10 if(m==0&&n==0&&t==0&&q==0) 11 return 0; 12 for(int i=0;i<=n;i++) 13 for(int j=0;j<=m;j++) 14 mp[i][j]=1; 15 int op,p; 16 while(t--) 17 { 18 scanf("%d%d",&op,&p); 19 if(op==1) 20 { 21 if(2*p<=m) 22 { 23 for(int i=1;i<=n;i++) 24 { 25 for(int j=p+1;j<=2*p;j++) 26 mp[i][j]+=mp[i][2*p+1-j]; 27 } 28 for(int i=1;i<=n;i++) 29 for(int j=1;j<=m-p;j++) 30 mp[i][j]=mp[i][j+p]; 31 m-=p; 32 } 33 else 34 { 35 for(int i=1;i<=n;i++){ 36 for(int j=p+1;j<=m;j++) 37 bp[i][j]=mp[i][j]+mp[i][2*p+1-j]; 38 for(int j=m+1;j<=2*p;j++) 39 bp[i][j]=mp[i][2*p+1-j]; 40 } 41 for(int i=1;i<=n;i++) 42 { 43 k=0; 44 for(int j=p+1;j<=2*p;j++) 45 { 46 mp[i][++k]=bp[i][j]; 47 } 48 } 49 m=p; 50 } 51 } 52 else 53 { 54 if(2*p<=n) 55 { 56 for(int i=n-2*p+1;i<=n-p;i++) 57 for(int j=1;j<=m;j++) 58 mp[i][j]+=mp[2*(n-p)+1-i][j]; 59 n-=p; 60 } 61 else 62 { 63 k=p; 64 for(int i=n-p+1;i<=2*(n-p);i++) 65 { 66 for(int j=1;j<=m;j++) 67 bp[i][j]=mp[i][j]+mp[2*(n-p)+1-i][j]; 68 } 69 for(int i=2*(n-p)+1;i<=n;i++) 70 { 71 for(int j=1;j<=m;j++) 72 bp[i][j]=mp[i][j]; 73 } 74 75 for(int i=n-p+1;i<=n;i++){ 76 for(int j=1;j<=m;j++){ 77 mp[k][j]=bp[i][j]; 78 } 79 k--; 80 } 81 n=p; 82 } 83 } 84 } 85 int x,y; 86 while(q--) 87 { 88 scanf("%d%d",&x,&y); 89 printf("%d ",mp[n-y][x+1]); 90 } 91 } 92 return 0; 93 }
输入n，求一个最长的公差为1的等差数列，满足他们的和为n，输出等差数列的第一项和它的长度
由求和公式( 2*a + (k-1) )*k / 2=n.得a=(2*n - k*k +k )/(2*k) ，由于a>1我们可以知道k的范围是1--sqrt(2*n),那么直接从大到小枚举即可，直到找出k满足a为整数
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 5 int main() 6 { 7 ll n; 8 while(1) 9 { 10 scanf("%lld",&n); 11 if(n==0) 12 { 13 return 0; 14 } 15 ll maxx=sqrt(2*n); 16 ll tmp; 17 for(ll i=maxx;i>=1;i--) 18 { 19 tmp=2*n-i*i+i; 20 if(tmp%(2*i)==0) 21 { 22 printf("%lld %lld ",tmp/(2*i),i); 23 break; 24 } 25 } 26 } 27 return 0; 28 }
输入n代表有多少支队伍，已知m组队伍的比赛结果，问能有多少种方式能达到“full playoff”（指的是每个队胜场数一样）
首先预处理一下，如果这个队的胜场数或者败场数达到了要求，就把这个队与其他队的情况相应地设为失败或者胜利。然后就搜索，但直接搜的话会超时。主要是当n=9时，m=0、1、2的情况比较多。我们可以直接输出
搜索部分代码是参考大佬的
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 int n,m,f[10][10],r[15],c[15],nn,ans;//0-unknown 1-win 2-lose 5 int fr[10],fc[10];//r[]代表当前行的胜场数，fr[]代表当前行的败场数，c[]代表当前列的胜场数。fc[]代表当前列的败场数 6 void dfs(int x,int y) 7 { 8 if(x>n) 9 { 10 ans++; 11 return ; 12 } 13 if(y>n) 14 { 15 dfs(x+1,x+1); 16 return ; 17 } 18 if(r[x]>nn||r[y]>nn) return ; 19 if(!f[x][y]&&x!=y) 20 { 21 if(r[x]<nn) 22 { 23 r[x]++; 24 f[x][y]=1; 25 f[y][x]=2; 26 dfs(x,y+1); 27 r[x]--; 28 f[x][y]=f[y][x]=0; 29 } 30 if(r[y]<nn) 31 { 32 r[y]++; 33 f[x][y]=2; 34 f[y][x]=1; 35 dfs(x,y+1); 36 r[y]--; 37 f[x][y]=f[y][x]=0; 38 } 39 } 40 else 41 dfs(x,y+1); 42 } 43 int main() 44 { 45 // freopen("in.txt","r",stdin); 46 while(1) 47 { 48 scanf("%d",&n); 49 if(n==0) return 0; 50 scanf("%d",&m); 51 nn=(n-1)/2; 52 int x,y; 53 memset(f,0,sizeof(f)); 54 memset(fr,0,sizeof(fr)); 55 memset(fc,0,sizeof(fc)); 56 memset(r,0,sizeof(r)); 57 memset(c,0,sizeof(c)); 58 int aa,bb,cc,dd; 59 if(n==9) //n==9特判一下 60 { 61 if(m==0) {printf("3230080 ");continue;} 62 else if(m==1) 63 { 64 scanf("%d%d",&aa,&bb); 65 printf("1615040 "); 66 continue; 67 } 68 else if(m==2) 69 { 70 scanf("%d%d%d%d",&aa,&bb,&cc,&dd); 71 if(aa==cc) 72 { 73 printf("692160 "); 74 continue; 75 } 76 else if(aa==dd||bb==cc) 77 { 78 printf("922880 "); 79 continue; 80 } 81 else 82 { 83 printf("807520 "); 84 continue; 85 } 86 } 87 } 88 while(m--) 89 { 90 scanf("%d%d",&x,&y); 91 f[x][y]=1; 92 f[y][x]=2; 93 } 94 95 bool flag=0; 96 int p=0; 97 for(int i=1;i<=n;i++)//统计每行每列的状态 98 { 99 for(int j=1;j<=n;j++) 100 { 101 if(f[i][j]==1) 102 r[i]++,c[j]++; 103 else if(f[i][j]==2) 104 fr[i]++,fc[j]++; 105 } 106 if(r[i]>nn||fr[i]>nn) 107 { 108 flag=1; 109 break; 110 } 111 p+=r[i]; 112 } 113 for(int i=1;i<=n;i++) //预处理 114 { 115 if(r[i]==nn) 116 { 117 for(int j=1;j<=n;j++) 118 { 119 if(i==j) continue; 120 if(!f[i][j]) 121 { 122 f[i][j]=2; 123 f[j][i]=1; 124 fr[i]++;fc[j]++; 125 r[j]++;c[i]++; 126 } 127 } 128 } 129 else if(fr[i]==nn) 130 { 131 for(int j=1;j<=n;j++) 132 { 133 if(i==j) continue; 134 if(!f[i][j]) 135 { 136 f[i][j]=1; 137 f[j][i]=2; 138 fr[j]++;fc[i]++; 139 r[i]++;c[j]++; 140 } 141 } 142 } 143 } 144 for(int j=1;j<=n;j++) 145 { 146 if(c[j]==nn) 147 { 148 for(int i=1;i<=n;i++) 149 { 150 if(i==j) continue; 151 if(!f[i][j]) 152 { 153 f[i][j]=2; 154 f[j][i]=1; 155 fr[i]++;fc[j]++; 156 r[j]++;c[i]++; 157 } 158 } 159 } 160 } 161 if(flag){printf("0 ");continue;} 162 ans=0; 163 dfs(1,1); 164 printf("%d ",ans); 165 } 166 return 0; 167 }