XCPC Notes

Appearance

发布时间：2025-03-03

题目链接

G. Menji 和 gcd ​

在这里插入图片描述

思路：

  • 通过O(1)O(1)的方法可以检测：Rx−L−1x>1\frac{R}{x}-\frac{L-1}{x}>1
  • 可以直接枚举1e6以内的ii，大于1e6的因数可以通过Ri\frac{R}{i}枚举出来
  • 复杂度O(R)O(\sqrt R)
cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
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 L,R,ans;
void check(int x){
    if(!x)return;
    if(R/x-(L-1)/x>1)ans=max(ans,x);
}
void solve(){
    ans=0;
    cin>>L>>R;
    for(int i=1;i<=1e6;i++){
        check(i);
        check(R/i);
    }
    cout<<ans<<"\n";
}   
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    cin>>T;
    while(T--)solve();
    return 0;
}

I. 不等式 ​

在这里插入图片描述 思路：

  • 拓扑排序贪心，有环或者总和大于1e9则输出-1
cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=2e5+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 ans[N],din[N];
vector<int> adj[N];
vector<PII> e[N];
int n,m,res;
bool topu(){
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(din[i]==0)q.push(i);
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        ans[u]=1;
        for(auto [x,y]:e[u])ans[u]=max(ans[u],ans[x]+ans[y]);
        res+=ans[u];
        if(res>1e9)return false;
        for(auto v:adj[u]){
            if(--din[v]==0)q.push(v);
        }
    }
    for(int i=1;i<=n;i++){
        if(din[i])return false;
    }
    return true;
}
void solve(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        adj[y].push_back(x);
        adj[z].push_back(x);
        e[x].emplace_back(y,z);
        din[x]+=2;
    }
    if(topu()){
        cout<<res<<"\n";
    }
    else cout<<"-1\n";
}   
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    // cin>>T;
    while(T--)solve();
    return 0;
}

C.DFS 序 ​

在这里插入图片描述

思路：

  • 经典的换位置，看贡献的变化
  • 假设有两部分i和ji和j，不换位置的贡献为1w11+2w12+...+iw1i+(i+1)w21+...(i+j)w2j1w_{11}+2w_{12}+...+i w_{1i}+(i+1)w_{21}+...(i+j)w_{2j}
  • 交换位置后，1w21+2w22+...+jw2j+(j+1)w11+...+(j+i)w1i1w_{21}+2w_{22}+...+jw_{2j}+(j+1)w_{11}+...+(j+i)w_{1i}
  • 展开后发现有一部分贡献相同∑x=1ixw1x+∑x=1jxw2x\sum_{x=1}^i xw_{1x}+\sum_{x=1}^jxw_{2x}
  • 能否交换位置取决于siz1W2和siz2W1siz_1W_2和siz_2W_1的大小
  • 复杂度O(nlogn)O(nlogn)
cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=2e5+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());
vector<int> adj[N];
int w[N];
vector<int> dfs(int u,int fa){
    vector<vector<int>> V;
    vector<array<int,3>> tmp;
    for(auto v:adj[u]){
        if(v==fa)continue;
        V.push_back(dfs(v,u));
        int W=0;
        for(auto it:V.back())W+=w[it];
        tmp.push_back({W,(int)V.back().size(),(int)V.size()-1}); 
    }
    sort(tmp.begin(),tmp.end(),[&](auto x,auto y){
        return x[1]*y[0]>y[1]*x[0];
    });
    vector<int> ans={u};
    for(auto [w,sz,id]:tmp){
        for(auto it:V[id])ans.push_back(it);
    }
    return ans;
}
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>w[i];
    for(int i=2;i<=n;i++){
        int x;
        cin>>x;
        adj[x].push_back(i);
        adj[i].push_back(x);
    }
    auto v=dfs(1,0);
    int ans=0;
    for(int i=0;i<n;i++)ans+=(i+1)*w[v[i]];
    cout<<ans<<"\n";
}   
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    // cin>>T;
    while(T--)solve();
    return 0;
}

E. 循环赛 ​

在这里插入图片描述

思路：

  • 不会，打表打到7，摁猜
  • 结论：
    • m=1,n%2=1则是1否则为2m=1,n\%2=1则是1否则为2
    • m≤⌊n2⌋+1,答案为nm \leq \lfloor \frac{n}{2} \rfloor+1,答案为n
    • 否则每增加1，答案减2
cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=1010,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());
void solve(){
    int n,m;
    cin>>n>>m;
    if(m==1){
        if(n%2)cout<<"1\n";
        else cout<<"2\n";
        return;
    }
    if(m<=n/2+1){
        cout<<n<<"\n";
    }   
    else cout<<n-(m-n/2-1)*2<<"\n";
}   
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    cin>>T;
    while(T--)solve();
    return 0;
}

B. 腊肠披萨 ​

在这里插入图片描述 思路：

  • 最长公共前后缀，可以使用AC自动机求解
  • 理由：假设当前ac自动机的节点为ii，对应的字符串为sis_i,j=neij=ne_i,对应的字符串为sjs_j，根据ac自动机的定义，sjs_j一定是sis_i的后缀，同时sis_i一定又是某个字符串的前缀
  • 因此我们可以nei向i连边，维护每个前缀的贡献ne_i向i连边，维护每个前缀的贡献，保证当枚举到节点uu对应的字符串sus_u时，当前的贡献即为所有前缀对sus_u后缀的贡献
  • 复杂度:O(∣S∣)O(|S|)
cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=3e6+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 tr[N][26],ne[N],idx,L,C,P,ans[N],res,lst[N],ID[N];
vector<array<int,2>> g[N];
vector<int> adj[N]; 
void insert(string &s,int id){
    int p=0;
    for(int i=0,c=1;i<s.size();i++){
        int u=s[i]-'a';
        if(!tr[p][u])tr[p][u]=++idx;
        p=tr[p][u];
        c=c*C%P;
        g[p].push_back({id,c});
    }
    ID[id]=p;
}
void build(){
    queue<int>q;
    for(int i=0;i<26;i++){
        if(tr[0][i])q.push(tr[0][i]);
    }
    while(q.size()){
        int p=q.front();q.pop();
        for(int i=0;i<26;i++){
            if(tr[p][i]){
                ne[tr[p][i]]=tr[ne[p]][i];
                q.push(tr[p][i]);
            }else tr[p][i]=tr[ne[p]][i];
        }
    }
}
void dfs(int u){
    vector<array<int,2>> tmp;
    for(auto [id,c]:g[u]){
        res=(res+c-lst[id]+P)%P;
        tmp.push_back({id,lst[id]});
        lst[id]=c;
    
    }
    ans[u]=res;
    for(auto v:adj[u])dfs(v);
    for(auto [id,c]:tmp){
        res=(res+c-lst[id]+P)%P;
        lst[id]=c;
    }
}
void solve(){
    cin>>L>>C>>P;
    for(int i=1;i<=L;i++){
        string s;
        cin>>s;
        g[0].push_back({i,1});
        insert(s,i);
    }
    build();
    for(int i=1;i<=idx;i++)adj[ne[i]].push_back(i);
    dfs(0);
    int res=0;
    for(int i=1;i<=L;i++)res=(res+ans[ID[i]])%P;
    cout<<res<<'\n';    
}   
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    // cin>>T;
    while(T--)solve();
    return 0;
}

F. 图 ​

在这里插入图片描述 思路：

  • 构造⌈mn−1⌉\lceil\frac{m}{n-1}\rceil颗生成树，每次尽可能地靠前加边，那么最后一颗树至少有一条边，任取联通的u,vu,v，那么它们在前面也已经联通，直接找到每一棵树的u,v路径即可
  • 二分加边即可，复杂度为mlogmmlogm
cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=3e6+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());
struct DSU {
    std::vector<int> f, siz;
    std::vector<vector<int>> adj;
    vector<PII> e;
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
        adj.assign(n, vector<int>());
    }
    
    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) {
        int fx = find(x);
        int fy = find(y);
        if (fx == fy) {
            return false;
        }
        siz[fx] += siz[fy];
        f[fy] = fx;
        adj[x].push_back(y);
        adj[y].push_back(x);
        e.push_back({x,y});
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
    vector<int> find_path(int u,int fa,int y){
        bool f=false||(u==y);
        vector<int> ans;
        for(auto v:adj[u]){
            if(v==fa)continue;
            auto tmp=find_path(v,u,y);
            if(tmp.size()){
                f=true;
                ans=tmp;
            }
        }
        if(f)ans.push_back(u);
        return ans;
    };
};
void solve(){
    int n,m;
    cin>>n>>m;
    vector<array<int,2>> edges(m);
    for(auto &[u,v]:edges)cin>>u>>v;
    int k=(m+n-2)/(n-1);
    vector<DSU> dsu(k);
    for(int i=0;i<k;i++)dsu[i].init(n+1);
    for(auto &[u,v]:edges){
        int l=0,r=k-1;
        while(l<r){
            int mid=l+r>>1;
            if(!dsu[mid].same(u,v))r=mid;
            else l=mid+1;
        }
        if(!dsu[l].same(u,v))dsu[l].merge(u,v);
    }
    auto [u,v]=dsu[k-1].e[0];
    vector<vector<int>> ans={{u,v}};
    for(int i=0;i<k-1;i++){
        auto path=dsu[i].find_path(u,0,v);
        ranges::reverse(path);
        ans.push_back(path);
    }   
    cout<<u<<" "<<v<<"\n";
    for(auto &v:ans){
        cout<<v.size()<<" ";
        for(auto &x:v)cout<<x<<" ";
        cout<<"\n";
    }
}   
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    cin>>T;
    while(T--)solve();
    return 0;
}

J. 另一个计数问题 ​

在这里插入图片描述

  • x≤n2，x与2x联通，2与2x联通，因此，2到n2联通x \leq \frac{n}{2}，x与2x联通，2与2x联通，因此，2到 \frac{n}{2}联通
  • 不连通的孤点当且仅当为大于n2\frac{n}{2}的质数
  • 用总贡献减去孤点的贡献
  • 定义S1S1为[1,n][1,n]的前缀和,S2S2为[1,n][1,n]的平方前缀和，S3S3为[n2+1,n][\frac{n}{2}+1,n]的质数和，S4S4为[n2+1,n][\frac{n}{2}+1,n]的质数平方和
  • 那么我们假设f(u,v)=1f(u,v)=1恒成立，总贡献就是∑i=1ni(S1−i)2−(S1−1)=S12−S22−(S1−1)\frac{\sum_{i=1}^ni(S_1-i)}{2}-(S_1-1)=\frac{S_1^2-S_2}{2}-(S_1-1)
  • 然后我们回顾min25板子g函数的定义为gng_n表示小于等于nn的所有质数对应的函数和
  • 因此假设原函数f′0(x)=x,f′1(x)=x2f'0(x)=x,f'1(x)=x^2，那么S3=g0n−g0n2,S4=g1n−g1n2S_3=g0_n-g0_{\frac{n}{2}},S_4=g1_n-g1_{\frac{n}{2}}，本质是前缀和作差
  • 质数的贡献为∑pp(S1−1−p)−质数之间互相的贡献(∑pp(S3−p)2)=∑pp(S1−1−p)−(S32−S4)2\sum_p p(S_1-1-p)-质数之间互相的贡献(\frac{\sum_p p(S_3-p)}{2})=\sum_p p(S_1-1-p)-\frac{(S_3^2-S_4)}{2}
