Q779’s Blog

洛谷P9156 「GLR-R4」芒种 题解 题目链接：P9156 「GLR-R4」芒种 题意：   双重神经衰弱 是一个极其考验记忆力的卡牌游戏，其规则如下。   有 \(n\) 种不同类型的卡牌，每种两张，初始时这 \(2n\) 张牌全部倒扣在桌面上。两位玩家轮流操作，每次操作选择两张不同的牌同时翻起，这两张牌将对双方展示，此后： 若两张牌类型相同，则操作者得 \(1\) 分，将这两张牌拿走。下一次操作由当前操作者继续进行。 否则，操作者将这两张牌扣回。下一次操作轮到对方进行。   当所有牌全部被拿走时，游戏结束。   两位玩家的目标都是最大化自己的最终得分。此外，在双方同意的情况下，两人可以选择和局。设和局时还剩下 \(2n'\) 张牌，则双方各获得 \(n'/2\) 分，游戏结束。为避免游戏无法结束的情况，我们认为：当选择和局同时是双方的最优选择之一时，双方会立即和局。   现在，阿绫和天依想来玩玩这个游戏。因为太饿，负责摆牌的天依不小心把 \(2n\) 张牌中的 \(m\) 张牌牌面朝上地摆放了，这 \(m\) 张牌的的类型恰好两两不同，双方悄悄记住...

CF1415E New Game Plus! 题解 题目链接：CF1415E New Game Plus! 题意： 你有 \(n\) 个数 \(c_{1 \cdots n}\) 和 \(1\) 个初始为 \(0\) 的计数器 boss bonus。 你可以任意选择一个尚未被选择过的 \(c_{i}\)，把 boss bonus 加上 \(c_{i}\)。 你也有 \(k\) 次机会把 boss bonus 变成 \(0\)。 每次「选择数字前的 boss bonus 的和」记为你的收获。求收获的最大值。 注意 \(c_{i}\) 和最后的收获可以为负数。 输入格式： 输入的第一行两个整数，分别是 \(n,k\)。 输入的第二行 \(n\) 个整数，表示 \(c_{1 \cdots n}\)。 输出格式： 输出一行，最大收获。 数据范围： \(1 \leq n \leq 5 \times 10^5,0 \leq k \leq 5 \times 10^5,-1 \times 10^6 \leq c_{i} \leq 1 \times 10^6\) 容易发现，这 \(k\) 次机会...

CF1396B Stoned Game 题解 题目链接：CF1396B Stoned Game 题意： 有 \(n~(1 \le n \le 100)\) 堆石子，每堆分别有 \(a_i~(1 \le n \le 100)\) 个石子。 两者轮流取其中一个石子。但不能取上次对手取过的那一堆。特殊的，第一次取可以取任何一堆的石子。 当前先手取完要取的石子之后使对手无路可走时，先手获胜。 \(T(T \le 100)\) 组数据，每组数据给出 \(n\) 和 \(a\) ，输出谁必会胜利。若先手胜利输出 T，若后者胜利输出 HL。 萌萌的博弈论题。 设最大的那一堆为 \(a_p\) ，并记 \(S = (\sum_i a_i) - a_p\) 。 当 \(a_p > S\) 时，显然先手必胜 否则，\(a_p\) 一定被全取完，同时 \(S \gets S - a_p\) 。 然而这并没有改变 \(S\) 的性质，也就是说，一定还剩下一堆最大的，先手依然会选择它。 因此其实这道题几乎只需要判断奇偶性即可。 时间复杂度 \(\mathcal{O}(T\cdot n)\) ...

CF1338B Edge Weight Assignment 题解 题目链接：CF1338B Edge Weight Assignment 题意： 给定一棵 \(n(3 \le n\le 10^5)\) 个点的无根树。 要求给每条边分配一个正整数权值，使得任意两个叶子节点之间路径上的边权异或值为 \(0\)。 求最少要多少种不同权值，以及最多可以使用多少种不同权值。 填入的边权值可以为任意大。 直觉告诉我们，第二个问题的答案和第一个问题的答案高度相关（废话）。 先找一个度数不为 \(1\) 的点作根，那么题目就转化为：叶子节点到根的路径上边权异或值相同。 如果所有这样的路径长度的奇偶性都相同，那么可以全部填 \(1\) 。 否则我们可以…等等，好像并不能靠填 \(0,1\) 到达这个目的，怎么办呢？（写完才发现是正整数） 观察样例可以发现，\(\left((01)_2 \land (10)_2\right) \oplus (11)_2 = 0\) ，也就是说我们可以用 \(1,2,3\) 来填。 对于长为偶数的路径就填 \(1,2,1,\cdots,1,2\) ，对于奇数的路...

