2023杭电多校第一场

Hide-And-Seek Game

题目大意

给定一个树，m组询问，每次询问给定四个数$S\mathrm{\_}a,T\mathrm{\_}a,S\mathrm{\_}b,T\mathrm{\_}b$，Serenade从$S\mathrm{\_}a$开始走到$T\mathrm{\_}a$，再从$T\mathrm{\_}a$开始走到$S\mathrm{\_}a$，如此循环往复。Rhapsody同时从$S\mathrm{\_}b$开始走到$T\mathrm{\_}b$，再从$T\mathrm{\_}b$开始走到$S\mathrm{\_}b$，如此循环往复。输出他们第一次相遇的结点，若永远不会相遇则输出$-1$

解题思路

先找出从$S\mathrm{\_}a$到$T\mathrm{\_}a$的路径与$S\mathrm{\_}b$到$T\mathrm{\_}b$路径相交的结点，分别表示Serenade和Rhapsody到这些结点的时间。
如$S\mathrm{\_}a$到$T\mathrm{\_}a$的路径中有一点u，则$t\mathrm{\_}u1=dist(S\mathrm{\_}a,u)+k\mathrm{\_}1\times 2dist(S\mathrm{\_}a,T\mathrm{\_}a)$（从$S\mathrm{\_}a$向$T\mathrm{\_}a$方向经过该点）或$t\mathrm{\_}u2=2\times dist(S\mathrm{\_}a,T\mathrm{\_}a)-dist(S\mathrm{\_}a,u)+k\mathrm{\_}2\times 2dist(S\mathrm{\_}a,T\mathrm{\_}a)$（从$T\mathrm{\_}a$向$S\mathrm{\_}a$方向经过该点）($k\mathrm{\_}1,k\mathrm{\_}2\in Z^{+}$)

同理，$S\mathrm{\_}b$到$T\mathrm{\_}b$的路径中有一点v，则$t\mathrm{\_}v1=dist(S\mathrm{\_}b,v)+k\mathrm{\_}3\times 2dist(S\mathrm{\_}b,T\mathrm{\_}b)$（从$S\mathrm{\_}b$向$T\mathrm{\_}b$方向经过该点）或$t\mathrm{\_}v2=2\times dist(S\mathrm{\_}b,T\mathrm{\_}b)-dist(S\mathrm{\_}b,v)+k\mathrm{\_}4\times 2dist(S\mathrm{\_}b,T\mathrm{\_}b)$（从$T\mathrm{\_}b$向$S\mathrm{\_}b$方向经过该点）($k\mathrm{\_}3,k\mathrm{\_}4\in Z^{+}$)

因此我们还要用$bfs$预处理出$u$到$S\mathrm{\_}a$的距离和$S\mathrm{\_}a$到$T\mathrm{\_}a$的距离以及$u$到$S\mathrm{\_}b$的距离和$S\mathrm{\_}b$到$T\mathrm{\_}b$的距离

令两人在$u,v$相遇，则有四种可能：

$$t\mathrm{\_}u1=t\mathrm{\_}v1\$\$\mathrm{或}\$\$t\mathrm{\_}u2=t\mathrm{\_}v1\$\$\mathrm{或}\$\$t\mathrm{\_}u1=t\mathrm{\_}v2\$\$\mathrm{或}\$\$t\mathrm{\_}u2=t\mathrm{\_}v2$$

每个方程都可以转化为$a\times x+b\times y=c$的形式，找到每组解的最小非负整数解$k\mathrm{\_}x,k\mathrm{\_}y$或返回解不存在

我们取其中一种情况：

$$t\mathrm{\_}u1=t\mathrm{\_}v1\Rightarrow dist(S\mathrm{\_}a,u)+k\mathrm{\_}1\times 2dist(S\mathrm{\_}a,T\mathrm{\_}a)=dist(S\mathrm{\_}b,v)+k\mathrm{\_}3\times 2dist(S\mathrm{\_}b,T\mathrm{\_}b)$$$$\Rightarrow 2dist(S\mathrm{\_}a,T\mathrm{\_}a)\times k\mathrm{\_}1+(-2dist(S\mathrm{\_}b,T\mathrm{\_}b))\times k\mathrm{\_}3=dist(S\mathrm{\_}b,v)-dist(S\mathrm{\_}a,u)$$

即：$a=2dist(S\mathrm{\_}a,T\mathrm{\_}a),x=k_1,b=(-2dist(S\mathrm{\_}b,T\mathrm{\_}b)),y=k\mathrm{\_}3,c=dist(S\mathrm{\_}b,v)-dist(S\mathrm{\_}a,u)$

