Codeforces Round #821(Div.2) (A-C)
A.Consecutive Sum
大致题意
给定一组共 n 个数据 ，如果俩个数的下标在 mod k 意义下同余，则可以交换a[I] 和 a[j] ,求操作后一段连续的数的和的最大值。
基本思路
本题属于水题，因为 t 和 n 都比较小，所以可以直接暴力的把所有最大的数移到最前面的 k 个位置，即从最后 k 个数开始向前枚举比较，做冒泡排序即可。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=105;
ll a[N];
int main(){
int T;
cin>>T;
while(T--){
memset(a,0,sizeof a);
int n,k;
cin>>n>>k;
for (int i=1;i<=n;i++){
cin>>a[i];
}
for (int i=1;i<=k;i++){
for (int j=n-i+1;j>=1+k;j-=k) {
if (a[j]>a[j-k]) swap(a[j],a[j-k]);
}
}
ll ans=0;
for (int i=1;i<=k;i++) ans+=a[i];
cout<<ans<<endl;
}
return 0;
}
建议
读题速度要快，尽早秒杀。
B.Rule of League
大致题意
有 n 个选手举办羽毛球比赛，总共比 n-1 场，每个人不是赢了 x 场就是赢了 y 场，要求构造
一组合理的每场获胜选手的数据。
基本思路
这是一道考研思维的题，我们可以结合生活实际，首先了解比赛的规则。
比赛必须有输有赢，所以 x 和 y 中必须有一个大于 0 ,一个等于 0 (因为总会有人输，也有人赢)。
因为总共比 n-1 场，而赢得人都赢了 x 或 y 次，所以要求 (n-1) mod max(x,y)=0 ,即赢的人的获胜场次必须是 n-1 的因子。
综上，可以得到三个不存在合理数据的条件，可以由此特判输出 -1 。
接着，对于合理的数据，只要从 1 开始枚举获胜者的编号即可，如果害怕枚举出错，可以模拟比赛
过程，枚举当前场次的对手，这样获胜者的坐标不会出错且时间复杂度不变。
代码如下。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int t;
cin>>t;
while(t--) {
int n,x,y;
cin>>n>>x>>y;
ll ans=0;
int p=n-1;
ll nowx=max(x,y),nowy=min(x,y);
if (nowy!=0 || nowx+nowy==0 || p%nowx!=0) {
puts("-1");
continue;
}
int i;
int tot=1,k=2; //用k模拟对手
for (i=1; i<=p;) {
for (int j=1; j<=nowx; j++) {
cout<<tot<<" ";
k++;
}
i=i+nowx;
tot=k;
}
cout<<endl;
}
return 0;
}
C.Parity Shuffle Sorting
大致题意
给定一组非负整数，可以最多进行 n 次操作，选取俩个数，当俩个数之和为奇数，可以把右边的数变成左边的数；如果是偶数，可以将左边的数变成右边的数。要求经过操作后得到一组非递减序列。
基本思路
依旧是一道思维题。
由于俩数之和为奇数时，右边的数可以变成左边的数，所以显然，每个与第一个数之和为奇数的数可以变成第一个数；反之，每个与最后一个数之和为偶数的数可以变成最后一个数。由此可得：每个数都可以变成第一个数或者最后一个数。
除此之外，根据操作规则，我们也能把第一个数变成最后一个数，或者把最后一个数变成第一个数。将头尾俩数变成同一个数之和，便可以将每个数都变成同一个数，操作次数最多为 n-1 次，即单组数据时间复杂度为 O(n) 。
需要注意的是，当 n=1 时，无需操作，可直接输出 0 ；整个程序时间复杂度为 O(n*t) ，因为俩个数最大都为 1e5 所以不能用 memset 函数初始化数组，不然会超时。（实际上也不需要初始化）
代码如下
代码
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
typedef long long ll;
ll a[N];
int l[N],r[N];
int main() {
int T;
cin>>T;
while(T--) {
int n;
cin>>n;
for (int i=1; i<=n; i++) cin>>a[i];
int cnt=0;
if (n==1){
puts("0");
continue;
}
if (a[1]!=a[n]) {
if (a[1]%2==1 && a[n]%2==0) {
l[++cnt]=1;
r[cnt]=n;
a[n]=a[1];
} else if (a[1]%2==1 && a[n]%2==1) {
l[++cnt]=1;
r[cnt]=n;
a[1]=a[n];
} else if (a[1]%2==0 && a[n]%2==0) {
l[++cnt]=1;
r[cnt]=n;
a[1]=a[n];
} else {
l[++cnt]=1;
r[cnt]=n;
a[n]=a[1];
}
}
for (int i=2; i<=n-1; i++) {
int now=a[i]+a[1];
if (now%2==0) {
l[++cnt]=i;
r[cnt]=n;
} else {
l[++cnt]=1;
r[cnt]=i;
}
}
cout<<cnt<<endl;
for (int i=1; i<=cnt; i++) cout<<l[i]<<" "<<r[i]<<endl;
}
return 0;
}
总结
Codeforces 的比赛前三题主要重视的是思维而非算法，并不能读完题就思考用什么算法解决问题，且题目的真意常常不如题面上描述的复杂，所以应该借助样例，探究其中的规律，了解题目的真实意图，这一点与 OI 注重算法思维的比赛有些许不同。
除此之外，由于有时不能直接借用某种算法来解决问题，所以还要会精确地计算时间复杂度，避免超时。当然，由于有可能被其他选手 hack ，在考虑问题的时候需要注意某些特别的数据。
总体而言，div.2的前三题相对简单，想要快速解决，应该多加锻炼思维能力（多打比赛）。
标签：cnt,int,题解,ll,cin,long,Div.2,变成,821 From： https://www.cnblogs.com/you-mu-jv-ruo/p/16712303.html