CF1379C Choosing flowers 题解 题目链接：CF1379C Choosing flowers 题意： 有 \(m\) 种物品，每种物品有无限个，你可以购买 \(n\) 个物品。 对于第 \(i\) 种物品： 第一次买时的贡献是 \(a_i\) ,接下来每购买一个的贡献都是 \(b_i\)。即当你买了 \(x_i\) 个第 \(i\) 种物品时，贡献是 \(a_i+b_i \times (x_i-1)\) 现在要你求出最大贡献。 输入格式： 第一行一个 \(t (1≤t≤10^4)\)，表示有 \(t\) 组数据。 对于每组数据： 第一行\(n\) 和 \(m (1≤n≤10^9,1≤m≤10^5)\) 接下来 \(m\) 行，每行两个整数\(a_i\)和\(b_i(0≤a_i,b_i≤10^9)\) 每组数据后有一个空行。 输出格式： 对于每组数据，输出一行一个整数表示最大的贡献。 容易发现，最优解一定只有一种物品被买了多次。 考虑枚举这个物品 \(i\) ，如果 \(i\) 被买了多次，则其他物品 \(k_i\) 一定有 \(a_{k_i} > ...

CF1325D Ehab the Xorcist 题解 题目链接：CF1325D Ehab the Xorcist 题意： 给定整数 \(u\) 和 \(v(0\le u,v \le 10^{18})\) 试构造长度最短的数组，使得数组内所有元素的异或和为 \(u\)，加和为 \(v\)。 如果有解，输出两行，第一行输出一个整数 \(n\)，第二行输出 \(n\) 个非负整数，表示数组里的元素。 多解输出任意一组即可。如果无解，输出一行一个整数 \(-1\)。 Codeforces 居然没有 C++14 的提交方式了。 简单观察样例可以发现结论， \(u > v\) 时一定无解。 这点很容易证明，因为异或本质上是二进制下的不进位加法，所以无论如何值都不会变得更大。 根据上面的结论，可以发现 \[ a + b = (a\oplus b) + 2(a \land b) \] 即 \[ a + b - (a\oplus b) = 2(a \land b) \] 这里的 \((a\land b)\times 2\) 表示的是手动进位（因为异或是不进位加法） 当然这里还有一个附加...

[AGC010F] Tree Game 题解 题目链接：[AGC010F] Tree Game 题意： 有一棵 \(n\) 个节点的树，第 \(i\) 条边连接 \(a_i,b_i\)，每个节点 \(i\) 上有 \(A_i\) 个石子，高桥君和青木君将在树上玩游戏 首先，高桥君会选一个节点并在上面放一个棋子，然后从高桥君开始，他们轮流执行以下操作： 从当前棋子占据的点上移除一个石子，将棋子移动到相邻节点 如果轮到一个人执行操作时棋子占据的点上没有石子，那么他就输了。 请你找出所有的点 \(v\)，使得如果高桥君在游戏开始时把棋子放到 \(v\) 上，他可以赢。 输入格式： 第一行一个整数 \(n\) 第二行 \(n\) 个整数 \(A_{1..n}\) 接下来行每行两个整数 \(a_i,b_i\) 表示一条边 输出格式： 以编号递增的顺序在一行中输出所有满足条件的点 数据范围： \(2 \le n \le 3000,~0 \le A_i \le 10^9\) 根据博弈论的套路，记 \(f_u = \mathrm{N/P}\) 表示点 \(u\) 先手为必胜态/必败态。 ...

洛谷P9034 「KDOI-04」Again Counting Set 题解 题目链接：P9034 「KDOI-04」Again Counting Set 题意： 小 S 不喜欢集合，不喜欢自然数，不喜欢求和，不喜欢求积，不喜欢最小值，不喜欢最大值，不喜欢 \(\operatorname{mex}\)，所以有了这题。 给出 \(n,k\)，求有多少个可重整数集合 \(S\) 满足： \(|S|=k\)； 对于任意 \(x\in S\)，\(0\le x\le n\)； \(\displaystyle{\prod_{x\in S} x=\min_{x\in S} x}\)； \(\displaystyle{\sum_{x\in S} x=\min_{x\in S} x+\max_{x\in S}x+{\operatorname{mex}}(S)}\)。 注： \(\bf{mex}\) 指集合中没有出现过的最小的自然数。 输入格式： 本题包含多组测试数据。 输入的第一行包含一个正整数 \(T\)，表示测试数据组数。 对于每组测试数据，输入包含一行两个正整数 \(n,k\)。 输...

CF1292B Aroma’s Search 题解 题目链接：CF1292B Aroma’s Search 题意： 获得了新身体后，我们的偶像 Aroma White（或者应该被称为 Kaori Minamiya？）开始在 OS 空间中寻找她尘封的过去。 这个空间可以看作是一个二维平面，在其内部有着无限多的数据点，从 \(0\) 开始标号，它们的坐标定义如下： 第 \(0\) 个点的坐标为 \((x_0, y_0)\)。 对于 \(i > 0\)，第 \(i\) 个点的坐标为 \((x_i, y_i) = (a_x \cdot x_{i-1} + b_x, a_y \cdot y_{i-1} + b_y)\)。 初始时 Aroma 的位置为 \((x_s, y_s)\)。她只能留在 OS 空间中最多 \(t\) 秒，因为她还需要传送回真实世界。她不需要返回初始位置 \((x_s, y_s)\) 也能传送回家。 在 OS 空间中，Aroma 可以做如下操作： 在点 \((x, y)\) 上时，Aroma 可以移动到这四个点之一：\((x-1, y), (x+1, y)...

CF1415D XOR-gun 题解 题目链接：CF1415D XOR-gun 题意： 给定一个长为 \(n\) 的不降序列，每次操作可以任选相邻的两个数，并将这两个数替换为两个数按位异或的结果，现在需要破坏序列的不降，求最少操作次数，无解输出 \(-1\) 。 输入格式： The first line contains a single integer \(n\) ( \(2 \le n \le 10^5\) ) — the initial length of the array. The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) ( \(1 \le a_i \le 10^9\) ) — the elements of the array. It is guaranteed that \(a_i \le a_{i + 1}\) for all \(1 \le i < n\) . 输出格式： Print a single integer — the minimum number of ste...

CF1446C Xor Tree 题解 题目链接：CF1446C Xor Tree 题意： 给定长为 \(n(n \le 2\times 10^5)\) 的非负整数序列 \(a\)，保证其中每个数两两不同且 \(a_i \le 10^9\) 。 对于每个 \(a _ i\)，它会向 \(j \ne i\) 且 \(a_i\oplus a_j\)（\(\oplus\) 代表异或）最小的 \(a _ j\) 连双向边。 如果 \(a _ j\) 也向 \(a _ i\) 连了边，只算一条边。 现在要让你删去序列中的一些数，使得最后形成的图是一颗树，输出最少需要删除几个数。 输入格式： 第一行 \(n\) ，第二行 \(a_i\) 。 输出格式： 只有一行，即答案。 首先把问题中的最小删除多少个看作最多可以保留多少个。 考虑建 01 trie，然后递归地考虑每个子树能保留多少个点，记为 \(f_u\) 。 对于点 \(u\) ，如果它只有一棵子树，则 \(f_u\) 为那棵子树的大小，否则为左右子树中最大的那一棵 \(+1\) 。 前者很好理解，后者解释一下：例如右子树较大，我们就...

CF1349B Orac and Medians 题解 题目链接：CF1349B Orac and Medians 题意： Slime 有一个正整数序列 \(a_1, a_2, \ldots, a_n\)。 在一次操作中，Orac可以选择这个序列的任意子段 \([l \ldots r]\) 并将 \(a_l, a_{l+1}, \ldots, a_r\) 的所有值替换为 \({a_l, a_{l+1}, \ldots, a_r}\) 的中位数。 在这个问题中，对于整数多重集 \(s\)，\(s\) 的中位数等于其中第 \(\lfloor \frac{|s|+1}{2}\rfloor\) 小的数字。例如，\({1,4,4,6,5}\) 的中位数是 \(4\)，\({1,7,5,8}\) 的中位数是 \(5\)。 Slime 希望 Orac 通过这些操作使得 \(a_1 = a_2 = \ldots = a_n = k\)。 Orac 认为这是不可能的，他不想浪费时间，所以决定问你是否有可能满足 Slime 的要求，他可能会多次问这个问题。 输入格式： 输入的第一行是一个整数 \(...