XCPC Notes

Appearance

发布时间：2025-03-10

题目链接

I - Cyclic Apple Strings(思维) ​

在这里插入图片描述 每次可以把连续的一段1移到最后面，因此统计连续1的段数，特判最后一段1即可

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=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());
void solve(){ 
    string s;
    cin>>s;
    int cnt=0;
    bool f=false;
    for(int i=1;i<s.size();i++){
        if(s[i]<s[i-1]){
            f=true;
            break;
        }
    }
    if(!f){
        cout<<0<<"\n";
        return;
    }
    for(int i=0;i<s.size();i++){
        if(s[i]=='0')continue;
        cnt++;
        while(i+1<s.size()&&s[i+1]==s[i])i++;
    }
    cout<<cnt-(s.back()=='1')<<"\n";
}   
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    // cin>>T;
    while(T--)solve();
    return 0;
}

K - Party Games(结论) ​

在这里插入图片描述

⨁i=1ni={1,nmod  4=1n+1,nmod  4=20,nmod  4=3nnmod  4=0\bigoplus_{i=1}^n i= \begin{cases} 1, & n \mod 4=1 \\ n+1,& n \mod 4=2\\ 0,& n \mod 4=3\\ n & n \mod 4=0 \end{cases}

  • 因此只有nmod  4≤1n \mod 4 \leq 1是必胜的
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=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());
void solve(){ 
    int n;
    cin>>n;
    if(n%4==0||n%4==1)cout<<"Fluttershy\n";
    else cout<<"Pinkie Pie\n";
}   
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    cin>>T;
    while(T--)solve();
    return 0;
}

B - Countless Me(贪心) ​

在这里插入图片描述

  • 可以发现值可以任意分配给每位数
  • 二进制从高到低考虑，贪心填补总值，假设当前枚举到第ii位，那么看前i−1i-1位全部填11是否能将剩余的值填满，如果可以，该位可以不填11，否则该位必定产生贡献，贪心的把能填的11填进去
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=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());
void solve(){ 
    int n;
    cin>>n;
    vector<int> a(n);
    int s=0;
    for(auto &i:a)cin>>i,s+=i;
    int ans=0;
    for(int i=32;i>=0;i--){
        if(s>n*((1ll<<i)-1)){
            ans+=1ll<<i;
            int x=min(n,s/(1ll<<i));
            s-=x*(1ll<<i);
        }
    }
    cout<<ans<<"\n";
}   
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    // cin>>T;
    while(T--)solve();
    return 0;
}

F - Custom-Made Clothes(思维) ​

在这里插入图片描述

  • 假设ai,j>xa_{i,j}\gt x，那么ai,k>x,k∈[j,n]a_{i,k} \gt x, k \in[j,n]
  • 因此可以双指针维护，nn次询问就可以判断小于等于xx的数有多少个
  • 考虑二分答案，询问次数位为nlogn2nlogn^2,20000次左右足够询问
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=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 ask(int i,int j,int x){
    cout<<"? "<<i<<" "<<j<<" "<<x<<endl;
    cin>>i;
    return i;
}
void claim(int x){
    cout<<"! "<<x<<endl;
}
int n,k;
bool check(int mid){
    int cnt=0;
    for(int i=1,j=n;i<=n;i++){
        while(j>=1&&!ask(i,j,mid))j--;
        cnt+=j;
    }
    return cnt>=k;
}
void solve(){ 
    cin>>n>>k;
    k=n*n-k+1;
    int l=1,r=n*n;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    claim(l);
}   
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    // cin>>T;
    while(T--)solve();
    return 0;
}

M - Merge(思维) ​

题意：

x和x+1可以合成2x+1x和x+1可以合成2x+1，对数组进行操作，最大化数组(排序后的)的字典序

1≤n≤2e5,1≤ai≤1e181\leq n \leq 2e5,1 \leq a_i \leq 1e18

