题解codeforces round 1805

CF785D Anton and School - 2 题解 分析 很明显有一种 \(\mathcal O(n^2)\) 的做法，遍历每一个 (，再枚举 \(k\)，左边不包含这一位选 \(k-1\) 个 (，右边选 \(k\) 个 )，求组和即可。 但是数据范围是 \(n \le 2\times ......

给一个正整数的集合 \(S\) ，需要将他分成两个非空子集 \(A\) 和 \(B\) 满足 \(S = A + B, A \cap B = \varnothing\) 。你需要使 \(mex(A) + mex(B)\) 最大，询问这个最大值。 若 \(mex(A) + mex(B)\) 最大，则 ......

Codeforces Round 903 (Div. 3) F. Minimum Maximum Distance 思路 对标记点更新fg，从0开始进行bfs，更新d1为所有点到0的距离 获得到0最远的标记点L，从L开始bfs，更新d2为所有点到L的距离 获得距离L最远的标记点R，从R开始bfs，更 ......

将图按照邻接矩阵存为一个矩阵，则有性质为：该矩阵的 \(k\) 次方反映了 在该图上恰好走 \(k\) 次的可达性。 有了这条性质可以按边权将所有边排序，在图上动态加入能新走的边，用矩阵快速幂处理出当前图恰好走这条边边权次的可达性矩阵。每新加入一条边，用 floyd 求出加入这条边影响后新的最短路。 ......

洛谷传送门 CF 传送门 把题意抽象成，给你长为 \(n\) 的序列 \(a\) 和长为 \(m\) 的序列 \(b\)，初始有 \(m\) 个空集合（可重集），\(a\) 中的每个元素至多被分到 \(m\) 个集合中的一个。要求最后第 \(i\) 个集合 \(T_i\) 不为空，且 \(\fora ......

P1084疫情控制 前言：这题思路不难，实现稍微有点难。总体来说，不算特别难的那种紫题，建议评蓝。 题目描述 给定一些点，用这些点来切断根节点到所有叶子节点的路径，可以移动这些点,不同的点可以同时移动，求时间最少。 思考过程 不同的点可以同时移动：看到这里，我们可以转化一下题目： 给定一些点，用这些 ......

思路 可以看出，每次对一个点 \(u\) 操作一次，就相当于删除以 \(u\) 为根的所有叶节点。 当然我们还是没有什么思路，我们可以想简单一点：在一条链上的情况。 如果 \(u\) 是链的端点：以 \(u\) 为根节点的叶节点只有一个，所以链的长度减一。 如果 \(u\) 不是链的端点：以 \(u ......

思路 我们可以很好的想到一种 \(O(nm)\) 的 dp: 状态：\(dp_{i,j}\) 为搜到第 \(i\) 个,最后一个数是 \(j\) 的方案数。 转移：\(dp_{i,j} = \displaystyle\sum_{k|j,k\not =j}dp_{i-1,k}\) 当然这是会超时的。 ......

思路 看到条件 \(2\)，我们得知：这个节点对应的最长链，一定在这个节点到根节点的简单路径上。 所以我们记录 \(1\) 到 \(i\) 之间的权值和，记为 \(sum_i\)。因为权值是正整数，所以满足单调性，可以二分。 如何二分路径上的点呢？我们维护一个与当前 dfs 同步的栈，记录从根节点到 ......

\(R\) 和 \(B\) 在玩一个数字游戏，给一个含有 \(n\) 位的正整数 \(x\) 。俩人轮流操作， \(R\) 先行动。 在每一步中，\(R\) 可以选择 \(x\) 中一个未被标记的奇数位置并标记，\(B\) 可以选择 \(x\) 中一个未被标记的偶数位置并标记。 当最后只剩下一个未被 ......

给一个正整数 \(n\) ，在一步操作中可以移除 \(n\) 中的一个。当 \(n\) 只剩下一位时将不能再操作，如果过程中产生了前导 \(0\) ，则会被自动移除且不耗费操作次数。 询问最少需要多少次操作可以使得 \(n\) 被 \(25\) 整除。 显然一个正整数 \(x\) 若可以被 \(25 ......

给一个长为 \(n\) 的字符串 \(s\) ，只包含 \(0\) \(1\) 两种字符。定义 \(AB(s)\) 是 \(s\) 中出现的 \(01\) 子串个数，\(BA(s)\) 是 \(s\) 中出现的 \(10\) 子串个数。 在一步操作中，可以选择一个字符进行异或。询问最小的操作次数使得 ......

Codeforces Round 903 (Div. 3) E. Block Sequence 思路： 设dp[i]为当i~n为完美的最少删除次数 dp[n]=1,dp[n+1]=0; 从后至前对于dp[i]更新 若直接删除当前点，则为 dp[i+1]+1 若不删除 则为 min（dp[i+a[i] ......

题目 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1： 输入：nums = [3,2,3] 输出：3 示例 2： 输入：nums = [2,2,1,1,1,2 ......

题目 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。 示例 1: 输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7 ......

D题被hack了 哭了 第一题简单的只用把字符串重复的同时尝试匹配，然后判断就好了，只是需要一点代码能力 第二题，也很简单最多剪断3次，就先从小到大排序，然后用最小的，看看大的是他的几倍，如果不是几倍的关系就不可能完成，如果是就算要几次就好了 第三题，也很简单，很明显，对于一个格子，在它旋转90度后 ......

有 \(n\) 个方块，第 \(i\) 个方块重量为 \(a_i\) 。需要使方块按照非降序排列摆放。在每一步操作中，可以交换任意相邻的两块方块。询问可以使所有方块按照非降序排序的最小操作数 \(p\) 是否 \(\frac{n \cdot (n - 1)}{2}\) 。 考虑一个事实，对于任意第 ......

有 \(n\) 块 \(2 \times 2\) 的瓷砖，瓷砖上的每个方格包含一个数字，每种瓷砖都有无数种。现在需要用所给瓷砖构造一个 \(m \times m\) 的方形矩阵 \(a\) 满足： 每块瓷砖都在方形矩阵内 瓷砖之间不能存在覆盖 \(a_{i, j} = a_{j, i}\) 。 输出 ......

思路 考虑树形 \(\text{dp}\)。 我们将每个人与把自己淘汰的人连边。 得到一颗以一为根的树。 由于我们需要求出必须赢的场数最多的那位选手，至少要赢多少场。 考虑最多的限制。 可以使用树型动态规划。 每一次两个人比赛的代价为： \[dp_i=\max(dp_i,dp_j)+1 \]这样就达 ......

D. Divide and Equalize 思路： 1.某个数除以x，某个数再乘以x，可发现数组总的乘积没有变化 2.也就是说，要使数组中的每一个元素相同，它们总的质因子应该满足：某个质因子的数量%n==0 E. Block Sequence 简单的dp dp[i]，表示删除这个数字后的最小删除次 ......

给一个大小为 \(n\) 的数组 \(a_1, a_2, \cdots, a_n\) 。你需要构造一个大小为 \(n\) 的数组 \(b\) 且满足以下条件： 数组 \(b\) 是数组 \(a\) 的冲排列 对于 \(\forall k =1, 2, \cdots, n\) ， \(\sum_{i= ......

Tarjan 思路 先来看一下题目给出的无解的这个样例。 不难发现，导致无解的两条边就是 \(6 - 7\) 和 \(2 - 4\) 这两个桥。所以这个题就转换成了求桥，如果存在桥就是无解。 代码 #include<bits/stdc++.h> using namespace std; const ......

有三种建筑：三室厅、五室厅、七室厅。每个房间严格有一扇窗户。现在有 \(n\) 扇窗户，询问完全用完这些窗户的情况下，\(3, 5, 7\) 室厅各有多少间。输出任意一种答案，或者回答不可能。 假设一定有解，显然可以选择 \(mod\) 任意一个数贪心，不妨选最小的 \(3\) 。假设答案为 \(a ......

有 \(n\) 只水虎鱼在水族馆，大小为 \(a_1, a_2, \cdots, a_n\) 。 一只水虎鱼被称为是主导的，当它可以吃掉水族馆中其他所有水虎鱼。其他水虎鱼不会有任何行动。 一只水虎鱼只可以吃掉当前与它相邻并且体型严格比它小的水虎鱼。当大小为 \(x\) 的水虎鱼吃掉大小为 \(y\) ......

学长给我看了这道题，感觉很有趣啊！想了想想出来了。 考虑先把每个数还原到对应行上，然后用最后一次把它们斗出来。 那么我们就是要在第一次操作后，对于每种颜色使得它平铺在这个块上。 那么我们直接网络流或二分图匹配构造一下方案就做完力！ ......

Fox And Travelling 题面翻译 给定一张 \(n\) 个点 \(m\) 条边的无向图。 一个点只有当与它直接相连的点中最多只有一个点未被选择过时才可被选择。 询问对于每个 \(k \in [0,n]\)，有序选择 \(k\) 个点的方案数。 \(n \le 100\)，\(m \le ......

定义 \(median\) 是一个非降序数组中第 \(\lceil \frac{n}{2} \rceil\) 的数。数组从 \(1\) 开始标号。 给两个数 \(n\) 和 \(k\) ，并给出一个长为 \(nk\) 的数组 \(a\) 。 需要分出为 \(k\) 个大小为 \(n\) 的数组，每个 ......

题目大意： 给你两个数 \(l,r\)，定义 \(bal(x)\) 代表 \(x\) 是否满足出现过的每一数位，每个偶数出现奇数次，每个奇数出现偶数次。求 \[\sum \limits_{i=l}^{r} bal(i) \]思路： 看到记录每一数位出现几次，就是直接告诉你这是数位dp。至于如何记录每 ......

一个比赛有一百人进入决赛，但是需要经过两轮初赛的选拔。初赛的最终结果由两场初赛产生，不幸的是初赛的最终排名被丢失了。 在每场初赛中，参赛者的排名按非升序排序。当两位参赛者的成绩一样，参赛编号更小的靠前。 现在只知道如下信息： 第一场初赛中，第一百名的成绩为 \(a\) 。且第一场初赛中前一百名的选手 ......

include<bits/stdc++.h> pragma GCC optimize(1) pragma GCC optimize(2) pragma GCC optimize(3,"Ofast","inline") define reg register define int long long ......