XCPC Notes

Appearance

发布时间：2025-04-28

题目链接

A. 盒子(签到) ​

在这里插入图片描述

cpp
int z0,h,u0,v0,u1,v1;
bool check(int x,int y,int z){
    return x>=min(u0,u1)&&x<=max(u0,u1)&&y>=min(v0,v1)&&y<=max(v0,v1)&&z>=z0&&z<=z0+h;
}
void solve(){
    cin>>z0>>h>>u0>>v0>>u1>>v1;
    int q;
    cin>>q;
    while(q--){
        int x,y,z;
        cin>>x>>y>>z;
        cout<<(check(x,y,z)?"YES\n":"NO\n");
    }
}

C. CCPC(签到) ​

在这里插入图片描述

cpp
void solve(){
    string s;
    cin>>s;
    int c=0,p=0;
    for(auto it:s)c+=it=='C',p+=it=='P';
    if(c<3||p<1){
        cout<<"0\n";
        return;
    }
    c-=3,p-=1;
    int ans=1;
    while(1){
        if(c>=2&&p>=1){
            c-=2;
            p--;
            ans++;
        }
        else break;
    }
    cout<<ans<<"\n";
}

H. 平方根(签到) ​

在这里插入图片描述

  • 尽可能地划分出独立的11，奇数很好处理，偶数划分到剩下两个连续11
cpp
void solve(){
    string s;
    cin>>s;
    int a=0,b=0;
    for(int i=0,j;i<s.size();i++){
        if(s[i]=='0')continue;
        j=i;
        while(j+1<s.size()&&s[j+1]==s[j])j++;
        int len=j-i+1;
        if(len%2)a+=(len+1)/2;
        else a+=len/2-1,b++;
        i=j;
    }
    double ans=sqrt(2)*b+a;
    cout<<setprecision(10)<<fixed<<ans<<"\n";
}

M. 覆盖一棵树(签到，贪心) ​

在这里插入图片描述 对于每个节点，选取深度最小的往上传即可

cpp
void solve(){
    int n;
    cin>>n;
    vector<int> adj[n+1];
    for(int i=2;i<=n;i++){
        int x;
        cin>>x;
        adj[x].push_back(i);
    }
    int ans=0;
    function<int(int)> dfs=[&](int u){
        vector<int> tmp;
        for(auto v:adj[u]){
            tmp.push_back(dfs(v)+1);
        }
        sort(tmp.begin(),tmp.end());
        for(int i=1;i<tmp.size();i++)ans=max(ans,tmp[i]);
        return tmp.size()?tmp[0]:0;
    };
    ans=max(ans,dfs(1));
    cout<<ans<<"\n";
}

L. 拼图(二分) ​

在这里插入图片描述 枚举BB，二分CC的最大值，统计答案

cpp
void solve(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    if(a<4){
        cout<<"0\n";
        return;
    }
    int ans=0;
    for(int i=0;i<=min(b,c);i++){
        int l=0,r=min(b,c)-i;
        while(l<r){
            int mid=l+r>>1;
            if(i*mid>d)r=mid;
            else l=mid+1;
        }
        if(i*l>d)l--;
        ans=max(ans,(i+2)*(l+2));
    }
    cout<<ans<<"\n";
}

G. 递增序列(数位dp) ​

在这里插入图片描述

  • 首先肯定按位考虑
  • 定义bi,jb_{i,j}为第ii个数的第jj位，只考虑相邻两个数的不同的最高位
  • 如果bi,j=0,bi+1,j=1b_{i,j}=0,b_{i+1,j}=1，那么这一位必须选00,否则必须选11
  • 把所有位的选取情况列出来，如果有矛盾直接输出00
  • 否则就是有一些位固定，其他未知，求小于等于kk的合法数
  • 这就是典型的数位dp