思路：

  • 可以发现合成是一个斐波那契式的迭代，因此对于是否能合成数xx,递归深度不会超过log⁡v,v为值域\log v,v为值域
  • 另一个重要的点是一个奇数和一个偶数生成一个奇数，因此偶数是不可再生的，因此递归时碰到偶数有就是有没有就是没有，不需对偶数递归，因此dfs求解答案可以从原来一个节点会产生两个分支变成一个分支
  • 因此可以从大到小考虑每个值是否参与合成
  • 复杂度O(nlog⁡v)O(n \log v)
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=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());
void solve(){ 
    int n;
    cin>>n;
    vector<int> a(n+1);
    map<int,int> mp,mp1;
    int mx=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        mp[a[i]]++;
    }
    sort(a.begin()+1,a.end(),greater<>());
    vector<int> ans;
    auto dfs=[&](auto dfs,int x){
        if(mp[x]){
            mp[x]--;
            mp1[x]++;
            return true;
        }
        if(x%2==0)return false;
        int a=x/2,b=x-a;
        if(dfs(dfs,a)&&dfs(dfs,b)){
            return true;
        }
        return false;
    };
    ranges::sort(ans,greater<>());
    for(int i=1;i<=n;i++){
        if(!mp[a[i]])continue;
        mp[a[i]]--;
        mp1.clear();
        if(dfs(dfs,a[i]+1)){
            mp[2*a[i]+1]++;
            continue;
        }
        for(auto [x,y]:mp1)mp[x]+=y;
        mp1.clear();
        if(dfs(dfs,a[i]-1)){
            mp[2*a[i]-1]++;
            continue;
        }
        for(auto [x,y]:mp1)mp[x]+=y;
        mp[a[i]]++;
    }
    for(auto [x,y]:mp)for(int i=1;i<=y;i++)ans.push_back(x);
    ranges::sort(ans,greater<>());
    cout<<ans.size()<<"\n";
    for(auto it:ans)cout<<it<<" ";
    cout<<"\n";
}   
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    // cin>>T;
    while(T--)solve();
    return 0;
}

D - ICPC(dp) ​

在这里插入图片描述

  • 首先如果不能回头吃其他的菜品，可以暴力n2n^2求出来
  • 其次考虑回头的问题，可以dp
  • dpi,jdp_{i,j}表示走到节点ii用了时间jj的最大值

dp_{i,j}=\max(dp_{i,j},dp_{i+1,j-1},dp_{i-1,j-1})

