题解p9580 round game

机动训练 这题的瓶颈，在于把 \(a_i^2\) 看作 \(\sum\limits_{i=1}^{a_i}\sum\limits_{j=1}^{a_i}1\)，然后我们就可以看成“两两相同的机动路径都能贡献 1”。于是我们设 \(f_{x1,y1,x2,y2}\) 表示两条起点为 \((x1,y1) ......

二叉查找树 首先该树的中序遍历是唯一可以确定的（直接按照数据值排序即可）。 然后，因为权值可以被修改成一切实数，故我们完全可以把权值离散化掉。 于是我们现在可以设置一个 DP 状态 \(f[l,r,lim]\) 表示： 区间 \([l,r]\) 中的所有东西构成了一棵子树，且树中最小权值不小于 \( ......

Permutation and Minimum 看到 300 的数据范围，再加上计数题，很容易就往计数 DP 方向去想。 为方便，我们将 \(n\) 乘二。 因为是两个位置取 \(\min\)，于是我们便想到从小往大把每个数填入序列。于是DP数组第一维的意义便出来了：当前已经填入了前 \(i\) 小 ......

Maxim and Increasing Subsequence 首先，我们可以发现，当这个重复次数很大的时候，答案就等于序列中出现的不同权值个数。实际上，这个“很大”就可以被当作“大于等于不同权值个数”。 不同权值个数实际上是 \(\min(n,m)\) 级别的，其中 \(n\) 是序列长度，\( ......

Kuro and Topological Parity 我们考虑在一张染色完成的图里，我们连上了一条边，会有何影响？ \(\bullet\) 在同色节点间连边——明显不会有任何影响。 \(\bullet\) 在异色节点间连边，但是出发点是个偶点（即有偶数条路径以其为终点的节点），终点的路径数增加了， ......

Subsequence Reversal P 思路： 发现，翻转一个子序列，就意味着两两互换子序列里面的东西。 于是我们就可以设 \(f[l][r][L][R]\) 表示： \(\max[1,l)=L,\min(r,n]=R\) 时的最长长度。 则边界为： \(L>R\) 时， \(f=-\inft ......

MRO-Ant colony 根据下取整除法的性质 \((\left\lfloor\dfrac{\left\lfloor\dfrac{x}{y}\right\rfloor}{z}\right\rfloor=\left\lfloor\dfrac{x}{yz}\right\rfloor)\)，我们可以反 ......

Good Sequences 状态很显然，设 \(f[i]\) 表示位置 \(i\) 的最长长度。 关键是转移，暴力转移是 \(O(n^2)\) 的，我们必须找到一个更优秀的转移。 因为一个数的质因子数量是 \(O(\log n)\) 的，而只有和这个数具有相同质因子的数是可以转移的； 因此我们可以 ......

New Year and Arbitrary Arrangement 思路： 期望题果然还是恶心呀！ 我们设 \(f[i][j]\) 表示当串中有 \(i\) 个 \(a\) 和 \(j\) 个 \(ab\) 时的方案数。为了方便，设 \(A=\dfrac{P_a}{P_a+P_b},B=\dfra ......

Moovie Mooving G 设 \(f[i][S]\) 表示在第 \(i\) 场（注意是场，不是部）电影时，已经看了 \(S\) 里面的电影是否合法。 然后贪心地取 \(|S|\) 最小的状态保存。光荣 MLE 了， \(21\%\)。 发现当一场电影结束后，无论这一场是在哪里看的都没关系。 ......

给定一个排列，要求交换最多 $n-1$ 对元素，使得这个排列变成 [1,2,...,n] 的有序排列。 当然没有那么简单，对于交换还是有限制的，对于相邻的两次交换，不妨叫做 $(l_i, r_i)$ 和 $(l_{i+1}, r_{i+1})$，必须满足**这两个交换所对应的区间，没有交集**，即... ......

题目链接 相当牛逼。 这种找数量的题型，确定树形 \(dp\) 没跑了。 首先思考常规树形 \(dp\)，不难想到设 \(f_{u,a,b}\) 表示以 \(u\) 为根节点的子树内（包括点 \(u\)），最大值是 \(a\)，最小值是 \(b\) 的连通子图数量，转移很容易，但是这样时间空间复杂度 ......

碎碎念 赛时没出题（真可恶吖）在上晚自习，补了一下。ACD都套着字符串的外壳，差点直接劝退，后来仔细一读发现和字符串没什么关系...大概字符串的用处是为了劝退我这种有些怂字符串的人叭。 A. 小红的环形字符串 题意：对于给定的环形字符串s，可以删除相邻的两个相同字母，问最多删除多少个字符 思路：相邻 ......

给一个长为 \(n\) 的数组 \(a\) 和一个正整数 \(x\) 。你可以执行以下操作任意次：用两个相邻元素的和替换这两个元素。如 \([\cdots, a_i,a_{i+1},\cdots] \rightarrow [\cdots, a_i + a_{i+1},\cdots]\) 。 一个数组 ......

实时更新。 众所周知的，原创题就是即原神又创人的题。 当然有的题不会放，等考了在放。 波特 问题描述 流水线上有 \(n\) 个波特，每个波特有一个工作效能 \(a_i\) 。对于每一个波特，当它遇到一个工件时，它会对其进行加工，耗费 \(1\) 个单位时间，然后把它传递给它前面中工作效能最大的波特 ......

给一个正整数 \(n\) ，判断 \(n\) 是否存在一个 \(> 1\) 的奇数因子。 只要 \(n\) 的唯一分解下存在除 \(2\) 以外的质因子，则 \(n\) 存在 \(>1\) 的奇数因子。 于是 \(n \neq lowbit(n)\) 则 \(n\) 存在奇数因子。(应用了 \(2^ ......

又是一道锻炼代码能力的题目。 首先遇到这种求经过多少个节点的题可以先缩点，然后我们考虑那个特殊限制怎么用。 如果对于两个强联通分量 \(x\) 能到 \(z\)，\(y\) 能到 \(z\)，则 \(x,y\) 之间一定有一个限制，假设这个限制是 \(x\) 能到 \(y\)，那么我们可以只记录 \ ......

首先对每个数分解只因数，然后把只因数的指数对3取模，把 \(s\) 划分成多个等价类。对于每一个等价类，有唯一对应的另一个等价类不能同时选，取最多的即可。 分解只因数用 polard's rho 算法，时间复杂度 \(O(nw^{0.25})\) code: #include<bits/stdc++ ......

整体二分板题 首先瑞平翻译。 考虑整体二分，用分治函数 solve(l,r,L,R) 解决答案在 \([L,R]\) 之间的边。每次我们加入所有 \([1,MID]\) 之间的边，查询这时的询问是否满足要求，进行整体二分即可。 由于多次加入边比较麻烦，我们用可撤销并查集维护。 时间复杂度 \(O(n ......

一道十分有趣的题。 一眼推式子，发现自己不会。 看了题解，发现是有趣思维题。但是由于我的朋友学习了有趣的思维题做法，因此我决定学习更有趣的生成函数做法！！！ 考虑把原式拆开， \[\frac{1}{2}\times \left( \sum_{i=1}^{n}\sum_{j=1}^{n} \binom ......

考虑 kruskal 算法的过程。 先将边按边权排序，考虑当加入 \((u,v)\) 时只有 \((u,v)\) 不联通才可能使得其出现在最小生成树中，所以对于所有的边权小于 \(L\) 的边，我们希望去除尽可能少的边使得 \((u,v)\) 不联通。这显然是一个网络流模型。对于每一条边 \((x, ......

非常有意思的思维题。 首先我先瑞平一下翻译，我根本没看懂，还是去看英文题面看懂的。 首先可以发现整个字符串被拆成了若干个奇回文串与偶回文串。现考虑如何判是否合法。可以发现一个回文串就是要求部分位置匹配。我们对这些匹配的位置建边，如果得到的图是联通的，那么就只能填入 \(1\) 种字符，否则就可以填入 ......

给出一个数 \(n\) ，询问能否存在 \(2020x + 2021y = n\) 。 对于方程 \(ax + by = n\) 可以直接解 \(exgcd\) 查询是否有解。 观察到 \(2020x + 2021y = n\) 可以化为 \(2020(x + y) + y = n\) 。不妨定为 ......

首先考虑一些简单的情况，比如 \(m=1\)。 容易发现操作 1 和操作 2 的顺序不会影响结果，于是可以钦定所有操作 1 在操作 2 之前。并且可以发现，进行完所有 1 后 2 的次数即为 \((\text{连续段个数}-1)\)。 然后考虑将 \(m>1\) 的情况。显然最后序列上每 \(m\) ......

[CF1098E] Fedya the Potter 题解 前言 一道类欧好题。 题解 这道题让求 \(c\) 数组的中位数，那么有一个比较套路的方法就是二分答案 \(mid\) 然后计算 \(b\) 数组中区间和小于 \(mid\) 的区间个数进行 \(check\)。但是 \(b\) 数组总共有 ......

英雄卡初始存在 \(A\) 点力量值和 \(B\) 点生命值。有 \(n\) 张怪物卡，第 \(i\) 张怪物卡拥有 \(a_i\) 点力量和 \(b_i\) 点生命值。任意卡的生命值 \(\leq 0\) 则阵亡。 在任意一步中可以选择一张怪物卡与英雄卡决斗，战斗结束后双方各受到对方力量点数的伤害 ......

CF882E1+CF1882E2 Two Permutations 题解-构造题 哇，人类智慧，太智慧了。。。 此题作为20231010联考的 T3。 感觉赛时根本没有去往这方面想。 CF1882E1 CF1882E2 E1 是简单版，就是没有要求操作数最小化。 E1-Easy Version 方法 ......

[ABC245G] Foreign Friends 题解 想法 考虑所有颜色相同的弱化版。 这种情况下，只需要把所有特殊点都推入队列之后跑多源 Dijkstra 即可。 思路 正解与上述做法大致相同。 如果有颜色限制，那么可以考虑这个神仙思路： 把所有特殊点的颜色用二进制表示，对于每一位，这一位是 ......

给定 \(n\) 个石堆，第 \(i\) 个石堆高为 \(h_i\) 并且代表这堆石块的个数。在一次操作中你可以将第 \(i\) 堆中的一块石块移动（需要存在石块）到 \(i + 1\) 堆。询问是否可以使石堆的高度严格递增。 显然贪心地让第 \(1\) 堆的高度为 \(0\) 。 然后线性模拟使得 ......

[USACO17JAN] Promotion Counting P 题解 前言 好久没写题解了，今天趁我心情好赶紧水一篇。 思路 首先拿到这题，关键词检索：子树，比 \(p_i\) 大的，树状数组！现在考虑如何去掉其他子树的贡献……emm，我直接在算贡献的时候去掉其他子树的贡献不就好了！ 当然，暴力 ......