Codeforces Round #789 (Div. 2) A~D(E,F待补)个人题解

题意：有一个长度为n的数组a,每次可以从数组种选择俩个下标不同的元素进行下面俩个操作：

（1）如果两个元素相同，把其中一个变成0,()

（2）如果两个元素不同，把两个元素都变成这两个的最小值()

问，最少的操作数把数组a全部变成0？

知识点：思维

思路：可以分类一下，

1、如果数组中本来就有0，那操作数一定是不为0的数和0进行（2）操作，答案就是不为0的个数

2、如果数组中没有0，但是有相同的两个元素，那进行一次（1）操作，把一个不为0的数变成0，剩下的又是情况1、，答案就是 1+(不为0的个数-1)

3、数组中没有0，没有相同的两个元素，进行一次操作（2），变出两个想等的元素，剩下的又是情况2、，答案就是  1+[1+(不为0的个数-1)]

代码：

#include 
using namespace std;
typedef long long ll;
const ll N = 1e6+5;
const ll mod =998244353;
ll a[N];
void solve(){
    ll n;cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i];
    ll res=0;//不为0的元素的个数
    for(int i=1;i<=n;++i)if(a[i])res++;
    sort(a+1,a+n+1);//排个序，让相等元素相邻
    if(a[1]==0)cout<>_;
    while(_--){
        solve();
    }
    return 0;
}

题意：有一个长度为偶数的01串，

定义数组d,表示这个01串连续子串的长度，比如 01串“100101001”，数组d={1,2,1,1,1,2,1}("1","00","1","0","1","00","1")。

定义一个01串是好的，那要满足这个01串的数组d的元素都是偶数。

你可以进行任意次操作，每次操作可以让01串的0变成1，1变成0

问最少的操作数把这个01串变成好的，并且在此前提下让数组d的长度最小？

输出 最少操作数和数组d的长度

知识点：贪心，思维

思路：首先要注意到，01串长度是偶数，连续子串的长度也要是偶数，那么01串S的S[i]和S[i+1]一定是相同的(S从下标1开始,i是奇数)。

那么对于最少的操作数，每次看S[i]和S[i+1]，如果相同就不用改，如果不同改其一，答案就出来了。

然后是让数组d长度最小，每次看S[i]和S[i+1]，如果相同是不用改的，如果不同改其一，改哪个？

这下就是贪心了，如果他前面的字符是0，那我就改成00，如果是1，改成11。

都改完了，相同的合并，最后的长度就是答案。

（有一个点，如果开始的两个就不同怎么办，我们可以开一个-1的状态，表示他是谁都可以）

代码：

#include 
using namespace std;
typedef long long ll;
const ll N = 2e5+5;
const ll mod =998244353;
int s[N];
void solve(){
    ll n;cin>>n;
    for(int i=1;i<=n;++i){
        char c;
        cin>>c;
        s[i]=c-'0';//输入01串
    }
    int pre=-1;//记录他前面是谁，-1表示任意
    ll ans=0,d=0;//操作数，长度
    for(int i=1;i<=n;i+=2){
        if(s[i]^s[i+1]==0){//如果这两个相等
            if(s[i]==pre)continue;//如果等于他前面的，那继续
            d++;//不等于他前面的，长度+1
            pre=s[i];//更新
        }
        else ans++;//如果两个不等，操作数要+1
    }
    d=max(1ll,d);//上面代码可能d++操作都不会执行，但是长度一定是大于等于1的，所以取个1
    cout<>_;
    while(_--){
        solve();
    }
    return 0;
}

题意：给你一个长度为n的数组p,问有多少个本质不同的四元组（a,b,c,d）满足p_d" src="https://latex.codecogs.com/gif.latex?1%5Cleq%20a%3Cb%3Cc%3Cd%20%5Cleq%20n%20%5C%20and%20%5C%20p_a%3Cp_c%5C%20and%20%5C%20p_b%3Ep_d" />？

知识点：计数，桶，前缀和

思路：我是通过枚举A,D来实现的，每次把一个A放入桶中，选择一个B，然后往后看C的时候，看桶中比C小的A的个数，存到一个变量res里，如果看D的时候满足D

首先第一步确定了 A

代码：

#include 
using namespace std;
typedef long long ll;
const ll N = 5e3+5;
const ll mod =998244353;
ll a[N],has[N],d[N],n;//d是桶，has是前缀和数组
void solve(){
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i],d[i]=0;
    ll ans=0;
    for(int i=3;ia[j])ans+=res;//如果B>D
            res+=has[a[j]];//更新A,C关系
        }
    }
    cout<>_;
    while(_--){
        solve();
    }
    return 0;
}

题意：现在有一个大小的会议室，有个学生，每个学生都有两个属性0和1(?)，他们依次进入会议室，依次进入规则如下图

 问，对于每个时刻，有多少行，多少列的和不为0？

输出每个时刻，满足条件的行和列的个数和

知识点：思维

思路：可以考虑列和行分开来算，

我们定义ans[i]为第i个时刻满足条件的列的个数

对于列来说，每次一个属性为0的学生进入会议，会发现他们每次都符合

其实也很好想，每次来一个都进1就这样了，

这时ans[i]=ans[i-1]，因为0不会把这一列改成符合的

如果是属性为1的学生进入会议 

 会发现，1可以把这一列改成符合的，所以我们要看这个绿色的是不是满足了，因为都是同一列的，他们对行长取模大小相同，所以我们维护一个对行长取模的数组来看这一列是不是满足了就行了。

我们定义res[i]为第i个时刻满足条件的行的个数

对于行来说，每次学生进入会议，会发现他们每次都符合

 这个绿色框子里行的个数其实我们早在之前算过了，所以问题就是第一行是不是满足，所以维护一个长度为行长的第一行就行了，看是不是符合,res[i]=res[i-m]+(符合)，不够一行就没有res[i-m]所以只看符合不符合就行了，res[i]=(符合)

代码：

#include 
using namespace std;
typedef long long ll;
const ll N = 1e6+5;
const ll mod =998244353;
ll ans[N],res[N];//列个数，行个数
bool has[N];
ll n,m;
ll getid(ll x){//因为我是下标从1开始，所以取模要改一下
    if(x%m==0)return m;
    return x%m;
}
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n*m;++i)ans[i]=res[i]=0,has[i]=false;//初始化
    string s;cin>>s;
    s='#'+s;//让下标从1开始
    for(int i=1;i=1);//这一行个数不为0
        }
        else {
            if(s[i-m]=='1')d--;//滑动，更新
            if(s[i]=='1')d++;//滑动，更新
            res[i]=(d>=1)+res[i-m];//这一行满足不满足加下面那个已经算过的
        }
    }
    for(int i=1;i<=n*m;++i)cout<>_;
    while(_--){
        solve();
    }
    return 0;
}