Hide-And-Seek Game

题目大意

给定一个树，m组询问，每次询问给定四个数，Serenade从开始走到，再从开始走到，如此循环往复。Rhapsody同时从开始走到，再从开始走到，如此循环往复。输出他们第一次相遇的结点，若永远不会相遇则输出

解题思路

先找出从到的路径与到路径相交的结点，分别表示Serenade和Rhapsody到这些结点的时间。
如到的路径中有一点u，则（从向方向经过该点）或（从向方向经过该点）()

同理，到的路径中有一点v，则（从向方向经过该点）或（从向方向经过该点）()

因此我们还要用预处理出到的距离和到的距离以及到的距离和到的距离

令两人在相遇，则有四种可能：

每个方程都可以转化为的形式，找到每组解的最小非负整数解或返回解不存在

我们取其中一种情况：

即：

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

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

求解更一般的方程

设，当且仅当时有解即

通解=特解+齐次解

特解：

1
2
3
4
5
6
7
8
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

齐次解：

即的解

通解：

通解=特解+齐次解

令,则对于x的最小非负整数解为

令,则对于y的最小非负整数解为

复杂度分析

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

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#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状态机模型（状态转移只考虑它的节点）

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

易得结论：当时，最多一组物品数量为；否则为。

复杂度分析

时间复杂度：O(1)

参考代码

1
2
3
4
5
6
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区间的每个数都变成ai=|ai-xj|,

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

解题思路

用线段树维护。

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

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

其中，当，，直接懒标记维护即可。

当，，即将取相反数加上x，叠加情况后发现如以下情况操作了j-1次时：

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

易得：

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

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

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

时间复杂度线性

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#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;
}