思维题 9 道 题解

A 数字天平 题解

题目标签：思维题

解答思路

由题意可知，若所有的 $n$ 个数字都相同，则 $k$ 可以取到最大值 $k=n$，当 $n$ 个数字不完全相同的时候，考虑这个时候的 $k=n-1$ 能否满足条件。由于题目没有限制减少之后数字的范围，也就是可以不限次数地减少下去，此时对于其中 $n-1$ 个元素同时减一，等效于给剩下的那个元素加一，而通过不限次数的对单一元素增加一的操作，最后一定能够得到一串完全相同的数字。故当 $n$ 个数字不完全相同的时候，$k$ 有最大值为 $n-1$。

备注

这是一道很简单也很明显的思维题，没有算法需求，故不放出代码。

B 简单题 题解

题目标签：思维题

解答思路

过于氵了，看到题目以为是数论，结果发现直接输出 3 个 $3\times S$ 就结束了。

备注

这是一道很简单也很明显的思维题，没有算法需求，故不放出代码。

C 纸牌游戏 题解

题目标签：思维题 预处理 STL

解题思路

看到题面，题意很简单，把双方的牌分成数量相同的两组，分别应用不同的判胜规则，求出最大获胜局数。但是看到暴力枚举的时间复杂度为 $\mathrm{\Theta }(n^2)$ 发现会爆，怎么办，想到优化我们的策略。

首先考虑手牌的分配策略，即，我们应该怎么分配上下半场的手牌来使得能取到最优解。很显然，对于持续了 $N-i$ 回合的上半场（比大局），我们从我们的手牌中选取 $N-i$ 张最大的牌来应对是能保证答案的正确性的，对应的，下半场则是选择 $i$ 张最小的牌应对。也就是说，并不会出现要考虑上半场和下半场 “抢牌” 的情况，因为适合上半场的牌一定不适合下半场，反之亦然。

那我们在这种分配方案的基础上，尝试将每一种分割上下半场的方案的最大胜场求出，即很容易得到，我们只需要求出 $F_1(i)$ 来表示前 $i$ 张牌用于上半场时的 ** 上半场最多胜局，即所谓前缀最优解；对应地，$F_2(i)$ 用来表示下半场最多胜局，即所谓后缀最优解，由于前面提到的出牌策略，前缀最优解和后缀最优解使用的牌一定不会相冲突 **。而易得每一种分割上下半场的方案的最大胜场 $F(i)=F_1(i)+F_2(i)$。

现在问题转化为了如何求取 $F_1(i)$ 与 $F_2(i)$，枚举的话时间复杂度仍然是 $\mathrm{\Theta }(n^2)$。于是想到了因为是求前缀最优解，状态是连续的，考虑使用动态规划，但是始终没有想到合适的状态转移方法，故放弃考虑 dp 解法。我们注意到，对于每一个上半场情况，可以不限制我们选择的手牌一定是最大的那些牌，对于对方出的某一牌面为 $a_i$ 的牌，我们可以选择牌面比 $a_i$ 大的手牌中最小的那一张打出，能找到这样的牌即可说明这回合获胜的可能性，反之即不可获胜，这样做的好处是，它避免了你限制出牌是最大的那几张后，出现 “田忌赛马” 的情况，使得你最大的牌对上了对方较小的牌，而当对方新引入了较大的牌（但仍有方案可以取胜）时，由于较大牌被先前的小牌 “占用” 而不得不重新考虑方案。现在的出牌逻辑使得各牌 “各取所需” 在同一半场内不会冲突，但是又引入了新的问题，因为我们取用的是可用牌中的最小牌，那到了下半场比小应该怎么办呢？其实，上半场并不会将小牌 “误占用”，我们对于上半场求取的其实只是一个 “可能性”，假设我们手上的牌从大到小排序为 $a_1,a_2,a_3,\cdots ,a_N$，且在上半场的 $i$ 回合中使用了牌面数值为 $b_1,b_2,b_3,\cdots ,b_i$ 的这 $i$ 张，那么使用更大的第 $1,2,3,\cdots ,i$ 这几张显然能够获得相同的效果（因为一定有 $a_1\ge b_1,a_2\ge b_2,a_3\ge b_3,......,a_i\ge b_i$），并且为下半场让出所有最小牌。

到这里不难看出，最后我们需要维护一个数据结构，能够先其中放入我们的手牌，从其中查询是否存在能取胜的牌，并且在使用这张牌后删去它避免二次使用，于是我们选择了 C++ STL 库中的set 内置容器来实现，set 的原理是红黑树，感兴趣可以自行了解。

