Codeforces Round#853 div2 A-C
等了很久终于迎来了一场cf比赛，白天出去玩了一圈，晚上回来打比赛，这次只出了A,B题。C题思路很巧妙，赛时没做出来，看了大佬学习到了，还是很不错。
A.Serval and Mocha’s Array 签到
题意：这个题题目有点绕，看了十分钟才明白意思，就是给你一个数组，判断能否重新排列数组使得数组前两项的最大公约数是否小于等于2。
思路：数据范围小，直接暴力枚举判断即可。
void Showball(){
int n;
cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++) cin>>a[i];
int ok=0;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
int g=gcd(a[i],a[j]);
if(g<=2) {ok=1;break;}
}
}
if(ok) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
B. Serval and Inversion Magic
题意：给你一个只含0和1的字符串，给你一个操作，可以将区间[L,R]之间的字符0变成1,1变成0。问你能否通过一次操作，将字符串变成回文串。
思路:因为我们只能够操作一段连续的区间。我们可以对比回文串对应的字符
s
[
i
]
s[i]
s[i]和
s
[
n
−
i
−
1
]
s[n-i-1]
s[n−i−1]如果出现不相同，又相同，又不相同的情况，那么两端区间都需要操作，但是不连续，那么我们无法满足题意。所以进行标记判断这种情况即可。
void Showball(){
string s,t;
int n;
cin>>n;
cin>>s;
if(s==t) {cout<<"YES"<<endl;return;}
int ok=1;
bool f1=false,f2=false;
for(int i=0;i<n/2;i++){
if(s[i]!=s[n-i-1]) f1=true;
if(f1&&s[i]==s[n-i-1]) f2=true;
if(f2&&s[i]!=s[n-i-1]) {ok=0;break;}
}
if(ok) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
C. Serval and Toxel’s Arrays 思维
题意:给你一个数组
A
i
A_i
Ai,并且进行m次操作，每次操作都会将上一个数组中的第p个元素修改为v。得到新的数组。然后我们需要统计
所有
A
i
A_i
Ai和
A
j
A_j
Aj数组之间不同元素个数之和。
思路：如果我们直接进行模拟，在暴力计算，无疑会超时。那么遇到这种题目我们就需要算贡献，算贡献是一种计数类问题的经典套路。对于本题，我们可以算出每个数对答案的贡献，我们知道一共会有
m
+
1
m+1
m+1个数组，对于数
x
x
x,我们假设它在这
m
+
1
m+1
m+1个数组中出现的次数为cnt，那么就可以分为两种情况，第一种情况，计算的两个数组中都含x，那么x对答案的贡献是1，这种情况一共有
C
c
n
t
2
=
c
n
t
∗
(
c
n
t
−
1
)
/
2
C_{cnt}^2=cnt*(cnt-1)/2
Ccnt2=cnt∗(cnt−1)/2种情况，对于计算的两个数组，一个含x另外一个不含x，那么他的贡献也是1，这种情况一种有
c
n
t
∗
(
m
−
c
n
t
+
1
)
cnt*(m-cnt+1)
cnt∗(m−cnt+1)种，对于计算的两个数组都不含x的情况，那么x没有贡献，则不用计算。
所以我们现在就只需要计算出每个数在所有数组中出现的次数，以及在每次操作时维护好这个次数即可。
我们可以开一个map去记录每个数出现的次数，一个比较好的思路就是一开始我们假定后面每个数都没有改变，那么每个数出现的次数都是
m
+
1
m+1
m+1次，那么在第i次操作时，将
a
[
p
]
a[p]
a[p]变为了
v
v
v，那么
a
[
p
]
a[p]
a[p]的次数就会减少，减少了多少呢，很明显在这次操作之后的数组中都暂时不在含有
a
[
p
]
a[p]
a[p]，也就是
m
−
i
+
1
m-i+1
m−i+1个。所以
m
p
[
a
[
p
]
]
−
=
(
m
−
i
+
1
)
mp[a[p]]-=(m-i+1)
mp[a[p]]−=(m−i+1),同理
v
v
v这个数出现的次数自然就暂时增加了这么多。
最后带入公式计算即可，注意开long long。
void Showball(){
int n,m;
cin>>n>>m;
vector<int> a(n);
map<int,LL> mp;
for(auto &it:a){
cin>>it;
mp[it]=m+1ll;
}
for(int i=1;i<=m;i++){
int p,v;
cin>>p>>v;
mp[a[--p]]-=m-i+1;
mp[v]+=m-i+1;
a[p]=v;
}
LL ans=0;
for(auto &[k,v]:mp){
ans+=v*(v-1)/2ll+(m-v+1)*v;
}
cout<<ans<<endl;
}