2023.1.19
T3
题目大意
给定一棵树，边有黑白两种颜色，初始边都是黑色
有两种操作
- 将u到v路径上的边颜色反转
- 询问u只经过黑边能走到几个点
solution
可以想一下链的部分分，用线段树维护边的颜色，然后在线段树上二分（或者二分套线段树）来找到点u经过黑边走到的区间
拓展到树上，考虑树链剖分，每个节点维护其轻儿子和本身组成的黑色连通块大小（就是只经过黑边能走到的点数）\(f_i\)
然后查询就比较简单，从点u向上跳重链，保证路径上都是黑边，然后找到第一个不符合的重链和对应的位置，然后对于这个点和重链做链的部分。不过每个点的贡献变成\(f_i\)，还要再打个线段树
那么如何修改，先考虑差分，修改u到根的边，那么维护边的线段树要维护反转，维护 \(f\) 的线段树在轻边处要修改。修改时先从上到下黑变白，然后颜色反转，最后从下到上白边黑（这个顺序时保证减去的原来的，加上的是新的），修改时还要调用二分的那个部分
所以时间复杂度是\(O(q\log^2 n)\)
2023.1.22
T1
题目大意
给定一棵树，树上每个点有权值\(a_i\)，有以下两种操作：
- 让第x层的节点都变成其子树中的最小值
- 让第x层的节点都变成其子树中的最大值
问最后根节点的权值
solution
这道题有启发性的部分分是 \(a_i=0/1\) ，但是这档分可以用水法过掉，就没有仔细想，亏...
首先这道题的第一想法是把每一层的状态压起来，叶子节点的权值不变。对于\(a_i=0/1\)，进行简单的分讨：
- 最后一次对根的修改是取最小值
- 最后一次对根的修改是取最大值，与上面类似
那么若存在 \(a_i>1\) ，应该这么做呢？
不难发现，如何我们对于第一种情况，我们把 \(a_i<=mid\) 当成1，其他当成0，然后做一遍链的部分，若可以答案为1，则答案一定小于n，这可以二分
情况二类似，时间复杂度\(n\log^2n\)
T2
题目大意
n个有标号的数放进k个有标号的集合，要求每个数都在一个集合，每个集合至少有一个数
定义一个集合的贡献为集合中的全部数的按位与和，一种分配方案的贡献为k个集合的贡献和
求全部分配方案中，贡献最大的的值和数量
solution
首先可以想到从高位往低位做，那么我们就可以贪心，因为高位一定能选就选，否则一定不会更优
令还剩下n个数，k个集合，有c个数的第w位为p
- 如果 \(n=c\) ，我们给 \(ans1\) 累加 \(k2^p\)
- 否则如果 \(c\le k-1\) ，意味着c个1我们都要放到不同集合，我们给 \(ans1\) 累加 \(c2^p\) ，给 \(ans2\) 乘上 \(\binom{k}{c}c!\) ，然后把这c个数删掉，\(k=k-c\)
- 否则，我们就把这位为0的合并起来，给 \(ans1\) 累加 \((k-1)2^p\)
最后我们发现，可能剩下n个数，k个集合，那么就把答案乘上 \(S(n,k)k!\)
2024.1.23
T1
考场上差不多想到了
题目大意
定义 \(f(a[1,2,...,n],S)\) 表示把集合 \(S\) 插入序列 \(a\) 中，最小的逆序对数
给定 \(n,m\) 和 \(p\) 序列，有个序列 \(b\) ，满足 \(b_i\in [1,n+m]\cup\Z\) ，\(b_i\) 互不相同且为第 \(p_i\) 小的
问所有符合要求的序列 \(b\) 的 \(f(b,\{1,2,...,n+m\}-\{b_1,b_2,...b_n\})\) 的和
solution
首先用历史版本最小值求出，分别在这 \(n+1\) 个间隙中插入数字最小增加的逆序对数
然后发现答案是新增加的逆序对+方案数 \(\times\) 原逆序对数
题目就变成了有 \(m\) 个求，\(n+1\) 个位置，在 \(i\) 个位置放 \(x\) 个球的贡献为 \(xw_i\)，问所有放置方案的贡献和
发现每个位置是等价的，而且都恰好贡献了 \(\binom{n+m}{n+1}\) 次
T2
题目大意
有 \(n\) 只老鼠，位置和家分别在 \(x_i,y_i\) ，我们在其中建造 \(k\) 个中转站 \(z_1,z_2,...,z_k\)，代价为 \(\sum_{i=1}^nmin_{j=1}^k|x_i-z_j|+|y_i-z_j|\)
问 \(k=1,2,...,m\) 的答案
solution
首先考虑贪心，我们按照 \(x_i+y_i\) 排序，那么一个中转站一定管理一段区间
那么知道了一段区间，如何算贡献呢？继续贪心，中转站应该建在这段区间的 \(x,y\) 的中位数上
那么我们就可以打一个时间复杂度为 \(O(n^3m)\) 的暴力（可以拿50pts）
考虑先优化计算区间的一个 \(n\) ，这里可以用主席树解决
然后观察到决策单调性（区间越长，增速越大），然后用分治再优化掉一个转移的 \(n\)
最后的时间复杂度为 \(O(nm\log^2n)\)
2024.1.25
没得去清北营，滚回来打A组，题目一般，可以乱搞
T3
唯一一道清新的构造题
题目大意
有 \(m\) 条电线， \(n\) 条导线
依次给出 \(n\) 条导线，连接着 \(x,y\) 两条电线，设原来两条线的通电状态为 \(s_x,s_y\) 。那么可以让两条的状态变成 \(s_x|s_y,0\) 或 \(0,s_x,s_y\)
初始的通电状态都是 \(s_i=1\) ，要求最后的通电电线数量不小于 \(\lfloor\frac m2\rfloor\) ，问导线方向
solution
可以想到把电线两两分组（奇数就单独一组），要求每组内至少有一条电线是通电的，且可以通过改变导线方向决定是哪个通电
顺推分组，若有导线 \((x,y)\) ，有两组 \((x,u),(y,v)\) 电线，那么调整成 \((x,y),(u,v)\) 也满足
同理：有两组 \((x,u),(y)\) ，可以调整成 \((x,y),(u)\)
然后倒推，先给每组电线钦定一个通电状态，然后撤回导线操作，判断是否合法，输出导线方向
2024.1.26
还是A组，题目比较水，记录一点题
T3
矩乘好题，是没做过的类型
题目大意
给定 \(n,k,a,b\)
你现在位于 \((1,\frac k2)\) ，每次移动只能是从 \((x,y)\) 到$ (x+1,y)(x+1,y-1)(x+1,y+1)$，目 \(y\) 不能超 \([1,k]\) 的范围，你的目标是到 \((n,\frac k2)\)
在 \([2,n-1]\) 中，会随机出现一个障碍 \([1,a]\cup[b,k]\)
求期望可行的行路径数量 \(\mod 10^9+7\)
solution
我们定义正常的转移矩阵为\(A\)，障碍的转移为 \(B\) ，那么答案就
\[\frac{\sum_{i=2}^{n-1}A^{i-1}BA^{n-i}}{n-2} \]无法直接计算，我们考虑定义
\[X_i=A^i,Y_i=\sum_{j=2}^iA^{j-1}BA^{i-j} \]于是就有转移：
\[X_i=X_{i-1}A,Y_i=Y_{i-1}A+X_{i-1}B \]于是我们把 \(Y\) 接在 \(X\) 的右下角即可转移，转移矩阵为：
最后答案为\(Y_{n-1}A\)
2024.1.29
比赛时一直在摸鱼，最后两个小时水了一下提答题，结果水了70
T1
题目大意
构造一个有 \(2n\) 个点的二分图，在左边选定点的集合 \(S\) ，定义 \(F(S)\) 表示与 \(S\) 中的点有连边的点的集合，若对于所有的集合 \(S\) ，满足 \(|F(S)|<|S|\) 的恰好有k个
solution
考虑 \(i\) 连边的集合为 \(s_i\) ，那么要求 \(s_i\subseteq s_{i+1}\)，令 \(d_i=|s_{i+1}|-|s_i|\)
那么考虑
2024.2.1
考场切了T1，T2胡了一个贪心，挂了，还挂了7分的部分分
T2
ds好题，和联考的lis很像，但要难
题目大意
有 \(n\) 个二元组 \((x,y)\) ，若满足 \(x_i\le x_j\) ，那么可以获得 \(y_j-y_i\) 的贡献，并把它们删掉
问至多取 \(k\) 对二元组，问最大贡献。对 \(k=1\sim\lfloor\frac n2\rfloor\) 求出答案
solution
先按照 \(x\) 为第一关键字， \(y\) 为第二关键字排序
考虑费用流建模，暴力建模：
- \(i<j\) ，连费用 \(y_j-y_i\) ，流量为 \(1\) 的边
- 原点向 \(i\) 和 \(i\) 向汇点连流量为 \(1\) ，费用为 \(0\) 的边
再考虑差分优化一下
- 把上面第一种边改为，对于 \(i\) 到 \(i+1\) 连费用为 \(y_{i+1}-y_i\) ，流量为 \(1\) 的边
那么我们找一条可行流，就等价于找一个最大子段和
找一条退流，就等价于在反边中找最大子段和
然后对于选择的两个端点，不能再作为起点或终点
正的流量，考虑进行区间+1操作，若一段中都有流量，即最小值不为0，则可以退流
考虑如何维护，维护三个字段和信息，分别为正边的，反边的，反边且不能流最小值位置的
push up的时候，前两个可以直接合并，最后一个则判断最小值在哪边，分3种情况合并
再维护一个区间+1和-1
关于删除端点，有点细节，因为我们的节点维护的是边的信息，所以假如我们删去的是 \(l,r\) :
- l删去后缀，l-1删去前缀
- r+1删去后缀，l删去前缀
然后每次选最优的区间即可，若最小值等于0，就在第一和第三个中取最大值，否则在第一和第二中取
若某次的增量小于0，就不选
第二期...
2024.2.16
开始联考
2024.2.17
用自己的题
number
对于一个值域和定义域均为 \(U\) 的函数 \(f(x)\)，定义其将所有 \(i=1,2,\cdots,n\) 由 \(i\) 向 \(f(i)\) 连边形成的内向基环森林为 \(T(f)\)。
考虑对于某个 \(g(x)\)，\(T(g^{n-1})\) 具有怎样的特征，将 \(T(g^{n-1})\) 中 \(i\) 的出边视作在 \(T(g)\) 中从 \(i\) 点沿出边方向走 \(n-1\) 步的终点：对于 \(T(g)\) 中在环上的点，在 \(T(g^{n-1})\) 中其依然在环上；对于 \(T(g)\) 中不在环上的点，在 \(T(g^{n-1})\) 中其依然不在环上，但由于 \(n-1\) 充分大，其在 \(T(g^{n-1})\) 中与所在基环树上的环的距离必然为 \(1\)。
首先忽略 \(T(g^{n-1})\) 中不在环上的点，容易发现如果有 \(i\) 个点在环上，那么环外的点的方案数即为 \(i^{n-i}\)（这是因为对于每一个环外点的连接方案，都容易反向构造出 \(T(g)\)），则我们只需要对于所有 \(i=1,2,\cdots,n\) 计算出有 \(i\) 个点在环上的方案数 \(h_i\)。
接下来只需要考虑环长的限制，若 \(T(g)\) 中有一个长度为 \(d\) 的环，那么在 \(T(g^{n-1})\) 中其会被分裂为 \(\gcd(d,n-1)\) 个长度为 \(\dfrac{d}{\gcd(d,n-1)}\) 的环，记 \(v_d=\dfrac{d}{\gcd(d,n-1)}\)，对于每个 \(i\)，记所有 \(v_d=i\) 的 \(d\) 形成的集合为 \(S_i\)，那么长度为 \(i\) 的出现次数 \(c\) 的限制即为：\(S_i\) 内元素除 \(i\) 后进行完全背包，\(c\) 需要能被若干可重物品的和表出，这里做完全背包的复杂度是总体 \(O(n^2)\) 的。
那么，我们已经刻画了对于所有环长及其出现次数的限制，可以使用一个背包计算答案，每次枚举新加入的环长使用了多少个，使用组合数计算贡献。注意到对于长度为 \(i\) 的环，其至多使用 \(O(\dfrac{n}{i})\) 个，那么由调和级数，总复杂度即为 \(O(n\sum\limits_{i=1}^n\dfrac{n}{i})=O(n^2\log n)\)。
yoimiya
考虑一个串 \(a\)，考虑刻画出所有的 \(i,k\) 使得 \(a[i,i+k-1]=a[i+k, i+2k-1]\)。
枚举 \(k\)，设 \(b_i=[a_i==a_{i+k}]\)，那么我们只需要找到 \(b\) 中所有长度 \(\ge k\) 的连续段。
注意到这样的连续段的段数不超过 \(\lfloor n/k\rfloor\)，考虑一段一段找。发现长度 \(\ge k\) 就至少需要经过 \(k,2k,\cdots\) 这些位置中的一个，考虑枚举 \(x=ik\)，算出经过 \(x\) 的极长连续段长度。那么只需要查询 \([1,x],[1,x+k]\) 的最长公共后缀与 \([x,n],[x+k,n]\) 的最长公共前缀即可。SA 配合 ST 表容易做到 \(O(n\log n)\)。
现在我们找到了一个极长的连续段 \([L,R]\)，那么相当于对每个 \(i=L,L+1,\cdots,R-k\)，连边 \((i,i+k)\)。然后对每个连通块，把他的 \(L\) 限制取 max，\(R\) 限制取 min，每个连通块的 \((R-L+1)\) 的乘积就是答案。
注意到合并只会发生 \(O(n)\) 次，考虑快速找到所有需要合并的位置。考虑建 \(O(n\log n)\) 个虚点，\((i,j)\) 代表 \([i,i+2^j-1]\) 这个区间整体的合并情况，然后用并查集维护每一层所有点的连通情况。
换言之，如果 \((x,j),(y,j)\) 已经连通，代表着我们已经确定 \(b[x,x+2^j-1]=b[y,y+2^j-1]\)。
那么每次区间连边我们首先拆成两个长为 \(2^k\) 的区间连边，然后自顶向下递归，即可在 \(O(\alpha(n)\times\log n)\) 的时间内找到一个未被合并的位置。然后并查集在合并的时候处理一下对答案的影响即可。
由调和级数可知外层的连边次数不超过 \(O(n\log n)\)；另一方面在并查集上面每次连边必然会少一个连通块，而一共只有 \(O(n\log n)\) 个点，因此复杂度为 \(O(n\alpha(n)\times \log n)\)。
标签：总结,那么,题目,log,训练,solution,寒假,集合,考虑 From： https://www.cnblogs.com/zhy114514/p/18258903