因为要求第一次相遇，$t$应该尽可能小，所以$k1,k2$应该尽可能小所以取最小非负整数解。

套入扩展欧几里得模板即可：

求解更一般的方程$ax+by=c$

设$d=gcd(a,b)$，当且仅当$d|c$时有解即$cmodgcd(a,b)=0$

通解=特解+齐次解

特解：

$$x^{\prime }=x\mathrm{\_}0\times c/d,y^{\prime }=y\mathrm{\_}0\times c/d$$

int exgcd(int a,int b,int &x,int &y);//函数同上
int a,b,x0,y0,x,y;cin>>a>>b;
int d=exgcd(a,b,x0,y0);
x1=x0\times c/d,y1=y0\times c/d;
//x0和y0为ax+by=gcd(a,b)的一组解
//x1和y1为ax+by=c的一组特解
通解：
x=x1+k\times b/d,y=y1-k\times a/d,k∈z

齐次解：

即$ax+by=0$的解

通解：

通解=特解+齐次解

$$x=x^{\prime }+k\times b/d,y=y^{\prime }-k\times a/d,k\in z$$

令$t=b/d(x=x^{\prime }+kt)$,则对于x的最小非负整数解为$(x^{\prime }modt+t)modt$

令$t^{\prime }=a/d(y=y^{\prime }+kt)$,则对于y的最小非负整数解为$(y^{\prime }mod{t}^{\prime }+t^{\prime })mod{t}^{\prime }$

复杂度分析

时间复杂度：O(n+m)

参考代码

#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
#define x1 x111111
#define y1 y111111
#define x0 x00000
#define y0 y00000
/*====================*/
typedef long long ll;
typedef pair<int,int> pii;
/*====================*/
const double eps=1e-8;
/*====================*/
bool multi=1;
int n,m;
vector<vector<int>> edge;

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;
}

int check(int a1,int b1,int a2,int b2){
    int a=b1,b=-b2,c=a2-a1,x0,y0;
    int d=__gcd(a,b);
    if(c%d!=0) return 1e9;//永远不会相遇
    exgcd(a,b,x0,y0);
    int x1=x0*c/d,y1=y0*c/d;
    int ta=abs(b/d);
    int tb=abs(a/d);
    int xp=(x1%ta+ta)%ta;//xp为最小非负整数
    return a1+b1*xp;
}

int query(int sa,int ta,int sb,int tb){
    vector<int> disa(n+1),disb(n+1),from(n+1);
    //disa[i],disb[i]分别存储从i到sa和sb的最短距离
    //from[i]表示从sa到ta或sb到tb的路径中i的前一个结点是谁
    vector<bool> sta(n+1),stb(n+1);
    //sta[i],stb[i]分别表示i是否在sa到ta路径中,sb到tb路径中

    //从start开始bfs到end结束，处理出dis数组和from数组
    auto bfs=[&](int start,int end,vector<int>&dis,vector<int>&from){
        queue<int> q;
        q.push(start);
        while(q.size()){
            int u=q.front();
            // cout<<u<<endl;
            q.pop();
            for(auto v:edge[u]){
                if(v==from[u]) continue;
                from[v]=u;//这里的from数组表示从start到end的路径中i的前一个结点是谁
                dis[v]=dis[u]+1;
                q.push(v);
                if(v==end){
                    while(q.size()) q.pop();
                    break;
                }
            }
        }
    };

    bfs(sa,ta,disa,from);

//将所有sa到ta路径经过的点存入patha中
    vector<int> patha;
    int cur=ta;
    while(1){
        sta[cur]=true;
        patha.push_back(cur);
        if(cur==sa) break;
        cur=from[cur];
    }

    for(int i=1;i<=n;i++) from[i]=0;
    bfs(sb,tb,disb,from);
    
//将从sb到tb路径上的点标记到stb数组
    cur=tb;
    while(1){
        stb[cur]=true;
        if(cur==sb) break;
        cur=from[cur];
    }

    int dza=disa[ta],dzb=disb[tb];
    int res=1e9,ver;//res记录最早相遇时间,ver记录相遇时间最早的顶点
    for(auto i:patha){
        if(!stb[i]) continue;
        int da=disa[i],db=disb[i];
        int a1=da,b1=2*dza,a2=2*dza-da,b2=b1;
        int a3=db,b3=2*dzb,a4=2*dzb-db,b4=b3;
        //分别对t_{u1}=t_{v1},t_{u2}=t_{v1},t_{u1}=t_{v2},t_{u2}=t_{v2}进行check找到最早相遇时间和对应的顶点
        int val=min({check(a1,b1,a3,b3),check(a1,b1,a4,b4),check(a2,b2,a3,b3),check(a2,b2,a4,b4)});
        if(res>val){
            res=val;
            ver=i;
        }
    }
    if(res==1e9){
        return -1;
    }else{
        return ver;
    }
}

