Ptilopsis_w's little blog

岛屿观测 原题 P3616 Fucking Forest Park 题目需要求露出水面的连通块个数，我们没法直接维护，考虑每个连通块挑出来一个代表点，选最左边或者最右边都可，这时我们就需要求它左边比水面低，它自己比水面高的石头的个数，你可以将其看成一个二维数点，但是有更简单的做法：把询问差分一下，用比水面高的石头的个数减去它左边和它都比水面高的石头的个数即可，这样就变成一维数点了，树状数组维护即可。 #include <bits/stdc++.h>using namespace std;struct Rhine_Lab { Rhine_Lab() { freopen("patrick.in", "r", stdin); freopen("patrick.out", "w", stdout); }};Rhine_Lab Ptilopsis_w;const int N = 5e5+10;int lim;struct ...

会议选址 有一个很显然的贪心: 先随便选一个点，然后往它子树里会减小答案的方向走，走到最后一定是最优点。 维护这个步骤我们需要在一棵子树内查询编号在 [l,r][l,r][l,r] 内的点的个数，这个可以用 dfs 序和主席树实现。 但是如果树是一条链的话会被卡成单次 O(n)O(n)O(n) 询问，所以可以用树分治保证树高是 log⁡n\log nlogn 级别的。 但是每走一个点要查询一遍它的所有子树，如果给个菊花图的话还是会被卡成单次 O(n)O(n)O(n)，我们可以用三度化来使每个点的度数最大为 333 ，保证时间复杂度是 O(nlog⁡2n)O(n \log^2 n)O(nlog2n) 的。 #include <algorithm>#include <cstdio>#include <iostream>#include <vector>using namespace std;const int SIZE = 1e5 + 10; struct EDGE { int v, nxt;} edge[SIZE ...

分身游走 看到 k≤30k \le 30k≤30 ，就大概想到是个关于 kkk 的 DP, 然而太菜了当时连暴力 DP 都写不出来。 观察性质： 在最优方案中，一定不会出现超过一个分身进入以 xxx 为根的子树又回到 xxx 的父亲的情况。 在最优方案中，如果有至少两个分身进入了以 xxx 为根的子树，那么这些分身都应该停在以 xxx 为根的子树内。 用这两条性质可以将 DP 优化到 O(n2k2)O(n^2k^2)O(n2k2)。 这个 DP 需要枚举出发点，重新计算以每个点为根的子树的 DP 值，但是其中有不少重复计算。 我们可以枚举每一条边 (x,y)(x,y)(x,y), 计算以 yyy 为父节点，xxx 为根的子树的 DP 值，并在之后的 DP 中重复利用。 这样我们枚举出发点时只需要将所有儿子的答案合并起来即可。 然而这个算法的时间复杂度又是与点的度数有关的，可以用三度化保证时间复杂度为 O(nk2)O(nk^2)O(nk2)。 #include <cstdio>#include <cstring>#include <iostrea ...

EntropyIncreaser 与金字塔 LOJ6676 第二个和第三个矩阵都是蛇形填数，而第一个矩阵是环形的，这启发我们按照第一个矩阵分层考虑。 先考虑 x1=y1=1,x2=y2=nx_1=y_1=1, x_2=y_2=nx1​=y1​=1,x2​=y2​=n 时的做法。 设当前的环为从外到内第 aaa 个环，则这个环里最小的数 LLL 为 4(a−1)(n−a−1)+14(a-1)(n-a-1)+14(a−1)(n−a−1)+1，最大的数 RRR 为 4a(n−a)4a(n-a)4a(n−a)，这个可以按每个环里数的个数推导。 先把每个环里左上角的数抠出来，剩下的数的答案就是 ∑i=L+1Ri∗(R+L+1−i)\sum\limits _{i=L+1}^{R} i*(R+L+1-i)i=L+1∑R​i∗(R+L+1−i)，把这个式子拆开得到 (R+L+1)∑i=L+1Ri−∑i=L+1Ri2(R+L+1)\sum\limits_{i=L+1}^Ri - \sum\limits _{i=L+1}^{R}i^2(R+L+1)i=L+1∑R​i−i=L+1∑R​i2，用平方和公式就可 ...

Sasha and a Very Easy Test 原题 CF1109E 因为模数 PPP 不一定是质数，可能不存在逆元，所以除法比较难搞。 考虑一个数只有与模数 PPP 不互质时才没有逆元，我们可以考虑将 PPP 质因数分解，并把操作的每一个数都分离出 PPP 的因子来。 这样一个数被分成两部分：与 PPP 互质的部分 和 与 PPP 不互质的部分。 互质的部分就直接乘逆元就行了，不互质的部分可以记录一个数所含 PPP 的每个质因子的指数，将这两部分乘起来就可以得到原数，除法的话直接指数相减再更新答案就没事了。 #include <cmath>#include <cstdio>#include <cstring>#include <iostream>using namespace std;typedef long long ll;const int N = 5e5+15;struct type { int cnt[10]; ll mul; type() { memset(cnt ...

