XCPC Notes

Appearance

发布时间：2025-04-01

题目链接

L.网络预选赛 ​

在这里插入图片描述 签到

cpp
char a[510][510];
void solve(){ 
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    int ans=0;
    for(int i=1;i<n;i++){
        for(int j=1;j<m;j++){
            if(a[i][j]=='c'&&a[i][j+1]=='c'&&a[i+1][j]=='p'&&a[i+1][j+1]=='c'){
                ans++;
            }
        }
    }
    cout<<ans<<"\n";
}

K.取石子游戏 ​

在这里插入图片描述

  • lowbit(n)≤klowbit(n) \leq k先手取掉lowbit(n)lowbit(n)，则后面跟着后手取就行，先手必胜
  • 否则随便取一个数都会变成情况一，先手必败

B.军训 ​

在这里插入图片描述

  • 很容易想到是排序好的数组
  • 然后相同值的任意排
  • 升序降序都可，要乘2，特殊考虑所有数相同
cpp
void solve(){ 
    int n;
    cin>>n;
    vector<int> a(n+1),fac(n+1,1);
    for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
    map<int,int> cnt;
    for(int i=1;i<=n;i++)cin>>a[i],cnt[a[i]]++;
    sort(a.begin()+1,a.end());
    int ans=1,res=0;
    for(auto [x,y]:cnt)ans=ans*fac[y]%mod;
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            res+=a[j]-a[i];
        }
    }
    cout<<res<<" "<<ans*(cnt.size()==1?1:2)%mod<<"\n";
}

D.编码器-解码器 ​

在这里插入图片描述

  • 定义dpl,rdp_{l,r}为当前字符串能构成T[l,r]T[l,r]的方案
  • 迭代一次,分类讨论
    • 不使用中间的元素
      • 继承左右两边有ndpl,r+=2dpl,rndp_{l,r} += 2dp_{l,r}
      • 左右两边分别贡献一部分ndpl,r+=∑dpl,k⋅dpk+1,rndp_{l,r}+=\sum dp_{l,k}\cdot dp_{k+1,r}
    • 使用中间的元素,si=tjs_i=t_j
      • 那么更新以j−1j-1为右端点的部分，以j+1j+1为左端点的部分
      • 以j−1j-1为右端点和以j+1j+1为左端合并
cpp
void solve(){ 
    string s,t;
    cin>>s>>t;
    int n=s.size(),m=t.size();
    s=" "+s,t=" "+t;
    vector dp(m+1,vector<int>(m+1,0));
    for(int i=1;i<=n;i++){
        auto ndp=dp;
        for(int l=1;l<=m;l++){
            for(int r=l;r<=m;r++){
                ndp[l][r]=ndp[l][r]*2%mod;
            }
        }
        for(int len=2;len<=m;len++){
            for(int l=1;l<=m-len+1;l++){
                int r=l+len-1;
                for(int k=l;k<r;k++)ndp[l][r]=(ndp[l][r]+dp[l][k]*dp[k+1][r]%mod)%mod;
            }
        }
        for(int j=1;j<=m;j++){
            if(s[i]!=t[j])continue;
            ndp[j][j]=(ndp[j][j]+1)%mod;
            for(int l=1;l<j;l++)ndp[l][j]=(ndp[l][j]+dp[l][j-1])%mod;
            for(int r=j+1;r<=m;r++)ndp[j][r]=(ndp[j][r]+dp[j+1][r])%mod;
            for(int l=1;l<j;l++){
                for(int r=j+1;r<=m;r++){
                    ndp[l][r]=(ndp[l][r]+dp[l][j-1]*dp[j+1][r]%mod)%mod;
                }
            }
        }
        swap(dp,ndp);
    }
    cout<<dp[1][m]<<"\n";
}

E.随机过程 ​

在这里插入图片描述

  • 对于第ii层的点，他们出现概率相同为126i\frac{1}{26^i}
  • nn个字符串都没出现该节点的概率为(1−126i)n(1-\frac{1}{26^i})^n，出现的概率为(1−(1−126i)n)(1-(1-\frac{1}{26^i})^n)
  • 因此期望节点为(1−(1−126i)n)⋅26i(1-(1-\frac{1}{26^i})^n) \cdot 26^i
cpp
int qpow(int a,int b){
    a%=mod;
    int ans=1;
    for(;b;b>>=1){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
    }
    return ans;
}
void solve(){ 
    int n,m;
    cin>>n>>m;
    int pw=1,ans=1,res=1;
    for(int i=1;i<=m;i++){
        pw=pw*26%mod;
        if(pw<=n)ans=(ans+pw)%mod;
        else{
            ans=(ans+(m-i+1)*n%mod)%mod;
            break;
        }    
    }
    pw=1;
    for(int i=1;i<=m;i++){
        pw=pw*26%mod;
        res+=(1-qpow(1-qpow(pw,mod-2)+mod,n)+mod)%mod*pw%mod;
        res%=mod;
    }
    cout<<ans<<' '<<res<<'\n';
}

J.找最小 ​