cpp
void solve(){
    int n,k;
    cin>>n>>k;
    vector<int> a(n+1),bit(65,-1);
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<n;i++){
        for(int j=61;j>=0;j--){
            if((a[i]>>j&1)==(a[i+1]>>j&1))continue;
            int g;
            if((a[i]>>j&1)==0)g=0;
            else g=1;
            if(bit[j]==-1)bit[j]=g;
            else if(bit[j]!=g){
                cout<<"0\n";
                return;
            }
            break;
        }
    }
    vector<int> f(65,-1);
    function<int(int,bool)> dfs=[&](int pos,bool limit){
        if(pos==-1)return 1ll;
        if(!limit&&~f[pos])return f[pos];
        int ans=0;
        int up=limit?(k>>pos&1):1;
        if(bit[pos]==-1){
            for(int i=0;i<=up;i++){
                ans+=dfs(pos-1,limit&&i==up);
            }
        }
        else if(bit[pos]<=up)ans+=dfs(pos-1,limit&&bit[pos]==up);
        if(!limit)f[pos]=ans;
        return ans;
    };
    cout<<dfs(61,1)<<"\n";
}

E. 重心树(诈骗，并查集) ​

在这里插入图片描述

  • 因为父亲节点小于儿子节点编号，因此树的形态实际上是确定的
  • 用并查集从nn到11枚举合并，注意并查集中小的编号是大的编号父亲
cpp
struct DSU {
    std::vector<int> f, siz;
    
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }
    
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
};
void solve(){
    int n;
    cin>>n;
    vector<int> c[n+1];
    for(int i=1;i<=n;i++){
        int m;
        cin>>m;
        for(int j=1;j<=m;j++){
            int x;
            cin>>x;
            c[i].push_back(x);
        }
    }
    DSU dsu(n+1);
    vector<PII> edge;
    for(int i=n;i>=1;i--){
        for(auto x:c[i]){
            if(dsu.same(x,i))continue;
            int fx=dsu.find(x),fi=dsu.find(i);
            if(fx>fi)swap(fx,fi);
            dsu.merge(fx,fi);
            edge.emplace_back(fx,fi);
        }
    }
    for(auto [x,y]:edge)cout<<x<<" "<<y<<"\n";
}

F. 平方数(数学) ​

在这里插入图片描述

  • 很明显可以按每个质因数考虑贡献
  • 对于每个质因数，定义fi,0/1f_{i,0/1}表示考虑到第ii个数，质因数的个数为奇数还是偶数的和
  • 那么答案就是∏fp,0\prod f_{p,0}
  • 复杂度O(nlog⁡n)O(n \log n)
cpp
vector<int> prime[N];
void init(){
    for(int i=2;i<=1e6;i++){
        if(prime[i].size())continue;
        for(int j=i;j<=1e6;j+=i)prime[j].push_back(i);
    }
}
void solve(){
    init();
    int n;
    cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    set<int> p;
    map<int,vector<int>> mp;
    for(int i=1;i<=n;i++){
        for(auto &it:prime[a[i]]){
            int cnt=0;
            while(a[i]%it==0)a[i]/=it,cnt++;
            mp[it].push_back(cnt);
        }
    }
    vector<vector<int>> f(2,vector<int>(2,0));
    vector<int> pw(60);
    int ans=1;
    for(auto &[P,v]:mp){
        f.assign(2,vector<int>(2,0));
        f[1][0]=1;
        pw[0]=1;
        for(int i=1;i<=35;i++)pw[i]=pw[i-1]*P%mod;
        for(int i=0;i<v.size();i++){
            f[i&1][0]=f[i&1][1]=0;
            int cnt=v[i];
            for(int j=0;j<=cnt;j++){
                if(j%2==0){
                    (f[i&1][1]+=f[i-1&1][1]*pw[j/2]%mod)%=mod;
                    (f[i&1][0]+=f[i-1&1][0]*pw[j/2]%mod)%=mod;
                }
                else{
                    (f[i&1][0]+=f[i-1&1][1]*pw[(j+1)/2]%mod)%=mod;
                    (f[i&1][1]+=f[i-1&1][0]*pw[j/2]%mod)%=mod;
                }
            }
        }
        ans=ans*f[(v.size()-1)&1][0]%mod;
    }
    cout<<ans<<"\n";
}

B. Aho-Corasick 自动机(dp) ​

