XCPC Notes

Appearance

发布时间：2025-03-15

前言 ​

全场都是结论板子题，最后一题一眼莫队，但是太久没写忘了还有回滚这种东西，导致整场一直在卡常试图卡过去 题目链接

A 小柒的数字 ​

答案为min⁡(n,x−1)\min(n,x-1)

B 小柒的逆序对(一) ​

题意： 给一个长度为nn的排列，求每次交换一次位置的逆序对奇偶性 结论：一个permutationpermutation任意交换一次位置奇偶性必改变

类似的逆序对结论有：翻转区间逆序对的奇偶性是否改变只与区间长度lenlen,len(len−1)2\frac{len(len-1)}{2}的奇偶性有关

C 小柒的逆序对(2) ​

预处理对数后贪心

D 小柒分糖果 ​

在这里插入图片描述

  • 对于每种糖果分别考虑，假设分配ii个相同的糖果，隔板法可知(i+m−1m−1)\binom{i+m-1}{m-1}，因此如果糖果有xx个，则方案为∑i=0x(i+m−1m−1)\sum_{i=0}^x\binom{i+m-1}{m-1}，由组合数求和公式∑k=0n(k+rr)=(n+r+1r+1)\sum_{k=0}^n\binom{k+r}{r}=\binom{n+r+1}{r+1}得，方案为(x+mm)\binom{x+m}{m}
  • 对每种糖果累乘即可
  • 另一种本质相同的想法，将x分配成m+1份，x1+x2+x3+...+xm+xm+1=xx_1+x_2+x_3+...+x_m+x_{m+1}=x，方案有(x+m+1−1m+1−1)=(x+mm)\binom{x+m+1-1}{m+1-1}=\binom{x+m}{m}
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=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 fac[N],inv[N];
int qpow(int a,int b){
    int ans=1;
    for(;b;b>>=1){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
    }
    return ans;
}
void init(){
    for(int i=(fac[0]=1);i<N;i++)fac[i]=fac[i-1]*i%mod;
    inv[N-1]=qpow(fac[N-1],mod-2);
    for(int i=N-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
}
int C(int n,int m){
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
void solve(){ 
    init();
    int n,m;
    cin>>n>>m;
    int ans=1;
    // cout<<C(0,0)<<" "<<fac[0]<<" "<<inv[0]<<"\n";
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        // int tmp=0;
        // for(int j=0;j<=x;j++)tmp+=C(j+m-1,m-1),tmp%=mod;
        ans=ans*C(x+m,m)%mod;    
    }
    cout<<ans<<"\n";
}   
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    // cin>>T;
    while(T--)solve();
    return 0;
}

E 小柒的神器 ​

在这里插入图片描述

  • 如果一段区间合法，那么ii和i+1i+1连通，因此可以预处理ii和i+1i+1的连通性，前缀和O(1)O(1)判断是否连通
  • 同样地，一段区间的最大代价=max⁡(i和i+1连通的最大代价)\max(i和i+1连通的最大代价)
  • 判断两个点连通的路径中，最大边最小，可以使用kruscal重构树，计算出来后直接查询区间最值即可
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=2e5+10,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());
template<typename T,typename F>
struct SpraseTable{
    int n;
    vector<vector<T>> st;
    F op;
    void init(int n,const vector<T>& a,int r=0){
        this->n=n;
        st.assign(n+1,vector<T>(__lg(n)+1,r));
        for(int i=1;i<=n;i++)st[i][0]=a[i];
        for(int j=1;1<<j<=n;j++){
            for(int i=1;i+(1<<j)-1<=n;i++){
                st[i][j]=op(st[i][j-1],st[i+(1<<j-1)][j-1]);
            }
        }
    }
    T query(int l,int r){
        int k=__lg(r-l+1);
        return op(st[l][k],st[r-(1<<k)+1][k]);
    }
};
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)];
    }
} dsu;
SpraseTable<int,decltype([](int a,int b){return max(a,b);})> st;
int n,m,q;
vector<int> adj[N];
vector<array<int,3>> e;
int a[N],dep[N],w[N],idx,par[N][30];
void ex_kruscal(){
    sort(e.begin(),e.end());
    dsu.init(2*n+1);
    idx=n;
    for(auto &[c,u,v]:e){
        if(dsu.same(u,v))continue;
        ++idx;
        u=dsu.find(u);
        v=dsu.find(v);
        adj[idx].push_back(u);
        adj[idx].push_back(v);
        dsu.merge(idx,u);
        dsu.merge(idx,v);
        w[idx]=c;
    }
}
void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    par[u][0]=fa;
    for(int i=1;i<=__lg(dep[u]);i++)par[u][i]=par[par[u][i-1]][i-1];
    for(int v:adj[u]){
        dfs(v,u);
    }
}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    while(dep[x]>dep[y]){
        x=par[x][__lg(dep[x]-dep[y])];
    }
    if(x==y)return x;
    for(int i=__lg(dep[x]);i>=0;i--){
        if(par[x][i]!=par[y][i]){
            x=par[x][i];
            y=par[y][i];
        }
    }
    return par[x][0];
}
void solve(){
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        e.push_back({a[u]+a[v],u,v});
    }
    ex_kruscal();
    dfs(idx,0);
    vector<int> have(n+1),ans(n+1);
    for(int i=1;i<n;i++){
        if(!dsu.same(i,i+1))have[i]=1;
        ans[i]=w[lca(i,i+1)];
        have[i]+=have[i-1];
    }
    
    st.init(n,ans);
    while(q--){
        int l,r;
        cin>>l>>r;
        if(l==r){
            cout<<"0\n";
            continue;
        }
        if(have[r-1]-have[l-1]){
            cout<<"-1\n";
            continue;
        }
        cout<<st.query(l,r-1)<<"\n";
    }
}  
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    // cin>>T;
    while(T--)solve();
    return 0;
}

