当前位置:   article > 正文

Codeforces Round#853 div2 A-C

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[i] s[i] s [ n − i − 1 ] s[n-i-1] s[ni1]如果出现不相同,又相同,又不相同的情况,那么两端区间都需要操作,但是不连续,那么我们无法满足题意。所以进行标记判断这种情况即可。

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 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(cnt1)/2种情况,对于计算的两个数组,一个含x另外一个不含x,那么他的贡献也是1,这种情况一种有 c n t ∗ ( m − c n t + 1 ) cnt*(m-cnt+1) cnt(mcnt+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 mi+1个。所以 m p [ a [ p ] ] − = ( m − i + 1 ) mp[a[p]]-=(m-i+1) mp[a[p]]=(mi+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;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
声明:本文内容由网友自发贡献,转载请注明出处:【wpsshop】
推荐阅读
相关标签
  

闽ICP备14008679号