rounding maximum 1857b cf

贪心，二进制 很容易想到：把 \(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 ......

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\) ......

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

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

首先 \(a\) 边可以随便选。 显然，若某条 \(b\) 边的两端位于同一 \(a\) 连通块，一定不会被我们考虑。剩下的 \(b\) 边一定会将两个 \(a\) 连通块相连。 那么此时我们对于 \(b\) 边的约束是，位于一个环上的 \(b\) 边不能同时存在图中，即，我们的路径不能从当前连通块 ......