Codeforces Global Round 10 A~D题解

发布于 2020-08-20  0 次阅读


A. Omkar and Password

题目大意:

给你一个长度为n的数组,每次可以合并两个相邻且不同的数,问最后数组最小的长度

思路:

其实答案只有1或者n,因为全部一样肯定是n,如果有一个不一样,它可以和其他的结合到最后为1

AC Code

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=2e5 +9;
int n, a[N], flag;
void solve(){
    cin>>n;
    flag=0;
    for(int i=1; i<=n; i++){
        cin>>a[i];
        if(i>1){
            if(a[i]!=a[i-1])    flag=1;
        }
    }
    if(flag)    cout<<"1"<<endl;
    else        cout<<n<<endl;
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

B. Omkar and Infinity Clock

题目大意:

给你一个长度为n的数组a,和一个操作的次数k
操作:找到数组最大值d,每个值变成d − ai

思路:

对于操作k,其实变化是交替出现的,所以我们只需要求得第一次和第二次的变化的情况,然后判断k的奇偶性即可

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=2e5 +9;
int n, k, a[N], mx, mx2;
void solve(){
    cin>>n>>k;
    mx=mx2=-INF;
    for(int i=1; i<=n; i++){
        cin>>a[i];
        if(a[i]>mx) mx=a[i];
    }
    for(int i=1; i<=n; i++){
        a[i]=mx-a[i];
        if(a[i]>mx2)    mx2=a[i];
    }
    if(k&1){
        for(int i=1; i<=n; i++) cout<<a[i]<<" ";
        cout<<endl;
    }
    else{
        for(int i=1; i<=n; i++) cout<<mx2-a[i]<<" ";
        cout<<endl;
    }
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

C. Omkar and Waterslide

题目大意:

给你一个长度为n的数组,要求将其变成非递减数组
操作:选择一个非递减的子段,将每个位置+1
求最小的操作次数

思路:

对于出现减少的位置(即ai < ai−1 ),将 ai变为ai−1 ,需要的操作次数为ai−1 < ai
​例如:
4
5 3 2 5
即将3 2变成5
3变成5需要2,2变成5需要3,但是可以先将2变成3再变成5,即为ai−1 < ai

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=2e5 +9;
int n, a[N], ans;
void solve(){
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    ans=0;
    for(int i=1; i<=n; i++) if(a[i]<a[i-1]) ans+=a[i-1]-a[i];
    cout<<ans<<endl;
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

D. Omkar and Bed Wars

题目大意:

给你一个长度为n的字符串,字符串由L和R组成表示其攻击的人的方向
所有人围成一个圈,每个人必须攻击相邻的人,每人受到的攻击数可能为0,1,2,当只受到一个人的攻击时,你必须要反击这个人,受到0或者2个人的攻击可以随便攻击
求使得字符串满足该种情况需要的最小纠正次数

思路:

统计其中连续且相同的字符的长度,如果全为一种一样的则每三个改变一个即可,即为1 + (n-1)/3
否则即为连续且相同的字符的长度/ 3

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=2e5 +9;
int n, b[N];
string s;
void solve(){
    cin>>n;
    int ans=1, cnt=0;
    cin>>s;
    for(int i=1; i<n; i++){
        if(s[i]==s[i-1])    ans++;
        else                b[cnt++]=ans, ans=1;
    }
    b[cnt++]=ans;
    if(cnt>1 && s[0]==s[n-1])   b[0]+=b[cnt-1], b[cnt-1]=0;
    if(cnt==1)  cout<<(1+(n-1)/3)<<endl;
    else{
        ans=0;
        for(int i=0; i<cnt; i++)    ans+=b[i]/3;
        cout<<ans<<endl;
    }
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

平平无奇的大学在读本科生