Educational Codeforces Round 63题解

A题

找到相邻两个逆序就行，这是最方便的

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    string s;
    cin>>s;
    int i;
    for(i=1;i<(int)s.size();i++){
        if(s[i]<s[i-1]){
            cout<<"YES"<<endl;
            cout<<i<<" "<<i+1<<endl;
            return 0;
        }
    }
    cout<<"NO"<<endl;
}

B题

观察到，每个人要-（n-11）/2次，并且8在第一位，我们肯定是删8前面的数字，删完了就在后面删，而对面肯定是为了阻止我们，当我们有符合条件的8，他一定会删掉

因此从头统计一下我们能够生成的符合条件的8的个数，和对面删的次数比较

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    string s;
    cin>>s;
    int x=n-11;
    int cnt=0;
    int last=0;
    s=" "+s;
    int res=0;
    for(int i=1;i<(int)s.size();i++){
        if(s[i]=='8'){
            if(i-1-cnt<=x/2){
                last++;
            }
            cnt++;
        }
    }
    if(last>x/2){
        cout<<"YES"<<endl;
    }
    else{
        cout<<"NO"<<endl;
    }
 
}

C题

这种题应该想到做差，右边就是gcd求一下

问题是左边的等式可以推得右边得等式组

但是反过来并不一定成立，当y=x1得时候右边成立肯定左边成立

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
ll a[N];
ll b[N];
ll p[N];
map<ll,int> m1;
ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}
int main(){
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    int i;
    for(i=1;i<=n;i++)
        cin>>a[i];
    for(i=2;i<=n;i++){
        b[i-1]=a[i]-a[i-1];
    }
    ll d=b[1];
    for(i=2;i<n;i++){
        d=gcd(d,b[i]);
    }
    for(i=1;i<=m;i++){
        cin>>p[i];
        if(d%p[i]==0){
            cout<<"YES"<<endl;
            cout<<a[1]<<" "<<i<<endl;
            return 0;
        }
    }
    cout<<"NO"<<endl;
}

 D题

洛谷翻译有毒，题意理解有误，写成别的题意了，不过正好给我的出题库加了一道题

这题就是带修的最大子串和，可以使用dp记录三种状态，没用过乘法，已经用过乘法，正在使用乘法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
ll f[N][4];
ll a[N];
int main(){
    ios::sync_with_stdio(false);
    ll n,x;
    cin>>n>>x;
    int i;
    for(i=1;i<=n;i++){
        cin>>a[i];
    }
    ll ans=0;
    for(i=1;i<=n;i++){
        f[i][1]=max(f[i-1][1]+a[i],0ll);
        f[i][2]=max(f[i-1][1]+a[i]*x,max(f[i-1][2]+a[i]*x,0ll));
        f[i][3]=max(f[i-1][2]+a[i],max(f[i-1][3]+a[i],0ll));
        ans=max(ans,f[i][1]);
        ans=max(ans,max(f[i][2],f[i][3]));
    }
    cout<<ans<<endl;
}