规划
今天这一天是自己做题,改题,复习,学习。这一天也可以说比较充实,要抓紧时间,做更有效的事情。首先是今日的计划:
- 上午
- 改前天的 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
|