前记
（开始写于 \(2023.9.9\)）
（本来是不想写的，但是看到学长以及身边人都写，思考了一下，感觉有点用，于是也写了）
（里面也写了一些闲话）
（以前的比赛我就记个排名得了，懒得补了）
7.20 ~ 7.22 CSP 模拟 1 ~ 3 没考
7.24 CSP 模拟 4 (rk 6)
7.25 CSP 模拟 5 (rk 3)
7.26 CSP 模拟 6 (rk 23)
7.27 CSP 模拟 7 (rk 12)
7.28 CSP 模拟 8 (rk 9)
7.30 CSP 模拟 9 (rk 6)
7.31 CSP 模拟 10 (rk 23)
8.1 CSP 模拟 11 (rk 8)
8.2 CSP 模拟 12 (rk 11)
8.3 CSP 模拟 13 (rk 18)
8.4 CSP 模拟 14 (rk 23)
8.7 CSP 模拟 15 (rk 15)
8.9 CSP 模拟 16 (rk 20)
8.10 CSP 模拟 17 (rk 18)
8.11 CSP 模拟 18 (rk 9)
8.12 CSP 模拟 19 (rk 22)
8.13 CSP 模拟 20 (rk 6)
8.14 CSP 模拟 21 (rk 21)
8.16 CSP 模拟 22 (rk 4)
8.17 CSP 模拟 23 (rk 8)
8.18 CSP 模拟 24 (rk 10)
8.19 CSP 模拟 25 (rk 12)
8.20 CSP 模拟 26 (rk 30)
8.21 CSP 模拟 27 (rk 6)
8.23 CSP 模拟 28 (rk 25)
8.24 CSP 模拟 29 (rk 29)
8.25 CSP 模拟 30 (rk 26)
8.25+ CSP 模拟 30++ (rk 29)
8.26 CSP 模拟 31 (rk 24)
暑假模拟赛总结（补）
当时一直没有写每场比赛的赛后总结，现在没时间补那么多了，就写个总的吧。
一共打了 \(29\) 场，\(2\) 次前 \(5\)，\(11\) 次前 \(10\)，\(7\) 次 \(11 \sim 20\)，\(11\) 次 \(21\) 及以后。
\(26 \sim 31\) 场的时候，感觉状态不对，基本场场垫底，至于为什么，我也不知道，我真的不知道，感觉没发生什么事啊，我也在一如既往地学着。
感觉过了一个暑假，更让我看清楚和别人的差距了。感觉我刚摸着门道，别人却早就知道怎么学奥赛了。嗯，反正崩是不会崩的，好好学吧。
9.1 CSP 模拟 32 (rk 25)
9.9 CSP 模拟 33 (rk 14)
T1 光
（乱搞的）
非正解做法，但是跑的飞快，碾压正解。
首先你得会暴力枚举，\(O(n^3)\) 或 \(O(n^4)\) 都行，我用的 \(O(n^3)\)。
先将原来的四个数同除一个数 \(K\)，跑一边，再将跑出来的四个答案 \(-4K\) 作为下边界，\(+4K\) 作为上边界。原来的四个数的答案就在这个区间浮动，枚举区间就变成了 \(8K\)，即时间复杂度为 \(O((8K)^3)\)。我的 \(K\) 取的是 \(\displaystyle \frac{max(a, b, c, d)}{4}\)，也有人取的一个常数。
代码
点击查看代码
#include <bits/stdc++.h>
using namespace std;
struct Sol {
int t1, t2, t3, t4;
};
inline pair<int, Sol> judge(int a, int lim_a_min, int lim_a_max, int b, int lim_b_min, int lim_b_max, int c, int lim_c_min, int lim_c_max, int d) {
int ans = INT_MAX, t[5];
Sol s;
for(int i = max(lim_a_min, 0); i <= lim_a_max; ++ i) {
t[1] = a;
t[2] = b;
t[3] = c;
t[4] = d;
t[1] = t[1] - i;
t[2] = t[2] - i / 2;
t[3] = t[3] - i / 2;
t[4] = t[4] - i / 4;
if(t[1] < 0 && t[2] < 0 && t[3] < 0 && t[4] < 0) {
if(i < ans) {
ans = i;
s = {i, 0, 0, 0};
}
break;
}
for(int j = max(lim_b_min, 0); j <= lim_b_max; ++ j) {
t[1] = t[1] - j / 2;
t[2] = t[2] - j;
t[3] = t[3] - j / 4;
t[4] = t[4] - j / 2;
if(t[1] < 0 && t[2] < 0 && t[3] < 0 && t[4] < 0) {
t[1] = t[1] + j / 2;
t[2] = t[2] + j;
t[3] = t[3] + j / 4;
t[4] = t[4] + j / 2;
if(i + j < ans) {
ans = i + j;
s = {i, j, 0, 0};
}
break;
}
for(int k = max(lim_c_min, 0); k <= lim_c_max; ++ k) {
t[1] = t[1] - k / 2;
t[2] = t[2] - k / 4;
t[3] = t[3] - k;
t[4] = t[4] - k / 2;
if(t[1] < 0 && t[2] < 0 && t[3] < 0 && t[4] < 0) {
t[1] = t[1] + k / 2;
t[2] = t[2] + k / 4;
t[3] = t[3] + k;
t[4] = t[4] + k / 2;
if(i + j + k < ans) {
ans = i + j + k;
s = {i, j, k, 0};
}
break;
}
int maxn = max({t[4], t[3] * 2, t[2] * 2, t[1] * 4});
if(i + j + k + maxn < ans) {
ans = i + j + k + maxn;
s = {i, j, k, maxn};
}
t[1] = t[1] + k / 2;
t[2] = t[2] + k / 4;
t[3] = t[3] + k;
t[4] = t[4] + k / 2;
}
t[1] = t[1] + j / 2;
t[2] = t[2] + j;
t[3] = t[3] + j / 4;
t[4] = t[4] + j / 2;
}
}
return {ans, s};
}
signed main() {
int a, b, c, d;
cin >> a >> b >> c >> d;
int maxn = max({a, b, c, d}), K = sqrt(maxn / 4), lim = maxn / K;
pair<int, Sol> ji = judge(a / K, 0, lim, b / K, 0, lim, c / K, 0, lim, d / K);
cout << judge(a, ji.second.t1 * K - K * 4, ji.second.t1 * K + K * 4, b, ji.second.t2 * K - K * 4, ji.second.t2 * K + K * 4, c, ji.second.t3 * K - K * 4, ji.second.t3 * K + K * 4, d).first <<'\n';
}
/*
50 24 25 12
50
*/
/*
8 8 8 8
15
*/
/*
49 47 42 11
76
*/
/*
50 49 26 31
71
*/
/*
1500 1500 1500 1500
2668
*/
/*
400 400 400 400
712
*/
T2 爬
其实挺可做的。
异或，所以按位考虑。
先维护一个点的 \(son\)，即他的儿子数 \(+1\)（他自己）
对于每一个点的每一位，记录他和他儿子里有多少个点，这一位为 \(1\)，拿 \(cnt\) 记一下。
对于第 \(i\) 个点的第 \(j\) 位，如果 \(3 \le cnt[i][j]\) 这一位产生的贡献为
\[\begin{aligned} 2^j \times (({cnt[i][j] \choose 3} + {cnt[i][j] \choose 5} + {cnt[i][j] \choose 7} + \dots) \times 2^{n - cnt[i][j] - 1} + cnt[i][j] \times 2^{son[i] - cnt[i][j] - 1} \times 2^{n - son[i] - 1}) \end{aligned}\]否则为
\[\begin{aligned} 2^j \times cnt[i][j] \times 2^{son[i] - cnt[i][j] - 1} \times 2^{n - son[i] - 1} \end{aligned}\]根节点特判一下，不写了。
代码
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define M 100005
#define mod 1000000007
using namespace std;
inline int read() {
int x = 0, s = 1;
char ch = getchar();
while(ch < '0' || ch > '9') {
if(ch == '-')
s = -s;
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + ch - '0';
ch = getchar();
}
return x * s;
}
void write(int x) {
if(x < 0) {
x = ~(x - 1);
putchar('-');
}
if(x > 9)
write(x / 10);
putchar(x % 10 + 48);
}
int n, a[M], fa[M], bin[M], cnt[M][32], ans, son[M];
signed main() {
n = read();
bin[0] = 1;
for(int i = 1; i <= n; ++ i)
bin[i] = (bin[i - 1] << 1) % mod;
for(int i = 1; i <= n; ++ i)
a[i] = read();
for(int i = 2; i <= n; ++ i) {
fa[i] = read();
++ son[fa[i]];
++ son[i];
for(int j = 0; j <= 29; ++ j)
if(bin[j] & a[i])
++ cnt[i][j], ++ cnt[fa[i]][j];
}
for(int j = 0; j <= 29; ++ j) {
if(bin[j] & a[1]) {
if(cnt[1][j] >= 2)
ans = (ans + ((bin[cnt[1][j] - 1] - 1) * bin[n - cnt[1][j] - 1] % mod + bin[n - son[1] - 1] * (bin[son[1] - cnt[1][j]] - 1) % mod) % mod * bin[j] % mod) % mod;
else
ans = (ans + (bin[son[1] - cnt[1][j]] - 1) % mod * bin[n - son[1] - 1] % mod * bin[j] % mod) % mod;
}
else
if(cnt[1][j] >= 1)
ans = (ans + bin[cnt[1][j] - 1] * bin[n - cnt[1][j] - 1] % mod * bin[j] % mod) % mod;
}
for(int i = 2; i <= n; ++ i)
for(int j = 0; j <= 29; ++ j)
if(cnt[i][j] >= 3)
ans = (ans + ((bin[cnt[i][j] - 1] - cnt[i][j] + mod) % mod * bin[n - cnt[i][j] - 1] % mod + cnt[i][j] * (bin[son[i] - cnt[i][j]] - 1 + mod) % mod * bin[n - son[i] - 1] % mod) % mod * bin[j] % mod) % mod;
else
if(cnt[i][j] >= 1)
ans = (ans + cnt[i][j] * (bin[son[i] - cnt[i][j]] - 1) % mod * bin[n - son[i] - 1] % mod * bin[j] % mod) % mod;
write(ans);
}
/*
5
5 3 1 9 3
1 1 2 2
126
*/
T3 字符串
首先对三条规则进行简单分析
- 对于规则 3 来说，假设 \(c=3\)，那么如果想要通过 AB 切换来获得价值，那字符串就应该形如 BBBABBBABBBA 这样，即每 3 个 B 就切换成 A。
- 对于规则 1.2 来说，把字母放在连续的一段地方，第一次产生价值需要 \(a+1\) 个 A 或者 \(b+1\) 个 B，第二次及以后产生价值只需要 \(a\) 个 A 或者 \(b\) 个 B
我们可以枚举 A 和 B 切换了多少次，假定我们切换的方式就是 BBBABBBABBBA，即每一段 A 的长度都为 1，我们又知道 AB 的切换次数，就可以知道现在已经用掉了几个 A，然后我们先考虑把 A 全部用完。
- 在 BBBABBBA 的形式前面 只需要花费一个 A 就可以拿到一个价值
- 然后将多余的 A 填充进字符串中，因为每一段 A 的长度都是 1，所以此时本质上是每多 \(a\) 个 A，答案 +1。
然后再考虑将剩余的 B 用完。
- 如果倒数第二个位置是 A 的话，那么最后一个只需要花费一个 B 就能拿到一个价值
- 例如 \(b=4,c=3\)，本来我们填充的是 BBBABBBABBBA，根据规则 2，当一段 B 的长度达到 5 的时候又可以使得价值 +1，所以我们尽量将每一段 B 都填充到长度为 5。如果全部填充好了且还有多余的 B，那么每多 \(b\) 个 B，答案 +1。
代码
点击查看代码
#include <bits/stdc++.h>
#define M 100005
using namespace std;
inline int read() {
int x = 0, s = 1;
char ch = getchar();
while(ch < '0' || ch > '9') {
if(ch == '-')
s = -s;
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + ch - '0';
ch = getchar();
}
return x * s;
}
void write(int x) {
if(x < 0) {
x = ~(x - 1);
putchar('-');
}
if(x > 9)
write(x / 10);
putchar(x % 10 + 48);
}
int n, m, a, b, c, T, ans, sum;
signed main() {
T = read();
for(int t = 1; t <= T ; ++ t) {
n = read();//n 个 A
m = read();//m 个 B
a = read();//a 个 A +1
b = read();//b 个 B +1
c = read();//至少 c 个 B 换 A
ans = sum = 2 + (n - 1) / a + (m - 1) / b;
for(int i = 1; i <= min(n, m / c); ++ i) {
sum = 2 + (i - 1) * 2;
if(n - i >= 1)
sum += (n - i - 1) / a + 1;
if(c > b)
sum += (c - 1) / b * i;
if(m - c * i >= 1) {
++ sum;
int remain = m - c * i - 1, need = (((c - 1) / b + 1) * b) - (c - 1);
if(remain / need >= i)
sum += i, remain -= need * i;
else
sum += remain / need, remain -= remain / need * need;
sum += remain / b;
}
ans = max(ans, sum);
}
write(ans);
putchar('\n');
}
}
/*
6
1 1 1 1 1
5 4 3 3 2
5 5 3 3 2
3 9 3 3 3
7 3 3 5 8
4 7 2 8 5
2
5
6
8
4
5
*/
T4 奇怪的函数
嗯，挺好的一道题，可能是因为我以前没见过这类的吧。
看到又有操作又有查询，想到线段树。
线段树维护操作。
正常的线段树的合并，一般写为 \(f(f(ls), f(rs))\)，\(f(x)\) 可以代表取最大值最小值，相加，相乘等等等等。
但是也可以写作 \(g(f(ls))\)，这里的 \(f\) 和 \(g\) 与我们维护的东西有关。
比如这道题。我们发现总的操作总能写成 \(max(min(x + v, l), r)\) 的形式。
怎么合并？
我们知道：
\[\begin{aligned} min(max(a, b), c) &= min(max(a, c), max(b, c))\\ max(min(a, b), c) &= max(min(a, c), min(b, c)) \end{aligned}\]那么设左儿子 \(f(x) = max(min(x + v, l), r)\)，右儿子 \(g(x) = max(min(x + V, L), R)\)
我们先设 \(c = min(max(l + V, r + V), L)\)，免得我一会写的太长。
那么对于这个节点的 \(h(x)\)，有：
\[\begin{aligned} h(x) &= max(min(f(x) + V, L), R)\\ &= max(min(max(min(x + v, l), r) + V, L), R)\\ &= max(min(max(min(x + v + V, l + V), r + V), L), R)\\ &= max(min(min(max(x + v + V, r + V), max(l + V, r + V)), L), R)\\ &= max(min(max(x + v + V, r + V), min(max(l + V, r + V), L)), R)\\ &= max(min(max(x + v + V, r + V), c))\\ &= max(max(min(x + v + V, c), min(r + V, c)), R)\\ &= max(min(x + v + V, c), max(min(r + V, c), R))\\ \end{aligned}\]设 \(h(x) = max(min(x + a, c), b)\)
我们发现 \(c\) 就等于我们上面设的那个 \(c\)，\(a = v + V\)，\(b = max(min(r + V, c), R)\)
于是就会 \(push_up\) 了。
这道题就没有难点了。
代码
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define M 100005
#define mod 1000000007
#define pair<int, int> P
#define make_pair MP
#define time() chrono::system_clock::now().time_since_epoch().count()
using namespace std;
inline int read() {
int x = 0, s = 1;
char ch = getchar();
while(ch < '0' || ch > '9') {
if(ch == '-')
s = -s;
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + ch - '0';
ch = getchar();
}
return x * s;
}
void write(int x) {
if(x < 0) {
x = ~(x - 1);
putchar('-');
}
if(x > 9)
write(x / 10);
putchar(x % 10 + 48);
}
int n, q, op[M], val[M], minn[M << 2], maxn[M << 2], v[M << 2];
void build(int rt, int l, int r) {
if(l == r) {
if(op[l] == 1) {
minn[rt] = INT_MAX;
maxn[rt] = 0;
v[rt] = val[l];
}
if(op[l] == 2) {
minn[rt] = val[l];
maxn[rt] = 0;
v[rt] = 0;
}
if(op[l] == 3) {
minn[rt] = INT_MAX;
maxn[rt] = val[l];
v[rt] = 0;
}
return;
}
int mid = (l + r) >> 1, ls = rt << 1, rs = ls | 1;
build(ls, l, mid);
build(rs, mid + 1, r);
int c = min(max(minn[ls] + v[rs], maxn[ls] + v[rs]), minn[rs]);
maxn[rt] = max(min(maxn[ls] + v[rs], c), maxn[rs]);
minn[rt] = c;
v[rt] = v[ls] + v[rs];
}
void change(int rt, int l, int r, int pos) {
if(l == r) {
if(op[l] == 1) {
minn[rt] = INT_MAX;
maxn[rt] = 0;
v[rt] = val[l];
}
if(op[l] == 2) {
minn[rt] = val[l];
maxn[rt] = 0;
v[rt] = 0;
}
if(op[l] == 3) {
minn[rt] = INT_MAX;
maxn[rt] = val[l];
v[rt] = 0;
}
return;
}
int mid = (l + r) >> 1, ls = rt << 1, rs = ls | 1;
if(pos <= mid)
change(ls, l, mid, pos);
else
change(rs, mid + 1, r, pos);
int c = min(max(minn[ls] + v[rs], maxn[ls] + v[rs]), minn[rs]);
maxn[rt] = max(min(maxn[ls] + v[rs], c), maxn[rs]);
minn[rt] = c;
v[rt] = v[ls] + v[rs];
}
signed main() {
n = read();
for(int i = 1; i <= n; ++ i) {
op[i] = read();
val[i] = read();
}
build(1, 1, n);
q = read();
for(int i = 1; i <= q; ++ i) {
int opp = read();
if(opp == 4) {
int x = read();
write(max(min(x + v[1], minn[1]), maxn[1]));
putchar('\n');
}
else {
int pos = read(), vall = read();
op[pos] = opp;
val[pos] = vall;
change(1, 1, n, pos);
}
}
}
/*
10
1 48
1 50
1 180
2 957
1 103
1 100
1 123
3 500
1 66
1 70
3
4 20
4 50
4 700
760
790
1419
*/
9.10 CSP 模拟 34 (rk 17)
T1 斐波那契树
考场想了个差不多，打完正解以后准备打对拍，打完对拍和暴力电脑死机了，然后就重启了，然后就拍子和暴力没了，然后就不想再打一遍了，然后就正解打炸了，，，
挺正常的一个 \(T1\)，颜色是白色的边权设成 \(1\)，黑色的设成 \(0\)，跑一边最小生成树和最大生成树，求出总权值。可证，在最小权值与最大权值之间的所有值，都可以被构建出相应的树。于是就找这两个值之间是否存在一个斐波那契数。
当然，还得判断一下是否连通。
代码
点击查看代码
#include <bits/stdc++.h>
#define M 200005
#define P pair<int, int>
#define MP make_pair
using namespace std;
inline int read() {
int x = 0, s = 1;
char ch = getchar();
while(ch < '0' || ch > '9') {
if(ch == '-')
s = -s;
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + ch - '0';
ch = getchar();
}
return x * s;
}
void write(int x) {
if(x < 0) {
x = ~(x - 1);
putchar('-');
}
if(x > 9)
write(x / 10);
putchar(x % 10 + 48);
}
int n, T, m, fa[M], fib[M], tot, res;
bool vis[M];
pair<int, P> pa[M];
int find(int x) {
while(x != fa[x])
x = fa[x] = fa[fa[x]];
return x;
}
inline bool cmp1(pair<int, P> a, pair<int, P> b) {
return a.first < b.first;
}
inline bool cmp2(pair<int, P> a, pair<int, P> b) {
return a.first > b.first;
}
inline bool Kruskal(int op) {
for(int i = 1; i <= n; ++ i)
fa[i] = i;
res = 0;
tot = 0;
if(op == 1)
stable_sort(pa + 1, pa + 1 + 2 * m, cmp1);
else
stable_sort(pa + 1, pa + 1 + 2 * m, cmp2);
for(int i = 1; i <= 2 * m; ++ i) {
int x = find(pa[i].second.first), y = find(pa[i].second.second);
if(x == y)
continue;
res += pa[i].first;
fa[x] = fa[y];
if(++ tot == n - 1)
break;
}
return tot == n - 1;
}
signed main() {
T = read();
fib[0] = 1;
fib[1] = 1;
for(int i = 2; i <= 30; ++ i)
fib[i] = fib[i - 1] + fib[i - 2];
for(int t = 1; t <= T; ++ t) {
n = read();
m = read();
for(int i = 1; i <= n; ++ i)
fa[i] = i;
for(int i = 1; i <= m; ++ i) {
int u = read(), v = read(), color = read();
pa[i * 2 - 1] = MP(color, MP(u, v));
pa[i * 2] = MP(color, MP(v, u));
}
if(!Kruskal(1)) {
printf("NO\n");
continue;
}
int lim = res;
Kruskal(2);
int ji = 1, flag = 0;
while(fib[ji] <= res) {
if(fib[ji] >= lim)
flag = 1;
++ ji;
}
if(flag == 1)
printf("YES\n");
else
printf("NO\n");
}
}
/*
2
4 4
1 2 1
2 3 1
3 4 1
1 4 0
5 6
1 2 1
1 3 1
1 4 1
1 5 1
3 5 1
4 2 1
YES
NO
*/
T2 期末考试
赛时因为一些玄学问题，挂了 \(30\)，赛后用异或哈希 \(+\) 状压，两个全炸了，一个负责 \(WA\)，一个负责 \(T\)，，，
我发誓这是我最后一次用异或哈希，，，
题还是挺好的，第一次了解到 \(meet in the middle\) 这个东西。
先枚举前五道题的答案，用哈希存一下每个状态有多少种情况，再去枚举后五个。打的丑的话会卡常，，，
代码
点击查看代码
#include<bits/stdc++.h>
#define M 200005
#define int long long
#define mod 993244853
#define time() chrono::system_clock::now().time_since_epoch().count()
using namespace std;
int T, n, bin[31], Pow[11], hash_qian, hash_hou, R, ans, sc, grade[M], s[M];
string str;
unordered_map<int, int> mp;
void Hash() {
Pow[0] = R;
for(int i = 1; i <= 10; ++ i) {
Pow[i] = Pow[i - 1] << 13;
Pow[i] ^= Pow[i] >> 17;
Pow[i] ^= Pow[i] << 5;
Pow[i] %= mod;
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
srand(time());
R = 131;
Hash();
cin >> T;
for(int t = 1; t <= T; ++ t) {
mp.clear();
cin >> n;
ans = 0;
for(int i = 1; i <= n; ++ i) {
cin >> str >> grade[i];
grade[i] /= 10;
s[i] = 0;
for(int j = 9; j >= 0; -- j)
s[i] = (s[i] << 2) + (str[j] - 'A');
}
for(int i = 0; i <= 1023; ++ i) {
bool flag = 0;
hash_qian = 0;
for(int j = 1; j <= n; ++ j) {
int x = 3;
sc = 0;
for(int k = 1; k <= 5; ++ k) {
if((x & i) == (s[j] & x))
++ sc;
x <<= 2;
}
if(sc > grade[j]) {
flag = 1;
break;
}
hash_qian = (hash_qian * R + Pow[sc]) % mod;
// hash_qian = (hash_qian + Pow[sc]) << 13;
// hash_qian ^= hash_qian >> 17;
// hash_qian ^= hash_qian << 5;
// hash_qian %= mod;
}
if(!flag)
++ mp[hash_qian];//, cout << hash_qian << '\n';
}
for(int i = 1; i <= n; ++ i)
s[i] >>= 10;
for(int i = 0; i <= 1023; ++ i) {
bool flag = 0;
hash_hou = 0;
for(int j = 1; j <= n; ++ j) {
int x = 3;
sc = grade[j];
for(int k = 1; k <= 5; ++ k) {
if((x & i) == (s[j] & x))
-- sc;
x <<= 2;
}
// cout << "!!" << sc << '\n';
if(sc < 0 || sc > 5) {
flag = 1;
break;
}
hash_hou = (hash_hou * R + Pow[sc]) % mod;
// hash_hou = (hash_hou + Pow[sc]) << 13;
// hash_hou ^= hash_hou >> 17;
// hash_hou ^= hash_hou << 5;
// hash_hou %= mod;
}
if(!flag)
ans += mp[hash_hou];//, cout << "!!!" << hash_hou << '\n';
}
cout << ans << '\n';
}
}
/*
3
3
AAAAAAAAAA 0
BBBBBBBBBB 0
CCCCCCCCCC 0
1
CCCCCCCCCC 90
2
AAAAAAAAAA 10
ABCDABCDAB 20
1
30
57456
*/
T4 小X的 的Galgame
（至于为什么题目里两个"的"中间还有一个空格，我也不知道）
我就今天没逆序开题，就今天 \(T4\) 好写，，，
树形dp吧算是。
\(tree[u][1]\) 代表 \(u\) 的子树里有存档点的最小花费，\(tree[u][0]\) 代表 \(u\) 的子树里没存档点的最小花费。
考虑怎么去转移。
\(tree[u][0]\) 比较好想
策略应当为将 \(u\) 存档时，一次性去到所有应当去到的叶子，再去被 u 子树内其他节点存档时覆盖的叶子，反过来考虑就是每个叶子是在到根路径上第一个存档节点 u 存档时被去到的。
可以将 1 看作被存档，而如果一个节点没有存档，但子树内和祖先都存在存档点，那么这个节点是否存档没有影响，不妨看作存档。
这样存档的节点实际是原树删去一些叶子部分的子树剩余的全部子树，根据这个性质，DP 变得容易。
设 fu 表示 u 子树没有存档的最小代价，实际就是 u 到所有叶子距离之和，gu 表示 u 子树被存档的最小代价。
设 cntu 为 u 子树内的叶子个数，那么 fu 转移是容易的。
gu 转移是讨论儿子 v 有没有存档，没有存档即 cntv×w(u,v)+fv，有存档即 dist(1,v)+gv。
注意到在实际过程中，存在一个有存档的 v，是直接从 u 而不是 1 出发的，相当于如果存在有存档的 v，那么最终 gu 应当减去 dist(1,u)。这部分可以特殊处理，具体只需要维护差值的最小值，判断是否存在有存档的 v 或者将一个不存档的替换成有存档的来减去 dist(1,u) 会不会更优。
代码
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define M 100005
using namespace std;
int n, dis[M], tree[M][2], size[M];
vector<pair<int, int> > edge[M];
void dfs(int u, int fu, int t) {
dis[u] = dis[fu] + t;
int minn = LONG_LONG_MAX, cnt_1 = 0, cnt_0 = 0;
for(int i = 0; i < edge[u].size(); ++ i) {
int v = edge[u][i].first, tt = edge[u][i].second;
if(v == fu)
continue;
dfs(v, u, tt);
tree[u][0] += tree[v][0] + tt * size[v];
if(tree[v][1] + dis[v] < tree[v][0] + tt * size[v]) {
tree[u][1] += tree[v][1] + dis[v];
++ cnt_1;
}
else {
tree[u][1] += tree[v][0] + tt * size[v];
minn = min(minn, tree[v][1] + dis[v] - tree[v][0] - tt * size[v]);
++ cnt_0;
}
size[u] += size[v];
}
if(cnt_1 + cnt_0 == 0) {
size[u] = 1;
return;
}
if(cnt_1)
tree[u][1] -= dis[u];
else
tree[u][1] += min(0ll, minn - dis[u]);
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i < n; ++ i) {
int u, v, t;
cin >> u >> v >> t;
edge[u].push_back({v, t});
edge[v].push_back({u, t});
}
dfs(1, 0, 0);
cout << min(tree[1][1], tree[1][0]) << '\n';
}
/*
8
1 2 1
3 1 1
2 4 2
5 4 2
6 2 2
3 7 3
8 3 3
14
*/
/*
10
1 2 707939188
2 3 782074741
3 4 46843572
4 5 615425450
1 6 218457033
5 7 644550627
3 8 117264669
7 9 802389431
5 10 634181190
4569125901
*/
9.11 CSP 模拟 35 (rk 3)
T1 一般图最小匹配
考场想了个错解（贪心），然后又细想了想怎么让错解对的更多。
维护整个数列的从小到大的排序时间复杂度不太行，于是就想到值维护最小值。
但是值维护最小值不行啊，太容易 \(WA\) 了，于是维护了次小值。
然后，，，
次次小值，次次次小值，，，
然后再测试点分治，\(n \le 1000\) 的维护排序后的序列，其他的维护最小值，次小值，次次小值，次次次小值，，，
然后就是暴力最高分，\(75\)
错解代码
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define M 5005
#define mod 1000000007
#define P pair<int, int>
#define MP make_pair
#define time() chrono::system_clock::now().time_since_epoch().count()
using namespace std;
inline int read() {
int x = 0, s = 1;
char ch = getchar();
while(ch < '0' || ch > '9') {
if(ch == '-')
s = -s;
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + ch - '0';
ch = getchar();
}
return x * s;
}
void write(int x) {
if(x < 0) {
x = ~(x - 1);
putchar('-');
}
if(x > 9)
write(x / 10);
putchar(x % 10 + 48);
}
int n, T, m, a[M], ans, tong[M];
signed main() {
T = 1;
for(int t = 1; t <= T; ++ t) {
n = read();
m = read();
for(int i = 1; i <= n; ++ i)
a[i] = read();
if(n > 1000) {
priority_queue<pair<int, P>, vector<pair<int, P>>, greater<pair<int, P>> > zong;
for(int i = 1; i <= n ; ++ i) {
int minn = LONG_LONG_MAX, ci_minn = LONG_LONG_MAX, cci_minn = LONG_LONG_MAX, ccci_minn = LONG_LONG_MAX, ii = 0, jj = 0, ci = 0, cj = 0, cci = 0, ccj = 0, ccci, cccj;
for(int j = 1; j <= n; ++ j) {
if(i == j)
continue;
int ji = abs(a[i] - a[j]);
if(ji <= minn)
ccci_minn = cci_minn, cci_minn = ci_minn, ci_minn = minn, minn = ji, ccci = cci, cccj = ccj, cci = ci, ccj = cj, ci = ii, cj = jj, ii = i, jj = j;
else
if(ji < ci_minn)
ccci_minn = cci_minn, cci_minn = ci_minn, ci_minn = ji, ccci = cci, cccj = ccj, cci = ci, ccj = cj, ci = i, cj = j;
else
if(ji < cci_minn)
ccci_minn = cci_minn, cci_minn = ji, ccci = cci, cccj = ccj, cci = i, ccj = j;
else
if(ji < ccci_minn)
ccci_minn = ji, ccci = i, cccj = j;
}
zong.push(MP(minn, MP(ii, jj)));
zong.push(MP(ci_minn, MP(ci, cj)));
zong.push(MP(cci_minn, MP(cci, ccj)));
zong.push(MP(ccci_minn, MP(ccci, cccj)));
}
for(int i = 1; i <= m && (!zong.empty()); ++ i) {
while(tong[zong.top().second.first] || tong[zong.top().second.second])
zong.pop();
ans += zong.top().first;
tong[zong.top().second.first] = 1;
tong[zong.top().second.second] = 1;
}
}
else {
priority_queue<pair<int, P>, vector<pair<int, P>>, greater<pair<int, P>> > q[M], zong;
for(int i = 1; i <= n ; ++ i) {
for(int j = 1; j < i; ++ j) {
zong.push(MP(abs(a[i] - a[j]), MP(i, j)));
}
}
for(int i = 1; i <= m; ++ i) {
while(tong[zong.top().second.first] || tong[zong.top().second.second])
zong.pop();
ans += zong.top().first;
tong[zong.top().second.first] = 1;
tong[zong.top().second.second] = 1;
}
}
write(ans);
}
}
/*
4 1
2 4 7 3
1
*/
/*
8 3
9 2 3 12 11 7 6 5
3
*/
卡的话也比较容易，让 \(1001 \le n\)，并让 \(\displaystyle \frac{n}{m}\) 尽可能小，就 \(WA\) 了。
然后来讲正解。
一个显然的事实是 一点都不显然 :
最优匹配只会考虑匹配排序后相邻的两个元素。
考虑先排序，\(f_{i, j}\) 表示前 \(i\) 个元素中，选取 \(j\) 对匹配的最小值。
不选当前元素时 \(f_{i, j} = f_{i − 1, j}\)
选取当前元素时 \(f{i, j} = f{i − 2, j} + a_i − a_{i − 1}\)
两者取 \(min\) 即可。总复杂度 \(O(nm)\)
代码
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define M 5005
using namespace std;
inline int read() {
int x = 0, s = 1;
char ch = getchar();
while(ch < '0' || ch > '9') {
if(ch == '-')
s = -s;
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + ch - '0';
ch = getchar();
}
return x * s;
}
void write(int x) {
if(x < 0) {
x = ~(x - 1);
putchar('-');
}
if(x > 9)
write(x / 10);
putchar(x % 10 + 48);
}
int n, T, m, a[M], dp[M][M], ans;
signed main() {
T = 1;
for(int t = 1; t <= T; ++ t) {
n = read();
m = read();
for(int i = 1; i <= n; ++ i)
a[i] = read();
stable_sort(a + 1, a + 1 + n);
ans = LONG_LONG_MAX;
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = dp[1][0] = 0;
for(int i = 2; i <= n; ++ i) {
dp[i][0] = 0;
for(int j = 1; j <= min(i / 2, m); ++ j)
dp[i][j] = min(dp[i - 2][j - 1] + a[i] - a[i - 1], dp[i - 1][j]);
ans = min(ans, dp[i][m]);
}
write(ans);
}
}
/*
4 1
2 4 7 3
1
*/
/*
8 3
9 2 3 12 11 7 6 5
3
*/
/*
10 2
606771589 56825125 185482190 132818542 406283233 460383919 497973450 244096167 17502318 238309819
*/
如果压一维会跑得很快，至少比我这个快 \(10 \sim 20\) 倍。
T2 重定向
（场切，但是写的奇丑无比）
这里讲个人思路，但毕竟是考场思路，有些地方比较麻烦。所以建议去看官方题解。
先看的数据范围，嗯，\(O(n)\)。
考虑直接去扫一遍，但是不知道扫到什么地方去决策。
从左往右扫，可以从最左边先弄出一段来，保证这一段里不需要操作，即已经最优了。（这一段的长度可以为 \(0\)）
怎么找这一段呢？
设 \(a[i]\) 为 \(i\) 位置上的数，\(tong[i]\) 表示 \(i\) 出现的位置，没出现过就是 \(0\)。
从左往右枚举 \(pos1\)，如果满足
\[\begin{aligned} a[pos1] = pos1\\ a[pos1] = 0 且 tong[pos1] = 0 \end{aligned}\]这两个条件中的任意一个，就继续枚举。
如果 \(a[pos1] = 0\) 且 \(tong[pos1] \not= 0\)
那就好说了，直接把 \(tong[pos1]\) 那个位置删掉，拿来用。
然后直接走到尾就行了，但是 \(tong[pos1]\) 那个位置不输出。
但是如果 \(a[pos1] \not= pos1\) 且 \(a[pos1] \not= 0\)
那还是挺麻烦的，这一段已经到头了，需要进行其他处理。
如果 \(a[pos1] < a[pos1 + 1]\)，继续枚举 \(pos1\)。
如果 \(a[pos1] > a[pos1 + 1]\) 继续分情况讨论：
如果 \(a[pos1 + 1] = 0\)
如果存在 \(pos3\) 小于 \(pos1\) 且没有被用到过且 \(tong[pos3] = 0\)，那么就删除当前位置，让下一个位置为 \(pos3\)
否则，设 \(pos2\) 为以前没有被用到过的，且 \(tong[pos2] = 1\) 的最小的数，那么删掉位置 \(tong[pos2]\)
如果 \(a[pos1] < a[pos1 + 1]\)，那么直接删掉 \(pos1\)。
嗯，如果这次枚举已经删掉了一个位置，那么以后就不要再删了。
基本讲完了，但是发现还会有 \(1\ 2\ 3\ 4 \dots n\) 这种情况以及 \(0\ 0\ 0\dots\) 这种情况，这些情况会导致我们输出 \(n\) 个数，所以我们不能一边扫一遍输出，得把要输出的答案记下来，存到 \(ans\) 数组里，最后只输出 \(ans\) 数组的 \(1 \sim n - 1\) 位这些数就行了。
代码
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define M 200005
using namespace std;
inline int read() {
int x = 0, s = 1;
char ch = getchar();
while(ch < '0' || ch > '9') {
if(ch == '-')
s = -s;
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + ch - '0';
ch = getchar();
}
return x * s;
}
void write(int x) {
if(x < 0) {
x = ~(x - 1);
putchar('-');
}
if(x > 9)
write(x / 10);
putchar(x % 10 + 48);
}
int n, T, m, q, a[M], tong[M], ban, pos1, pos2, ans[M], cnt, pos3, ji;
signed main() {
T = read();
for(int t = 1; t <= T; ++ t) {
for(int i = 1; i <= n; ++ i)
tong[a[i]] = 0;
tong[ji] = 0;
n = read();
for(int i = 1; i <= n; ++ i)
a[i] = read(), tong[a[i]] = i;
pos1 = 1, pos2 = 1, ban = 0, cnt = 0, pos3 = 1;
if(a[1] <= 1) {
for(; pos1 <= n; ++ pos1) {
if(a[pos1] == pos2) {
ans[++ cnt] = pos2;
++ pos2, ++ pos3;
continue;
}
if(a[pos1] == 0) {
if(tong[pos2]) {
ans[++ cnt] = pos2;
ban = tong[pos2];
++ pos2;
++ pos3;
++ pos1;
break;
}
ans[++ cnt] = pos2;
++ pos2, ++ pos3;
continue;
}
break;
}
if(ban) {
for(; pos1 <= n; ++ pos1) {
if(pos1 == ban)
continue;
if(a[pos1])
ans[++ cnt] = a[pos1];
else {
while(tong[pos2])
++ pos2, ++ pos3;
ans[++ cnt] = pos2;
++ pos2, ++ pos3;
}
}
for(int i = 1; i <= min(cnt, n - 1); ++ i)
if(ans[i])
write(ans[i]), putchar(' ');
putchar('\n');
continue;
}
}
for(; pos1 <= n; ++ pos1) {
if(pos1 == ban)
continue;
if(a[pos1] == 0) {
while(tong[pos2])
++ pos2;
ans[++ cnt] = pos2;
++ pos2;
continue;
}
else {
if(ban) {
ans[++ cnt] = a[pos1];
continue;
}
if(a[pos1] > a[pos1 + 1] && a[pos1 + 1]) {
tong[a[pos1]] = 0;
ban = 1;
continue;
}
while(tong[pos3])
++ pos3;
if(a[pos1] > a[pos1 + 1] && (!a[pos1 + 1]) && pos3 < a[pos1]) {
tong[a[pos1]] = 0;
ban = 1;
ji = pos3;
continue;
}
if(a[pos1] > a[pos1 + 1] && (!a[pos1 + 1])) {
ban = tong[pos2];
tong[pos2] = 0;
ans[++ cnt] = a[pos1];
continue;
}
ans[++ cnt] = a[pos1];
}
}
for(int i = 1; i <= min(cnt, n - 1); ++ i)
if(ans[i])
write(ans[i]), putchar(' ');
putchar('\n');
}
}
/*
1
10
0 6 7 9 0 4 2 3 5 8
*/
/*
1
4
2 4 0 0
2 1 3
*/
/*
8
7
0 0 0 0 7 6 5
7
1 2 3 4 5 7 6
7
1 2 5 0 0 3 4
7
2 4 1 3 0 0 6
7
2 0 1 3 0 0 6
7
2 4 3 0 0 0 6
7
1 2 5 0 0 0 4
7
0 0 0 0 0 0 0
1 2 3 4 6 5
1 2 3 4 5 6
1 2 5 3 6 4
2 1 3 4 5 6
2 1 3 4 5 6
2 3 1 4 5 6
1 2 3 5 6 4
1 2 3 4 5 6
*/
T3 斯坦纳树
虚树，现在还没学，不会，以后再说（以后就不说了）
粘一下官方题解：
先考虑所有边权都不为0的情况应该怎么做。
首先不难看出，点集在树上的斯坦纳树即为其虚树。虚树上的边权和即为正确答案。
我们下面证明：该算法是正确的，当且仅当给定点集 \(V1\) 在 \(G\) 上的虚树点集 \(V′1\) 和 \(V1\) 相同。（另一个说法是，任意 \(V1\) 中的两个点 \(u, v\) 的 \(LCA\) 也在 \(V1\) 中）
其充分性不难证明，下面证其必要性：
若存在属于虚树点集 \(V′1\)，且不属于 \(V1\) 的点（下面简称虚点），则在虚树上，虚点 \(u\) 至少存在三条相关联的边。在斯坦纳树中，这三条边对答案的贡献是这三条边的权值和；而在我们建立的最小生成树中，至少有一条边的权值被计算了两次（由于虚点并不在原先的点集中，所以要让这三条边的另一个端点联通，就不得不经过其中一条边两次），因而答案就是错误的。
对于边权存在 \(0\) 的情况，只需要将所有由 \(0\) 边连结的连通块视为一个点，一个连通块被选中当且仅当其中至少有一个点被选中，然后应用上述做法即可。
关于如何维护虚点：可以考虑倒着做，每次删去一个点。如果删去的这个点有三条及以上的边相连，它就转型成为虚点。如果某次删除后，某个虚点只有两条边相连，则该虚点消失。答案为 \(1\) 当且仅当不存在虚点时。