题目链接 https://vjudge.csgrandeur.cn/contest/578660
题解
- A CodeForces 1859A United We Stand
- B CodeForces 1858A Buttons
- C CodeForces 1857A Array Coloring
- D CodeForces 1856A Tales of a Sort
- E CodeForces 1855A Dalton the Teacher
- F CodeForces 1853A Desorting
- G CodeForces 1851B Parity Sort
- H CodeForces 1851A Escalator Conversations
- I CodeForces 1850C Word on the Paper
- J CodeForces 1850B Ten Words of Wisdom
- K CodeForces 1850A To My Critics
- L CodeForces 1849A Morning Sandwich
- M CodeForces 1847A The Man who became a God
- N CodeForces 1846B Rudolph and Tic-Tac-Toe
- O CodeForces 1846A Rudolph and Cut the Rope
- P CodeForces 1845A Forbidden Integer
- Q CodeForces 1844A Subtraction Game
- R CodeForces 1843C Sum in Binary Tree
- S CodeForces 1843B Long Long
- T CodeForces 1843A Sasha and Array Coloring
- U CodeForces 1842A Tenzing and Tsondu
- V CodeForces 1841A Game with Board
- W CodeForces 1840A Cipher Shifer
- X CodeForces 1839A The Good Array
- Y CodeForces 1838A Blackboard List
- Z CodeForces 1837A Grasshopper on a Line
A CodeForces 1859A United We Stand
给定一个长度为n、包含整数的数组a。最初有两个空数组b和c。您需要将数组a的每个元素添加到数组b或c中的一个数组中，以满足以下条件：
- 数组b和c都不是空的。更正式地说，让lb是数组b的长度，lc是数组c的长度。那么lb，lc≥1。
- 对于任意两个指数i和j（1≤i≤lb，1≤j≤lc），cj不是bi的除数
输出可以获得的数组b和c，如果不存在，则输出−1。
分析
\(c_j \nmid b_i ===> c_j > b_i\)
所以只需要构造b数组的元素都小于c数组即可。
B CodeForces 1858A Buttons
安娜和凯蒂最后进了一个秘密实验室。
实验室里有a+b+c按钮。a按钮只能由安娜按下，b按钮只能由凯蒂按下，c按钮可以由他们中的任何一个按下。安娜和凯蒂决定玩一个游戏，轮流按下这些按钮。安娜第一个转弯。每个按钮最多可以按下一次，所以在某个时候，其中一个女孩将无法转动。
不会按按钮的女孩输了。决定如果两个女孩都打得最好，谁会赢。
分析
都先按c，这样能最大化自身效益。
直接计算先后手最多可按下的按钮数量即可。
先手可以按下的按钮数量为 a + c/2 + c%2，
后手可以按下的按钮数量为 b + c/2.
C CodeForces 1857A Array Coloring
给定一个由n个整数组成的数组 . 您的任务是确定是否有可能以两种颜色为其所有元素上色，从而使两种颜色的元素的和具有相同的奇偶性，并且每种颜色至少有一个元素上色。
例如，如果数组是[$1,2,4,3,2,3,5,4$]，我们可以这样给它上色: [$\color{blue}{1},\color{blue}{2},\color{red}{4},\color{blue}{3},\color{red}{2},\color{red}{3},\color{red}{5},\color{red}{4}$],，蓝色元素的和是6，红色元素的和是18。.
分析
两种颜色和具有相同奇偶性，那么也就是偶数个数与奇数个数都是偶数个。
D CodeForces 1856A Tales of a Sort
Alphen有一个长度为n的正整数a的数组。
Alphen可以执行以下操作：
- 对于从1到n的所有i，将ai替换为max(0,ai−1)。
Alphen将执行上述操作，直到a被排序，即a满足 a1≤a2≤…≤an。Alphen将进行多少次操作？在问题的约束下，可以证明Alphen将执行有限数量的运算。
分析
如果出现逆序对（前>后者），元素必定都降为最小值 0，下降次数就是最大的 ai。
E CodeForces 1855A Dalton the Teacher
Dalton 是一个班的老师，班上有n个学生，编号从1到n。教室里有n把椅子，编号也从1到n。最初，学生i坐在椅子pi上。保证p1，p2，…，pn是长度为n的全排列。
如果一个学生的号码和他/她的椅子号码不同，他/她的学生会很高兴。为了让所有的学生都开心，Dalton 可以反复执行以下操作：选择两个不同的学生并交换他们的椅子。让所有学生都开心所需的最少动作次数是多少？可以证明，在这个问题的约束下，用有限的动作让所有学生都感到高兴是可能的。
长度n的全排列是由从1到n的任意顺序的n个不同整数组成的数组。例如，[2,3,1,5,4]是全排列，但[1,2,2]不是全排列（2在数组中出现两次），[1,3,4]也不是全排列（n=3，但数组中有4）。
分析
每一次交换会使得两名选手高兴，
假设当前不高兴的选手(pi==i) 人数为 m，则需要交换 \(\lceil \frac{m}{2} \rceil\) 次。
F CodeForces 1853A Desorting
如果满足 \(a_1 \leq a_2 \leq \ldots \leq a_{n-1} \leq a_n\)，则称长度为
\(n\) 的数组 \(a\) 已排序。
Ntarsis有一个长度为 \(n\) 的数组 \(a\)。
他被允许对其执行一种操作（零次或多次）：
- 选择一个索引 \(i (1 \leq i \leq n-1)\)。
- 将 1 添加到 \(a_1, a_2, \ldots, a_i\)。
- 从 \(a_{i+1}, a_{i+2}, \ldots, a_n\) 中减去 1。
操作后，\(a\) 的值可能为负数。
确定使 \(a\) 未排序所需的最小操作次数。
分析
要使得数组未排序，也就是需要出现 \(a_i > a_{i+1}\)，根据操作发现，
修改一个点的效率最高，修改相邻差值最小的点代价最低。
也就是 \(m = \min_{i=1}^{n} {( a_i - a_{i+1} )}\)
如果 \(m<0\) 也就是原序列未排序，操作次数为 0；否则操作次数为 \(\lfloor \frac{m}{2} \rfloor +1\)
G CodeForces 1851B Parity Sort
您有一个长度为n的整数a数组。您可以对给定的数组应用以下操作：
- 交换两个元素ai和aj，使得 \(i \neq j\) 要么都是偶数，要么都是奇数。
通过执行任意次数（可能为零）的操作来确定是否可以按非递减顺序对数组进行排序。
例如，设 a=[7,10,1,3,2]。然后我们可以执行3个操作来对数组进行排序：
- 交换 a3=1 和 a1=7，因为1和7是奇数。我们得到 a=[1,10,7,3,2]；
- 交换 a2=10 和 a5=2，因为10和2是偶数。我们得到 a=[1,2,7,3,10]；
- 交换 a4=3 和 a3=7，因为3和7是奇数。我们得到 a=[1,2,3,7,10]。
分析
由于同奇偶性才能交换，那么当排序完成，每个位置的元素应当与初始元素的奇偶性相同。
H CodeForces 1851A Escalator Conversations
有一天，Vlad 很好奇在地铁扶梯上可以和谁交谈。共有 \(n\) 名乘客。自动扶梯共有 \(m\)级，所有梯级的高度从 \(1\)到 \(m\)依次递增，第 \(i\) 级的高度为 \(i \cdot k\)。
Vlad 的身高是\(H\)厘米。两个身高分别为\(a\)和\(b\)的人如果站在个不同的台阶上，并且他们之间的高度差等于台阶之间的高度差，那么他们可以在自动扶梯上进行对话。
例如，如果两个人的身高分别为\(170\)厘米和\(180\)厘米，以及\(m = 10, k = 5\)厘米，那么他们可以站在\(7\)和\(5\)的梯级上，梯级之间的高度差等于两个人的身高差：\(k \cdot 2 = 5 \cdot 2 = 10 = 180 - 170\).还有其他可能的方法。
给定一个大小为\(n\)的数组\(h\)，其中\(h_i\)表示第\(i\)个人的身高。Vlad 感兴趣的是他能在自动扶梯上与多少人交谈。
例如，如果\(n = 5, m = 3, k = 3, H = 11\)和\(h = [5, 4, 14, 18, 2]\)，Vlad 可以与身高为\(5\)的人交谈（Vlad 将站在\(1\)级、和身高 \(14\)的人进行对话（例如，Vlad 可以站在台阶 \(3\)上，而另一个人将站在台阶 \(2\)上）。Vlad 不能与身高为\(2\)的人交谈，因为即使他们站在自动扶梯的最高阶梯上，他们之间的身高差也是\(6\)，而他们的身高差是\(9\)。Vlad 不能与自动扶梯上的其他人交谈，因此本例的答案是 \(2\)。
分析
对于每个 \(h_i\) 计算出对应的台阶差值 t = abs(H=h[i])，最后检验 t是否是一个满足当前状态的值即可。