[数据结构与算法]Codeforces Round #784 (Div. 4) All Problems

Codeforces Round #784 (Div. 4)

前言：

题目都挺新手的，符合$div4$该有的难度，并且给我贡献了史上第一次$ak$局，相对还蛮欢乐的，适合新人。

$1$小时$15$分钟$ak$，老年人手速了。

A. Division?

思路：$if$ $else$即可。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
void cf(){
    int x;
    cin>>x;
    if(x<1400)cout<<"Division 4"<<endl;
    else if(x<1600)cout<<"Division 3"<<endl;
    else if(x<1900)cout<<"Division 2"<<endl;
    else cout<<"Division 1"<<endl;
} 
signed main(){
    int t=1;
    cin>>t;
    while(t--){
        cf();
    }
}

B. Triple

思路： $a$的数据范围很小直接拿数组存，边跑边存，出现某个数个数大于等于$3$输出那个数，都没有输出$?1$

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+10;
int a[N];
int sum[N];
void cf(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){cin>>a[i];sum[a[i]]=0;}
    for(int i=1;i<=n;i++){
        sum[a[i]]++;
        if(sum[a[i]]>=3){cout<<a[i]<<endl;return ;}
    }
    cout<<"-1"<<endl;
} 
signed main(){
    int t=1;
    cin>>t;
    while(t--){
        cf();
    }
}

C. Odd/Even Increments

思路： 奇偶性问题，不管奇数位怎么变，偶数位怎么变，如果两个数都在奇数位或者两个数都在偶数位，他们之间的奇偶关系始终保持不变，例如$1$ $3$ $5$这组数据$1$和$5$都是奇数位不管怎么加，他们都是共奇共偶的，如果是$1$ $3$ $6$这组数据，$1$和$6$都是奇数位不管怎么加，他们都是$1$奇$1$偶。且奇数位和偶数位相互独立互不影响，所以我们是要判断是否存在奇数位上的所有数且偶数位上的所有数都是共奇共偶的情况，如果存在即为YES否则是NO，注意只有两个数的情况，因此我们直接从$3$和$4$开始判断即可。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 55;
int a[N];
void cf(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    bool ok = true;
    for(int i=3;i<=n;i+=2){
        if((a[i]%2)!=(a[i-2]%2)){
            ok=false;
        }
    }
    for(int i=4;i<=n;i+=2){
        if((a[i]%2)!=(a[i-2]%2)){
            ok=false;
        }
    }
    if(ok)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
} 
signed main(){
    int t=1;
    cin>>t;
    while(t--){
        cf();
    }
}

D. Colorful Stamp

思路： 这题是个结论题，红蓝染色问题，因为不能染到格子外，所以我们令下标$0$和下标$n+1$全部当作$w$处理。然后将$w、b、r$分别转化为$0、1、2$。此外，如果一段区间染色，那么必然两种颜色都存在，全为$b$或者全为$r$显然是不成立的。且每段染色区间由两个$w$进行隔开，例如染色区间为：wrrbrbrbrbrw。那么同样得到了这个结论我们进行$O(n)$扫描，如果出现不合法的输出NO，否则输出YES。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+10;
int a[N];
void cf(){
    a[0]=0;
    int n;
    cin>>n;
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++){
        if(s[i]=='W')a[i+1]=0;
        else if(s[i]=='B')a[i+1]=1;
        else if(s[i]=='R')a[i+1]=2;
    }
    a[n+1]=0;
    for(int i=0;i<=n+1;i++){
        if(a[i]==0){
            bool ok = false;
            int res=0;//用来判断出现几种颜色
            for(int j=i+1;j<=n+1;j++){
                if(a[j]!=0&&res==0){
                    res=a[j];
                }
                else if(a[j]!=0&&res!=0&&res!=a[j]){
                    ok=true;//出现两种颜色区间合法
                }
                if(a[j]==0){//右边的w
                    if(!ok&&res!=0){//如果没染色或者染了两种颜色是合法的
                        cout<<"NO"<<endl;
                        return ;
                    }
                    else{//更新i,因为右边的w可以作为新的区间段的左边界所以i=j-1
                        i=j-1;
                        goto GG;
                    }
                }
            }
            GG:;
        }
    }
    cout<<"YES"<<endl;
    return ;
} 
signed main(){
    int t=1;
    cin>>t;
    while(t--){
        cf();
    }
}

