cf

原题链接 链式前向星，他来了 通过观察发现，每个集合的大小最小为 \(2\)，显然我们需要构造一种方案使得每一个集合的大小都为 \(2\)，这样是最优的。 每个集合大小为 \(2\)，等价于把每条边转换成新树上的一个点，一共 \(n-1\) 边，对应 \(n-1\) 个集合，每个集合的点对在 dfs ......

原题 翻译 初看此题，显然感觉有点不对劲，因为感觉如果 \(a_i\) 很大的话肯定是选越多越优秀，但之后并没有什么思路，反而想到线段树上去了(值域这么大做 nm 线段树) 发现如果 \(\prod a_i > 2 \times 10^{14}\) ，那就把做右端点收敛到都不是 \(0\) 的最远位 ......

CF1204D2 Kirk and a Binary String (hard version) 题解 分析 先来分析 \(01\) 串的最长不下降子序列。全是 \(0\) 显然是不下降的，如果中间出现一个 \(1\)，为了维护不下降的性质，后面就只能全是 \(1\)。一句话概括一下，\(0\) 后 ......

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

选一些 \(\text{div 1}\) 中的好题总结一下 \(\textrm{qwq}\) 从现在开始像 \(\color{red}\text{r} \color{black}\text{ainboy}\) 一样打比赛 \(\textrm{qaq}\) $$\textrm{Codeforces R ......

贪心，二进制 很容易想到：把 \(n\) 转化为二进制，考虑如何得到每一位。 很显然，用小的数去“凑出”大的数不花费代价，用大的数“分解”出小的数要花费代价。所以。一个简单的贪心是：设当前要得到 \(n\) 的第 \(i\) 位的数 \(2^i\)，尽量用小的数凑，若小的数凑不出，再用大的数分出 \ ......

Survey in Class 题面翻译 有 \(n\) 个学生同时对课堂内容进行了预习。有 \(m\) 个问题，第 \(i\) 个人预习的问题是一个区间，可以用 \([l_i,r_i]\) 表示。每当老师问出一个问题，如果一个人不会，它的分数就会 \(-1\)，否则 \(+1\)。注意，分数可能为 ......

Game with Reversing 题面翻译 小 L 和小 S 在玩游戏。他们有两个长度均为 \(n(1 \le n \le 10^5)\) 的字符串 \(S, T\)，小 L 和小 S 轮流操作，小 L 先手。 小 L 的回合，他可以选择 \(1 \to n\) 中的一个整数 \(i\)，再选 ......

Maximum Strength 题面翻译 题目描述 每一种材料的力量由一个十进制整数表示。 对于一个武器，由两种材料构成。假如第一种材料的力量为 \(X = \overline{x_1x_2 \dots x_n}\)，第二种材料的力量为 \(Y = \overline{y_1y_2 \dots y ......

Ranom Numbers 题面翻译 Ranom Number 是一个字符串，这个字符串只含字母 \(\texttt A \sim \texttt E\)。\(\texttt{A}\) 的值是 \(1\)，\(\texttt{B}\) 的值是 \(10\)，\(\texttt{C}\) 的值是 \( ......

Keep it Beautiful 题面翻译 定义一个序列为好, 当且仅当我们能从头开始选一段序列(长度可以为0, 相对顺序不变)放到尾部的后边, 由此得到的新序列是非递减的, 注意当序列为空时, 这个序列也是好序列 初始时序列为空, 然后给你 \(q\) 个数字, 按次序询问你对于当前这个数 \( ......

Game with Board 题面翻译 Alice 和 Bob 玩游戏，他们有一块黑板。最初，有 \(n\) 个整数 \(1\)。Alice 和 Bob 轮流操作，Alice 先手。 轮到时，玩家必须在棋盘上选择几个（至少两个）相等的整数，擦除它们，然后写一个等于它们总和的新整数。 如果玩家不能移 ......

Insert Zero and Invert Prefix 题面翻译 你有一个长度为 \(n\) 的 01 序列 \(a\)，以及一个初始为空的序列 \(b\)。你接下来需要执行 \(n\) 次操作，每次操作将会使序列 \(b\) 的长度增加 \(1\)。 在第 \(i\) 次操作，你需要选择一个在 ......

Lamps 题面翻译 有 \(n\) 盏灯，每盏灯有不亮，亮，坏掉 3 种状态。一开始每盏灯都不亮。 第 \(i\) 盏灯有属性 \(a_i,b_i\)。每次操作你可以选择一盏灭的灯将其点亮，并得到 \(b_i\) 的分数。 每次操作结束后，记有 \(x\) 盏灯亮着，则所有 \(a_i \le x ......

The Good Array 题面翻译 题目描述 对于一个由 \(0\) 和 \(1\) 构成的数组 \(a_1,a_2,\dots,a_n\)，如果对于从 \(1\) 到 \(n\) 中所有的整数 \(i\) 都满足以下两个条件，我们称这个数组为『好的数组』： 前 \(i\) 个元素中有至少 \( ......

No Prime Differences 题面翻译 \(n \times m\) 的网格，填入 \(1,2,3,...,n \times m\)，使得相邻的两个方格的差不是质数。 多组数据，输出任意一种方案（保证有解），每组输出间有空行（见样例）。 题目描述 You are given intege ......

Minimize Permutation Subarrays 题面翻译 给定一个长度为 \(n\) 的排列 \([p_1, p_2, ..., p_n]\) ，任选两个元素（可以相同）并交换一次，使得其所有子段中排列（长度不一定为 \(n\) ）的个数最少，输出被交换的元素的位置（下标从 \(1\) ......

Blackboard List 题面翻译 在黑板上有两个数字，进行如下操作 \(n-2\) 次： 每次在黑板上选择任意两个数，将两个数的差的绝对值写在黑板上。 这样你会得到一个长度为 \(n (3 \le n \le 100)\) 的序列。 一共 \(t (1 \le t \le 100)\) 组数 ......

Best Binary String 题面翻译 给定由 1 0 ? 所组成的字符串，你需要用 0 或 1 替换 ?。 我们将 \(s_{l},s_{l+1},\dots,s_r\) 反转成为一次操作。 你要使通过“反转”操作使原字符串成为升序的操作次数尽可能的小。 问最终构造出的字符串，有多解输出其 ......

Comparison String 题面翻译 给你一个长度为 \(n\) 的由 < 和 > 构成的字符串 \(s\)，如果一个数列 \(a\) 能满足将字符串 \(s\) 的所有大于号和小于号按顺序填入后满足大小关系，则 \(a\) 数列和 \(s\) 字符串是“相容的”。 定义一个数列的花费是这个 ......

Long Legs 题面翻译 给你一个无限大小的棋盘，一个机器人初始位置为 \((0,0)\)，初始每次可移动的长度为 \(1\)。 对于一个当前在 \((x,y)\) 的机器人，且它当前的可移动长度为 \(m\)（初始为 \(1\))。则它可以耗费一个时间进行如下操作： \(\qquad\) 1. ......

Coins 题面翻译 本题一共有 \(t\) 组数据。 每组数据包含两个整数 \(n\) 和 \(k\)，如果存在两个非负整数 \(x,y\)，满足 \(2\times x+k\times y=n\)，输出 YES，否则输出 NO 题目描述 In Berland, there are two typ ......

Grid Reconstruction 题面翻译 题目描述 在一个 \(2×n\) 的网格中 （\(n\) 为偶数），标记 \(1,2,\ldots,2n\)，但每个数只能被使用 \(1\) 次。 某条路径是从 \((1,1)\) 开始的单元序列，随后不断地向下走或向右走，直到到达 \((2,n)\ ......

Ian Visits Mary 题面翻译 题目描述 \(\textrm{lan}\) 和 \(\textrm{Mary}\) 是生活在笛卡尔坐标系格点上的青蛙，\(\textrm{lan}\) 在 \((0,0)\)，而 \(\textrm{Mary}\) 在 \((a,b)\)。 \(\textr ......

Ian and Array Sorting 题面翻译 题目描述 为了感谢 \(\textrm{lan}\)，\(\textrm{Mary}\) 赠送了 \(\textrm{lan}\) 一个长度为 \(n\) 的序列。为了让他自己看起来聪明，他想要让序列按非递减排序。他可以执行以下操作若干次： 选择 ......

CF1817A 题面翻译 给定长度为 \(n\) 一个序列 \(a\) 以及 \(q\) 次询问，每次询问给出 \(l\) 和 \(r\)，找出序列 \(a\) 在 \([l,r]\) 内最长的几乎递增子序列。 对于几乎递增的定义：如果一个序列中不存在连续的三个数 \(x\)，\(y\)，\(z\) ......

给定序列 \(m_i\)，求有多少排列 \(p\) 满足：对于满足 \(l \le r \le m_l\) 的所有 \((l,r)\)，\(p_{l \sim r}\) 都不是 \(l \sim r\) 的排列。答案对 \(10^9 + 7\) 取模。 \(n \le 200\)，时限 \(\tex ......

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

暴力 dp 是很拉跨的，我们会设 \(dp_{i,j}\) 表示前 \(i\) 个 \(a_i\) 分裂后，最后一个 \(b\) 为 \(j\) 时的最小答案，爆炸。 但这里面有很多性质啊，直观地我们可以感受到，若已经确定了决策 \(dp_{i-1,k}\)，那么无论如何选择 \(a_i\) 的分裂 ......

当前的状态有：传送门的激活状态，已经完成的任务数量，当前的位置（传送门/任务），经过的时间。显然我们会先将所有任务按照 \(t_i\) 升序排序。把前三维列为状态，后一维列为答案，此时我们可以得到一个状态数为 \(O(2^nm^2)\)，转移为 \(O(m)\) 的 dp。 状态数很没救，显然要被优 ......