当前位置：首页 > news >正文

Codeforces Round 1102 (Div. 2)

news 2026/7/13 2:11:52

A题链接

a [ i + 2 ] a[i+2]a[i+2]一定属于0到a [ i + 1 ] − 1 a[i+1]-1a[i+1]−1之间
所以该序列一定是严格单调递减的

将序列倒序后，判断相邻三个元素是否满足数量关系即可

#include<bits/stdc++.h>#defineendl'\n'#defineintlonglongusingnamespacestd;voidsolve(){intn;cin>>n;vector<int>a(n+1);for(inti=1;i<=n;i++)cin>>a[i];sort(a.begin()+1,a.end());reverse(a.begin()+1,a.end());for(inti=1;i<=n-2;i++){if(a[i+2]!=a[i]%a[i+1]){cout<<-1<<endl;return;}}cout<<a[1]<<' '<<a[2]<<endl;return;}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intt;cin>>t;while(t--)solve();return0;}

B题链接
b需要被12整除，考虑算n mod 12
发现n mod 12 的结果为0到11
其中除了10 以外，均为回文数
所以可以令 a=n mod 12,b=n-a
对于n mod 12=10的情况
a一定是10再加上x个12，才能使b能被12整除
发现22就是回文数
所以对于n大于等于22的情况，可以令a=22,b=n-22
当n=10时，不存在合法的a和b

#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;voidsolve(){intn;cin>>n;if(n==10)cout<<-1<<endl;elseif(n%12==10){cout<<22<<' '<<n-22<<endl;}else{intd=n%12;cout<<d<<' '<<n-d<<endl;}return;}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intt;cin>>t;while(t--)solve();return0;}

C题链接

n的范围允许O ( n 2 ) O(n^2)O(n2)
可以对每个i ii单独思考

断环为链，将整个数组长度复制为2倍
从i到i+n-1，即为一个环

当固定i ii为w [ i ] = 0 w[i]=0w[i]=0
对于每一个j jj,能容纳的最大值 = m i n ( 左边容器壁的最大值，右边容器壁的最大值 ) 能容纳的最大值=min(左边容器壁的最大值，右边容器壁的最大值)能容纳的最大值=min(左边容器壁的最大值，右边容器壁的最大值)

等效于，在断环为链下，对于每个i，处理i+1到i+n-1的这段区间

#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;voidsolve(){intn;cin>>n;vector<int>a(2*n+1);for(inti=1;i<=n;i++){cin>>a[i];a[i+n]=a[i];}for(inti=1;i<=n;i++){ints=0;vector<int>l(2*n+1),r(2*n+1);vector<int>w(2*n+1);for(intj=i+1;j<i+n;j++)l[j]=max(l[j-1],a[j-1]);for(intj=i+n-1;j>i;j--)r[j]=max(r[j+1],a[j]);for(intj=i+1;j<i+n;j++){w[j]=min(l[j],r[j]);s+=w[j];}cout<<s<<' ';}cout<<endl;return;}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intt;cin>>t;while(t--)solve();return0;}