第一场
1001
题目:
现在存在一个边权都是1的树，存在两个人 A 和 B，他们各自有一个起点和一个终点，并且在起点和终点直接来回跑。
问你他们第一次相遇的节点是哪个。
思路：
讨论他们相遇的情况。
因为来回跑，一个人到一个点有两种情况，1.直接到，2.从终点跑回来。 如果他们到同一个点说明。两者到达同一个点的时间相同。
所以我们可以找到他们路径上的所有点，枚举他们相遇在哪个交点上。 LCA 可以解决树上两个点之间的距离。
不难列出等式， 2 * k1 * a + x1 == 2 * k2 * b + x2
2 * k1 表示一个A来回的路径长度，因为可能在很多个来回的情况下，两者相遇。
x1, x2 表示两者从起点到达这个点的长度。 这样 A 在经过 a 个来回的可能下， B 在 经过 b 的来回的可能下 相遇了
其中 x1 和 x2,各有两种情况，总共 4 种，枚举出后，两元一次方程求解最小非负整数解。
做法：
因为我们会用到树上两个点之间的距离，所以先预处理出来 LCA。 然后找到两人的路径交点，先标记A走过的点，然后存入B走过的标记过的点。通过fa数组，每次向上跳，跳到lca，再从终点跳到lca。
然后枚举所有交点，x1 和 x2 各有两种情况，各存下这两种，然后枚举情况。
每次得到两人同时到达这个点的时间，每次记录最小值和最小值的点就是答案。
拓展欧几里得中，因为我们得到的 x 和 y 必须是非负整数，所以当我们求 x 的最小非负整数解的时候，如果 b / d 是负数，那么取模后仍然是负数，所以我们对 t 取反，保证的正数，因为符号可以根据 x 改变不受影响。
代码：
int exgcd(int a, int b, int &x, int &y)
{
if(b==0){
x = 1, y = 0;
return a;
}
int x1,y1,gcd;
gcd = exgcd(b, a%b, x1, y1);
x = y1, y = x1 - a/b*y1;
return gcd;
}
int get_dis(int x, int y, int lc)
{
return depth[x] + depth[y] - 2 * depth[lc];
}
int get_ans(int a, int b, int x, int y, int c)
{
int d = exgcd(a, b, x, y);
if(c % d) return -1;
int t1 = b / d;
x = x * c / d;
if(t1 < 0) t1 = -t1;
x = (x % t1 + t1) % t1;
return x;
}
int work(int x1, int x2, int a, int b)
{
int x, y;
int k1 = get_ans(a, b, x, y, (((x2 - x1) % b + b) % b));
if(k1 == -1) return 1e18;
int ans1 = k1 * a + x1;
if(x1 != x2)
{
return ans1;
}else
{
return x1;
}
}
void solved()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) h[i] = -1;
for(int i = 0; i <= n; i++) for(int j = 0; j < 20; j++) fa[i][j] = 0;
for(int i = 0; i < n - 1; i++)
{
int a, b, c; cin >> a >> b;
add(a, b), add(b, a);
}
bfs();
for(int i = 0; i < m; i++)
{
for(int i = 1; i <= n; i++) oper[i] = false;
int xa, ya, xb, yb; cin >> xa >> ya >> xb >> yb;
int lc = lca(xa, ya);
vector<int> point;
int ta = xa;
oper[ta] = true;
while(ta != lc)
{
ta = fa[ta][0];
oper[ta] = true;
}
ta = ya;
oper[ta] = true;
while(ta != lc)
{
ta = fa[ta][0];
oper[ta] = true;
}
lc = lca(xb, yb);
ta = xb;
if(oper[ta]) point.push_back(ta);
while(ta != lc)
{
ta = fa[ta][0];
if(oper[ta])
point.push_back(ta);
}
ta = yb;
if(oper[ta]) point.push_back(ta);
while(ta != lc)
{
ta = fa[ta][0];
if(oper[ta])
point.push_back(ta);
}
int nans = 1e18, nid = 0;
for(auto te : point)
{
vector<int> v1, v2;
v1.push_back(get_dis(te, xa, lca(te, xa)));
v1.push_back(2 * get_dis(xa, ya, lca(xa, ya)) - get_dis(te, xa, lca(te, xa)));
v2.push_back(get_dis(te, xb, lca(te, xb)));
v2.push_back(2 * get_dis(xb, yb, lca(xb, yb)) - get_dis(te, xb, lca(te, xb)));
int a = 2 * get_dis(xa, ya, lca(xa, ya)), b = 2 * get_dis(xb, yb, lca(xb, yb));
for(auto p : v1)
{
for(auto q : v2)
{
int now = work(p, q, a, b);
if(nans > now)
{
nans = now;
nid = te;
}
}
}
}
if(nid != 0)
cout << nid << endl;
else cout << -1 << endl;
}
}
1002
题目：
现在存在一棵树，当某个点放入路由器，与他相邻的点都会被覆盖，请你得到全部点被覆盖的最小代价。
思路：
树形dp。
f[i][1] 表示当前被覆盖是自己放入了一个，[0] 表示当前点是被父亲覆盖的,[2] 表示当前点是被儿子覆盖的
f[i][1] 由f[j][0/1/2] 都可以转移而来 f[1][0] 只能由 f[j][1/ 2] 因为当前自己这个点没有放置，下面儿子没有被覆盖`
f[1][2] 只能由儿子中 f[j][1/2]覆盖而来，并且必须有一个儿子是放置了节点的，否则本身自己没有被覆盖`
所以f[j][1] - min(f[j][1], f[j][2])， 如果 j 1 小，那么这个儿子一定会被放置，
所以就是 0， 如果 j 2 小，那么放置的代价就是f[j][1] - f[j][2]，
因为此前已经在f[u][0]， 得到了f[j][2]， 所以减去 f[j][2] 来得到 f[j][1]
int f[N][3];
// 1 自己 0 父亲 2 儿子
void dfs(int u, int fa)
{
f[u][1] = a[u];
f[u][0] = 0;
int sum = 1e18;
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(j == fa) continue;
dfs(j, u);
f[u][1] += min({f[j][1], f[j][0], f[j][2]});
f[u][0] += min(f[j][1], f[j][2]);
sum = min(sum, f[j][1] - min(f[j][1], f[j][2]));
}
f[u][2] = f[u][0] + sum;
}
void solved()
{
for(int i = 1; i <= n; i++) f[i][0] = f[i][1] = f[i][2] = 0;
idx = 0;
memset(h, -1, sizeof h);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[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][2], f[1][1]) << endl;
}
1003
题目：
现在存在 n 个卡牌，你可以无限操作，要么直接打出这张牌，要么合成两张 i - 1 等级的牌得到 i 等级的牌，这两张牌必须相邻。
第 i 个等级的价值为原本的价值 * (p) (i - 1)
现在问你最终可以得到的最大价值是多少。
思路：
考虑区间dp，不难发现，我们尽可能的去合成牌，是最优选择。因为相邻才可以合成，所以对于一个不相邻的两张要合成的牌的区间，中间的牌必须被打出。所以定义状态为 这个区间内剩下一张牌。 但是我们也要得到这个区间全部售出的价值。
我们定义 dp[l][r][i][j] 表示在 l 到 r 这个区间内，只剩下一张 等级为 i 的 j 类型的牌。 dp[l][r][0][0] 为区间牌全部卖出的价值
做法：
考虑复杂度，首先枚举区间 O（n ^ 2）然后要枚举断点 O（n ^ 3）,此外还要枚举剩下的两个状态的所有情况。
n ^ 4 肯定不可以接受。 我们观察 m 和 r。 因为 r 合成的性质，所以 r 的范围最大为 7， 所以可以通过。
状态转移：
首先更新 dp[l][r][0][0] 枚举断点左边的全部卖出加上右边全部卖出即可。
然后我们更新所有的状态，对于 dp[l][r][k][j] = max(dp[l][r][k][j], dp[l][i][k - 1][j] + dp[i + 1][r][k - 1][j]);
对于第 k 个等级，我们需要 k - 1 等级。所以第 1 级，我们可以先预处理出来， 对于这个区间 等级为 1类型为 j 的。
dp[l][r][1][j] = max(dp[l][r][1][j],
max(dp[l][i][0][0] + dp[i + 1][r][1][j], dp[l][i][1][j] + dp[i + 1][r][0][0])); 如果留下左边区间类型为1的，那么就把右边全部卖掉，反之亦然。
不要忘了dp[l][r][0][0] 包含两种情况，一种直接卖，第二种合成后卖，每次合成完更新dp[0][0]
void solved()
{
cin >> n >> m >> q >> p;
q = min(7ll, q);
for(int i = 0; i < 110; i++)
for(int j = 0; j < 110; j++)
for(int k = 0; k < 10; k++)
for(int z = 0; z < 110; z++) dp[i][j][k][z] = -1e18;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= m; i++) cin >> v[i];
for(int len = 1; len <= n; len++)
{
for(int l = 1; len + l - 1 <= n; l++)
{
int r = len + l - 1;
if(len == 1)
{
dp[l][r][0][0] = v[a[l]];
dp[l][r][1][a[l]] = 0;
continue;
}
for(int i = l; i < r; i++)
{
dp[l][r][0][0] = max(dp[l][r][0][0], dp[l][i][0][0] + dp[i + 1][r][0][0]);
}
for(int i = l; i < r; i++)
{
for(int j = 1; j <= m; j++)
{
dp[l][r][1][j] = max(dp[l][r][1][j], max(dp[l][i][0][0] + dp[i + 1][r][1][j], dp[l][i][1][j] + dp[i + 1][r][0][0]));
}
}
for(int i = l; i < r; i++)
{
for(int j = 1; j <= m; j++)
{
for(int k = 2; k <= q; k++)
{
dp[l][r][k][j] = max(dp[l][r][k][j], dp[l][i][k - 1][j] + dp[i + 1][r][k - 1][j]);
dp[l][r][0][0] = max(dp[l][r][0][0], dp[l][r][k][j] + po(p, k - 1) * v[j]);
}
}
}
}
}
cout << dp[1][n][0][0] << endl;
}
1010
题目：
对一段区间都减去一个数字 x，并且取绝对值。 区间查询和。保证 下一次减去的数字 x 一定大于 前一次。
思路：
毫无疑问线段树。
|a - x| 存在两种情况， a > x 直接减，用线段树维护sum 即可。
x > a, 那么需要编号，线段树无法直接维护。因为保证了 x_i - 1 < x_i， 所以当第一次取绝对值后，后面可以直接维护。
所以我们把每个点分成两个阶段，取绝对值前和取绝对之后，分别维护。取绝对值时必须到根节点去标记，每个点最多被遍历一遍，符合复杂度。
对于一段区间，可能存在第一阶段，也可能存在第二阶段。
1.我们维护 sum1 和 sum2 分别表示区间阶段1的和，阶段2的和。
2.维护区间最小值，当 x > min 时候说明这个区间有点需要进入第二回合，否则没有，可以直接更新
3.维护 cnt，来表示有多少点是第一阶段，可以得到第二阶段是多个点，这样可以计算两个阶段的和
4.lz1 维护阶段1的 区间减的懒标记， lz2 维护阶段2的区间减的懒标记， lz3用来维护符号。
对于第二阶段如何区间维护，我们手玩一些样例来发现。
5 - 6 》 6 -5 》 7 - 6 + 5 》 8 -7 + 6 - 5 不难发现符号每经过一次都会反转。
对于modify中
如果cnt == 0，那么都是二阶段 直接修改：
lz2： 对于当前的 lz2 = x - lz2， 因为x 一定大于之前的 x_i- 1， 同时原本的值 5，的符号也会反转。
lz3：lz3初始值为 1， 每次 lz3 *= -1
sum2: x * (tr[u].r - tr[u].l + 1) - tr[u].sum2; 绝对值直接更改
如果递归到根节点，这个点要进入二阶段，所以更新 cnt,mi, sum1, sum2
如果 mi > x, 说明没有人要进入2，那么直接都更新一遍，否则继续递归。
pushdown 中
如果laz1存在可以直接维护。
lz2: 结果上面手玩的样例可知，当前的未更新的 lz2，需要经历好几次更新，那么就需要变换符号，所以先更新符号再加当前的更新完的懒标记。
lz3，同样直接变换符号。
sum2：同样变换符号，然后加上传递下来的 lazy2，注意一部分是一阶段一部分是二阶段
struct Node
{
int l, r;
int sum1, sum2;
int mi;
int cnt;
int lz1, lz2, lz3;
}tr[N * 4];
void push_up(int u)
{
Node &root = tr[u], &le = tr[u <<1], &ri = tr[u << 1 | 1];
root.mi = min(le.mi, ri.mi);
root.cnt = le.cnt + ri.cnt;
root.sum1 = le.sum1 + ri.sum1;
root.sum2 = le.sum2 + ri.sum2;
}
void build(int u, int l, int r)
{
if(l == r)
{
tr[u] = {l, r, a[l], 0, a[l], r - l + 1, 0, 0, 1};
return;
}
int mid = l + r >> 1;
tr[u] = {l, r};
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
push_up(u);
}
void push_down(int u)
{
Node &root = tr[u], &le = tr[u <<1], &ri = tr[u << 1 | 1];
if(root.lz1)
{
le.lz1 += root.lz1;
ri.lz1 += root.lz1;
le.sum1 -= le.cnt * root.lz1;
ri.sum1 -= ri.cnt * root.lz1;
le.mi -= root.lz1;
ri.mi -= root.lz1;
}
le.lz2 = le.lz2 * root.lz3 + root.lz2;
ri.lz2 = ri.lz2 * root.lz3 + root.lz2;
ri.lz3 *= root.lz3;
le.lz3 *= root.lz3;
le.sum2 = (le.r - le.l + 1 - le.cnt) * root.lz2 + le.sum2 * root.lz3;
ri.sum2 = (ri.r - ri.l + 1 - ri.cnt) * root.lz2 + ri.sum2 * root.lz3;
root.lz1 = 0;
root.lz2 = 0;
root.lz3 = 1;
}
void modify(int u, int l, int r, int x)
{
if(tr[u].l >= l && tr[u].r <= r)
{
// cout << tr[u].l << " " << tr[u].r << endl;
if(tr[u].cnt == 0)
{
tr[u].lz2 = x - tr[u].lz2;
tr[u].sum2 = x * (tr[u].r - tr[u].l + 1) - tr[u].sum2;
tr[u].lz3 *= -1;
// cout << tr[u].l << " " << tr[u].r << " " << tr[u].sum1 << " " << tr[u].sum2 << endl;
return;
}
if(tr[u].l == tr[u].r)
{
if(tr[u].mi >= x)
{
tr[u].mi = tr[u].mi - x;
tr[u].sum1 = tr[u].sum1 - x;
}else
{
tr[u].sum2 = x - tr[u].sum1;
tr[u].sum1 = 0;
tr[u].mi = 1e18;
tr[u].cnt = 0;
// cout << tr[u].l << " " << tr[u].r << " " << tr[u].sum1 << " " << tr[u].sum2 << endl;
}
return;
}
if(tr[u].mi >= x)
{
// cout << tr[u].l << " " << tr[u].r << " " << tr[u].sum1 << " " << tr[u].sum2 << endl;
tr[u].mi -= x;
tr[u].sum1 -= x * (tr[u].cnt);
tr[u].lz1 += x;
tr[u].lz2 = x - tr[u].lz2;
tr[u].lz3 *= -1;
tr[u].sum2 = (tr[u].r - tr[u].l + 1 - tr[u].cnt) * x - tr[u].sum2;
// cout << tr[u].l << " " << tr[u].r << " " << tr[u].sum1 << " " << tr[u].sum2 << endl;
}else
{
push_down(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) modify(u << 1, l, r, x);
if(r > mid) modify(u << 1 | 1, l, r, x);
push_up(u);
}
return;
}
push_down(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) modify(u << 1, l, r, x);
if(r > mid) modify(u << 1 | 1, l, r, x);
push_up(u);
}
int query(int u, int l, int r)
{
// cout << tr[u].l << " " << tr[u].r << " " << tr[u].sum1 <<endl;
if(tr[u].l >= l && tr[u].r <= r)
{
return tr[u].sum1 + tr[u].sum2;
}
push_down(u);
int mid = tr[u].l + tr[u].r >> 1;
int sum = 0;
if(l <= mid) sum += query(u << 1, l, r);
if(r > mid) sum += query(u <<1 | 1, l, r);
return sum;
}
void solved()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n);
for(int i = 0; i < m; i++)
{
int op; cin >> op;
int l, r, x;
if(op == 1)
{
cin >> l >> r >> x;
modify(1, l, r, x);
}else
{
cin >> l >> r;
// cout << query(1, 1, 1) << endl;
cout << query(1, l, r) << endl;
}
}
}
1005
题目：
现在存在一堆字符串，每次查询两个字符串是不是循环同构的。
思路：
不难发现是字符串的最小表示，字符串最小表示是，当前字符串的循环同构的字典序最小的情况。
所以我们每次把当前字符串转换成最小表示，然后字符串哈希，每次查询判断两个字符串哈希值是否相同
字符串哈希要么开 ULL 自动溢出，或者取模 666623333
代码
LL to_hash(string s)
{
int n = s.size();
s = "?" + s;
LL num = 0;
for(int i = 1; i <= n; i++)
{
num = num * M + s[i];
num %= 666623333;
}
return num % 666623333;
}
int get_min(string s)
{
int k = 0, i = 0, j = 1;
while(k < m && i < m && j < m)
{
if(s[(i + k)% m] == s[(j + k) % m])
{
k++;
}else
{
s[(i + k) % m] > s[(j + k) % m] ? i = i + k + 1 : j = j + k + 1;
if(i == j) i++;
k = 0;
}
}
return min(i, j);
}
void solved()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
cin >> s1[i];
int pos = get_min(s1[i]);
s1[i] += s1[i];
h[i] = to_hash(s1[i].substr(pos, m));
}
int q; cin >> q;
for(int i= 0; i < q; i++)
{
int a, b; cin >> a >> b;
if(h[a] == h[b]) cout << "Yes" << endl;
else cout << "No" << endl;
}
}
1012
题目：
A和B在树上玩游戏，每次可以选择一个点，然后把这个点和它的子树都删去，谁最终删了根节点就输了，问你在所有点都可能为根的所有情况下，A赢的可能性， B先手
思路：
树上博弈，此题判断是 NIM游戏树上模型，只需要得到 SG函数即可，因为需要换根，所以要换根dp
对于 sg[u] = sg[son1] + 1 ^ (son2 + 1) 所以我们可以先得到1的SG函数，然后进行换根。
我们设f[u]是以 1为根的 u节点的SG函数的值， S[U] 是以 u 为根节点父亲方向的sg函数值，只需要再 f[u] ^ (s[u] + 1) 可得到
以 u 为根的sg函数的值，第一遍dfs 求 f 函数 第二遍求 s函数
s[u] = f[fa] ^ (fu + 1) ^ (s[fa] + 1) 首先fa先^fu 得到 父亲除了当前这个点子树的 f 函数的值，然后再^父亲的 s 函数，就可以得到
u 的 s 函数的值。
代码：
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int qmi(int a, int b)
{
int res = 1;
while(b)
{
if(b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
int f[N];
void dfs(int u, int fa)
{
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(j == fa) continue;
dfs(j, u);
f[u] ^= f[j] + 1;
}
}
int s[N];
void dfs2(int u, int fa)
{
if(u == 1) s[u] = -1;
else s[u] = f[fa] ^ (f[u] + 1) ^ (s[fa] + 1);
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(j == fa) continue;
dfs2(j, u);
}
}
void solved()
{
idx = 0;
cin >> n;
for(int i = 1; i <= n; i++) f[i] = s[i] = 0, h[i] = -1;
for(int i = 0; i < n - 1; i++)
{
int a, b; cin >> a >> b;
add(a, b), add(b, a);
}
dfs(1, -1), dfs2(1, -1);
int ans = 0;
if(f[1]) ans = 1;
for(int i = 2; i <= n; i++)
{
if(f[i] ^ (s[i] + 1)) ans++;
}
cout << ans * qmi(n, MOD - 2) % MOD << endl;
}
