Codeforces Round #789 (Div. 2) [已补BCDE，F待补]

贪心

1. 最少操作数：对于11，00这类我们不需要取操作它们，而对于10，01，我们需要把它们改成11或00
2. 所以我们就把a pair看作一组，出现01、10的次数即为我们的操作数
3. 而对于最小字段数量：我们去进行上面操作的时候，把10、01改11、00的时候，取决于前面哪个一对是11还是00，改成与前面相同的，这样修改的pair就不会对子段数量有贡献。所以就统计以下11和00变化的次数就行了

#include 
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    for(cin>>t;t;t--){
        int n;
        string s;
        cin>>n>>s;
        int cnt=0,judge=0,ans=0;
        for(int i=0;i 
 
Problem - C - Codeforces 
tags 
折半枚举思想
 
思路 
 
代码 
#include
#include
#define ll long long
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    for(cin>>t;t;t--){
        int n;
        cin>>n;
        vectorp(n+1);
        vectorsum(n+1,0);
        vectorf(n+1,0);
        for(int i=1;i<=n;i++)cin>>p[i];
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                if(p[i]>p[j])f[i]++;
            }
        }
        ll ans=0;
        for(int i=1;i<=n;i++){
            for(int j=1;jp[i])f[j]--;
            }
            for(int j=1;j<=i;j++)sum[j]=sum[j-1]+f[j];
            for(int j=1;j 
 
Problem - D - Codeforces 
tags 
思维
 
思路1 
行列分开计算
对于列的计算： 
  
每次加入一个人，所以的列都会往右移一列（第m列移到第1列），所以一个人只对单独一列有影响。
总共有m列，第ai个人影响第i%m列
若加入的人所在的列没有淘气的人，count++
判断有无淘气的人，只需以列首i%m为索引
 
对于行的计算：❓❓❓我不是很理解
 
 
代码 
AC代码1 
#include
#include
using namespace std;

void solve(){
    int n,m;
    string s;
    cin>>n>>m>>s;
    vectorc(m,0);
    vectorr(m,0);
    int count=0,last=-n*m;
    for(int i=0;i>t;t;t--){
        solve();
    }
}
 
超时代码 
#include
#include
#include
using namespace std;

int n,m;
int c[1000005],r[1000005];

void solve(){
    string s;
    cin>>n>>m>>s;
    memset(c,0,sizeof(c));
    memset(r,0,sizeof(r));
    int count=0,last=-n*m;
    for(int i=0;i>t;t;t--){
        solve();
    }
}
 
都是memset惹的祸
 
思路2 
列的思路与上面相同
 
行对答案的贡献：
 
每新增m名学生，所有学生的位置下移一列，行的贡献将如下增加
这m名学生将占据一行，若其中有1，则带来1的贡献。否则没有贡献。
可以用前缀和在O（1）时间内计算有无贡献
总：枚举第一行的贡献，在枚举第一行的过程中，不断加入1行（m个人），判断这行的贡献
 
AC代码2 
#include
#include
using namespace std;

void solve(){
    int n,m;
    char s[1000005];
    cin>>n>>m>>s+1;
    vectorsum(n*m+1,0);
    vectorans(n*m+1,0);
    vectorc(m+1,0);
    for(int i=1;i<=n*m;i++)sum[i]=sum[i-1]+s[i]-'0';
    int all=0;
    for(int i=1;i<=n*m;i++){
        if(s[i]=='1'&&c[i%m]==0)c[i%m]=1,all++;
        ans[i]+=all;
    }
    int t=0;
    for(int i=1;i<=m;i++){
        t|=s[i]-'0';
        ans[i]+=t;
        int temp=t;
        for(int j=i+m;j<=n*m;j+=m){
            if(sum[j]!=sum[j-m])temp++;
            ans[j]+=temp;
        }
    }
    for(int i=1;i<=n*m;i++)cout<>t;t;t--){
        solve();
    }
}
 
注意 
别用memset!!!小心超时
 
memset复杂度为O(n)
 
当测试样例为1e4,而数组大小为1e6时，TLE
 
 
Problem - E - Codeforces 
tags 
环，图，dfs，贪心
 
思路 
这两个排列可以构成若干个环
而
     
      
       
        
         ∑
        
        
         
          ∣
         
         
          a
         
         
          [
         
         
          i
         
         
          ]
         
         
          −
         
         
          b
         
         
          [
         
         
          i
         
         
          ]
         
         
          ∣
         
        
       
       
        sum{|a[i]-b[i]|}
       
      
     ∑∣a[i]−b[i]∣可以通过每个环相邻两点绝对值之和求得
而为了使其最大，按照**最大值、最小值、最大值、最小值······**的贪心策略来给环赋值，这样的贪心策略每次得到的差值最大，最坏结果也会最大
注意，对于奇数环，最后一个点无论赋值什么都不会对结果有贡献，这时就先不对其赋值，等其他环赋值完后最后剩下什么就对它赋值什么（自环也一样）
 
题解对“山峰”“山谷”的分析还挺好的
 
 
注意有
    
     
      
       
        [
       
       
        C
       
       
        i
       
       
        r
       
       
        c
       
       
        l
       
       
        e
       
       
        S
       
       
        i
       
       
        z
       
       
        e
       
       
        /
       
       
        2
       
       
        ]
       
      
      
       [CircleSize/2]
      
     
    [CircleSize/2]个山峰山谷，可以直接在分别1~n两边取
    
     
      
       
        [
       
       
        C
       
       
        i
       
       
        r
       
       
        c
       
       
        l
       
       
        e
       
       
        S
       
       
        i
       
       
        z
       
       
        e
       
       
        /
       
       
        2
       
       
        ]
       
      
      
       [CircleSize/2 ]
      
     
    [CircleSize/2]个数，（自环和奇数环的情况在除2取整的过程中实现不给最后一个点赋值）
 
AC代码 
#include
#define ll long long
using namespace std;

const int maxn=1e5+5;
int n,count;
int a[maxn],b[maxn],f[maxn],vis[maxn];

void dfs(int x){
    if(vis[x])return;
    vis[x]=1;
    count++;
    dfs(f[a[x]]);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    for(cin>>t;t;t--){
        cin>>n;
        for(int i=0;i>a[i];
        for(int i=0;i>b[i];
            f[b[i]]=i;
        }
        int ans=0;
        for(int i=0;i>1;
        }
        cout<<2ll*(n-ans)*ans< 
利用全局变量count来记录dfs次数（也就是环的大小）