题解1525f cf

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\%\)。 发现当一场电影结束后，无论这一场是在哪里看的都没关系。 ......

思路: 分别求出 最小区间 和最大区间, 利用单调zai 处理即可 然后 在利用 调和级数 , 求最小值的倍数 后记: 为什么我不2个元素都求一个区间呢? ......

2023.10.12 开坑，打了几场 div.2 之后一直觉得这方面水平差太多，今天刚好在洛谷看到这个题单就准备开始做了，里面从黄到黑都有，我会尽量都做，并在这里记录。总共 49 题，我可能平时有时间就做一两题，估计是个长期坑了（（。 题单链接 [Y] 表示独立完成，[N] 表示看题解之后完成。 ......

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

思路: 利用操作 使得题目更好分析, t 的后缀,反转t , 来看t 的前缀, 实际操作的时候, 把s 和 t 的前缀在反转一下进行交换就可以了, 发现性质 1 C(si, ti) 他们的相对位置不会变化, 一直是匹配的 然后利用 翻转的性质, 一定会产生任意我想要的排列 (从后开始构造, 先把目标 ......

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

补充: 每次操作可以往左 或者 右 走一步 思路: 性质: 以一边为重点使劲走, 然后 利用另外一边来给自己权值变大 当 这边要死了, 就把这边回退到最大值, 在走另一边, 看另一边能到哪, 这样每次都可以扩展最大值, 于是利用双指针? 也不是双指针, 就是 l,r 分别贪心地向左 和 向右 扩张 ......

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

又是一道锻炼代码能力的题目。 首先遇到这种求经过多少个节点的题可以先缩点，然后我们考虑那个特殊限制怎么用。 如果对于两个强联通分量 \(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\) 种字符，否则就可以填入 ......

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

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

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

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

Problem 题目简述 给你一个整数 \(n\) 和字符串 \(s\)，问：能不能在小于 \(n\) 次操作的情况下，输出字符串 \(s\)。 有两次操作可供使用： 在已打出内容的最后添加一个字符。 复制已打出内容的一个连续的子串并加到内容的末尾。 思路 用到的容器：\(\text{map}\)。 ......

Problem 题目简述 给你一个 \(n \times m\) 的方格，构造一个方案，使得方案中 \(B = W + 1\)。 \(B\)：相邻的格子有至少一个白色格子的黑色格子的个数。 \(W\)：相邻的格子有至少一个黑色格子的白色格子的个数。 思路 分奇偶讨论。 \(n \times m\) ......

Problem 题目简述 两个序列 \(A, B\)。这两个序列都是由 \(0,1,2\) 这三个数构成。 \(x_1,y_1,z_1\) 和 \(x_2,y_2,z_2\) 分别代表 \(A\) 序列和 \(B\) 序列中 \(0,1,2\) 出现的次数。 你可以重新排列两个序列中的元素，然后生成 ......

Problem 题目简述 有 \(n\) 个人分别在 \(c_i\) 的时刻来，他们都要在 \(k_1\)，\(k_2\) 和 \(k_3\) 窗口干不同的事，当有后面一人也排在在同一窗口时，必须等待前面的人办完事才能轮到他。 问怎么在最优分配情况下，使停留时间最长的人停留时间最短。 思路 这道题的 ......

Problem 题目简述 给你一个数列 \(a\)，有这两种情况，这个数列是「可爱的」。 它本身就是回文的。 定义变量 \(x\)，满足：序列 \(a\) 中所有值等于 \(x\) 的元素删除之后，它是回文的。 思路 首先考虑暴力。暴力枚举数组中的每一个数，当作变量 \(x\)，然后进行回文检验。 ......

Problem 题目简述 现有 \(n\) 个已经加过油的加油站，如果当前剩余油量 \(< 10\) 升，则会加 \(x\) 升的油。 初始状态下，有 \(x\) 升油。每个加油站之间的距离为 \(100\) 米，耗油量为 \(10\) 升。 思路 首先，从左向右求出能到达的编号最小的车站，记为 \ ......

Problem 题目简述 设序列 \(a\) ，并且是单调递增的。设 \(a\) 当前长度为 \(l\)，你要对 \(a\) 作差分，即令 \(b_i = a_{i+1} - a_i(1\le i < l)\)，然后使 \(b\) 数组保持单调递增。 一直持续操作，直到 \(a\) 数组中只有一个元 ......

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

题目描述 贝茜听说一场特别的流星雨即将到来：这些流星会撞向地球，并摧毁它们所撞击的任何东西。她为自己的安全感到焦虑，发誓要找到一个安全的地方（一个永远不会被流星摧毁的地方）。 如果将牧场放入一个直角坐标系中，贝茜现在的位置是原点，并且，贝茜不能踏上一块被流星砸过的土地。 根据预报，一共有 \(M\) ......