cpp
struct mint {
    constexpr static int mod = 998244353;
    // constexpr static int mod = 1e9+7;
	int x;
	inline mint(int o = 0) { x = o%mod; }
	inline mint & operator = (int o) { return x = o%mod, *this; }
	inline mint & operator += (mint o) { return (x += o.x) >= mod && (x -= mod), *this; }
	inline mint & operator -= (mint o) { return (x -= o.x) < 0 && (x += mod), *this; }
	inline mint & operator *= (mint o) { return x = (long long) x * o.x % mod, *this; }
    inline mint& qpow(int b){
        mint w = *this;
        mint ret(1);
        for(; b; b >>= 1, w *= w) if(b & 1) ret *= w;
        return x = ret.x, *this;
    }
	inline mint & operator /= (mint o) { return *this *= (o .qpow( (mod - 2))); }
	friend inline mint operator + (mint a, mint b) { return a += b; }
	friend inline mint operator - (mint a, mint b) { return a -= b; }
	friend inline mint operator * (mint a, mint b) { return a *= b; }
	friend inline mint operator / (mint a, mint b) { return a /= b; }
    friend ostream& operator<<(ostream& os, const mint& m) {
        return os << m.x;
    }
};
template<typename T>
struct Min25{
    // sum[0]质数前缀和，sum[1]质数平方前缀和
    // g为g1-g0, g0:f'(k)=k, g1:f'(k)=k^2
    // 将积性函数g拆分，注意g1,g0必须满足为完全积性函数即f(p)=p^k
    int prime[N],w[N],cnt,tot,id1[N],id2[N],sq,n;
    T sum[2][N],g[2][N];
    bool vis[N];
    void sieve(int n=N+1){
        int c=0;
        for(int i=2;i<=n;i++){
            if(!vis[i]){
                vis[i]=1;
                prime[++cnt]=i;
                //======= need to be modified =======//
                sum[0][cnt]=sum[0][cnt-1]+i;//f(x)=x的前缀和
                sum[1][cnt]=sum[1][cnt-1]+i*i;//f(x)=x^2的前缀和
                //============== END ==============//
            }
            for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
                vis[i*prime[j]]=1;
                if(i%prime[j]==0)break;
            }
        }
    }   
    int getid(int x){
        if(x<=sq)return id1[x];
        return id2[n/x];
    }
    T inv6=T(6).qpow(mod-2),inv2=T(2).qpow(mod-2);
    //====== need to be modified ======//
    T g0(T x){// g0 
        return x;
    }
    T g1(T x){// g1
        return x*x;
    }
    T f0(T x){// 1~x的前缀和 
        return x*(x+1)*inv2;
    }
    T f1(T x){// 1~x的前缀平方和
        return x*(x+1)*(2*x+1)*inv6;
    }
    //=========== END ==================//
    void init(int x){// 初始化下标的问题，并且预处理出要用到的完全积性函数
        n=x;
        sq=sqrtl(n);
        sieve(sq);
        for(int l=1,r;l<=n;l=r+1){
            r=n/(n/l);
            w[++tot]=n/l;
            //======= need to be modified =======//
            g[0][tot]=f0(w[tot])-1;//f(x)=x^2对应的g(n/l,0)
            g[1][tot]=f1(w[tot])-1;//f(x)=x对应的g(n/l,0)
            //============= END ==================//
            if(n/l<=sq)id1[n/l]=tot;//映射
            else id2[n/(n/l)]=tot;
        }
        //======= need to be modified ======//
        for(int i=1;i<=cnt;i++){
            for(int j=1;j<=tot&&prime[i]*prime[i]<=w[j];j++){
                g[0][j]-=g0(prime[i])*(g[0][getid(w[j]/prime[i])]-sum[0][i-1]);
                g[1][j]-=g1(prime[i])*(g[1][getid(w[j]/prime[i])]-sum[1][i-1]);
            }
        }
        //========== END =================//
    }
    //====== need to be modified ======//
    T F(T x){
        return x*(x-1); 
    }
    //=========== END =====================//
    T S(int x,int y){
        if(prime[y]>=x)return 0;
        int k=getid(x);// 获取下标
        //====== need to be modified ======//
        T res=g[1][k]-g[0][k]-sum[1][y]+sum[0][y];//q(n)=g[1][k]-g[0][k],\sum_{i=1}^yf(i)=sum[1][y]-sum[0][y]
        //=========== END ==================//
        for(int i=y+1;i<=cnt&&prime[i]*prime[i]<=x;i++){// 枚举p_i
            for(int e=1,p=prime[i];p<=x;p=p*prime[i],e++){// 枚举p_i^e
                res+=F(p)*(S(x/p,i)+(e!=1));
            }
        }
        return res;
    }
    T getg(int x,int y){
        return g[x][getid(y)];
    }
};
Min25<mint> sieve;

void solve(){
    int n;
    cin>>n;
    sieve.init(n);
    mint S1=sieve.f0(n),S2=sieve.f1(n);
    mint ans=(S1*S1-S2)/2-(S1-1);
    mint S3=sieve.getg(0,n)-sieve.getg(0,n/2),S4=sieve.getg(1,n)-sieve.getg(1,n/2);
    ans-=(S1-1)*S3-S4-(S3*S3-S4)/2;
    cout<<ans<<"\n";
}

Wenwei Lin · 2022 — 2025