Codeforces 1272 A-E

A Three Friends

直接枚举所有情况，共\(3\times 3\times 3=27\)种。

code

#include<bits/stdc++.h>
#define fi first
#define se second
#define lson l,mid,p<<1
#define rson mid+1,r,p<<1|1
#define pb push_back
#define ll long long
using namespace std;
const int inf=1e9;
const int mod=1e9+7;
const int maxn=1e5+10;
int q;
int main(){
    //ios::sync_with_stdio(false);
    //freopen("in","r",stdin);
    cin>>q;
    while(q--){
        int a,b,c;
        cin>>a>>b>>c;
        int ans=abs(a-b)+abs(b-c)+abs(a-c);
        for(int i=-1;i<=1;i++){
            for(int j=-1;j<=1;j++){
                for(int k=-1;k<=1;k++){
                    int x=a+i,y=b+j,z=c+k;
                    ans=min(ans,abs(x-y)+abs(y-z)+abs(x-z));
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

B Snow Walking Robot

因为是无限大的网格，所以最简单的构造方法是走一个矩形框

注意要特判向任意方向走一步再走回起点的情况，样例中有。

code

#include<bits/stdc++.h>
#define fi first
#define se second
#define lson l,mid,p<<1
#define rson mid+1,r,p<<1|1
#define pb push_back
#define ll long long
using namespace std;
const int inf=1e9;
const int mod=1e9+7;
const int maxn=1e5+10;
int q;
char s[maxn];
int main(){
    ios::sync_with_stdio(false);
    //freopen("in","r",stdin);
    cin>>q;
    while(q--){
        cin>>s+1;
        int n=strlen(s+1);
        int L=0,R=0,U=0,D=0;
        for(int i=1;i<=n;i++){
            if(s[i]=='L') ++L;
            else if(s[i]=='R') ++R;
            else if(s[i]=='U') ++U;
            else ++D;
        }
        L=R=min(L,R);
        U=D=min(U,D);
        if(L&&U==0){
            cout<<2<<endl;
            cout<<"RL"<<endl;
        }else if(U&&L==0){
            cout<<2<<endl;
            cout<<"DU"<<endl;
        }else if(U==0||L==0){
            cout<<0<<endl;
        }else{
            cout<<L*2+U*2<<endl;
            for(int i=1;i<=L;i++){
                cout<<'R';
            }
            for(int i=1;i<=D;i++){
                cout<<'D';
            }
            for(int i=1;i<=L;i++){
                cout<<'L';
            }
            for(int i=1;i<=D;i++){
                cout<<'U';
            }
            cout<<endl;
        }
    }
    return 0;
}

C Yet Another Broken Keyboard

在字符串s中所有不能打出的字母的位置作为隔板，隔出来的每个子串(设\(len\)为子串的长度)对答案的贡献即为\(len \times (len+1) /2\)。

code

#include<bits/stdc++.h>
#define fi first
#define se second
#define lson l,mid,p<<1
#define rson mid+1,r,p<<1|1
#define pb push_back
#define ll long long
using namespace std;
const int inf=1e9;
const int mod=1e9+7;
const int maxn=2e5+10;
int n,k;
char s[maxn],t[30];
int main(){
    ios::sync_with_stdio(false);
    //freopen("in","r",stdin);
    cin>>n>>k;
    cin>>s+1;
    for(int i=1;i<=k;i++){
        char c;
        cin>>c;
        t[c-'a']=1;
    }
    ll ans=0,cnt=0;
    for(int i=1;i<=n;i++){
        if(!t[s[i]-'a']){
            ans+=cnt*(cnt+1)/2;
            cnt=0;
        }else ++cnt;
    }
    ans+=cnt*(cnt+1)/2;
    cout<<ans<<endl;
    return 0;
}

D Remove One Element

\(O(n)\)预处理出\(l[i]\)为\(i\)作为终点的最长严格递增子段，\(r[i]\)为\(i\)作为起始点的最长严格递增子段。

• 不删除一个元素，\(ans=max\{l[i]\},(1<=i<=n)\)。
• 删除一个元素，\(ans=max\{l[i-1]+r[i+1]\},(1<i<n\&\&a[i-1]<a[i+1])\)

code

#include<bits/stdc++.h>
#define fi first
#define se second
#define lson l,mid,p<<1
#define rson mid+1,r,p<<1|1
#define pb push_back
#define ll long long
using namespace std;
const int inf=1e9;
const int mod=1e9+7;
const int maxn=2e5+10;
int n;
int a[maxn];
int l[maxn],r[maxn];
int main(){
    ios::sync_with_stdio(false);
    //freopen("in","r",stdin);
    cin>>n;
    int ans=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]>a[i-1]) l[i]=l[i-1]+1;
        else l[i]=1;
        ans=max(ans,l[i]);
    }
    r[n]=1;
    for(int i=n-1;i>=1;i--){
        if(a[i]<a[i+1]) r[i]=r[i+1]+1;
        else r[i]=1;
    }
    for(int i=2;i<n;i++){
        if(a[i+1]>a[i-1]) ans=max(ans,l[i-1]+r[i+1]);
    }
    cout<<ans<<endl;
    return 0;
}

E Nearest Opposite Parity

能发现若\(d[i+-a[i]]\)的值已确定，那么\(d[i]=min(d[i],d[i+-a[i]]+1)\)。

跟据这个性质我们以反边建图，所有边的边权都为1，以所有能一步到达奇偶性不同的点的点作为源点来跑最短路就行了(因为所有边权都为1，所以直接bfs也行)。

code

#include<bits/stdc++.h>
#define fi first
#define se second
#define lson l,mid,p<<1
#define rson mid+1,r,p<<1|1
#define pb push_back
#define ll long long
using namespace std;
const int inf=1e9;
const int mod=1e9+7;
const int maxn=2e5+10;
int n;
int a[maxn];
vector<int>g[maxn];
int dis[maxn];
struct ppo{
    int v,c;
    bool operator <(const ppo &r) const{
        return c>r.c;
    }
};
int main(){
    ios::sync_with_stdio(false);
    //freopen("in","r",stdin);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        dis[i]=inf;
        if(i-a[i]>=1){
            if(a[i-a[i]]%2!=a[i]%2) dis[i]=1;
            g[i-a[i]].pb(i);
        }
        if(i+a[i]<=n){
            if(a[i+a[i]]%2!=a[i]%2) dis[i]=1;
            g[i+a[i]].pb(i);
        }
    }
    priority_queue<ppo>q;
    for(int i=1;i<=n;i++){
        if(dis[i]==1) q.push(ppo{i,dis[i]});
    }
    while(!q.empty()){
        int u=q.top().v;q.pop();
        for(int x:g[u]){
            if(dis[u]+1<dis[x]){
                dis[x]=dis[u]+1;
                q.push(ppo{x,dis[x]});
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(dis[i]==inf) cout<<-1<<" ";
        else cout<<dis[i]<<" ";
    }
    return 0;
}