E. 2-Letter Strings

思路： 无脑$hash$，用$mp1$存第$1$关键字符，$mp2$存第$2$关键字符，$mp$存$string$，接下去每次出现新的$string$ $s$加上前面统计过的$mp1[s[0]]$和$mp2[s[1]]$，并且如果前面出现了和$s$相同的$string$，实则是不合法的，但是$mp1$和$mp2$同样会统计其第$1$关键字和第$2$关键字出现的次数，所以我们需要减去$mp[s]$ $?$ $2$

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+10;
map<char,int>mp1,mp2;
map<string,int>mp;
void cf(){
    mp.clear();
    mp1.clear();
    mp2.clear();
    int n;
    cin>>n;
    int sum=0;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        sum+=mp1[s[0]];
        sum+=mp2[s[1]];
        sum-=mp[s]*2;
        mp1[s[0]]++;
        mp2[s[1]]++;
        mp[s]++;
    }
    cout<<sum<<endl;
} 
signed main(){
    int t=1;
    cin>>t;
    while(t--){
        cf();
    }
}

F. Eating Candies

思路： 双指针，用$left$和$right$统计两边吃的$number$，如果相等就更新一下，否则$left$和$right$谁小谁吃糖，直至$l>r$退出。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+10;
int a[N];
void cf(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int l=1,r=n;
    int ma=0;
    int left=0,right=0;
    while(l<=r){
        if(left==right){
            ma=l-1+n-r;
        }
        if(left<=right){
            left+=a[l];
            l++;
        }
        else if(left>right){
            right+=a[r];
            r--;
        }
    }
    if(left==right)ma=n;
    cout<<ma<<endl;
} 
signed main(){
    int t=1;
    cin>>t;
    while(t--){
        cf();
    }
}

G. Fall Down

思路： 一道模拟题，数据范围很小直接暴力模拟，因为最后一层也算一个终止点，所以我们可以初始化令第$n+1$行的所有字符变成$o$，然后每次单独处理每一列即可，在碰到$o$之前只要出现$?$就统计一下$?$出现的次数，一旦碰到$o$，就将前面统计过的$?$出现从下到上依次放好，且清空$?$出现次数，重新统计。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 55;
char s[N][N];
void cf(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)cin>>s[i][j];
    for(int i=1;i<=m;i++)s[n+1][i]='o';
    for(int i=1;i<=m;i++){//列
        int cnt=0;
        int st=1;
        for(int j=1;j<=n+1;j++){
            if(s[j][i]=='*')cnt++;
            else if(s[j][i]=='.')continue;
            else if(s[j][i]=='o'){
                for(int k=st;k<=j-1;k++){
                    s[k][i]='.';
                }
                for(int k=j-cnt;k<j;k++){
                    s[k][i]='*';
                }
                st=j+1;
                cnt=0;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)cout<<s[i][j];cout<<endl;}
    return ;
} 
signed main(){
    int t=1;
    cin>>t;
    while(t--){
        cf();
    }
}

H. Maximal AND

思路： 二进制高位贪心，首先统计一下所有数在二进制位下每一位出现的次数，由于我们每次操作可以使一个数的二进制为从$0$变成$1$，且要求最终所有数的AND值最大，那么最优策略就是从高位进行填补，如果$k$的剩余值能将高位所有$0$变成$1$显然将所有$0$变成$1$更优。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+10;
int a[N];
int sum[35];
void cf(){
    memset(sum,0,sizeof sum);
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=30;i>=0;i--){
        for(int j=1;j<=n;j++){
            if((a[j]>>i)&1)sum[i]++;
        }
    }
    int res=0;
    for(int i=30;i>=0;i--){
        if(k>=n-sum[i]){
            k-=(n-sum[i]);
            res|=1<<i;
        }
    }
    cout<<res<<endl;
} 
signed main(){
    int t=1;
    cin>>t;
    while(t--){
        cf();
    }
}

阅读世界，共赴山海

423全民读书节，邀你共读