A. Trip For Meal
给 n a b c，分别表示一个数 n 和一个三角形的三边
你被要求从这个三角形的 a 和 b 的交点出发，在这个三角形上以最小距离走 n-1 步
那么这个，，，，
如果 a 或 b 是最短边的话，我们在单条边上抽搐 n-1 次即可
否则 c 就是最短边了
我们通过 a 或 b （哪条短啊qwq）走到 c 前
然后在 c 上抽搐 n-2 次
这很显然qwq 注意特判 n == 1
1 #include2 #include 3 using namespace std; 4 5 int a,b,c,n; 6 7 int main(){ 8 scanf("%d%d%d%d",&n,&a,&b,&c); 9 10 if(n == 1) return printf("0"),0;11 12 n--;13 14 if(a <= b && a <= c) return printf("%d",a*n),0;15 if(b <= a && b <= c) return printf("%d",b*n),0;16 17 if(a < b) return printf("%d",a+max(0,c*(n-1))),0;18 else return printf("%d",b+max(0,c*(n-1))),0;19 20 return 0;21 }
B. Divisiblity of Differences
给 n 个数，求出一个包含 k 个数的集合，该集合符合如下要求：
该集合中任意一个数对之差可以被 m 整除
本蒟蒻：从集合中挑任意一个数，和数列中的其他数做检测，符合则扔进集合，原理显然
Reek：求 m 的剩余系取最大
Orz Reek！！！
说的人话一点：每个数都拿去取模 m ，对余数用桶计数。最后的集合就是数量最多的那个余数集。
就是 bucket[ arr[i]%m ]++ qwq
1 #include2 #include 3 using namespace std; 4 5 int read(){ 6 int ret = 0; char ctr = getchar(); 7 while(ctr > '9' || ctr < '0') ctr = getchar(); 8 while(ctr >= '0' && ctr <= '9') ret = ret*10+ctr-'0',ctr = getchar(); 9 return ret;10 }11 12 int ans,ret,n,k,m,arr[101010],buck[101010];13 14 int main(){ 15 n = read(),k = read(),m = read();16 17 for(int i = 1;i <= n;i++){18 arr[i] = read();19 buck[arr[i]%m]++;20 if(ans < buck[arr[i]%m]){21 ret = arr[i]%m;22 ans = buck[arr[i]%m];23 }24 }25 26 if(ans < k) return printf("No"),0;27 28 printf("Yes\n");29 for(int i = 1,poi = 0;i <= n && poi < k;i++){30 if(arr[i]%m == ret){31 printf("%d ",arr[i]);32 poi++;33 }34 }35 36 return 0;37 }
C. Classroom Watch
给一个数 n
求出集合，该集合中的数字 x 满足这样的要求：
x + x的每个数位上的数字之和 == n
x 的范围极大，就别想枚举了
但是数字之和我们可以做文章
这个数字之和显然最大就是 9+9+9+9+9+9+9+9+9 = 81
所以枚举 n-100 到 n 进行检测即可
据说输出顺序需要注意
1 #include2 #include 3 #include 4 using namespace std; 5 6 queue Q; 7 8 int read(){ 9 int ret = 0; char ctr = getchar();10 while(ctr > '9' || ctr < '0') ctr = getchar();11 while(ctr >= '0' && ctr <= '9') ret = ret*10+ctr-'0',ctr = getchar();12 return ret;13 }14 15 int n,x,tot;16 17 bool check(int x){18 int ret1 = 0;19 for(int i = x;i;i /= 10){20 ret1 += i%10;21 }22 23 return ret1+x == n;24 }25 26 int main(){ 27 n = read();28 29 for(int i = n-100;i <= n;i++){30 if(i < 0) continue;31 if(check(i)){ Q.push(i); tot++; }32 }33 34 cout << tot << endl;35 while(!Q.empty()){36 int p = Q.front();37 printf("%d ",p);38 Q.pop();39 }40 41 return 0;42 }
D. Sorting the Coins
有 n 个硬币
然后对于这 n 个硬币，某个小可爱会翻转（不可逆） n 次（所以最后一次会全翻转完）
翻转完后可能会有 XOOO 这种情况，然后根据他的说法，我们会把这个变成 OOOX
对于每一次翻转，我们需要求出把他变成OOOXXX的操作次数
即使是没操作，也会扫描一次--因为要确定已经是OOOXXX
Reek：这不就冒泡排序求操作次数吗
qwq我不会冒泡啊
所以打了个暴力
根据Reek的启示，每次必然会有一个硬币被带到终点
终点大概是会有形如 ...OOXXX 的结构
那么终点的 XXX 有多长，就有多少硬币没有必要被带到终点
比如 XOXOXXXXX 就有两个硬币会被带到终点变成 00XXXXXXX
有多少硬币需要被移动，操作就会有多少次
最后还要扫描一次确定没有必要操作
所以是 操作次数+1
1 #include2 #include 3 using namespace std; 4 5 int n,pos,arr[303030],cnt; 6 7 int main(){ 8 scanf("%d",&n); 9 pos = n;10 11 cout << 1 << ' ';12 for(int i = 1;i <= n;i++){13 scanf("%d",&cnt);14 arr[cnt] = 1;15 while(arr[pos]) pos--;16 printf("%d ",i-(n-pos)+1);17 }18 19 return 0;20 }
F. High Cry
由于不是比赛时肛出来的，此处赛后补题链接
如果有更多问题请留言qwq
1 #include2 #include 3 using namespace std; 4 5 int n,arr[505050],max_num,s_poi,stack[505050]; 6 int L[505050],R[505050],uL[505050],uR[505050]; 7 int pos,iL[505050][32],iR[505050][32],inf = 1e9; 8 long long ans = 0; 9 10 int main(){11 scanf("%d",&n);12 13 for(int i = 1;i <= n;i++){14 scanf("%d",&arr[i]);15 max_num = max(arr[i],max_num);16 }17 18 for(int i = 1;i <= n;i++){19 while(s_poi && arr[stack[s_poi-1]] <= arr[i])20 R[stack[s_poi-1]] = i-1,21 s_poi--;22 stack[s_poi++] = i;23 }while(s_poi) R[stack[--s_poi]] = n;24 25 for(int i = n;i >= 1;i--){26 while(s_poi && arr[stack[s_poi-1]] < arr[i])27 L[stack[s_poi-1]] = i+1,28 s_poi--;29 stack[s_poi++] = i;30 }while(s_poi) L[stack[--s_poi]] = 1;31 32 int len = 0;33 for(int i = max_num;i;i >>= 1)34 len++;35 36 for(int j = 1;j <= len;j++){37 pos = 0;38 for(int i = 1;i <= n;i++){39 if(arr[i] & (1<<(j-1))) pos = i,iL[i][j] = 0;40 else iL[i][j] = pos;41 }pos = n+1;42 for(int i = n;i >= 1;i--){43 if(arr[i] & (1<<(j-1))) pos = i,iR[i][j] = n+1;44 else iR[i][j] = pos;45 }46 }47 // for(int j = len;j >= 1;j--){48 // for(int i = 1;i <= n;i++)49 // printf("%d/%d ",iL[i][j],iR[i][j]);50 // puts("");51 // }52 53 for(int i = 1;i <= n;i++){54 uL[i] = 0,uR[i] = n+1;55 for(int j = 1;j <= len;j++)56 uL[i] = max(uL[i],iL[i][j]),57 uR[i] = min(uR[i],iR[i][j]);58 }59 60 // for(int i = 1;i <= n;i++){61 // printf("%d %d %d %d\n",L[i],uL[i],uR[i],R[i]);62 // }63 64 for(int i = 1;i <= n;i++){65 ans += max(0LL,1LL*(uL[i]-L[i]+1)*(R[i]-i+1))+max(0LL,1LL*(i-L[i]+1)*(R[i]-uR[i]+1));66 ans -= max(1LL*(R[i]-uR[i]+1)*(uL[i]-L[i]+1),0LL);67 // printf("\n",1LL*(uL[i]-L[i]+1)*(R[i]-i+1),1LL*(i-L[i]+1)*(R[i]-uR[i]+1),1LL*(R[i]-uR[i]+1)*(uL[i]-L[i]+1),ans);68 }69 70 cout << max(ans,0LL) << endl;71 72 return 0;73 }