XCPC Notes

Appearance

发布时间：2024-07-29

CF思维题 ​

CF1348D Phoenix and Science ​

题意：
给定一个数n，初始有1个细菌质量为1，每天早上可以选择若干个细菌分裂，每天晚上细菌质量+1，问恰好到达n质量的天数
思路：

  • 假设当天细菌增加x，当前质量为y，那么当天晚上质量增加x+y
  • 先构造一个序列 a1+a2+...+ax=na_1+a_2+...+a_x=n
  • 每天乘2肯定是最优天数，最后剩下的部分插入数组，排序即可
  • 这样必定保证前后相差不超过两倍，并且满足条件
cpp
void solve(){
    int n;
    cin>>n;
    vector<int> ans;
    for(int i=1;i<=n;i*=2){
        ans.push_back(i);
        n-=i;
    }
    if(n>0){
        ans.push_back(n);
        sort(ans.begin(),ans.end());
    }
    cout<<ans.size()-1<<"\n";
    for(int i=1;i<ans.size();i++)cout<<ans[i]-ans[i-1]<<" \n"[i==ans.size()-1];
}

CF1365F ​

题意：
给定数组a,b,每次可以交换a的前i个数和后i个数(前缀和后缀的相对顺序不变)
问能否使a=b
思路：

  • i与n−i+1的数永远是相对的，判断对数是否相等即可，特判奇数时中间的那个数i与n-i+1的数永远是相对的，判断对数是否相等即可，特判奇数时中间的那个数
  • 如果要构造方案，不会超过 3n2\frac{3n}{2} 种
  • 从b[n/2]的位置构造，假设当前i的对数对应a数组的位置为j
    • 如果j==n，那么对a交换i长度
    • 如果j==1，先交换长度为1，再进行上一步操作
    • 否则，先让j到达1或n，再进行上面两个操作
  • 还原一对最多进行3次操作，有n/2对，因此总数最多为3*n/2

CF1527D MEX Tree ​

题意：
求有多少条树上路径的mex等于k(0-n)
思路：

  • 贪心容斥
  • 对于每个ans[i]表示mex大于等于i的路径数
  • 以0为根存储信息
  • 先求出ans0和ans1，找出1所在的路径的与0相连的点
  • 然后从小到达依次更新链的长度(两个端点)，如果发生劈叉，那么就是不合法的，直接break
cpp
void solve(){
    int n;
    cin>>n;
    vector<int> adj[n];
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int ts=0;
    vector<int> in(n+1),out(n+1),siz(n+1);
    function<void(int,int)> dfs=[&](int u,int fa){
        in[u]=++ts;
        for(auto v:adj[u]){
            if(v==fa)continue;
            dfs(v,u);
        }
        out[u]=ts;
        siz[u]=out[u]-in[u]+1;
    };
    dfs(0,-1);
    vector<int> ans(n+1);
    ans[0]=ans[1]=n*(n-1)/2;
    int l=-1;
    for(auto v:adj[0]){
        ans[1]-=siz[v]*(siz[v]-1)/2;
        if(in[v]<=in[1]&&in[1]<=out[v])l=v;
    }
    int u=1,v=-1;
    for(int i=1;i<n;i++){
        bool ok=0;
        if(in[i]<=in[u]&&in[u]<=out[i])ok=1;
        if(v!=-1&&in[i]<=in[v]&&in[v]<=out[i])ok=1;
        if(!ok){
            if(in[u]<=in[i]&&in[i]<=out[u])u=i;
            else if((v==-1&&!(in[l]<=in[i]&&in[i]<=out[l]))||(in[v]<=in[i]&&in[i]<=out[v]))v=i;
            else break;
        }
        if(v==-1)ans[i+1]=siz[u]*(n-siz[l]);
        else ans[i+1]=siz[u]*siz[v];
    }
    for(int i=0;i<n;i++)ans[i]-=ans[i+1];
    for(int i=0;i<=n;i++)cout<<ans[i]<<" \n"[i==n];
}

CF1922E ​

题意：
构造一个数组，使其递增子序列的个数为x(1<=x<=1e18)
思路：

  • 对于长度为n的子序列，它的最多个数为 2n2^n
  • 设x最高位为mx,因此考虑先构造一个长度为mx的数组
  • 观察发现，如果在数组 ii 后面插入一个最大数，使其不影响后面的数，那么以该数结尾的递增序列会增加 2i2^i 个
  • 问题转化为对于x二进制的每个1，除了最高位，都要插入一个数
  • 一共要插入 2log2x2log_2x 个数，小于等于200，满足题意
cpp
void solve(){
    int n;
    cin>>n;
    int mx;
    for(int i=61;i>=0;i--){
        if(n>>i&1){
            mx=i;
            break;
        }
    }
    vector<int> ans;
    for(int i=0;i<mx;i++){
        if(n>>i&1)ans.push_back(1e9-i);
        ans.push_back(i);
    }
    cout<<ans.size()<<"\n";
    for(auto it:ans)cout<<it<<" ";
    cout<<"\n";
}

CF1296E2 ​

