CF

题目链接：https://codeforces.com/contest/1867/problem/F 题意简述 记 \(P(T)\) 为一棵树 \(T\) 的所有子树的集合。给定一棵 \(n\) 个点的树 \(T\)，找出点数相同的树 \(T'\)，使 \(P(T')\) 的“与 \(P(T)\) ......

前言 duel 的时候做的题，做出来的时候感觉很神，看了题解做法感觉自己是个傻逼。 本做法时间复杂度是 \(O(n^{\tfrac{5}{2}})\)，可以作为补充了解。 题解 一个矩阵四个角的最大值有点烦，我们把它们排序，从小到大依次插入，则问题变为： 在 \(n\times m\) 的平面中，每 ......

CF Round 906 (Div. 1) C. Doremy's Drying Plan (√2000 / *2600) Easy ver. 可以得出只有被覆盖 1 / 2 次的才能被消除。 覆盖一次枚举线段，覆盖两次枚举点。 Hard ver. D. Game of Stacks (*3000) ......

题目链接：http://codeforces.com/problemset/problem/762/E 题目大意： 一共有 n 个电台，对于每个电台 i 有三个参数： \(x_i\), \(r_i\), \(f_i\),分别指它的一维坐标、作用半径和频率。如果两个电台的频率差值在 k 内，并且它们的 ......

CF1906B Button Pressing 题目链接：https://codeforces.com/problemset/problem/1906/B 题意简述 有 $n$ 盏灯，用一个 $0/1$ 序列代表关闭/打开的状态。若第 $i$ 盏灯处于打开的状态，允许对其执行如下的操作： 同时翻转第 ......

CF1876D Lexichromatography 题目链接：https://codeforces.com/problemset/problem/1876/D 题意 给一个 $n$ 个数的数组 $a$ 染色，每个元素被染为红色或蓝色。求满足下面两个条件的染色方案数： 将蓝色和红色的数分别取出成为两 ......

CF1906K Deck-Building Game 题目链接：https://codeforces.com/problemset/problem/1906/K 题意 有大小为 $n$ 的多重集 $A$。求找到两个不相交子集，使它们各自的异或和相等的方案数。 很容易将其转换为求如下值： $$ \su ......

CF1879F Last Man Standing 题目链接：https://codeforces.com/problemset/problem/1879/F 题意简述 有 $n$ 位英雄，每位英雄都有护甲值 $a$ 和生命值 $h$。对一次伤害值为 $x$ 的游戏，每位英雄的存活时间为 $t = ......

题目大意： 判断一个数组是否满足其中任意三个元素之和均为数组的元素 如果一个元素出现的次数大于三，那么我们将这个元素的数量减到三，答案不会变。 另外，我们发现，如果数组至少中有三个正数，或者至少有三个负数，那么答案一定为NO。 如果上面的条件不满足，那么现在这个数组里的元素最多只有7个（2个正数，2 ......

