[ABC149-A]字符串

题意

拼接两个字符串$T$和$S$。

解法

1. 直接定义两个string类型变量$S$和$T$并输入。
2. 输出$T+S$即可。

---

[ABC149-B]贪婪的高桥

题意

第一个人有A块饼干，第二个人有B块饼干。第一个人会先吃自己的，把自己吃完再吃第二个人的。问K次之后两个人分别有多少饼干。

解法

分类讨论即可。

如果$K \leq A$，直接输出$A-K$和$B$，即第一个人吃掉自己的$K$块饼干。 如果$A < K \leq A+B$，则输出$0$和$B-(K-A)$，即第一个人吃完自己的饼干，又吃了第二个人$K-A$块饼干。

如果$K > A+B$，直接输出$0$和$0$，因为两个人的饼干都被吃完了。

---

[ABC149-C]下一个质数

题意

找到大于或等于$X$的最小质数。

解法

从$X$开始往后枚举，判断是不是质数。

判断一个数字$X$是否是质数的方法为：令$i$从$2$一直枚举到$\sqrt{X}$，如果$X$除以$i$的余数为0，则$X$不是质数。如果一直枚举到$\sqrt{X}$都没有出现能整除的情况，则$X$是质数。

拓展：素数筛，本题用不到，感兴趣的同学可以了解。

---

[ABC149-D]预测与限制

题意

剪刀石头布游戏，已知机器的手势序列，如果自己赢了，在出剪刀、石头、布三种手势的情况下，获得三种不同的得分。

有一个限制，第$i$轮不能出和第$i-k$轮一样的手势。

解法

我们假设没有限制，那么就都出赢的手势就可以。

假设$i=10,k=5$。如果第$5$轮出的石头，并且第$10$轮也需要出石头才能赢，那么第$10$轮就只能输（因为规则限制）。假设我们为了让第$10$轮赢而放弃第$5$轮，第$10$轮赢和第$5$轮赢，获得的得分是一样的。

本题前面出的手势对整体得分没有影响，无后效性，可以使用贪心。

---

[ABC149-E]贪婪的高桥

题意

高桥在一个聚会上进行多次握手以增加聚会的快乐度。每位普通嘉宾有一个代表其“力量”的数值。高桥通过同时握住两位嘉宾的手来增加快乐度，快乐度的增加等于这两位嘉宾力量值的和。

解法

从n个人中任意选两个（允许相同），最多有$n \times n$中选法，需要找出这些选法中，组合出来最大的$m$个。

由于$n$较大，不能把所有组合都计算出来再排序。可以使用二分答案，假设我们按照能获得的快乐值从最大到最小的顺序握手，二分最后一次握手能达到的最大的快乐值。

---

[ABC149-E]贪婪的高桥

二分的对象是最后一次握手可以获得的最大快乐度$x$。二分范围是$[ 1,2×A[𝑛] ]$，其中$𝐴[𝑛]$是排序后的最大力量值（因为两个最大值握手得到的快乐度最高）。

二分快乐度，判断是否可以进行$M$次快乐度大于等于$mid$的握手，如果有，则 $l=mid+1$，否则$r=mid$；

验证函数 check(x)：

• 对于每个固定的$x$，我们需要判断是否可以进行$M$次快乐度大于等于$x$的握手。
• 对于每个嘉宾$i$，我们计算需要的另一位嘉宾的最小力量$x - A[i]$，使用二分查找在排序后的数组中找到这个最小力量的位置 pos。
• 所有大于等于这个力量的嘉宾都可以与嘉宾$i$握手，累计这样的握手数 cnt 和相应的快乐度总和 ans。
• 使用前缀和数组来快速计算所有符合条件嘉宾的力量和。

需要注意的是，可能有多个组合的快乐值和最后一次握手的相同，因此还需要减去那些。

---

[ABC148-F]玩树上的标签游戏

题意

这道题目是一个关于树形结构的追捕游戏，其中包含一个由N个顶点组成的树，Takahashi和Aoki分别站在不同的顶点上。游戏的规则是，Takahashi试图尽可能延长游戏时间，而Aoki则试图尽快结束游戏。两人轮流移动到相邻的顶点，如果两人达到同一顶点，游戏结束。题目要求计算在两人都采取最优策略的情况下，Aoki需要执行多少次移动才能结束游戏。

解法

考虑记录所有点到$u$和到$v$的最短距离，由于只有$n-1$条边，可以使用DFS算法完成。

如果点$i$到$v$的距离小于点$i$到$u$的距离，这意味着$T$不可能会来到这里，因为$T$需要尽可能延长游戏时间。

如果点$i$到$v$的距离大于点$i$到$u$的距离，则记录这个$i$到$v$的距离，选一个最大的即可。

由于问题询问的是$A$的行走次数，因此最终答案需要减一。