给字符串每个字符着色，可以对两个不同颜色的字符交换，求着色最少颜色数，及方案
思路：

  • 对于一个最长下降子序列而言，需要的颜色数等于序列长度
  • 这样可以构造出一种方案
cpp
void solve(){
    int n;
    string s;
    cin>>n>>s;
    vector<int> dp(n+1,1),mx(26);
    int cnt=0;
    for(int i=n;i>=1;i--){
        int v=s[i-1]-'a';
        for(int j=v-1;j>=0;j--)dp[i]=max(dp[i],mx[j]+1);
        mx[v]=max(mx[v],dp[i]);
        cnt=max(cnt,dp[i]);
    }
    cout<<cnt<<"\n";
    for(int i=1;i<=n;i++)cout<<dp[i]<<" ";
    cout<<"\n";
}

CF1296F ​

题意：

  • 给一颗无根树，给定m个条件，u v w表示u，v的简单路径最小边权为w
  • 询问是否存在满足的树

思路：

  • 直接构造，对于每个条件，更新走过的边权，取max
  • 然后check是否合法即可
cpp
void solve(){
    int n;
    cin>>n;
    vector<PII> adj[n+1];
    map<PII,int> mp;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        mp[{u,v}]=i;
        adj[u].push_back({v,i});
        adj[v].push_back({u,i});
    }
    vector<int> f(n+1),par(n+1),id(n+1),dep(n+1);
    function<void(int,int)> dfs=[&](int u,int fa){
        dep[u]=dep[fa]+1;
        for(auto [v,c]:adj[u]){
            if(v==fa)continue;
            par[v]=u,id[v]=c;
            dfs(v,u);
        }
    };
    dfs(1,0);
    auto update=[&](int u,int v,int x){
        if(dep[u]<dep[v])swap(u,v);
        while(dep[u]!=dep[v]){
            f[id[u]]=max(f[id[u]],x);
            u=par[u];
        }
        while(u!=v){
            f[id[u]]=max(f[id[u]],x);
            f[id[v]]=max(f[id[v]],x);
            u=par[u];
            v=par[v];
        }
    };
    auto check=[&](int u,int v,int x){
        if(dep[u]<dep[v])swap(u,v);
        int ans=1e9;
        while(dep[u]!=dep[v]){
            ans=min(f[id[u]],ans);
            u=par[u];
        }
        while(u!=v){
            ans=min(f[id[u]],ans);
            ans=min(f[id[v]],ans);
            u=par[u];
            v=par[v];
        }
        return ans==x;
    };
    int m;
    cin>>m;
    vector<array<int,3>> e(m+1);
    for(int i=1;i<=m;i++){
        cin>>e[i][0]>>e[i][1]>>e[i][2];
        update(e[i][0],e[i][1],e[i][2]);
    }
    for(int i=1;i<=m;i++){
        if(!check(e[i][0],e[i][1],e[i][2])){
            cout<<"-1\n";
            return;
        }
    }
    for(int i=1;i<n;i++)cout<<(f[i]?f[i]:1000000)<<" \n"[i==n-1];
}

CF1552D ​

题意：

给定一个数组a，询问是否能构造一个数组b，使得对于每个 ii ,都有一个 j,k,ai=bj−bkj,k,a_i=b_j-b_k

思路：

  • j向k连边，那么会连n条边，必然存在环
  • 对于环来讲总和a等于0
  • a可以取正负号
  • 因此题目转化为是否存在一个方案划分，使得选出来的a总和为0(符号任选)
  • a要么不选，要么正号，要么负号
  • 枚举每个状态 O(n3n)O(n3^n)
cpp
void solve(){
    cin>>n;
    int pw3=1;
    for(int i=1;i<=n;i++)cin>>a[i],pw3*=3;
    for(int i=1;i<pw3;i++){
        int tmp=i,sum=0;
        for(int j=1;j<=n;j++){
            int bit=tmp%3;
            tmp/=3;
            if(bit==1)sum+=a[j];
            else if(bit==2)sum-=a[j];
        }
        if(!sum){
            cout<<"YES\n";
            return;
        }
    }
    cout<<"NO\n";
}

CF1316C ​

题意：

给定两个多项式 f(x),g(x)f(x),g(x) ,问 f(x)∗g(x)f(x)*g(x) 里面是否存在一个系数c,gcd(c,p)=1

保证两个多项式系数gcd为1

思路：

  • 对于两个多项式分别找出第a,b个系数不是p的倍数(必然存在，否则gcd=p与题意不符)
  • 答案:a+b，原因:(p的倍数+不是p的倍数)必然不是p的倍数

CF1334D ​

题意：

求l，r的最小字典序的欧拉序

思路：

答案为:1 2 1 3 1 4...1 n 2 3 2 4...2 n.....n-1 n 1，在这个序列找[l,r]即可

CF1556D ​

题意：

给定n,k

交互题，询问不超过2n次，找出第k小值

or i j询问i和j的or值 and i j询问i和j的and值