最后总结求解逻辑：以求前缀最优（大牌获胜的半场）为例：我们先把自己手上的牌全部加入 set，然后遍历对方出牌顺序，每次看看这次加进去的牌能不能多完成一次获胜，就是去找对面容器里的上确界 upper_bound，如果找到，就把对面的那张牌从 set 里删掉；对下半场执行同样的操作，得到所有 $F_1(i)$ 与 $F_2(i)$，然后遍历 $F(i)=F_1(i)+F_2(i)$，维护一个 $F(i)$ 的最大值，即为最后的答案。由于 set 执行插入，查找，删除的复杂度均为 $\mathrm{\Theta }(\log n)$ , 则整体时间复杂度为 $\mathrm{\Theta }(n\log n)$，符合要求。

备注

此题稍难，但由于没有评测条件，且没有算法需求，故不放出代码。

D 巡视王国 题解

题目标签：思维题

由题意易得，每次删去两个节点，则对于奇数个结点的图一定无解，而对于偶数个节点的图，因为不存在重边和自环，所以这 $n$ 个节点的度数 $i$ 一定满足 $1\le i\le n-1$，所以一定存在两个度数相同的点，若其后 “巡视” 的过程中变成了两个不相连通的 $n^{\prime }$ 个节点的子图，这 $n^{\prime }$ 个节点的度数 $i$ 一定满足 $0\le i\le n-2$，同样一定存在两个度数相同的点，所以对于对于偶数个节点的图一定有解。

备注

这是一道很简单也很明显的思维题，没有算法需求，故不放出代码。

E 数学考试 题解

题目标签：思维题 数学 容斥原理

解题思路

看到了题面，思考后发现所有的条件之间均不互相矛盾，所以如果要暴力计算的话要考虑 $2^m$ 种情况，时间肯定爆了，那我们就会自然地想到：所有条件都可以随意地满足 / 违背，那可以使用容斥原理：

定义

设 $U$ 中元素有 $n$ 种不同的属性，而第 $i$ 种属性称为 $P_i$，拥有属性 $P_i$ 的元素构成集合 $S_i$，那么

$$\left|\bigcup _{i=1}^n{S}_i\right|=\sum _i|S_i|-\sum _{i<j}|S_i\cap S_j|+\sum _{i<j<k}|S_i\cap S_j\cap S_k|-\cdots +(-1{)}^{m-1}\sum _{a_i<a_{i+1}}\left|\bigcap _{i=1}^m{S}_{a_i}\right|+\cdots +(-1{)}^{n-1}|S_1\cap \cdots \cap S_n|$$

即

$$\left|\bigcup _{i=1}^n{S}_i\right|=\sum _{m=1}^n(-1{)}^{m-1}\sum _{a_i<a_{i+1}}\left|\bigcap _{i=1}^m{S}_{a_i}\right|$$

证明

对于每个元素使用二项式定理计算其出现的次数。对于元素 $x$，假设它出现在 $T_1,T_2,\dots ,T_m$ 的集合中，那么它的出现次数为

$$\begin{array}{rl}Cnt=& \left|\left\{T_i\right\}\right|-\left|\{T_i\cap T_j\mid i<j\}\right|+\cdots +(-1{)}^{k-1}\left|\{\bigcap _{i=1}^k{T}_{a_i}\mid a_i<a_{i+1}\}\right|+\cdots +(-1{)}^{m-1}\left|\{T_1\cap \cdots \cap T_m\}\right|\\ =& (\genfrac{}{}{0ex}{}{m}{1})-(\genfrac{}{}{0ex}{}{m}{2})+\cdots +(-1{)}^{m-1}(\genfrac{}{}{0ex}{}{m}{m})\\ =& (\genfrac{}{}{0ex}{}{m}{0})-\sum _{i=0}^m(-1{)}^i(\genfrac{}{}{0ex}{}{m}{i})\\ =& 1-(1-1{)}^m=1\end{array}$$

于是每个元素出现的次数为 1，那么合并起来就是并集。证毕。

对于这个问题中的容斥原理的应用，就应该考虑所谓的每种属性应该是什么：如果将方案对于这 $m$ 个要求的满足情况用 “1” 表示满足，“0” 表示违背，“-” 表示均可的话，我们就可以将所有错误方案按照 ** 第一个违背的条件 ** 来分为以下 $m$ 种：

$$\begin{gathered} S_1\{0,-,-,-,...,-,-\} \\ {S}_2\{1,0,-,-,...,-,-\} \\ {S}_3\{1,1,0,-,...,-,-\} \\ ... \\ {S}_m\{1,1,1,1,...,1,0\} \end{gathered}$$

同时用 $S_i$ 表示第 $i$ 种情况下的方案数，用 $F_i$ 表示第 $i$ 种情况下只考虑违背条件的作用域中（第 $1\mathrm{到}{P}_i$ 个数）的方案数，现在我们可以推导出 $S_i=F_i\times (n-P_i)!$。显然 $F_1=P_1!$，我们需要想出一个方法，利用已知的 $F_i$ 求出 $F_{i+1}$，由容斥原理可得：