F 小柒的颜色 ​

在这里插入图片描述

  • 如果没有第二问直接上普通莫队
  • 第二问需要询问最值maxmax，具有不可逆性，因此需要使用回滚莫队
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=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());
struct Node{
    int id,l,r;
};
int cnt[N],sum[N],w[M];
int be[M],L[M],R[M],tot,block;
bool vis[N];
vector<int> tmp;
bool cmp(Node x,Node y){
    return (be[x.l]^be[y.l])?be[x.l]<be[y.l]:x.r<y.r;
}
void add(int x,int &res,int &id,int &s){
    sum[w[x]]+=cnt[w[x]]*w[x];
    s+=cnt[w[x]]*w[x];
    cnt[w[x]]++;
    if(res<sum[w[x]]){
        res=sum[w[x]];
        id=w[x];
    }
    else if(res==sum[w[x]]&&id>w[x])id=w[x];
}
void del(int x){
    cnt[w[x]]--;
    sum[w[x]]-=cnt[w[x]]*w[x];
}
void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>w[i];
    vector<Node> q(m);
    vector<PII> ans(m);
    for(int i=0;i<m;i++)cin>>q[i].l>>q[i].r,q[i].id=i;
    block=max(1ll,n*n/m),tot=(n+block-1)/block;
    for(int i=1;i<=tot;i++){
        L[i]=(i-1)*block+1,R[i]=min(i*block,n);
        for(int j=L[i];j<=R[i];j++)be[j]=i;
    }
    sort(q.begin(),q.end(),cmp);
    for(int i=0,j;i<m;i++){
        int right=R[be[q[i].l]];
        j=i;
        while(j+1<m&&be[q[j+1].l]==be[q[i].l])j++;
        while(i<=j&&q[i].r<=right){
            auto [id,ql,qr]=q[i++];
            int res=0,ID=INF,s=0;
            for(int k=ql;k<=qr;k++)add(k,res,ID,s);
            ans[id]={s,ID};
            for(int k=ql;k<=qr;k++)del(k);
        }
        int l=right+1,r=right;
        int res=0,ID=INF,s=0;
        while(i<=j){
            auto [id,ql,qr]=q[i++];
            while(r<qr)add(++r,res,ID,s);
            int bres=res,bID=ID,bs=s;
            while(l>ql)add(--l,res,ID,s);
            ans[id]={s,ID};
            res=bres,ID=bID,s=bs;
            while(l<right+1)del(l++);
        }
        while(r>right)del(r--);
        i=j;
    }
    for(auto &[x,y]:ans)cout<<x<<" "<<y<<"\n";
}  
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    // cin>>T;
    while(T--)solve();
    return 0;
}

Wenwei Lin · 2022 — 2025