Codeforces Round #605 (Div. 3) 题解

总结

都是些没啥意思的题
卡点：A开始想的贪心，B有点细节，E开始写假了

A

爆搜一下即可，写成循环更方便

#include<bits/stdc++.h>
typedef long long LL;
#define pb push_back
const LL maxn=3e6+9,inf=0x3f3f3f3f;
LL Read(){
    LL x(0),f(1); char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-') f=-1; c=getchar(); 
    }
    while(c>='0' && c<='9'){
        x=(x<<3ll)+(x<<1ll)+c-'0'; c=getchar();
    }return x*f;
}
LL T,ans;
LL a[maxn];
void Dfs(LL N){
    if(N>3){
        LL ret(abs(a[1]-a[2])+abs(a[1]-a[3])+abs(a[2]-a[3]));
        ans=std::min(ans,ret); return;
    }
    a[N]++; Dfs(N+1); a[N]-=2; Dfs(N+1); a[N]++; Dfs(N+1);
}
int main(){
    LL T(Read());
    while(T--){
        ans=1e18;
        for(LL i=1;i<=3;++i) a[i]=Read();
        Dfs(1);
        printf("%lld\n",ans);
    }
}

B

走一个矩阵即可

#include<bits/stdc++.h>
typedef int LL;
#define pb push_back
const LL maxn=3e6+9,inf=0x3f3f3f3f;
LL Read(){
    LL x(0),f(1); char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-') f=-1; c=getchar(); 
    }
    while(c>='0' && c<='9'){
        x=(x<<3ll)+(x<<1ll)+c-'0'; c=getchar();
    }return x*f;
}
LL T;
LL sum[5],a[maxn];
char s[maxn];
int main(){
    T=Read();
    while(T--){
        scanf(" %s",s+1); LL n(strlen(s+1));
        for(LL i=1;i<=n;++i){
            if(s[i]=='L') a[i]=1;
            if(s[i]=='R') a[i]=2;
            if(s[i]=='U') a[i]=3;
            if(s[i]=='D') a[i]=4;
        }
        memset(sum,0,sizeof(sum));
        for(LL i=1;i<=n;++i) sum[a[i]]++;
        sum[1]=sum[2]=std::min(sum[1],sum[2]); sum[3]=sum[4]=std::min(sum[3],sum[4]);
        if(!sum[1] || !sum[3]){
            if(!sum[1] && !sum[3]) printf("0\n");
            else if(sum[1]) printf("2\nRL\n");
            else printf("2\nUD\n");
        }
        else{
            printf("%d\n",sum[1]*2+sum[3]*2);
            for(LL i=1;i<=sum[1];++i) printf("R");
            for(LL i=1;i<=sum[3];++i) printf("U");
            for(LL i=1;i<=sum[1];++i) printf("L");
            for(LL i=1;i<=sum[3];++i) printf("D");
            puts("");
        }
    }
    return 0;
}

C

把每个极大的区间提出来做

#include<bits/stdc++.h>
typedef long long LL;
#define pb push_back
const LL maxn=3e6+9,inf=0x3f3f3f3f;
LL Read(){
    LL x(0),f(1); char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-') f=-1; c=getchar(); 
    }
    while(c>='0' && c<='9'){
        x=(x<<3ll)+(x<<1ll)+c-'0'; c=getchar();
    }return x*f;
}
LL n,m;
LL a[maxn];
char s[maxn];
int main(){
    n=Read(); m=Read();  //puts("1");
    scanf(" %s",s+1); //puts("-33");
    for(LL i=1;i<=m;++i){
        char c; scanf(" %c",&c); a[c-'a']=1;
    }
    LL pre(0);
    LL ans(0);
    for(LL i=1;i<=n;++i){
        LL x(s[i]-'a');
        if(a[x]){
            
        }else{
            LL L(pre+1),R(i-1);
            if(L<=R){
                ans+=(R-L+1+1)*(R-L+1)/2;
            }
            pre=i;
        }
    }
    LL L(pre+1);
    if(L<=n) ans+=(n-L+1+1)*(n-L+1)/2;
    printf("%lld\n",ans);
    return 0;
}

D

考虑前缀的极大匹配跟后缀的极大匹配，然后不删除，枚举每个删除点即可

#include<bits/stdc++.h>
typedef int LL;
#define pb push_back
const LL maxn=3e6+9,inf=0x3f3f3f3f;
LL Read(){
    LL x(0),f(1); char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-') f=-1; c=getchar(); 
    }
    while(c>='0' && c<='9'){
        x=(x<<3ll)+(x<<1ll)+c-'0'; c=getchar();
    }return x*f;
}
LL n,ans;
LL a[maxn],f1[maxn],f2[maxn];
int main(){
    n=Read();
    for(LL i=1;i<=n;++i) a[i]=Read();
    for(LL i=1;i<=n;++i){
        if(a[i-1]<a[i]) f1[i]=f1[i-1]+1;
        else f1[i]=1;
    }
    a[n+1]=inf;
    for(LL i=n;i>=1;--i){
        if(a[i+1]>a[i]) f2[i]=f2[i+1]+1;
        else f2[i]=1;
    }
    for(LL i=1;i<=n;++i){
        ans=std::max(ans,f1[i]+f2[i]-1);
    }
    for(LL i=1;i<=n;++i){
        if(a[i-1]<a[i+1]) ans=std::max(ans,f1[i-1]+f2[i+1]);
    }
    printf("%d\n",ans);
    return 0;
}