很菜。 CF1905C 考虑先找到原串中的字典序最大串，这个直接单调栈求出。然后我们对这个字串 \(t\) 执行操作，\(t\) 是不上升的所以肯定能排好序，我们在找 \(t\) 的时候顺便记录下 \(t\) 在原串中的位置，然后把排好序的 \(t\) 放回去判断，如果是不下降的则输出排好 \(t\ ......

Number Clicker Luogu CF995E 题面翻译 小 y 在玩数学游戏，他有三种变化方式： 将该数 \(+1\)； 将该数 \(-1\) 将该数变成他的逆元（即 \(p-2\) 次幂），当然，我们所有操作都是在 \(\bmod\ p\) 意义下的 现在小 h 知道了变换前的数 \(u ......

Shortest Path Queries Luogu CF938G 题面翻译 给出一个连通带权无向图,边有边权,要求支持 \(q\) 个操作: \(1\) \(x\) \(y\) \(d\) 在原图中加入一条 \(x\) 到 \(y\) 权值为 \(d\) 的边 \(2\) \(x\) \(y\) ......

题目链接 简单贪心。 由于我们需要判断无解情况，于是我们可以在做的过程中记录答案。 比较容易发现，对于每个时间段，我们肯定是优先复习日期较近的考试的，贪心了这一点，就能轻松 AC 了。 参考代码： 点击查看代码 #include<bits/stdc++.h> using namespace std; ......

CF1774B Coloring 题意 Cirno_9baka 的纸条上有 \(n\) 个格子，他觉得空白的纸条看着有点无趣，于是想在纸条的格子上涂上 \(m\) 种颜色。同时，他认为第 \(i\) 种颜色必须要用 \(a_i\) 次，且每连续 \(k\) 个格子里涂的颜色必须互不相同。 Cirno ......

CF1760F Quests 题意 有 \(n\) 个任务，你每一天都可以选择其中的一个任务完成或不选。当你完成了第 \(i\) 个任务，你将获得 \(a_i\) 元。但是如果你今天完成了一个任务，那么你之后 \(k\) 天内都不能再完成这个任务。 给出两个数 \(c\)，\(d\)，要求求出满足在 ......

CF1744E1 Divisible Numbers (easy version) 题意 给你四个数 \(a,b,c,d\)，你需要找出一组 \(x,y\) 使得 \(a<x\leq c,b<y\leq d\) 并且 \(x\cdot y\) 能被 \(a\cdot b\) 整除，如果没有输出 -1 ......

题目链接 点击打开链接 题目解法 很有意思的题，但不难 首先一个显然的结论是：算着边的加入，直径长度递减 第一眼看到误差范围是 2 倍，可以想到二分 可以观察到如果取答案为 \(\frac{n}{2}\) 可以覆盖到 \(\frac{n}{4}\)（上下取整不重要），那这样每次可以把值域范围缩小 4 ......

题目传送门 前置知识 等比数列求和公式 | 乘法逆元 解法 设 \(lena\) 表示 \(a\) 的长度。 首先，若一个数能被 \(5\) 整除，则该数的末尾一定为 \(0\) 或 \(5\)。故考虑枚举 \(a\) 中所有的 \(0\) 和 \(5\) 的下标，设此下标后面有 \(x\) 个数字 ......

Fancy Arrays - 洛谷 我们先找这题看起来有点奇怪的部分： \(x\leq 40\) \(|a_i-a_{i-1}|\leq k\) 我们先考虑第二个条件怎么用。我们发现 \(\min a_i \in [0,x+k)\)，而原数组相邻两数之差的条件肯定要考虑成差分来处理 可以发现，一个差 ......

题目链接 算法一： 直接暴力，时间复杂度 \(O(n^2)\)。 算法二： 使用双指针维护，时间复杂度 \(O(n)\)。 算法三： 是用前缀和维护，时间复杂度 \(O(n)\)。 这里提供算法二的代码： 点击查看代码 #include<bits/stdc++.h> using namespace ......

题目链接 一道 dp 板子题。 只需要设 \(dp_{i,j}\) 为前 \(i\) 位 \(\bmod 3\) 为 \(j\) 的方案数的数量即可。 剩下的就看代码了。 参考代码： 点击查看代码 #include<bits/stdc++.h> using namespace std; #defin ......

萌萌交互题。 对网格图进行二分图建模，左部 \(n\) 个点表示每一行，右部 \(n\) 个点表示每一列。若格子 \((i,j)\) 被染成 \(c\) 色，就连接 \((L_i,R_j,c)\) 的边。 由抽屉原理易证，在初始局面中至少有一个各边颜色均不同的偶环。获胜条件相当于存在一个各边颜色均不 ......

CF1740D Knowledge Cards 题意 有一个 \(n \times m\) 的棋盘。现在\((1,1)\)中有一个栈，你可以按照一定的顺序进行出栈操作，每次都可以移动一个卡片到一个相邻的空白位置，但是卡片不能重合。问，能否通过若干次操作，将\((1,1)\)中全部的卡片移动到\((n ......

CF1722G Even-Odd XOR 题意 给定一个正整数 \(n\)，请你找出一个长度为 \(n\) 数组 \(a\)，满足数组是由互不相同的非负且小于 \(2^{31}\) 的整数组成，并且该数组中奇数项上元素的异或值与偶数项上元素的异或值要相等。 思路 根据异或的交换律，可以发现：奇偶位异 ......

CF1690E Price Maximization 题意 我们有 \(n\) 个礼物，而最终我们需要将所有的礼物两两包成 \(\frac{n}{2}\) 个包裹。 每一个礼物 \(i\) 都有其价值 \(a_i\)，而含有礼物 \(i\) 与礼物 \(j\) 的包裹的价值是 \(\lfloor \ ......

题目链接：https://codeforces.com/problemset/problem/1784/C 题目大意： 你面前有 \(n\) 只怪兽，每只怪兽都有一个初始血量，你可以进行两类操作： 操作1：选择任意一个血量大于 \(0\) 的怪兽，并将它的血量降低 \(1\)； 操作2：将所有存活的 ......

110和011互相转化，相当于就是0在连续两个1的情况下，移动两个位置 能够发现，0的位置的奇偶不会改变，且很多个0之间的相对位置不会改变 猜想考虑这个答案只跟0的奇偶性有关，下面小证一下：（注意下面所说的“奇偶”指的是两个字符串的分别第一个字母为奇数时的奇偶，不是总字符串的奇偶） 若0的相对位置奇 ......

显然O（n）划分之后可以用一个三维dp写 可以用bitset优化 也可以 化简为二维 dp i j 表示第i位 能搞到 a的j位 并且 搞到b位的 最大值 int dp[410][410]; bool check(string &s,string &pre,string &suf) { memset ......

Easy Version Hard Version Hard Version的做法可以从Easy Version 用数据结构优化得到。 首先我们想一下，什么情况需要进行操作？显然是\(a_i!=b_i\)的时候，并且当\(a_i>b_i\)的时候将会无解。 那么当\(a_i<b_i\)的时候，应该怎 ......

CF 1903F: 考虑二分答案 \(ans\)。 可以得到这样的限制： 若选择了 \(x\)，则不可以选择 \(x+1,x+2,...,x+ans\)。 若未选择 \(u_i\)，则必须选择 \(v_i\)。 这是一个 2-sat 的形式。但限制 1 建边太多，可以用线段树优化建图。 ......