在这里插入图片描述

  • 考虑求出异或和，那么交换两个数相当于同时对异或和异或上ci=ai⊕bic_i=a_i \oplus b_i
  • 那么转变成一共有nn个值，选出若干个与x,yx,y异或，最小化max⁡(x,y)\max(x,y)
  • 考虑使用线性基，从高到低按位考虑
  • xi=0,yi=0x_i=0,y_i=0直接跳过
  • xi=1,yi=1x_i=1,y_i=1如果当前线性基有数异或上，否则不变
  • 一个1一个0的情况，假设xi=1,yi=0,x>yx_i=1,y_i=0,x \gt y那么异或上肯定更优，否则不用管
cpp
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define TR tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
typedef pair<int,int> PII;
const int N=5e5+10,M=2e5+10;
// const int INF=1e18;
// const int mod=998244353;
// const int mod=1e9+7;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int qpow(int a,int b,int mod){
    int ans=1;
    for(;b;b>>=1){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
    }
    return ans;
}
struct LinearBasis{
    vector<int> d;
    int fail,mxb;
    static constexpr int SIZE=32;
    vector<int> nums;
    LinearBasis(){
        init();
    }
    void init(){
        d.assign(SIZE,0);
        fail=mxb=0;
        nums.clear();
    }
    bool insert(int x){
        for(int i=SIZE-1;i>=0;i--){
            if(!(x>>i&1))continue;
            mxb=max(mxb,i);
            if(d[i])x^=d[i];
            else{
                d[i]=x;
                return true;
            }
        }
        fail++;
        return false;
    }
    int query_max(int res=0){
        for(int i=SIZE-1;i>=0;i--){
            res=max(res,res^d[i]);
        }
        return res;
    }
    int query_min(int res=0){
        if(!res)return fail?0:*min_element(d.begin(),d.begin()+mxb+1);
        for(int i=SIZE-1;i>=0;i--){
            res=min(res,res^d[i]);
        }
        return res;
    }
} lb;
int dfs(int i,int x,int y){
    if(i==-1)return max(x,y);
    int l=x>>i&1,r=y>>i&1;
    if(!lb.d[i]||(l==0&&r==0))return dfs(i-1,x,y);
    if(l==1&&r==1)return dfs(i-1,x^lb.d[i],y^lb.d[i]);
    if((l==1&&r==0&&x>y)||(l==0&&r==1&&x<y))return dfs(i-1,x^lb.d[i],y^lb.d[i]);
    return dfs(i-1,x,y);
}
void solve(){ 
    lb.init();
    int n;
    cin>>n;
    int x=0,y=0;
    vector<int> a(n+1),b(n+1);
    for(int i=1;i<=n;i++)cin>>a[i],x^=a[i];
    for(int i=1;i<=n;i++)cin>>b[i],y^=b[i],lb.insert(a[i]^b[i]);
    cout<<dfs(31,x,y)<<"\n";
}   
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    cin>>T;
    while(T--)solve();
    return 0;
}

G.疯狂星期六 ​

在这里插入图片描述

  • 首先计算出yyq的最大花费，然后限制其他人的花费都比它小
  • 跑最大流，当能把菜品全部支付完，达到满流，是合法方案否则NO
  • 不需要判断yyq流出的边是否满流，因为当合法时，必定可以减少其他人对菜品的流量，增加yyq的流量
cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=3010,M=1e5+10;
const int INF=1e18;
const int mod=998244353;
// const int mod=1e9+7;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int n,m,S,T;//S为源点,T为汇点
int e[M],h[N],ne[M],idx;//链式前向星
int f[M],d[N],cur[N];//f存流量，d存层数，cur为弧优化，表示当前从哪条节点开始搜
void add(int a,int b,int c){
    e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;//反向流量初始为0
}   
bool bfs(){
    queue<int> q;
    memset(d,-1,sizeof d);
    q.push(S);
    d[S]=0,cur[S]=h[S];
    while(!q.empty()){
        auto u=q.front();
        q.pop();
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(d[v]==-1&&f[i]){
                d[v]=d[u]+1;
                cur[v]=h[v];//一开始所有边都可以搜
                if(v==T)return true;
                q.push(v);
            }
        }
    }
    return false;
}
int find(int u,int limit){//深搜，limit表示从源点流向u的最多能流的流，flow表示已经流向汇点多少流
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i]){//flow<limit优化很重要，否则易tle
        int v=e[i];
        cur[u]=i;//弧优化更新
        if(d[v]==d[u]+1&&f[i]){
            int t=find(v,min(f[i],limit-flow));
            if(!t)d[v]=-1;//如果到达不了T,标记下次就不会走到
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }   
    return flow;
}
int dinic(){
    int r=0,flow;
    while(bfs())
        while(flow=find(S,INF))r+=flow;
    return r;
}
void solve(){
	int n,m;
	cin>>n>>m;
	vector<int> a(n+1),V(n+1);
	for(int i=1;i<=n;i++)cin>>a[i]>>V[i];
	vector<array<int,3>> W(m+1);
	int all=V[1];
	int sum=0;
	memset(h,-1,sizeof h);
	for(int i=1;i<=m;i++){
		cin>>W[i][0]>>W[i][1]>>W[i][2];
		if(W[i][0]>W[i][1])swap(W[i][0],W[i][1]);
		if(W[i][0]==1)all+=W[i][2];
		sum+=W[i][2];
	}
	all=min(all,a[1]);
	S=0,T=n+m+1;
	add(S,1,all-V[1]);
	for(int i=2;i<=n;i++){
		int x=min(all-1,a[i])-V[i];
		if(x<0){
			cout<<"NO\n";
			return;
		}
		add(S,i,min(all-1,a[i])-V[i]);
	}
	for(int i=1;i<=m;i++){
		add(n+i,T,W[i][2]);
		add(W[i][0],n+i,INF);
		if(W[i][1]!=W[i][0])add(W[i][1],n+i,INF);
	}
	cout<<(dinic()==sum?"YES\n":"NO\n");
}   
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    // cin>>T;
    while(T--)solve();
    return 0;
}

