2.17

Unnamed114514 · 2025-02-19 15:48:40 · 个人记录

A. CF1710D Recover the Tree

容易想到按照区间大小合并，因为 [l,r-1] 的限制显然比 [l,r] 的限制更严格，参考 l 到 r-2 的链后接上 r 再接上 r-1，此时不满足 [l,r-1] 但是满足 [l,r]。

容易发现，在任意时刻，所有的连通块一定呈区间的形式。

于是我们先求出 l,r 所在的区间。

如果它们在同一个区间里，那么它们就已经在一个连通块里了，此时不操作即可。

否则我们我们假设 l 在区间 i_1，r 在区间 i_k，区间 i 为 [L_i,R_i]。

若 k=2，那么只需要向 l,r 连边即可，否则无论怎么连，[l,r] 都会少元素。

先考虑一个简单的情况，只有 [1,n] 为联通块（单元素区间不考虑），那么我们只需要让 1 向 3,\cdots,n 连边，2 向 n 连边即可。

那么类似地，我们只需要让 l 向 r 连边，R_{i_2} 向 r 连边，R_{i_3,\cdots,i_{k-1}} 向 l 连边即可。

注意单次操作完之后区间会合并，上述操作只涉及到了 R，那么相当于我们要维护一个能支持动态删除 R 的数据结构，vector 即可，因为每个元素只会删除一次，单次删除最多 O(n)，所以总的复杂度为 O(n^2)。然后你的所有的迭代器在遍历过一次之后都会删除，所以这里是 O(n) 的。

其实你会发现讨论了那么多，代码其实很简单。

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=2005;
int T,n;
char c[N][N];
vector<int> v;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n;
        for(int l=1;l<=n;++l) for(int r=l;r<=n;++r) cin>>c[l][r];
        v.clear(),v.shrink_to_fit(),v.emplace_back(0);
        for(int i=1;i<=n;++i) v.emplace_back(i);
        for(int len=1;len<=n;++len) for(int l=1,r=len;r<=n;++l,++r){
            if(c[l][r]=='1'){
                auto itl=lower_bound(v.begin(),v.end(),l),itr=lower_bound(v.begin(),v.end(),r);
                for(auto it=itl;it<itr;++it){
                    if(it==itl) cout<<l<<' '<<r<<endl;
                    else if(it==itl+1) cout<<r<<' '<<(*it)<<endl;
                    else cout<<l<<' '<<(*it)<<endl;
                }
                v.erase(itl,itr);
            }
        }
    }
    return 0;
}

D. CF1844G Tree Weights

题目等价于给出 dep_i+dep_{i-1}-2dep_{LCA(i,i-1)}=dis_i，显然直接解方程是不显示的。

注意到 LCA(i,i-1) 这一坨的系数是 2，我们先对原式模 2，就能得到 dep_i 的奇偶性。注意到 2\Delta\bmod 2^p=2(\Delta\bmod 2^{p-1})，那么我们就在得到模 2 之后带入模 4 的式子算即可，此时 2dep_{LCA(i,i-1)} 是已知值，那么就可以继续递归求解。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,d[N],siz[N],son[N],dep[N],fa[N],top[N],lca[N],f[2][N],u[N],v[N];
vector<int> G[N];
void dfs1(int u){
    siz[u]=1;
    for(auto v:G[u]){
        if(v==fa[u]) continue;
        dep[v]=dep[u]+1,fa[v]=u;
        dfs1(v);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]]) son[u]=v;
    }
}
void dfs2(int u,int t){
    top[u]=t;
    if(son[u]) dfs2(son[u],t);
    for(auto v:G[u]){
        if(v==son[u]||v==fa[u]) continue;
        dfs2(v,v);
    }
}
int LCA(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]>dep[top[v]]) swap(u,v);
        v=fa[top[v]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    return u;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<n;++i){
        cin>>u[i]>>v[i];
        G[u[i]].emplace_back(v[i]);
        G[v[i]].emplace_back(u[i]);
    }
    for(int i=2;i<=n;++i) cin>>d[i];
    dfs1(1),dfs2(1,1);
    for(int i=1;i<n;++i) if(dep[u[i]]>dep[v[i]]) swap(u[i],v[i]);
    for(int i=2;i<=n;++i) lca[i]=LCA(i,i-1);
    for(int i=1;i<=60;++i){
        f[i&1][1]=0;
        for(int j=2;j<=n;++j) f[i&1][j]=(d[j]-f[i&1][j-1]+2*f[i-1&1][lca[j]]+(1ll<<i))%(1ll<<i);
    }
    for(int i=1;i<n;++i) if(f[0][v[i]]<=f[0][u[i]]){
        cout<<-1<<endl;
        return 0;
    }
    for(int i=2;i<=n;++i) if(f[0][i]+f[0][i-1]-(f[0][lca[i]]<<1)!=d[i]){
        cout<<-1<<endl;
        return 0;
    }
    for(int i=1;i<n;++i) cout<<f[0][v[i]]-f[0][u[i]]<<endl;
    return 0;
}

