Exawizards Programming Contest 2021（AtCoder Beginner Contest 222） A~E 题解

2023-12-26 15:58:15

Exawizards Programming Contest 2021（AtCoder Beginner Contest 222）

A - Four Digits

水题

B - Failing Grade

水题

C - Swiss-System Tournament

题意：有\(2n\)个玩家，玩\(m\)轮石头剪刀布，每一轮都由两两不同的玩家进行，按照总积分的顺序进行，如果两个玩家积分相同，则序号小的排在上面，问最后的排名情况。
题解：数据范围很小，直接暴力模拟，用pair存权值和下表，每过一轮排个序即可。

代码：

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
#define pb push_back
const int N= 1e6+10;
const int mod=1e9+7;
const int INF= 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}

int n,m;
char s[500][500];

int main(){
    scanf("%d %d",&n,&m);

    for(int i=1;i<=2*n;++i){
        getchar();
        for(int j=1;j<=m;++j){
            scanf("%c",&s[i][j]);
        }
    }
    vector<int> v;
    vector<PII> tmp;
    unordered_map<int,int> mp;
    for(int i=1;i<=2*n;++i) v.push_back(i);

    for(int i=1;i<=m;++i){
        for(int j=0;j<2*n;j+=2){
            int num1=v[j];
            int num2=v[j+1];
            char c1=s[num1][i];
            char c2=s[num2][i];
            if(c1==c2){
                continue; 
            }
            if(c1=='G'){
                if(c2=='C'){
                    mp[num1]++;
                }
                else mp[num2]++;
            }
            else if(c1=='C'){
                if(c2=='P') mp[num1]++;
                else mp[num2]++;
            }
            else if(c1=='P'){
                if(c2=='G') mp[num1]++;
                else mp[num2]++;
            }
        }
        for(int j=1;j<=2*n;++j){
            tmp.pb({mp[j],j});
        }
        if(i==m) break;
            sort(tmp.begin(),tmp.end(),[&](PII a,PII b){
        if(a.fi!=b.fi) return a.fi>b.fi;
        return a.se<b.se;
    });
        v.clear();
        for(int j=0;j<2*n;++j){
            v.pb(tmp[j].se);
        }
        tmp.clear();
    }
    sort(tmp.begin(),tmp.end(),[&](PII a,PII b){
        if(a.fi!=b.fi) return a.fi>b.fi;
        return a.se<b.se;
    });
    for(int i=0;i<2*n;++i) printf("%d\n",tmp[i].se);
    return 0;
}

D - Between Two Arrays

题意：有两个长度为\(n\)的非降序列\(A\)和\(B\)，你需要构造一个新的非降序列\(C\)，使得\(A_i\le C_i\le B_i\)，问能构造多少\(C\)，对\(998244353\)取模。
题解：设\(dp[i][j]\)表示取前\(i\)个数，序列最后一个数字为\(j\)的最多方案数，那么不难写出状态转移方程：\(dp[i][j]=dp[i][j-1]+dp[i-1][j]\)，这里注意每个位置转移完后，还要将比\(B_i\)大的数的状态更新成\(dp[i][B_i]\)，防止后面转移的时候取到没更新的状态，也就是取\(0\)的情况。

代码：

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N= 1e6+10;
const int mod=998244353;
const int INF= 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}

int n;
int a[N],b[N];
int dp[3050][3050];

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;++i){
        scanf("%d",&b[i]);
    }
    for(int i=0;i<=3010;++i) dp[0][i]=1;
    for(int i=1;i<=n;++i){
        for(int j=a[i];j<=b[i];++j){
            dp[i][j]=(dp[i][j-1]+dp[i-1][j])%mod;
        }
        for(int j=b[i];j<=3010;++j) dp[i][j]=dp[i][b[i]];
    } 
    printf("%d",dp[n][b[n]]);
    return 0;
}

E - Red and Blue Tree

题意：一颗\(N\)个结点的树，给你\(M\)个点，你可以将每条边染成蓝色或红色，使得这\(M\)个点相邻两个点的简单路径经过的单边是红色的次数减去蓝色的次数刚好为\(K\).问你有多少种染色方案.
题解：不难发现，这些简单路径跑的单边我们是可以确定的，先找到这些单边出现的总次数\(sum\)，假设有\(x\)条边染成红色，那么有\(sum-x\)边染成蓝色，\(x-(sum-x)=k\)，得到\(x=\frac{sum-k}{2}\)，所以先判断正负和是否能整除，如果合法，那么每条边都有出现的次数，红色一共出现\(x\)次，简单路径没有经过的边的数量为\(rest\)，经典的01背包求方案数，答案就为\(dp[x]*2^{rest}\).

代码：

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
#define pb push_back
const int N= 1e6+10;
const int mod=998244353;
const int INF= 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}


int n,m,k;
int a[N];
vector<int> edge[N];
map<PII,int> mp,all;
ll sum=0;
int dp[N];
vector<int> v;

int fpow(int a,int k){
    int res=1;
    while(k){
        if(k&1) res=1ll*res*a%mod;
        k>>=1;
        a=1ll*a*a%mod;
    }
    return res;
}

void dfs(int u,int fa,int ed){
    v.pb(u);
    if(u==ed){
        for(int i=0;i<(int)v.size()-1;++i){
            mp[{min(v[i],v[i+1]),max(v[i],v[i+1])}]++;
            sum++;
        }
        v.pop_back();
        return;
    }
    for(auto to:edge[u]){
        if(to==fa || u==to) continue;
        dfs(to,u,ed);
    }
    v.pop_back();
}

int main(){
    scanf("%d %d %d",&n,&m,&k);
    for(int i=1;i<=m;++i){
        scanf("%d",&a[i]);
    }
    
    for(int i=1;i<n;++i){
        int u,v;
        scanf("%d %d",&u,&v);
        edge[v].pb(u),edge[u].pb(v);
    }

    for(int i=1;i<m;++i){
        v.clear();
        dfs(a[i],-1,a[i+1]); 
    }
    if(sum<k || (sum-k)%2) puts("0");
    else{
        int x=(sum-k)/2;
        dp[0]=1;
        int rest=n-1-(int)mp.size();
        for(auto w:mp){
            if(!w.se) continue;
            for(int i=x;i>=w.se;--i){
                dp[i]=(dp[i]+dp[i-w.se])%mod;
            }
        }
        printf("%lld\n",(1ll*dp[x]*(fpow(2,rest)+mod)%mod)%mod);
    }
    return 0;
}

码农公寓

Exawizards Programming Contest 2021（AtCoder Beginner Contest 222）

A - Four Digits

B - Failing Grade

C - Swiss-System Tournament

D - Between Two Arrays

E - Red and Blue Tree

相关文章