void solve(){
    cin>>n>>m;
    edge.clear();
    edge.resize(n+1);
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    while(m--){
        int sa,ta,sb,tb;
        cin>>sa>>ta>>sb>>tb;
        cout<<query(sa,ta,sb,tb)<<endl;
    }
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}

City Upgrading

题目大意

给定一个树和树上每个结点放置路由器的成本，每个路由器可以覆盖当前结点及其相邻的节点，输出最低成本使所有结点被覆盖。

解题思路

dp状态机模型（状态转移只考虑它的节点）

$$\text{You can't use 'macro parameter character \#' in math mode}$$

每组相等情况下最多每组分到$a$个，剩下$d$个物品，最坏情况下每组一个，分完为止。

易得结论：当$n|m$时，最多一组物品数量为$m/n$；否则为$m/n+1$。

复杂度分析

时间复杂度：O(1)

参考代码

void solve(){
    int n,m,d;
    cin>>n>>m>>d;
    if(m/n+(m%n!=0)>=d) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Easy problem I

题目大意

给定一个长度为n的序列，q次操作。

操作1：将l~r区间的每个数$a_i$都变成ai=|ai-xj|,$x_j\le x_{j+1}$

操作2：询问l~r的区间和。

解题思路

用线段树维护。

修改操作中，将数列分为两块进行维护，一块是ai出现过小于xj情况的数，还有一块是一直都大于等于xj的数。

由于每次修改操作中的xj不递减，小于xj的数在接下来的操作中不会出现大于xj的情况，而原来大于等于xj的数接下来可能会小于xj，我们直接把他的相关信息修改成小的那块。

其中，当$a\mathrm{\_}i\ge x$，$a[i]=a[i]-x$，直接懒标记维护即可。

当$ai<i$，$a[i]=x-a[i]$，即将$a[i]$取相反数加上x，叠加情况后发现如以下情况操作了j-1次时：

$$\text{You can't use 'macro parameter character \#' in math mode}$$

这里我们先规定根节点为1，然后用换根来O（1）改变结点。我们先求出每棵子树的sg值记作fs[u],因为要求以所有树为根的sg值，所以为了实现换根，我们需要再求出每个结点父亲方向上的sg值记作ff[u]。

易得：$ff[u]=fs[fa]\oplus (fs[u]+1)\oplus (ff[fa]+1)$

这里$ff[1]$要设置为-1，因为1没有父亲，根据上面解释，有一个点时sg值为0，这里用-1表示没有点。

求完后先计算1，然后换根每个点的sg值累加答案。

概率就是获胜点数/总点数

时间复杂度线性

参考代码

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define endl '\n'

bool multi=1;
int n,m;
vector<vector<int>> edge;
const int N = 2e5 + 10;
int ff[N],fs[N];

const int mod=1e9+7;
i64 qpow(i64 a, int k, int p){
    i64 res = 1 % p;
    while(k){
        if(k & 1) res = res * a % p;
        a = a * a % p;
        k >>= 1;
    }
    return res;
}

void dfs1(int u,int fa){
    fs[u]=0;
    for(auto v:edge[u]){
        if(v==fa) continue;
        dfs1(v,u);
        fs[u]^=fs[v]+1;
    }
}

void dfs2(int u,int fa){
    if(u==1) ff[u]=-1;
    else ff[u]=fs[fa]^(fs[u]+1)^(ff[fa]+1);
    for(auto v:edge[u]){
        if(v==fa) continue;
        dfs2(v,u);
    }
}

void solve(){
    cin>>n;
    edge.clear();
    edge.resize(n+1);
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    dfs1(1,0);//求fs
    dfs2(1,0);//求ff
    i64 ans=0;
    if(fs[1]) ans++;
    for(int i=2;i<=n;i++){
        if(fs[i]^(ff[i]+1)) ans++;
    }
    cout << ans * qpow(n, mod - 2, mod) % mod << '\n';
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T=1;
    if(multi) cin>>T;
    while(T--){
        solve();
    }

    return 0;
}