* 先枚举第二维，再枚举第一维转移即可 ```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=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()); void solve(){ int n; cin>>n; vector dp(n+1,vector<int>(2*n+1)); vector<int> a(n+1); for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++){ int sl=0,sr=0; for(int j=0;j<=2*n;j++){ if(i-j>=1)sl+=a[i-j]; if(i+j<=n)sr+=a[i+j]; dp[i][j]=max(sl,sr); } } for(int j=1;j<=2*n;j++){ for(int i=1;i<=n;i++){ if(i+1<=n)dp[i][j]=max(dp[i][j],dp[i+1][j-1]); if(i-1>=1)dp[i][j]=max(dp[i][j],dp[i-1][j-1]); } } int ans=0; for(int i=1;i<=n;i++){ int c=0; for(int j=1;j<=2*n;j++)c^=j*dp[i][j]; ans^=(c+i); } cout<<ans<<"\n"; } signed main(){ cin.tie(0)->sync_with_stdio(0); int T=1; // cin>>T; while(T--)solve(); return 0; } ``` # E - Boomerang(树的直径) ![在这里插入图片描述](/assets/img/remote/6d5c376aa0.png) ![在这里插入图片描述](/assets/img/remote/6d54cb93ab.png) ![在这里插入图片描述](/assets/img/remote/225bc2e6e4.png) * 假设对于确定的$k$最终结束的点集为$V(r,t)$，那么选取的出发点一定是直径的中点，这样离所有叶子节点的最大值最小 * 假设我们求出所有$t$对应的直径$D$,那么对于当前的$k$如果能覆盖掉对应的点集$V(r,t)$，需要满足$2k(t-t_0) \geq D$,随着$k$增大，满足条件的$t$减少，可以双指针求解答案 * 现在问题是如何求解每个$V(r,t)$的直径 * 假设一棵树，原本的直径为$u,v$，那么新加一个点$x$，直径如果变化，只会变成$u,x$或者$v,x$，因此我们需要一个可以查询树上两点距离的数据结构(LCA或者树剖) * $t$每增加$1$，点集扩散一层，相当于是对于深度相同的节点同时处理 * 复杂度$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 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 par[N][30],dep[N],n,r,t0,dis[N<<1]; vector<int> adj[N],g[N<<1]; void dfs(int u,int fa){ par[u][0]=fa; dep[u]=dep[fa]+1; for(int i=1;i<=__lg(dep[u]);i++)par[u][i]=par[par[u][i-1]][i-1]; for(auto v:adj[u]){ if(v==fa)continue; 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=25;i>=0;i--){ if(par[x][i]!=par[y][i])x=par[x][i],y=par[y][i]; } return par[x][0]; } int getdis(int x,int y){ return dep[x]+dep[y]-2*dep[lca(x,y)]; } void solve(){ cin>>n; for(int i=1;i<n;i++){ int u,v; cin>>u>>v; adj[u].push_back(v); adj[v].push_back(u); } cin>>r>>t0; dfs(r,0); for(int i=1;i<=n;i++){ g[dep[i]-1].push_back(i); } int d=0,x=r,y=r; for(int i=1;i<=2*n;i++){ for(auto v:g[i]){ int d1=getdis(x,v),d2=getdis(y,v); if(d1>d){ d=d1; y=v; } if(d2>d){ d=d2; x=v; } } dis[i]=d; } for(int k=1,t=n;k<=n;k++){ while((t-t0)*k*2>=dis[t])t--; while((t-t0)*k*2<dis[t])t++; cout<<t<<" "; } } signed main(){ cin.tie(0)->sync_with_stdio(0); int T=1; // cin>>T; while(T--)solve(); return 0; } ``` # G - Pack(EXGCD+整除分块) ![在这里插入图片描述](/assets/img/remote/6ee918316b.png) 线性同余方程好题，做完会对线性同余方程和整除分块有更深的理解 * $ax+by=k$可以用$exgcd$求出一组解 * 假设知道选择$x$个$A$个物品和$y$个$B$物品，那么答案就是$n+m-(x+y)\min(\lfloor \frac{n}{x} \rfloor,\lfloor \frac{m}{y} \rfloor)$ * 注意到后面的一坨是整除分块的形式 * 定义$x$为最小非负整数解，$y=\frac{k-ax}{b}$为对应的最大解,增长速率$dx=\frac{b}{\gcd(a,b)},dy=\frac{a}{\gcd(a,b)}$ * 通解$X=x+t\cdot dx,Y=y-t\cdot dy$ * 因为$y$此时为最大值，$x,y$均为非负整数，因此$t \in [0,\frac{y}{dy}]$ * 考虑先枚举$\lfloor \frac{n}{x} \rfloor$ * 假设当前整除分块的范围为$X=[l,r]$，那么此时的值$v=\lfloor \frac{n}{l} \rfloor$，那么另一边满足$Y \leq \lfloor \frac{m}{v} \rfloor=limit$的条件，此时$\frac{m}{Y} \geq v$ * 因此有$y-t\cdot dy \leq limit \rightarrow t \geq \lceil \frac{y-limit}{dy}\rceil$ * 对于$X$的范围，有$l \leq x+t \cdot dx \leq r \rightarrow t \geq \lceil\frac{l-x}{dx}\rceil \land t \leq \lfloor \frac{r-x}{dx} \rfloor$ * 对上面所有式子求出满足t的范围$[L,R]$,如果$dx-dy \geq 0$,t选择最大值即$R$否则为$L$ * 做完上面的反过来枚举一遍$\lfloor \frac{m}{y} \rfloor$ ```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 exgcd(int a,int b,int &x,int &y){ if(!b){ x=1,y=0; return a; } int d=exgcd(b,a%b,y,x); y-=a/b*x; return d; } void solve(){ int n,m,a,b,k; cin>>n>>m>>a>>b>>k; int x,y; int g=exgcd(a,b,x,y); if(k%g!=0){ cout<<n+m<<"\n"; return; } x*=k/g,y*=k/g; int dx=b/g,dy=a/g; int ans=0; x=(x%dx+dx)%dx; y=(k-a*x)/b; int t=y/dy; auto work=[&](int n,int m,int dx,int dy,int x,int y){ for(int l=1,r;l<=n;l=r+1){ r=n/(n/l); int v=n/l; int lim=m/v; // y-t*dy<=lim ==> t>=(y-lim)/dy // l<=x+t*dx<=r ==> t>=(l-x)/dx && t<=(r-x)/dx if(x>r)continue; int L=max({0ll,(y-lim+dy-1)/dy,(l-x+dx-1)/dx}); int R=min(t,(r-x)/dx); if(L<=R){ ans=max(ans,(x+L*dx+y-L*dy)*v); ans=max(ans,(x+R*dx+y-R*dy)*v); } } }; if(a*x>k){ cout<<n+m<<"\n"; return; } work(n,m,dx,dy,x,y); // cout<<ans<<"\n"; y=(y%dy+dy)%dy; x=(k-b*y)/a; work(m,n,dy,dx,y,x); cout<<n+m-ans<<"\n"; } signed main(){ cin.tie(0)->sync_with_stdio(0); int T=1; cin>>T; while(T--)solve(); return 0; } ```

Wenwei Lin · 2022 — 2025