Butteruni Blog
0%

2023杭电暑期多校1（I E L B A）

发表于 更新于 分类于

题目链接

难度排序：I，LBE，A

I. Assertion

鸽巢原理

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
#include <iostream>
using namespace std;
int main()
{
        ios::sync_with_stdio(0);
        cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        long long n, m, d;
        cin >> n >> m >>d;
        if(m % n == 0)
        {
            if(m / n >= d)
            {
                cout << "Yes\n";
            }
            else
            {
                cout << "No\n";
            }
        }
        else
        {
            if(m / n + 1 >= d)
            {
                cout << "Yes\n";
            }
            else
            {
                cout << "No\n";
            }
        }
    }
    return 0;
}

B. City Upgrading

树形dp，定义 为覆盖以 为根子树的花费(不含 )， 为覆盖以 为根子树的花费且选取 作为一个router(包含 )， 为覆盖以 为根子树的花费且不选取 作为一个router(包含 )，对每次转移有以下递推式： 对于 ，只有当选取过 后才能从 转移过来，因此初值赋为INF

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
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef long long ll;
int e[N << 1],ne[N << 1],h[N],idx;
ll dp[N][5];
ll cost[N];
void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
void dfs(int cur,int fa)
{
//     cout << cur <<endl;
    dp[cur][0] = dp[cur][1] = dp[cur][2] = 0;
    dp[cur][1] = cost[cur],dp[cur][2] = 1e10;
    for(int i = h[cur];i != -1;i = ne[i])
    {
        int j = e[i];
        if(j == fa)
            continue;
        dfs(j,cur);
        dp[cur][2] = min(dp[cur][2] + min(dp[j][1],dp[j][2]),dp[cur][0] + dp[j][1]);
        dp[cur][0] += dp[j][2];
        dp[cur][1] += min(min(dp[j][0],dp[j][1]),dp[j][2]);
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        memset(h,-1,sizeof(h));
        idx = 0;
        for(int i = 1;i <= n;++i)
        {
            cin >> cost[i];
        }
        for(int i = 1;i < n;++i)
        {
            int u,v;
            cin >> u >> v;
            add(u,v);
            add(v,u);
        }
        dfs(1,-1);
        cout << min(dp[1][2],dp[1][1]) << '\n';
    }
}

L. Cyclically Isomorphic

对每次询问，若 可由 移动得到，则 为 字串。于是直接暴力KMP即可

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
#include <bits/stdc++.h>
using namespace std;
int t,n,m,q;
void getNext(string p,vector<int> ne)
{
    int m=p.length()-1;
    for(int i=2,j=0;i<=m;i++)
    {
        while(j&&p[i]!=p[j+1])j=ne[j];
        if(p[i]==p[j+1])j++;
        ne[i]=j;
    }
}

