规划
今天这一天是自己做题，改题，复习，学习。这一天也可以说比较充实，要抓紧时间，做更有效的事情。首先是今日的计划：
- 上午
- 改前天的 T4 [[总结/2023年10月16日模拟赛#T4|2023年10月16日模拟赛]]
- 学习 [[可持久化并查集]]
- 下午 & 晚上
- 了解线段树分治 luogu P5787
- 适当重温暑假的一些内容，做一些比较有难度的题目。
- 今日模版：[[匈牙利算法]]。
早上
改完前天 T4 啦！用的是邓老师的方法。实在是太妙了，60多行就解决了。前天一直没有调出来错误，程序内对拍也没有检查出错误，最后发现是输出右移 i 位打成了右移 1位，蚌埠住了。挂一下代码：
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
| #include <bits/stdc++.h>
#define N 800010
using namespace std;
int n;
int m = 1, ym;
bool vis[N][2], vi[N];
int huan[N], cnt;
int ans[N], tot;
int now;
void dfs(int u) {
if (vi[u]) return;
vi[u] = 1;
dfs((u << 1) & ym);
dfs(((u << 1) | 1) & ym);
vis[u][huan[cnt] & 1] = 1;
huan[++cnt] = u;
}
void dfs1(int u, int pur) {
int tto;
if (u != pur) ans[++tot] = u;
++now;
if (!vis[u][0]) {
tto = (u << 1) & ym;
vis[u][0] = 1;
if (tto != pur) dfs1(tto, pur);
} else if (!vis[u][1]) {
tto = ((u << 1) | 1) & ym;
vis[u][1] = 1;
if (tto != pur) dfs1(tto, pur);
}
}
set<int> mw, m1w;
char s[N];
int wg;
int main() {
freopen("carpet.in", "r", stdin);
freopen("carpet.out", "w", stdout);
scanf("%d", &n);
if (n == 1) {
puts("0");
return 0;
}
while ((1 << m) + m - 1 <= n) ++m;
--m;
ym = (1 << m) - 1;
dfs(0);
reverse(huan + 1, huan + cnt + 1);
assert(((huan[cnt] << 1) & ym) == 0);
now = cnt;
int st = 1;
for (int i = 1; i <= cnt; ++i) {
ans[++tot] = huan[i];
if (now < n - m + 1 && (!vis[huan[i]][0] || !vis[huan[i]][1])) {
dfs1(huan[i], huan[i]);
ans[++tot] = huan[i];
if (now >= n - m + 1) st = tot;
}
}
for (int i = m - 1; i; --i) {
putchar(((ans[st] >> i) & 1) ^ 48);
}
for (int i = st, j = 1; j <= n - m + 1; ++j, i = i % tot + 1) {
putchar((ans[i] & 1) ^ 48);
}
return 0;
}
|
打了可持久化并查集，这里有一个要注意的。以后如果要合并两个东西，例如启发式合并，如果一个集合有多个相关的变量 一定要全部交换！ 不能只交换一个！切记！
下午
下午写了一下线段树分治，又犯了低级错误。我要哭死。首先是 n,m,k 的顺序读入错了，然后是循环，本来应该是次，写成了次。AFO小技巧又要加新东西了（)
复习了匈牙利算法，感觉还是要比打网络流方便一点，码量也不是很大，也比较好理解，就是找增广路。
看了一下 kruskal 重构树的题目，说是明天要考。
然后学习 qoj6662 。是韩语，翻译出来的题又要理解好久（可恶)。这里推荐 bing 翻译，稍微好理解一点点，但也没好到哪里去。至于题解，我将那个 pdf 翻译了，就像是在考古一样去猜测意思，挺有趣的。
首先我花了几个小时去翻译并理解题意，我太难了。后来发现这个好像 ppt 里写错题号了，mislead 我半天（)。但是不妨碍我去做这道题。这道题大概就是这个样子的。给一个树，然后求对于任意一个节点编号区间，让这个区间内所有点联通的最小边权和之和。这道题也非常有启发意义。首先我们将问题进行转化，本来相当于是以区间为主元，然后现在将主体换到一条边上。我们就看有哪些区间会经过这条边。于是我们就想到了染色，就是将这条边两边的分别染色，看有哪些区间会包含两种颜色。然后我们就得到了的算法。我们再通过链，发现可以用 set 来维护编号序列上黑色点的区间，然后单点修改。然后再拓展到树上，发现每次染色就是染一个子树，于是乎，我们就能自然而然地想到 [[启发式合并]]，处理完子树，然后将小的合并到大的，就能解决这道题！amazing！代码如下：
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
| #include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fi first
#define se second
#define mod 1000000007ll
#define t tie
using ll = long long;
int n;
ll ans;
#define N 250010
struct edg {
int v;
ll w;
edg(int v, ll w): v(v), w(w) {}
};
vector <edg> g[N];
set<pair<int, ll> >a[N];
ll f[N];
void dfs(int u, int v, ll co) {
a[u].emplace(u, 1);
f[u] = 1 + (ll)(u - 1) * u / 2 % mod + (ll)(n - u) * (n - u + 1) / 2 % mod;
f[u] %= mod;
for (auto&& tmp : g[u]) {
int i = tmp.v;
ll w = tmp.w;
if (i == v) continue;
dfs(i, u, w);
if (u == 1) continue;
if (a[i].size() > a[u].size()) {
swap(a[i], a[u]);
swap(f[i], f[u]);
}
for (auto j = a[i].begin(); j != a[i].end(); ++j) {
auto it = a[u].upper_bound(*j);
auto pt = prev(it);
ll cz = (it == a[u].end() ? n + 1 : it -> fi) - (it == a[u].begin() ? 1 : pt -> fi + pt -> se);
ll clz = j -> fi - (it == a[u].begin() ? 1 : pt -> fi + pt -> se);
ll ctz = (it == a[u].end() ? n + 1 : it -> fi) - j -> fi - j -> se;
f[u] += clz * (clz + 1) / 2 % mod + ctz * (ctz + 1) / 2 % mod - cz * (cz + 1) / 2 % mod;
f[u] %= mod;
if (f[u] < 0) f[u] += mod;
pair<int, int> ins = *j;
f[u] += (ll)(ins.se) * (ins.se + 1) / 2 % mod;
f[u] %= mod;
if (it != a[u].begin() && pt -> fi + pt -> se == j -> fi) {
f[u] += -(ll)(pt -> se) * (pt -> se + 1) / 2 % mod + (ll)(pt -> se + j -> se) * (pt -> se + j -> se + 1) / 2 % mod - (ll)(ins.se) * (ins.se + 1) / 2 % mod;
f[u] %= mod;
if (f[u] < 0) f[u] += mod;
ins.fi = pt -> fi;
ins.se = pt -> se + j -> se;
a[u].erase(pt);
}
if (it != a[u].end() && ins.fi + ins.se == it -> fi) {
f[u] += -(ll)(ins.se) * (ins.se + 1) / 2 % mod + (ll)(ins.se + it -> se) * (ins.se + it -> se + 1) / 2 % mod - (ll)(it -> se) * (it -> se + 1) / 2 % mod;
f[u] %= mod;
if (f[u] < 0) f[u] += mod;
ins.se += it -> se;
a[u].erase(it);
}
a[u].emplace(ins);
}
}
if (u == 1) return;
ll zs = (ll)n * (n + 1) / 2 % mod - f[u];
if (zs < 0) zs += mod;
ans += zs * co % mod;
ans %= mod;
}
int maintenance_costs_sum(vector<int> U, vector<int> V, vector<int> W) {
n = U.size() + 1;
for (decltype(U.size()) i = 0; i < U.size(); ++i) {
g[U[i] + 1].emplace_back(V[i] + 1, W[i]);
g[V[i] + 1].emplace_back(U[i] + 1, W[i]);
}
dfs(1, 0, 0);
return ans;
}
#ifdef localtest
int main() {
int tot = maintenance_costs_sum({0, 2, 2, 0}, {2, 1, 4, 3}, {2, 3, 6, 5});
cout << tot << endl;
return 0;
}
#endif
|