$$\begin{array}{rl}{F}_2& =\{1,0\}\\ & =\{-,0\}-\{0,0\}\\ & =P2!-F_1\times (P_2-P_1)!\\ \\ F_3& =\{1,1,0\}\\ & =\{1,-,0\}-\{1,0,0\}\\ & =(\{-,-,0\}-\{0,-,0\})-\{1,0,0\}\\ & =P_3!-F_1\times (P_3-P_1)!-F_2\times (P_3-P_2)!\\ \\ F_4& =\{1,1,1,0\}\\ & =\{1,1,-,0\}-\{1,1,0,0\}\\ & =(\{1,-,-,0\}-\{1,0,-,0\})-\{1,1,0,0\}\\ & =((\{-,-,-,0\}-\{0,-,-,0\})-\{1,0,-,0\})-\{1,1,0,0\}\\ & =P_4!-F_1\times (P_4-P_1)!-F_2\times (P_4-P_2)!-F_3\times (P_4-P_3)!\\ & ...\\ F_m& =\{1,1,...,1,0\}=P_m!-\sum _{i=1}^m[F_i\times (P_n-P_i)!]\end{array}$$

所以我们可以通过这种办法，把全部的 $F_i$ 求出来，进而求出全部的 $S_i$，用 $n!$ 减去 $\sum _{i=1}^m{S}_i$ 即为最后答案，计算需要高精度，同时为了避免重复计算，需要将 $n!mod998244353(1\le n\le 2000)$ 的值预处理出来以供直接使用。

F 区间 题解

题目标签：思维题 线段树

解题思路

看到这道题，要求实现修改和区间求和，很容易想到线段树实现，但是这道题的修改是一个开平方的操作，不想加法或乘法那样可以批量处理整个区间，所以想过去觉得不好办，但是思考后发现 $2^{2^5}=2^{32}>{10}^9$，所以对于题目给的每一个数，假使我们对于线段树的维护方式是一个一个维护的，操作轮数也只有 $5\times n\times \log n$ 完全在掌控之中，而求和就由线段树来完成。

简单介绍线段树算法：

概念

线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。

线段树可以在 $O(\log N)$ 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。

线段树将每个长度不为 $1$ 的区间划分成左右两个区间递归求解，把整个线段划分为一个树形结构，通过合并左右两区间信息来求得该区间的信息。这种数据结构可以方便的进行大部分的区间操作。

如果要求修改区间 $[l,r]$，把所有包含在区间 $[l,r]$ 中的节点都遍历一次、修改一次，时间复杂度无法承受。我们这里要引入一个叫做 「懒惰标记」 的东西。

懒惰标记，简单来说，就是通过延迟对节点信息的更改，从而减少可能不必要的操作次数。每次执行修改时，我们通过打标记的方法表明该节点对应的区间在某一次操作中被更改，但不更新该节点的子节点的信息。实质性的修改则在下一次访问带有标记的节点时才进行。

备注

此题由于没有评测条件，故不放出代码。

G 图计算 题解

题目标签：思维题 并查集 哈希表

解题思路

由于是无向图，所以求联通点对只需用用并查集溜一遍然后套公式就好了，问题的关键是怎么处理这些加边操作，对于每一条边开数组肯定炸空间，每加一个去查前面加进来的边会爆时间。需要存储小量的大范围数，那不就是哈希表吗？做法很明显：开一个哈希表，每次把新的边存到表中，如果这条边尚不存在，那就检查这次加边之后是否在全部的图中都存在，如果是，则标记为已存在并且更新答案。

备注

此题由于没有评测条件，故不放出代码。

H 纸盒糖果 题解

题目标签：思维题

解题思路

很简单的一道题，对于第一和第二盒这一对，如果其中糖果之和不满足条件，则优先将第二盒的糖果拿出（不能小于零），因为第二盒对第三盒还有贡献的可能而第一盒没有，然后对于第二盒与第三盒这一对进行相同的操作，直到所有都满足条件即可。

备注

这是一道很简单也很明显的思维题，没有算法需求，故不放出代码。

I 幸运数 题解

题目标签：思维题 数学

解题思路

最 “思维” 的一道题，最后的解法非常简单：对于给定的参数 d 和原数字（n 位数）a 的话，将它直接乘上 2*10^10，可以得到一个（至少）n+10 位数 A，并且 A 一定大于 B=123456789d9...9（后面补上 n 个 9，凑齐 n+10 位），那我们只需要将现在的这个 B 减去它对原数字 a 取模的结果，就一定是一个合法的幸运数 X（前十位数一定和 B 相同，满足要求，并且是 a 的倍数），我们要求的 k 就是 X 除以 a 的结果

备注

这是一道很简单但是不很明显的思维题，没有算法需求，故不放出代码。