I.找行李 ​

在这里插入图片描述

  • 如果第ii个人选了jj行李，后面的人再选前面的行李没有意义
  • 容斥，考虑分别计算最终答案大于等于ii的方案，那么i+1i+1能选的集合ii也能选
  • 定义dpj,kdp_{j,k}表示考虑了前jj个人，剩余kk个行李的方案，答案很容易转移，特殊地没有人选行李的方案不能统计进去
cpp
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define TR tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
typedef pair<int,int> PII;
const int N=1e5+10,M=2e5+10;
const int INF=1e18;
const int mod=998244353;
// const int mod=1e9+7;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int a[510],b[510],ans[510];
void solve(){ 
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++)cin>>b[i];
    sort(a+1,a+n+1);
    sort(b+1,b+m+1);
    for(int i=0;i<=500;i++){
        vector dp(n+1,vector<int>(m+1,0));
        dp[0][0]=1;
        for(int j=1;j<=n;j++){
            int d=upper_bound(a+1,a+n+1,b[j]-i)-a-1;
            int ld;
            if(j==1)ld=0;
            else ld=upper_bound(a+1,a+n+1,b[j-1]-i)-a-1;
            // cout<<i<<" "<<j<<" "<<d<<"\n";
            for(int k=0;k<=ld;k++){
                int x=ld-k;
                // cout<<"j="<<j<<" k="<<k<<" x="<<x<<" d="<<d<<" val="<<dp[j-1][k]<<"\n";
                if(d-x>=0)dp[j][d-x]=(dp[j][d-x]+dp[j-1][k])%mod;
                if(d-x-1>=0)dp[j][d-x-1]=(dp[j][d-x-1]+dp[j-1][k]*(d-x))%mod;
            }
        }
        // cout<<dp[2][1]<<"\n";
        int d=upper_bound(a+1,a+n+1,b[m]-i)-a-1;
        for(int j=0;j<=d-1;j++){
            ans[i]=(ans[i]+dp[n][j])%mod;
        }
    }
    int res=0;
    for(int i=0;i<=500;i++){
        // cout<<ans[i]<<"\n";
        if(i+1<=500)ans[i]-=ans[i+1];
        res=(res+ans[i]*i)%mod;
    }
    cout<<res<<"\n";
}

C.种树 ​

在这里插入图片描述

  • 每次可以选择两个点染色，因此考虑尽可能多地选择两个未涂的点
  • 发现顺序并不重要
  • 对于一个点，需要考虑的只有儿子未涂记为cnt1cnt_1，儿子的儿子未涂记为cnt2cnt_2
  • 假设当前节点已经涂了或者cnt2>0cnt_2 \gt 0，那么答案即为cnt2+cnt12cnt_2+\frac{cnt_1}{2}，此时节点必定已涂，如果剩一个儿子，那么向上传递2，否则为0
  • 否则，如果cnt1=0cnt_1=0,向上传递0
  • 否则只剩下儿子和当前节点，那么如果未涂儿子是奇数，则可以刚好匹配完，否则剩一个当前节点，向上传递1
  • 因为都是小于等于两个的未涂互相匹配，那么肯定会有与其他已涂的相交，保证了答案的合法性
cpp
void solve(){
    int n,k;
    cin>>n>>k;
    vector<int> have(n+1);
    for(int i=1;i<=k;i++){
        int x;
        cin>>x;
        have[x]++;
    }
    vector<int> adj[n+1];
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    if(n==k){
        cout<<"0\n";
        return;
    }
    int ans=0;
    function<int(int,int)> dfs=[&](int u,int fa){
        vector<int> cnt(3);
        for(auto v:adj[u]){
            if(v==fa)continue;
            cnt[dfs(v,u)]++;
        }
        if(have[u]||cnt[2]){
            ans+=cnt[2]+cnt[1]/2;
            if(cnt[1]%2)return 2;
            return 0;
        }
        if(cnt[1]==0)return 1;
        ans+=(cnt[1]+1)/2;
        if((cnt[1]+1)%2)return 1;
        return 0;
    };
    if(dfs(1,0)!=0)ans++;
    cout<<ans<<"\n";
}

Wenwei Lin · 2022 — 2025