在这里插入图片描述 求 n 个点字符集大小为 m 深度不超过 d （根的深度为 0）的 AC 自动机数量。 数据范围：1 ≤ n, m, d ≤ 100

  • 实际上是求trie的数量
  • 可以分层dp，定义fi,j,kf_{i,j,k}表示考虑前ii层，选了jj个点，第ii层选了kk个点的方案
  • 定义gk,tg_{k,t}表示上一层为kk个点，下一层tt个点的方案，则fi,j+t,t+=fi,j,k⋅gk,tf_{i,j+t,t}+=f_{i,j,k}\cdot g_{k,t}
  • 对于gg数组可以背包解决
  • 复杂度O(n4)O(n^4)
cpp
int f[110][110][110],g[110][110],C[110][110];
void init(){
    for(int i=0;i<=100;i++){
        C[i][0]=C[i][i]=1;
        for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    }
}
void solve(){
    init();
    int n,m,d;
    cin>>n>>m>>d;
    g[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            for(int k=n;k>=j;k--)(g[i][k]+=C[m][j]*g[i-1][k-j]%mod)%=mod;
        }
    }
    f[0][1][1]=1;
    for(int i=0;i<d;i++){
        for(int j=1;j<=n;j++){
            for(int k=0;k<=j;k++){
                for(int t=1;t<=n-j;t++){
                    (f[i+1][j+t][t]+=g[k][t]*f[i][j][k]%mod)%=mod;
                }
            }
        }
    }
    int ans=0;
    for(int i=0;i<=d;i++){
        for(int j=0;j<=n;j++){
            ans+=f[i][n][j],ans%=mod;
        }
    }
    cout<<ans<<"\n";
}

D. 优秀的拆分(LIS计数) ​

在这里插入图片描述

  • 答案是LIS+LDSLIS+LDS或者LIS+LDS−1LIS+LDS-1
  • 是否减11只需看是否有叫交点
  • 计算fif_i表示以ii结尾的最长上升子序列，FiF_i表示以ii开头的最长上升子序列，gig_i表示以ii结尾的最长下降子序列，GiG_i表示以ii开头的最长下降子序列
  • 设c1c_1为LISLIS个数，c2c_2为LDSLDS个数，那么任意选的方案为c1c2c_1c_2
  • 通过上面四个数组，计算选中ii的最长上升hih_i和下降HiH_i方案
  • 判断∑hiHi=c1c2\sum h_iH_i=c_1c_2是否成立来判断加1
  • 四个数组可以用树状数组快速求
  • 注意：方案数会爆long long，因此需要取模，并且卡自然溢出
  • 复杂度O(nlog⁡n)O(n \log n)
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 F first
#define S second
#define TR tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
typedef pair<int,int> PII;
const int N=1e6+10,M=3e4+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());

template<typename T,typename F>
struct Fenwick{
    int n;
    vector<T> c;
    T identity;
    F op;
    Fenwick(){}
    Fenwick(int n_,T identity_={0,0}){
        init(n,identity);
    }
    void init(int n_,T identity_={0,0}){
        n=n_;
        c.assign(n+1,identity);
        identity=identity_;
    }
    void add(int x,T v,int rev=0){
        if(rev)x=n-x+1;
        for(;x<=n;x+=x&-x)c[x]=op(c[x],v);
    }
    T query(int x,int rev=0){
        if(rev)x=n-x+1;
        T res=identity;
        for(;x;x&=x-1)res=op(res,c[x]);
        return res;
    }
};
Fenwick<PII,decltype([](const PII &a,const PII &b){
    if(a.F==b.F)return PII{a.F,(a.S+b.S)%mod};
    return a.F>b.F?a:b;
})> fw;
void solve(){
    int n;
    cin>>n;
    vector<int> p(n+1);
    for(int i=1;i<=n;i++)cin>>p[i];
    fw.init(n);
    vector<PII> f(n+1),g(n+1),F(n+1),G(n+1);
    int lis=0,lds=0;
    for(int i=1;i<=n;i++){
        auto val=fw.query(p[i]);
        if(val.F==0)f[i]={val.F+1,1};
        else f[i]={val.F+1,val.S};
        fw.add(p[i],f[i]);
        lis=max(lis,f[i].F);
    }
    fw.init(n);
    for(int i=n;i>=1;i--){
        auto val=fw.query(p[i],1);
        if(val.F==0)F[i]={val.F+1,1};
        else F[i]={val.F+1,val.S};
        fw.add(p[i],F[i],1);
    }
    fw.init(n);
    for(int i=1;i<=n;i++){
        auto val=fw.query(p[i],1);
        if(val.F==0)g[i]={val.F+1,1};
        else g[i]={val.F+1,val.S};
        fw.add(p[i],g[i],1);
        lds=max(lds,g[i].F);
    }
    fw.init(n);
    for(int i=n;i>=1;i--){
        auto val=fw.query(p[i]);
        if(val.F==0)G[i]={val.F+1,1};
        else G[i]={val.F+1,val.S};
        fw.add(p[i],G[i]);
    }
    int c1=0,c2=0;
    for(int i=1;i<=n;i++){
        if(f[i].F==lis)(c1+=f[i].S)%=mod;
        if(g[i].F==lds)(c2+=g[i].S)%=mod;
    }
    int ans=c1*c2%mod;
    for(int i=1;i<=n;i++){
        if(f[i].F+F[i].F-1==lis&&g[i].F+G[i].F-1==lds){
            ans-=f[i].S*g[i].S%mod*F[i].S%mod*G[i].S%mod;
            ans=(ans+mod)%mod;
        }
    }
    cout<<lis+lds-(ans==0)<<"\n";
}