E

设f[i][0/1]表示i走到偶/奇的最小步数
对于一个点u，可走到合法的v（我们默认u可走到自己），\(f[u][j]=min\{f[v][j]+(v!=u)\}\)
发现这样会构成环
考虑最终节点会是f[i][a[i]&1]这样的点，反向建边，多源最短路即可

#include<bits/stdc++.h>
typedef int LL;
#define pb push_back
const LL maxn=1e6+9,inf=0x3f3f3f3f;
LL Read(){
    LL x(0),f(1); char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-') f=-1; c=getchar(); 
    }
    while(c>='0' && c<='9'){
        x=(x<<3ll)+(x<<1ll)+c-'0'; c=getchar();
    }return x*f;
}
LL n;
LL f[maxn][2],pos[maxn][2],a[maxn],visit[maxn][2];
struct edge{
    LL to,nxt;
}dis[maxn];
LL num;
LL head[maxn];
LL Check(LL x){ return x>=1 && x<=n; }
void Add(LL u,LL v){
    dis[++num]=(edge){v,head[u]}; head[u]=num;
}
struct node{
    LL u,op;
};
std::queue<node> que;
void Solve(){
    while(que.size()){
        LL u(que.front().u),op(que.front().op); que.pop();
        for(LL i=head[u];i;i=dis[i].nxt){
            LL v(dis[i].to); if(!visit[v][op]){
                visit[v][op]=1; f[v][op]=f[u][op]+1; que.push((node){v,op});
            }
        }
    }
}
int main(){
    n=Read();
    for(LL i=1;i<=n;++i) a[i]=Read();
    for(LL i=1;i<=n;++i){
        pos[i][0]=2*(i-1); pos[i][1]=2*(i-1)+1;
        if(Check(i-a[i])) Add(i-a[i],i);
        if(Check(i+a[i])) Add(i+a[i],i);
    }
    
    for(LL i=1;i<=n;++i){
        f[i][0]=f[i][1]=-1;
        que.push((node){i,a[i]&1});
        visit[i][a[i]&1]=1; f[i][a[i]&1]=0;
    }
    Solve();
    for(LL i=1;i<=n;++i) //if(a[i]&1) 
        printf("%d ",f[i][1^(a[i]&1)]);
    return 0;
}

F

考虑一个暴力的东西f[i][j][k][l]表示构造了i长度，s匹配到j，t匹配到k，构造的串前缀和为l是否可行
\(O(800*200*200*400)\)

对于\((j,k,l)\)实际上仅有一个i是有效的

设\(f[j][k][l]\)表示s匹配到j，t匹配到k，前缀和为l，最小的i为多少

#include<bits/stdc++.h>
typedef int LL;
#define pb push_back
const LL maxn=1e6+9,inf=0x3f3f3f3f;
LL Read(){
    LL x(0),f(1); char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-') f=-1; c=getchar(); 
    }
    while(c>='0' && c<='9'){
        x=(x<<3ll)+(x<<1ll)+c-'0'; c=getchar();
    }return x*f;
}
LL n,m;
char s1[maxn],s2[maxn];
struct Heap{
    LL x,y,z;
};
struct Pre{
    LL x,y,z; char c;
}pre[201][201][401];
LL visit[201][201][401];
std::queue<Heap> que;
void Prin(LL x,LL y,LL z){
    if(!x && !y && !z) return;
    Pre Tmp(pre[x][y][z]);
    Prin(Tmp.x,Tmp.y,Tmp.z); printf("%c",Tmp.c);
}
void Solve(){
    while(que.size()){
        Heap Tmp(que.front()); que.pop();
        LL x0(Tmp.x),y0(Tmp.y),z0(Tmp.z);
        if(z0==400) continue;
        if(x0==n && y0==m && z0==0){
            Prin(x0,y0,z0);
            return;
        }
        LL x(x0),y(y0),z(z0);
        if(!z){
            if(x<n){
                if(s1[x+1]=='(') ++x;
            }
            if(y<m){
                if(s2[y+1]=='(') ++y;
            }
            if(!visit[x][y][z+1]){
                pre[x][y][z+1]=(Pre){x0,y0,z,'('}; visit[x][y][z+1]=1; que.push((Heap){x,y,z+1});
            }
        }else{
            if(x<n){
                if(s1[x+1]=='(') ++x;
            }
            if(y<m){
                if(s2[y+1]=='(') ++y;
            }
            if(!visit[x][y][z+1]){
                pre[x][y][z+1]=(Pre){x0,y0,z,'('}; visit[x][y][z+1]=1; que.push((Heap){x,y,z+1});
            }
            x=x0; y=y0; 
            if(x<n){
                if(s1[x+1]==')') ++x;
            }
            if(y<m){
                if(s2[y+1]==')') ++y;
            }
            if(!visit[x][y][z-1]){
                pre[x][y][z-1]=(Pre){x0,y0,z,')'}; visit[x][y][z-1]=1; que.push((Heap){x,y,z-1});
            }
        }
    }
}
int main(){
    scanf(" %s",s1+1); scanf(" %s",s2+1);
    n=strlen(s1+1); m=strlen(s2+1);
    que.push((Heap){0,0,0}); visit[0][0][0]=1;
    Solve();
    return 0;
}

Codeforces Round #605 (Div. 3) 题解

原文：https://www.cnblogs.com/y2823774827y/p/12033914.html