// 匹配
bool KMP(string s,string p,vector<int> ne)
{
    int n=s.length()-1,m=p.length()-1;
    for(int i=1,j=0;i<=n;i++)
    {
        while(j&&s[i]!=p[j+1])j=ne[j];
        if(s[i]==p[j+1])j++;
        if(j==m)
        {
            j=ne[j];
           return 1;
        }
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> t;
    while(t--)
    {
        cin >> n >> m;
        vector <string> s(n + 10);
        vector <vector<int> > ne(n + 10);
        for(int i = 1;i <= n;++i)
        {
            cin >> s[i];
            ne[i].resize(m + 10);
            getNext(" " + s[i],ne[i]);
        }
        cin >> q;
        map<pair<int,int>,int>vis;
        while(q--)
        {
            int x,y;
            cin >> x >> y;
            if(vis[make_pair(x,y)])
            {
                if(vis[make_pair(x,y)] == 1)
                    cout << "Yes" << '\n';
                else 
                    cout << "No" << '\n';
            }else 
            {
                if(KMP(" " + s[x] + s[x]," " + s[y],ne[y]) || KMP(" " + s[y] + s[y]," " + s[x],ne[x]))
                {
                    cout << "Yes" << '\n';
                    vis[make_pair(x,y)] = 1;
                    vis[make_pair(y,x)] = 1;
                }else 
                {
                    cout << "No" << '\n';
                    vis[make_pair(x,y)] = -1;
                    vis[make_pair(y,x)] = -1;
                }
            }
        }
    }
}

E. Play on Tree

先考虑在固定根节点情况下如何判断胜负，先固定 为根节点，对于以 为根的子树，获胜函数 于是先以 为根遍历一遍图，接下来计算分别以各个点为根的获胜情况，重新遍历一遍图，对于当前走到的点 ，由于已经计算好 和 前者表示以 为根的获胜情况，后者表示为第一次dfs时以 为子树的获胜情况，于是有 其中 表示以 为根节点， 为根的子树获胜情况。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int N = 2e5 + 10;
int ne[N << 1],e[N << 1],h[N],idx;
int sg[N],sg_1[N];
int sum;
void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
ll qpow(ll a,ll b)
{
    ll res = 1;
    while(b)
    {
        if(b & 1)
            res =res  * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res ;
}
void dfs_root(int cur,int fa)
{
    for(int i = h[cur];i != -1;i = ne[i])
    {
        int j = e[i];
        if(j == fa)
            continue;
        dfs_root(j,cur);
        sg[cur] ^= (sg[j] + 1);
    }
    sg_1[cur] = sg[cur];
}
void dfs(int cur ,int fa)
{
    if(cur != 1)
    {
        sg_1[cur] ^= ((sg_1[fa] ^ (sg[cur] + 1)) + 1);
    }
    for(int i = h[cur];i != -1;i = ne[i])
    {
        int j = e[i];
        if(j == fa)
            continue;
        dfs(j,cur);
    }
    if(sg_1[cur] != 0 && cur != 1)
        sum++;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        sum = 0;
        idx = 0;
        for(int i = 0;i <= n;++i)
        {
            h[i] = -1;
            sg[i] = sg_1[i] = 0;
        }
        for(int i = 1;i < n;++i)
        {
            int u,v;
            cin >> u >> v;
            add(u,v);
            add(v,u);
        }
        dfs_root(1,0);
        if(sg[1] == 0)
                sum = 0;
        else 
                sum = 1;
        dfs(1,0);
//         cout << sum << endl;
        cout << sum * qpow(n,mod - 2) % mod << endl;
    }
}

A. Hide-And-Seek Game

利用lca求出 ， 两条路径，由于两者只会在同一点相遇，枚举两条路径上公共点，分别计算在这个点相遇需要的时间，求时间的过程可转化为求解 其中 分别表示整条路径的两倍长（从起点回到起点）， 则根据双方是从起点还是终点走到公共点有4种情况，最终时间为 每次询问输出最小用时公共点即可。

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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
#include <bits/stdc++.h>
using namespace std;
const int N = 3e3 + 10;
typedef long long ll;
int ne[N << 1],e[N << 1],h[N],idx;
int t,n,m;
int anc[N][25],depth[N];
bool vis[N];
void init(int n)
{
    idx = 0;
    for(int i = 0;i <= n;++i)
    {
        h[i] = -1;
        depth[i] = 0;
        vis[i] = 0;
    }
    for (int j = 1; j <= log2(n); j++)
    {
        for (int i = 1; i <= n; i++)
        {
            anc[i][j] = anc[anc[i][j - 1]][j - 1];
        }
    }
}
void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
void dfs(int u,int p)
{
//     cout << u << endl;
    depth[u] = depth[p] + 1;
    anc[u][0]=p;
    vis[u] = 1;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int v=e[i];
        if(!vis[v])
            dfs(v,u);
    }
    return;
}
void up(int &u,int h)
{
    for(int i=0;h>0;i++)
    {
        if(h&1)
        {
            u=anc[u][i];
        }
        h>>=1;
    }
    return;
}
int lca(int u,int v)
{
    if (depth[u] < depth[v])
    {
        swap(u,v);
    }
    up(u, depth[u] - depth[v]);
    if (u == v)
    {
        return u;
    }
    for (int i = 13; i >= 0; i--)
    {
        if (anc[u][i] == anc[v][i])
            continue;
        u = anc[u][i];
        v = anc[v][i];
    }
    return anc[u][0];
}
//扩展欧几里得求逆元 若a*x≡1(mod b),a,b互质,则称x为a的逆元 ax0+by0=gcd(a,b)=1 ps:gcd(a,b)不为1说明逆元不存在,若为1,调整x0到0~m-1的范围中即可
ll exgcd(ll a,ll b,ll& x,ll& y) 
{
	if(!b) 
	{
  		x=1;
  		y=0;
  		return a;
 	}
 	ll k=exgcd(b,a%b,y,x);
 	y-=a/b*x;
 	return k;
}
int calc(int a,int b,int c)
{
    ll x,y;
    ll t = exgcd(a,b,x,y);
    if(c % t != 0)
        return -1;
    x *= c / t;
    b /= t;
    if(b < 0)
        b = -b;
    return (x % b + b) % b;
}
int calc_dis(int x,int y)
{
    int temp = lca(x,y);
    return depth[x] + depth[y] - 2 * depth[temp];
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> t;
    while(t--)
    {
        cin >> n >> m;
        init(n + 1);
        for(int i = 1;i < n;++i)
        {
            int u,v;
            cin >> u >> v;
            add(u,v);
            add(v,u);
        }
        dfs(1,0);
        for(int j = 1;(1 << j) < n;++j)
        {
            for(int i = 1;i <= n;++i)
            {
                if(anc[i][j - 1] != -1)
                {
                    anc[i][j] = anc[anc[i][j - 1]][j - 1];
                }
            }
        }
        while(m--)
        {
            int s_a,t_a,s_b,t_b;
            cin >> s_a >> t_a >> s_b >> t_b;
            map<int,int>route;
            int lca_a = lca(s_a,t_a),lca_b = lca(s_b,t_b);
            // cout << lca_a << " " << lca_b << endl;
            bool flag = 0;
            for(int i = s_a;i != lca_a;i = anc[i][0])
            {
                route[i] = 1;
                if(i == t_a)
                {
                    flag = 1;
                    break;
                }
            }
            if(!flag)
            {
                for(int i = t_a;i != lca_a;i = anc[i][0])
                {
                    route[i] = 1;
                }
                route[lca_a] = 1;
            }
            flag = 0;
            vector<int>same;
            for(int i = s_b;i != lca_b;i = anc[i][0])
            {
                if(route.count(i))
                {
                    same.push_back(i);
                }
                if(i == t_b)
                {
                    flag = 1;
                    break;
                }
            }
            if(!flag)
            {
                for(int i = t_b;i != lca_b;i = anc[i][0])
                {
                    if(route.count(i))
                    {
                        same.push_back(i);
                    }
                }
                if(route.count(lca_b))
                {
                    same.push_back(lca_b);
                }
            }
            int cnt = same.size();
//             cout << cnt << endl;
            int tim = 1e9,ans_node = -1;
            for(int i = 0;i < cnt;++i)
            {
                cout << same[i] << " ";
                int dis1 = calc_dis(s_a,same[i]);
                int dis2 = calc_dis(t_a,same[i]);
                int dis3 = calc_dis(s_b,same[i]);
                int dis4 = calc_dis(t_b,same[i]);
                int route_a = 2 * (dis1 + dis2);
                int route_b = 2 * (dis3 + dis4);
                int ans = calc(route_a,-route_b,dis3 - dis1); //分别从s_a,s_b走到这个点,这个过程中a走了几趟。
                if(ans != -1)
                {
                    if((ans * route_a + dis1) < tim)
                    {
                        tim = ans * route_a + dis1;
                        ans_node = same[i];
                    } 
                }
                ans = calc(route_a,-route_b,dis3 + dis1 - route_a); //分别从t_a,s_b走到这个点;
                if(ans != -1)
                {
                    if((ans * route_a + dis1 + 2 * dis2) < tim)
                    {
                        tim = ans * route_a + dis1 + 2 * dis2;
                        ans_node = same[i];
                    }
                }
                ans = calc(route_a,-route_b,route_b - dis3 + dis1 - route_a); //分别从t_a,t_b走到这个点
                if(ans != -1)
                {
                    if((ans * route_a + dis1 + 2 * dis2) < tim)
                    {
                        tim = ans * route_a + dis1 + 2 * dis2;
                        ans_node = same[i];
                    }
                }
                ans = calc(route_a,-route_b,route_b - dis3 - dis1);//分别从s_a,t_b走到这个点
                if(ans != -1)
                {
                    if((ans * route_a + dis1) < tim)
                    {
                        tim = ans * route_a + dis1;
                        ans_node = same[i];
                    } 
                }
            }
            cout << ans_node << '\n';
        }
    }
}