归并 考虑用 fhq-treap 维护数列。 设合并的时候数列 aaa 的第一个数为 xxx，数列 bbb 的第一个数为 yyy 。 如果 x<yx < yx<y ，就将数列 aaa 前面所有小于 yyy 的数合并到新序列里，否则就将数列 bbb 前面所有小于 xxx 的数合并到新序列里。 每次合并的时间复杂度是 O(段数∗log⁡n)O(段数* \log n)O(段数∗logn) 的。 但是每次合并的时候数列的前缀最大值会越来越小，也就是整个数列越来越接近有序。 但是总体的时间复杂度我不会证，直接 skip 罢。 #include <algorithm>#include <cstdio>#include <iostream>#include <random>using namespace std; const int N = 1e6+10; namespace fhq_treap { struct node { int ls, rs; int siz, key, v ...

导出子图 题目给了一个限制： ∣ai−bi∣≤12|a_i-b_i| \le 12∣ai​−bi​∣≤12 。 这启发我们进行状压DP，具体来说可以维护选择了哪些联通块，然后进行一个 DP 的做就 OK 了。 #include <cstdio>#include <iostream>#include <map>#include <vector>using namespace std; typedef long long ll;const int N = 55;const int P = 998244353; ll ans;int n, m;int g[N];map<vector<int>, ll> f[2]; int main(){ cin >> n >> m; for(int i = 1; i <= m; i++) { int x, y; cin >> x >> y; if(x < y) ...

tree 考虑怎么询问一个点 xxx 的编号最大的祖先，可以先把树拍到 dfs 序上，用每个节点的编号在它的子树里取 max⁡\maxmax，然后查询 dfn[x]dfn[x]dfn[x] 处的 max⁡\maxmax 值即为 xxx 的编号最大的祖先。 而这时我们还需要保证取到的 max⁡\maxmax 值在另一棵树上是 yyy 的祖先，我们可以只把 yyy 的祖先插入到线段树中，这样询问出来的就一定是 yyy 的祖先了。 直接暴力插入不太行，因为这题不带修，我们可以用主席树维护 yyy 到根的路径构成的线段树，时间复杂度 O((n+m)log⁡n)O((n+m) \log n)O((n+m)logn)。 #include <algorithm>#include <cmath>#include <cstdio>#include <iostream>#include <vector>using namespace std;const int N = 100005;namespace HJT_tree { str ...

树 设 gcd⁡(x→y)\gcd(x \rightarrow y)gcd(x→y) 为 xxx 到 yyy 的路径上边权的 gcd⁡\gcdgcd。 我们要求的就是 ∑i=1n∑j=i+1n[gcd⁡(x→y)]\sum{i=1}^{n} \sum_{j=i+1}^{n} [\gcd(x \rightarrow y)] ∑i=1nj=i+1∑n​[gcd(x→y)] 考虑经典莫反： ∑d=1Aμ(d)∑i=1n∑j=i+1n[d∣gcd⁡(x→y)]\sum_{d=1}^{A} \mu(d) \sum_{i=1}^{n} \sum_{j=i+1}^{n} [d|\gcd(x \rightarrow y)] d=1∑A​μ(d)i=1∑n​j=i+1∑n​[d∣gcd(x→y)] 考虑后两个求和式子，其实就是由 ddd 的倍数构成的边所组成的路径数，这个可以并查集解决。 但是还有一些修改操作，我们可以进行线段树分治，将被修改的边放到最后处理，计算出一个边的对于时间上的影响范围。 #include <algorithm>#include <cstdio>#incl ...

Zero-Sum Ranges 2 我们将数列的前缀和画到坐标系上，这玩意长得大概像个树(?)， 我们自顶向下构造这个树，每次添加一层。 设 flen,cnt,holwf_{len, cnt, holw}flen,cnt,holw​ 为目前构造了长度为 lenlenlen 的序列， 有 cntcntcnt 个和为 000 的区间， 中间有 holeholehole 个"洞"。 转移就可以 f[len+x][cnt+C(x,2)][x-(hole+2)] += f[len][cnt][hole] 了。 填好表格之后答案为 f2n+1,k,0+∑fi,j,k∗f2n+1−i,k−j,k−1f_{2n+1,k,0} + \sum{f_{i,j,k}*f_{2n+1-i,k-j,k-1}}f2n+1,k,0​+∑fi,j,k​∗f2n+1−i,k−j,k−1​ #include <bits/stdc++.h>using namespace std;typedef long long ll;const int N = 65;int n, m, l;ll fact ...