I. 字符串复制(后缀自动机) ​

在这里插入图片描述

  • 考虑每复制一次新增的字符串
  • 假设是SSSSSS而不是SSSS的子串，那么必然是xSyxSy的形式
  • 假设是SSSSSSSS而不是SSSSSS的子串，那么必然是xSSyxSSy的形式，那么可以发现上面两个值的方案是相等
  • 定义f(S,m)f(S,m)表示复制mm次的方案
  • 那么答案就是[f(S,3)−f(S,2)](m−2)+f(S,2)[f(S,3)-f(S,2)](m-2)+f(S,2)，特判小于等于2的情况
  • 计算本质不同子串直接套sam板子即可
  • 复杂度O(∣S∣)O(|S|)
cpp
struct SAM{
    struct Node{
        int len,link;
        array<int,26> ne;
        Node():len{},link{},ne{}{}
    };
    //最多2n-1个节点，3n-4条边
    vector<Node> t;
    int lst;
    SAM(){
        init();
    }
    void init(){
        t.assign(2,Node());
		lst=1;
    }
    int newNode(){
        t.emplace_back();
        return t.size()-1;
    }
    int extend(int p,int c){
        if(t[p].ne[c]){
            int q=t[p].ne[c];
            if(t[q].len==t[p].len+1)return q;
            int r=newNode();
            t[r]=t[q];
            t[r].len=t[p].len+1;
            t[q].link=r;
            while(p&&t[p].ne[c]==q){
                t[p].ne[c]=r;
                p=t[p].link;
            }
            return r;
        }
        int cur=newNode();
        lst=cur;
        t[cur].len=t[p].len+1;
        while(p&&!t[p].ne[c]){
            t[p].ne[c]=cur;
            p=t[p].link;
        }
        if(!p)t[cur].link=1;
        else t[cur].link=extend(p,c);
        return cur;
    }
    int extend(int p,char c,char offset='a'){
        return extend(p,(int)c-offset);
    }
    int next(int p,int c){
        return t[p].ne[c];
    }
    int next(int p,char c,char offset='a'){
        return next(p,(int)c-offset);
    }
    int link(int p){
        return t[p].link;
    }
    int len(int p){
        return t[p].len;
    }
    int size(){
        return t.size();
    }
} sam;
int get(string s){
	int n=s.size();
	int ans=0;
	sam.init();
	for(auto c:s)sam.extend(sam.lst,c);
	for(int i=1;i<sam.size();i++){
		ans+=sam.len(i)-sam.len(sam.link(i));
		ans%=mod;
	}
	return ans;
}
void solve(){
	int n,m;
	cin>>n>>m;
	string s;
	cin>>s;
	if(m==1){
		cout<<get(s)<<"\n";
		return;
	}
	int a2=get(s+s);
	int a3=get(s+s+s);
	cout<<((m-2)*((a3-a2)%mod+mod)%mod+a2)%mod<<"\n";
}

Wenwei Lin · 2022 — 2025