Codeforces Round #562 (Div. 2)

链接

[https://codeforces.com/contest/1169]

A

水题过了

B

这个你开始暴力找到某个与第一个两两都不同
如果没找到就YES
否则就对四个不同的任意两个看是否可以。
我用全排列枚举

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3e5+10;
struct str{
    int a,b;
}c[N];
int n,m;
bool ok(int l,int r){
    for(int i=0;i<m;i++)
    {
        if(c[i].a!=l&&c[i].a!=r&&c[i].b!=l&&c[i].b!=r)
        return 0; 
    }
    return 1;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    while(cin>>n>>m){
        //set<int> v1,v2;
        for(int i=0;i<m;i++)
        {
            cin>>c[i].a>>c[i].b;
            if(c[i].a>c[i].b) swap(c[i].a,c[i].b);
        }
        //sort(c,c+m,cp);
        int l=-1,r=-1;
        int x=c[0].a,y=c[0].b;
        for(int i=1;i<m;i++)
        {
            if(c[i].a!=x&&c[i].a!=y&&c[i].b!=x&&c[i].b!=y){
                l=c[i].a;r=c[i].b; break;
            }
        }
        if(l==-1&&r==-1)
        cout<<"YES"<<endl;
        else{
            int f[4]; f[0]=l,f[1]=r,f[2]=x,f[3]=y; 
            bool flag=0;
            sort(f,f+4);
            do{
                flag=ok(f[0],f[1]);
            }while(next_permutation(f,f+4)&&!flag);
            if(flag) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
    }
    return 0;
}

C

给你某个数列，和一个m每次你可以选一些数都加一再取模m,问最后是非递减的最小操作次数是多少？
这也是二分+贪心，关键是你没想到啊，你需要二分次数，check该次数是否可以达到目的。我去二分还是牛逼啊
贪心就是尽可能让当前和前面一样小，check分两种情况，当前大于等于前面，看是否k次后取模大于等于前面，不可以就直接下一个位置
如果当前小于前面看k次后是否大于等于前面，如果不可以就直接return 0；如果到最后都满足非递减，就return 1；
就这么简单

代码

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int a[N],b[N],n,m;

bool ok(int k){
    for(int i=1;i<=n;i++)
    b[i]=a[i];
    for(int i=1;i<=n;i++){
        if(b[i]>=b[i-1]) {
            if(b[i]+k-m>=b[i-1]) b[i]=b[i-1];
        }
        else if(b[i]+k>=b[i-1]) b[i]=b[i-1];
        if(b[i]<b[i-1]) return 0;
    }
    return 1;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    while(cin>>n>>m){
        for(int i=1;i<=n;i++)
        cin>>a[i];
        int l=0,r=1e9;
        int ans;
        while(l<=r){
            int mid=(l+r)/2;
            if(ok(mid)){
                ans=mid;
                r=mid-1;
            }
            else l=mid+1;
        }
        cout<<ans<<endl;
    }
    return 0;
}

D

给你一个01字符串，问有多少个l, r that 1≤l≤r≤n and there is at least one pair of integers x, k such that 1≤x,k≤n, l≤x<x+2k≤r, and sx=sx+k=sx+2k.
这题就是个思维+暴力
你暴力每个起始位置和间隔k,然后就记录第一个sx=sx+k=sx+2k，因为当前是可以最大化数量的。
后面你得从后面位置开始取记录的最小的右端，有可能你原来记录的区间存在间隔更小的右端，这样贪心才是正确，不然会会少很多。
具体看代码吧；

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int N=3e5+10;
const int ma=0x3f3f3f3f;
int a[N];
int main(){
    string s;
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    while(cin>>s){
        int l=s.length();
        memset(a,ma,sizeof(a));
        for(int i=0;i<l;i++)
        for(int k=1;i+2*k<l;k++)
        if(s[i]==s[i+k]&&s[i]==s[i+2*k]){
            a[i]=i+2*k;
            break;
        }
        for(int i=l-1;i>=0;i--)
        a[i]=min(a[i],a[i+1]);
        ll ans=0;
        for(int i=0;i<l;i++)
        if(a[i]!=ma) ans+=l-a[i];
        cout<<ans<<endl;
    }
    return 0;
}

D还是有点东西的，因为你不仔细想你是很容易出错的

E

待补

Codeforces Round #562 (Div. 2)

原文：https://www.cnblogs.com/mch5201314/p/10933428.html