思路：

  • (a or b)+(a and b)=a+b
  • 求出所有a[i]+a[i+1]，花费2n-2次
  • 只需要求出任意的ai即可，花费2次，求出a[1]+a[3],那么a[1]+a[2],a[2]+a[3]之前求过,则可以求出a[1]
  • 恰好2n次
  • 其他结论：
  • a⊕b=(a∣b)−(a&b)a \oplus b=(a|b)-(a \& b)
  • a+b=(a⊕b)+2(a&b)a+b=(a \oplus b)+2(a \& b)
  • a+b=(a∣b)+(a&b)a+b=(a|b)+(a \& b)

CF2005E2 ​

题意：

两个人轮流遍历一个长度为l的数组a，每次需要在剩余的矩阵范围内找到与当前a数组指针指向的值相等的数

记位置为(i,j),矩阵范围变为(i,j)~(n,m)

当一个人在矩阵找不到当前值或者a数组已经遍历完毕，则这个人输

判断谁赢

思路：

性质：遍历数组a中的元素不会有重复的

因此先对数组a去重并且缩短其长度

定义 dp0i,j表示当前下标索引为偶数的能获取胜利的最小索引，dp1表示奇数dp0_{i,j} 表示当前下标索引为偶数的能获取胜利的最小索引，dp1表示奇数

那么有两种情况：

  • dp0i,j=min(dp0i+1,j,dp0i,j+1)dp0_{i,j}=min(dp0_{i+1,j},dp0_{i,j+1}) ,表示不选当前数
  • dp0i,j=indexci,jdp_0{i,j}=index_{c_{i,j}} ,等于当前值对应的a数组下标，当 dpi+1,j+1>indexci,j+1dp_{i+1,j+1}>index_{c_{i,j}}+1 可以转移，即下一步对方必败，此时我方选择当前数必胜 最终答案，如果 dp11,1=1dp1_{1,1}=1 则先手赢
cpp
int l,n,m,a[N],c[N][N],dp0[N][N],dp1[N][N],index[N*N];
void solve(){
    cin>>l>>n>>m;
    for(int i=1;i<=l;i++)cin>>a[i];
    for(int i=1;i<=l;i++){
        if(index[a[i]]){
            l=i-1;
            break;
        }
        index[a[i]]=i;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)cin>>c[i][j];
    }
    for(int i=1;i<=n+1;i++){
        for(int j=1;j<=m+1;j++)dp0[i][j]=dp1[i][j]=INF;
    }
    for(int i=n;i>=1;i--){
        for(int j=m;j>=1;j--){
            dp0[i][j]=min(dp0[i][j+1],dp0[i+1][j]);
            dp1[i][j]=min(dp1[i][j+1],dp1[i+1][j]);
            if(!index[c[i][j]])continue;
            if(index[c[i][j]]%2==0&&index[c[i][j]]+1<dp1[i+1][j+1])dp0[i][j]=min(dp0[i][j],index[c[i][j]]);
            if(index[c[i][j]]%2==1&&index[c[i][j]]+1<dp0[i+1][j+1])dp1[i][j]=min(dp1[i][j],index[c[i][j]]);
        }
    }
    cout<<(dp1[1][1]==1?"T\n":"N\n");
    for(int i=1;i<=l;i++)index[a[i]]=0;
}

CF2028E(概率dp) ​

题意：

给定一棵树，假设当前在x节点，每次抛硬币，如果为正面，则往根节点移动，否则往儿子移动

到达根节点就赢否则输

询问全部不同节点的概率

思路：

假设是一条链，可以发现如下规律

dpn−1=12dpn−2,dpn−2=23dpn−3,dpn−3=34dpn−4dp_{n-1}=\frac{1}{2}dp_{n-2},dp_{n-2}=\frac{2}{3}dp_{n-3},dp_{n-3}=\frac{3}{4}dp_{n-4}

设当前节点为v，到叶子的最小距离为 dvd_v ,则 dpv=dv−1dvdpudp_v=\frac{d_v-1}{d_v}dp_u

拓展到树，对方肯定会往离叶子节点最近的走

cpp
    int n;
    cin>>n;
    vector<int> adj[n+1],dep(n+1,INF),ans(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);
    }
    function<void(int,int)> dfs1=[&](int u,int fa){
        if(adj[u].size()==1&&u!=1){
            dep[u]=1;
            return;
        }
        for(auto v:adj[u]){
            if(v==fa)continue;
            dfs1(v,u);
            dep[u]=min(dep[u],dep[v]+1);
        }
    };
    function<void(int,int)> dfs=[&](int u,int fa){
        for(auto v:adj[u]){
            if(v==fa)continue;
            ans[v]=(dep[v]-1)*qpow(dep[v],mod-2)%mod*ans[u]%mod;
            dfs(v,u);
        }
    };
    dfs1(1,0);
    ans[1]=1;
    dfs(1,0);
    for(int i=1;i<=n;i++)cout<<ans[i]<<" \n"[i==n];

结论 ​

  • 能使得字符串s和t是子序列的最小长度为 ∣s∣+∣t∣−LCS(s,t)|s|+|t|-LCS(s,t)

Wenwei Lin · 2022 — 2025