Codeforces Round#853 div2 A-C

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

B. Serval and Inversion Magic
题意：给你一个只含0和1的字符串，给你一个操作，可以将区间[L,R]之间的字符0变成1,1变成0。问你能否通过一次操作，将字符串变成回文串。
思路:因为我们只能够操作一段连续的区间。我们可以对比回文串对应的字符$s[i]$和$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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

C. Serval and Toxel’s Arrays 思维
题意:给你一个数组$A_i$,并且进行m次操作，每次操作都会将上一个数组中的第p个元素修改为v。得到新的数组。然后我们需要统计
所有$A_i$和$A_j$数组之间不同元素个数之和。
思路：如果我们直接进行模拟，在暴力计算，无疑会超时。那么遇到这种题目我们就需要算贡献，算贡献是一种计数类问题的经典套路。对于本题，我们可以算出每个数对答案的贡献，我们知道一共会有$m+1$个数组，对于数$x$,我们假设它在这$m+1$个数组中出现的次数为cnt，那么就可以分为两种情况，第一种情况，计算的两个数组中都含x，那么x对答案的贡献是1，这种情况一共有$C_{cnt}^2=cnt\ast (cnt-1)/2$种情况，对于计算的两个数组，一个含x另外一个不含x，那么他的贡献也是1，这种情况一种有$cnt\ast (m-cnt+1)$种，对于计算的两个数组都不含x的情况，那么x没有贡献，则不用计算。
所以我们现在就只需要计算出每个数在所有数组中出现的次数，以及在每次操作时维护好这个次数即可。
我们可以开一个map去记录每个数出现的次数，一个比较好的思路就是一开始我们假定后面每个数都没有改变，那么每个数出现的次数都是$m+1$次，那么在第i次操作时，将$a[p]$变为了$v$，那么$a[p]$的次数就会减少，减少了多少呢，很明显在这次操作之后的数组中都暂时不在含有$a[p]$，也就是$m-i+1$个。所以$mp[a[p]]-=(m-i+1)$,同理$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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22