C. P6860 象棋与马

先来考虑 p(a,b) 的性质。

首先能到达整个棋盘等价于能到达 (0,1)，那么我们设 4 种移动状态（(+a,+b),(+a,-b),(-a,+b),(-a,-b)）次数分别为 a_1,a_2,a_3,a_4，那么有：

这个系数似乎观察不出什么规律，我们令 x=a_1-a_4,y=a_2-a_3，然后拆括号，化简有：

两边相加知：

首先有个非常简单的容斥：

因为 b 是偶数所以 a 显然不是偶数，那么我们继续，令 s(n,m)=\sum\limits_{a=1}^{n}\sum\limits_{b=1}^m[\gcd(a,b)=1]，有：

你会发现后边这一坨其实就是等价于 f 的一个子问题，那么有：f(n,m)=s(\lfloor\dfrac{n}{2}\rfloor,m)-f(m,\lfloor\dfrac{n}{2}\rfloor)。

现在还剩下 s 的求解，套用莫反知：

考虑枚举 \gcd，有：

整除分块即可，对于 \mu(d) 的前缀和可以用杜教筛求解，具体的时间复杂度其实就是一个多次查询的杜教筛，应该是 O(n^{\frac{2}{3}}) 的。

#include<bits/stdc++.h>
#define int unsigned long long
#define endl '\n'
using namespace std;
const int N=1e7+5,INF=1e7;
int T,n,prime[N],cnt,Smu[N];
bool flg[N];
unordered_map<int,int> mp_mu;
void Euler(int n){
    Smu[1]=1,flg[1]=1;
    for(int i=2;i<=n;++i){
        if(!flg[i]){
            Smu[i]=-1;
            prime[++cnt]=i;
        }
        for(int j=1;j<=cnt&&i*prime[j]<=n;++j){
            flg[i*prime[j]]=1;
            if(i%prime[j]==0){
                Smu[i*prime[j]]=0;
                break;
            }
            Smu[i*prime[j]]=-Smu[i];
        }
    }
    for(int i=2;i<=n;++i) Smu[i]+=Smu[i-1];
}
int Sum_mu(int n){
    if(n<=INF) return Smu[n];
    if(mp_mu.count(n)) return mp_mu[n];
    int ans=1;
    for(int l=2,r;l<=n;l=r+1){
        r=n/(n/l);
        ans-=(r-l+1)*Sum_mu(n/l);
    }
    return mp_mu[n]=ans;
}
int s(int n,int m){
    int ans=0;
    for(int l=1,r;l<=min(n,m);l=r+1){
        r=min(n/(n/l),m/(m/l));
        ans+=(Sum_mu(r)-Sum_mu(l-1))*(n/l)*(m/l);
    }
    return ans;
}
int f(int n,int m){
    if(n==1) return 0;
    if(m==1) return n/2;
    return s(n/2,m)-f(m,n/2);
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    Euler(INF);
    cin>>T;
    while(T--){
        cin>>n;
        cout<<f(n,n)*2<<endl;
    }
    return 0;
}

E. CF878D Magic Breeding