2023“钉耙编程”中国大学生算法设计超级联赛（1）
1001 Hide-And-Seek Game
题意:
给出一颗树，两人在树上特定两点来回走，问最早在那个节点相遇。
分析：
两条路径相交，则一条路径的LCA一定在另一条路径上。我们可以预处理一个dfs时间戳，结合LCA来判断路径相交。
由于本题的点数较小,所以我们可以枚举相交链上的每一个点，然后计算他们在这个点最早相遇的时间，找到其中相遇时间最早的点作为答案输出。
对于相交链上的一个点x,我们可以计算出A到达x的时间满足2k1 · dis(Sa, Ta) + dis(Sa,x)或者2k1. dis(Sa,Ta) + dis(Sa,Ta) + dis(Ta,x)。(其中k为任意正整数)
类似的，B到达x的时间满足2k2 · dis(Sb, Tb) + dis(Sb,x)或者2k2 · dis(Sb, Tb) + dis(Sb, Tb) + dis(Tb, x)。然后两两联立成4个二元一次同余方程，使用拓展欧几里得算法求解最小正整数解即可。注意负数的处理。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 3e4 + 5, M = 6e4 + 5;
int h[N], e[M], ne[M], idx;
int depth[N], f[N][20], fa[N], mark[N], dfn[M], low[M], timestamp;
struct Point
{
int a, b;
}Data[N][2];
int sum_t, ans_ver;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int u, int pa)
{
dfn[u] = ++ timestamp;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (j == pa)
continue;
fa[j] = u;
dfs(j, u);
}
low[u] = timestamp;
}
void bfs(int u)
{
memset(depth, 0x3f, sizeof depth);
queue<int> q;
q.push(u);
depth[0] = 0, depth[u] = 1;
while (q.size())
{
int t = q.front();
q.pop();
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (depth[j] > depth[t] + 1)
{
depth[j] = depth[t] + 1;
f[j][0] = t;
q.push(j);
for (int k = 1; k <= 13; k ++)
f[j][k] = f[f[j][k - 1]][k - 1];
}
}
}
}
int lca(int a, int b)
{
if (depth[a] < depth[b])
swap(a, b);
for (int i = 13; i >= 0; i --)
{
if (depth[f[a][i]] >= depth[b])
{
a = f[a][i];
}
}
if (a == b)
return a;
for (int i = 13; i >= 0; i --)
{
if (f[a][i] != f[b][i])
{
a = f[a][i];
b = f[b][i];
}
}
return f[a][0];
}
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 cal(int u, Point A, Point B)
{
int a = A.a, b = -B.a, m1 = A.b, m2 = B.b, c = m2 - m1, x, y, d;
c = (c % B.a + B.a) % B.a;
d = exgcd(a, b, x, y);
if (c % d)
return;
a /= d, b /= d, c /= d;
x *= c, y *= c;
b = abs(b);
x = (x % b + b) % b;
if (x * A.a + m1 < sum_t)
{
sum_t = x * A.a + m1;
ans_ver = u;
}
}
bool check(int a, int b)
{
return dfn[b] <= dfn[a] && dfn[a] <= low[b];
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
memset(h, -1, sizeof h);
memset(f, 0, sizeof f);
memset(mark, 0, sizeof mark);
idx = timestamp = 0;
int n, m;
cin >> n >> m;
for (int i = 0; i < n - 1; i ++)
{
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
dfs(1, -1);
bfs(1);
for (int i = 1; i <= m; i ++)
{
int sa, ta, sb, tb;
cin >> sa >> ta >> sb >> tb;
if (sa == sb)
{
cout << sa << endl;
continue;
}
int la = lca(sa, ta), lb = lca(sb, tb);
if (depth[la] > depth[lb])
{
swap(sa, sb);
swap(ta, tb);
swap(la, lb);
}
if (!check(sa, lb) && !check(ta, lb))
{
cout << -1 << endl;
continue;
}
else
{
int da = depth[sa] + depth[ta] - 2 * depth[la], db = depth[sb] + depth[tb] - 2 * depth[lb];
int p = sa;
while (1)
{
Data[p][0] = (Point){2 * da, depth[sa] - depth[p]};
Data[p][1] = (Point){2 * da, 2 * da - (depth[sa] - depth[p])};
mark[p] = i;
if (p == la)
break;
p = fa[p];
}
p = ta;
while (p != la)
{
Data[p][0] = (Point){2 * da, da - (depth[ta] - depth[p])};
Data[p][1] = (Point){2 * da, da + (depth[ta] - depth[p])};
mark[p] = i;
p = fa[p];
}
sum_t = 0x3f3f3f3f;
ans_ver = -1;
p = sb;
while (1)
{
Point A = (Point){2 * db, depth[sb] - depth[p]};
Point B = (Point){2 * db, 2 * db - (depth[sb] - depth[p])};
if (mark[p] == i)
{
cal(p, Data[p][0], A), cal(p, Data[p][0], B);
cal(p, Data[p][1], A), cal(p, Data[p][1], B);
}
if (p == lb)
break;
p = fa[p];
}
p = tb;
while (p != lb)
{
Point A = (Point){2 * db, db - (depth[tb] - depth[p])};
Point B = (Point){2 * db, db + (depth[tb] - depth[p])};
if (mark[p] == i)
{
cal(p, Data[p][0], A), cal(p, Data[p][0], B);
cal(p, Data[p][1], A), cal(p, Data[p][1], B);
}
p = fa[p];
}
cout << ans_ver << endl;
}
}
}
return 0;
}
1002 City Upgrading
题意：
有一个树状的城市结构，现在需要给一些城市部署路由器，每个路由器覆盖其所在的节点及其相邻节点，问如何以最低成本部署路由器以确保覆盖每个节点？
分析：
树形dp。
定义状态：f[i][j]表示以i为根的子树且状态是j的最小花费。这里j取3，“0，1，2”分别表示在i的父节点放置路由，在i的子节点放置路由，在i处放置路由。
状态转移：
①f[i][0] = \(\sum_{j}\)min(f[j][1], f[j][2])
②f[i][2] = \(\sum_j\)min(f[j][0], f[j][1], f[j][2])
③f[i][1] = min(f[j][2] + \(\sum_k\)min(f[k][1], f[k][2])) (k表示除j外的其他子节点)
答案：min(f[root][1], f[root][2])
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 5, M = 2e6 + 5;
int h[N], e[M], ne[M], w[N], idx;
LL f[N][3];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int u, int fa)
{
f[u][2] = w[u];
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (j == fa)
continue;
dfs(j, u);
f[u][0] += min(f[j][1], f[j][2]);
f[u][2] += min(min(f[j][0], f[j][1]), f[j][2]);
}
// 可以借助f[u][0]来算f[u][1]
f[u][1] = 2e18;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
f[u][1] = min(f[u][1], f[j][2] + f[u][0] - min(f[j][1], f[j][2]));
}
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
memset(h, -1, sizeof h);
memset(f, 0, sizeof f);
idx = 0;
int n;
cin >> n;
for (int i = 1; i <= n; i ++)
cin >> w[i];
for (int i = 0; i < n - 1; i ++)
{
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
dfs(1, -1);
cout << min(f[1][1], f[1][2]) << endl;
}
return 0;
}
1005 Cyclically Isomorphic
题意：
给出n个字符串s，每个长度均为m，q次询问，每次问能否通过向右右循环移动得到。
分析：
复制一份s得到长度为2m的新串，若两个串能通过循环移动得到，则两者新串的字典序最小的子串应当相同，因此可以hash最小子串，对于每一次询问看hash值是否相同。
代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n, m;
cin >> n >> m;
unordered_map<int, string> mp;
for (int i = 1; i <= n; i ++)
{
string s, s2;
cin >> s;
s2 = s;
s = s + s;
for (int j = 0; j < m; j ++)
{
string s3 = s.substr(j, m);
if (s2 > s3)
s2 = s3;
}
mp[i] = s2;
}
int q;
cin >> q;
while (q --)
{
int a, b;
cin >> a >> b;
if (mp[a] == mp[b])
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
return 0;
}
1009 Assertion
题意:
Alice断言：m个物品分成n组，一定存在一组物品一定大于等于d。判断Alice的话对不对。
分析：
抽屉原理，至少有一堆有有\(\lfloor \frac{m-1}{n} \rfloor\) + 1个物品，判断\(\lfloor \frac{m-1}{n} \rfloor\) + 1于d的大小关系即可
代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n, m, d;
cin >> n >> m >> d;
int res = (m - 1) / n + 1;
if (res >= d)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}
1010 Easy problem I
题意：
分析：
我们可以用线段树同时维护两个状态: ai >= x部分和ai <= x部分
①ai >= x,直接用线段树维护区间和s1。同时，我们可以维护一个区间最小值判断是否发生状态转移，以及维护一个未发生状态转移的数量。
②ai < x,我们的操作实际上是对现有元素符号取反并加上x。每次操作会将\(x_1 - x_2 + x_3 - ... + x_{j-1} - ai\)变化为\(-x_1 + x_2 - x_3 - ... - x_{j-1} + x_j + a_i\) ,这时可以发现ai的数值不发生变化，只有符号改变, x标记可以直接叠加维护，所以也可以通过线段树维护。
根据\(x_{j-1}\) ≤ \(x_j\)的性质，发现如果\(a_i\) < \(x_{j-1}\), 修改后的|\(a_i\) - \(x_{j-1}\)|≤ \(x_{j-1}\) ≤ \(x_j\), 所以从\(a_i\) ≥ x转变为\(a_i\) < x的情况后就不会改变,所以转变总的次数是有限的。
综上，直接将树分为两类，分别通过线段树维护，并在分界点暴力转移状态。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e6 + 5;
struct Tree
{
int l, r;
LL s1, s2; \\s1表示状态变化前的和，s2表示状态变化后的和
LL minv, cnt, lazy1, lazy2, lazy3; \\ lazy1维护状态变化后的符号，lazy2维护状态变化前的变化量，lazy3维护状态变化后的变化量
}tr[N << 2];
LL w[N];
void pushup(int u)
{
tr[u].lazy2 = tr[u].lazy3 = 0;
tr[u].lazy1 = 1;
tr[u].minv = min(tr[u << 1].minv, tr[u << 1 | 1].minv);
tr[u].cnt = tr[u << 1].cnt + tr[u << 1 | 1].cnt;
tr[u].s1 = tr[u << 1].s1 + tr[u << 1 | 1].s1;
tr[u].s2 = tr[u << 1].s2 + tr[u << 1 | 1].s2;
}
void update1(int u, int v)
{
tr[v].minv -= tr[u].lazy2;
tr[v].s1 -= tr[v].cnt * tr[u].lazy2;
tr[v].lazy2 += tr[u].lazy2;
}
void update2(int u, int v)
{
tr[v].s2 = (tr[v].r - tr[v].l + 1 - tr[v].cnt) * tr[u].lazy3 + tr[u].lazy1 * tr[v].s2;
tr[v].lazy3 = tr[u].lazy3 + tr[u].lazy1 * tr[v].lazy3;
tr[v].lazy1 *= tr[u].lazy1;
}
void pushdown(int u)
{
if (tr[u].lazy2)
{
update1(u, u << 1);
update1(u, u << 1 | 1);
}
if (tr[u].lazy3)
{
update2(u, u << 1);
update2(u, u << 1 | 1);
}
tr[u].lazy2 = tr[u].lazy3 = 0;
tr[u].lazy1 = 1;
}
void build(int u, int l, int r)
{
if (l == r)
{
tr[u] = {l, r, w[l], 0, w[l], 1, 1, 0, 0};
return;
}
tr[u] = {l, r};
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void motify(int u, int l, int r, LL x)
{
if (l <= tr[u].l && tr[u].r <= r)
{
if (tr[u].minv >= x)
{
tr[u].minv -= x;
tr[u].s1 -= tr[u].cnt * x;
tr[u].s2 = (tr[u].r - tr[u].l + 1 - tr[u].cnt) * x - tr[u].s2;
tr[u].lazy2 += x;
tr[u].lazy3 = x - tr[u].lazy3;
tr[u].lazy1 *= -1;
}
else
{
if (tr[u].l == tr[u].r)
{
tr[u].s2 = x - tr[u].s1;
tr[u].cnt = tr[u].s1 = 0;
tr[u].minv = 2e18;
}
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid)
motify(u << 1, l, r, x);
if (r > mid)
motify(u << 1 | 1, l, r, x);
pushup(u);
}
}
return;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid)
motify(u << 1, l, r, x);
if (r > mid)
motify(u << 1 | 1, l, r, x);
pushup(u);
}
LL query(int u, int l, int r)
{
if (l <= tr[u].l && tr[u].r <= r)
return tr[u].s1 + tr[u].s2;
pushdown(u);
LL s = 0;
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid)
s = query(u << 1, l, r);
if (r > mid)
s += query(u << 1 | 1, l, r);
return s;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i ++)
cin >> w[i];
build(1, 1, n);
while (m --)
{
int op, l, r, x;
cin >> op;
if (op == 1)
{
cin >> l >> r >> x;
motify(1, l, r, x);
}
else
{
cin >> l >> r;
cout << query(1, l, r) << endl;
}
}
}
return 0;
}
1012 Play on Tree
题意：
随机选择一个节点作为根节点，进行树上删边游戏（每一轮选择一个节点x并删除它及其子树，删除根节点的输），问获胜的概率。
分析：
树上删边游戏+换根dp。
树上删边游戏：https://blog.csdn.net/wu_tongtong/article/details/79311284
换根dp：https://zhuanlan.zhihu.com/p/437753260
对于每棵树的SG函数，可以发现SG(u) = (SG(v1) + 1) xor (SG(v2) + 1) xor ... xor (SG(vk) + 1)
先计算出一个根节点的SG然后通过换根的方式计算其他节点作为根节点的SG：SG2(v) = SG(v) xor ((SG2(u) xor (SG(v) + 1)) + 1)
最后概率为：\(\frac{\sum_i^n{SG2(i) > 0}}{n}\)
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 5, M = 4e5 + 5, mod = 1e9 + 7;
int h[N], e[M], ne[M], idx;
int f1[N], f2[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
LL qmi(LL m, LL k)
{
LL res = 1, t = m;
while (k)
{
if (k & 1)
res = res * t % mod;
t = t * t % mod;
k >>= 1;
}
return res;
}
void dfs1(int u, int fa)
{
f1[u] = 0;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (j == fa)
continue;
dfs1(j, u);
f1[u] ^= (f1[j] + 1);
}
}
void dfs2(int u, int fa)
{
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (j == fa)
continue;
f2[j] = f1[j] ^ ((f2[u] ^ (f1[j] + 1)) + 1);
dfs2(j, u);
}
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
memset(h, -1, sizeof h);
memset(f1, 0, sizeof f1);
memset(f2, 0, sizeof f2);
idx = 0;
int n;
cin >> n;
for (int i = 0; i < n - 1; i ++)
{
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
dfs1(1, -1);
f2[1] = f1[1];
dfs2(1, -1);
LL m = 0;
for (int i = 1; i <= n; i ++)
if (f2[i])
m ++;
cout << (m * qmi(n, mod - 2)) % mod << endl;
}
return 0;
}