Codeforces Round 1102 (Div. 2)

A题链接a [ i 2 ] a[i2]a[i2]一定属于0到a [ i 1 ] − 1 a[i1]-1a[i1]−1之间所以该序列一定是严格单调递减的将序列倒序后判断相邻三个元素是否满足数量关系即可#includebits/stdc.h#defineendl\n#defineintlonglongusingnamespacestd;voidsolve(){intn;cinn;vectorinta(n1);for(inti1;in;i)cina[i];sort(a.begin()1,a.end());reverse(a.begin()1,a.end());for(inti1;in-2;i){if(a[i2]!a[i]%a[i1]){cout-1endl;return;}}couta[1] a[2]endl;return;}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intt;cint;while(t--)solve();return0;}B题链接b需要被12整除考虑算n mod 12发现n mod 12 的结果为0到11其中 除了10 以外均为回文数所以可以令 an mod 12,bn-a对于n mod 1210的情况a一定是10再加上x个12才能使b能被12整除发现22就是回文数所以对于n大于等于22的情况可以令a22,bn-22当n10时不存在合法的a和b#includebits/stdc.h#defineintlonglong#defineendl\nusingnamespacestd;voidsolve(){intn;cinn;if(n10)cout-1endl;elseif(n%1210){cout22 n-22endl;}else{intdn%12;coutd n-dendl;}return;}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intt;cint;while(t--)solve();return0;}C题链接n的范围允许O ( n 2 ) O(n^2)O(n2)可以对每个i ii单独思考断环为链将整个数组长度复制为2倍从i到in-1即为一个环当固定i ii为w [ i ] 0 w[i]0w[i]0对于每一个j jj,能容纳的最大值 m i n ( 左边容器壁的最大值右边容器壁的最大值 ) 能容纳的最大值min(左边容器壁的最大值右边容器壁的最大值)能容纳的最大值min(左边容器壁的最大值右边容器壁的最大值)等效于在断环为链下对于每个i处理i1到in-1的这段区间#includebits/stdc.h#defineintlonglong#defineendl\nusingnamespacestd;voidsolve(){intn;cinn;vectorinta(2*n1);for(inti1;in;i){cina[i];a[in]a[i];}for(inti1;in;i){ints0;vectorintl(2*n1),r(2*n1);vectorintw(2*n1);for(intji1;jin;j)l[j]max(l[j-1],a[j-1]);for(intjin-1;ji;j--)r[j]max(r[j1],a[j]);for(intji1;jin;j){w[j]min(l[j],r[j]);sw[j];}couts ;}coutendl;return;}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intt;cint;while(t--)solve();return0;}