7月22日-ABC149
# [ABC149-A]字符串
# 题意
拼接两个字符串
# 解法
- 直接定义两个string类型变量
和 并输入。 - 输出
即可。
# [ABC149-B]贪婪的高桥
# 题意
第一个人有A块饼干,第二个人有B块饼干。第一个人会先吃自己的,把自己吃完再吃第二个人的。问K次之后两个人分别有多少饼干。
# 解法
分类讨论即可。
如果
如果
# [ABC149-C]下一个质数
# 题意
找到大于或等于
# 解法
从
判断一个数字
拓展:素数筛,本题用不到,感兴趣的同学可以了解。
# [ABC149-D]预测与限制
# 题意
剪刀石头布游戏,已知机器的手势序列,如果自己赢了,在出剪刀、石头、布三种手势的情况下,获得三种不同的得分。
有一个限制,第
# 解法
我们假设没有限制,那么就都出赢的手势就可以。
假设
本题前面出的手势对整体得分没有影响,无后效性,可以使用贪心。
# [ABC149-E]贪婪的高桥
# 题意
高桥在一个聚会上进行多次握手以增加聚会的快乐度。每位普通嘉宾有一个代表其“力量”的数值。高桥通过同时握住两位嘉宾的手来增加快乐度,快乐度的增加等于这两位嘉宾力量值的和。
# 解法
从n个人中任意选两个(允许相同),最多有
由于
# [ABC149-E]贪婪的高桥
二分的对象是最后一次握手可以获得的最大快乐度
二分快乐度,判断是否可以进行
验证函数 check(x)
:
- 对于每个固定的
,我们需要判断是否可以进行 次快乐度大于等于 的握手。 - 对于每个嘉宾
,我们计算需要的另一位嘉宾的最小力量 ,使用二分查找在排序后的数组中找到这个最小力量的位置 pos
。 - 所有大于等于这个力量的嘉宾都可以与嘉宾
握手,累计这样的握手数 cnt
和相应的快乐度总和ans
。 - 使用前缀和数组来快速计算所有符合条件嘉宾的力量和。
需要注意的是,可能有多个组合的快乐值和最后一次握手的相同,因此还需要减去那些。
# [ABC148-F]玩树上的标签游戏
# 题意
这道题目是一个关于树形结构的追捕游戏,其中包含一个由N个顶点组成的树,Takahashi和Aoki分别站在不同的顶点上。游戏的规则是,Takahashi试图尽可能延长游戏时间,而Aoki则试图尽快结束游戏。两人轮流移动到相邻的顶点,如果两人达到同一顶点,游戏结束。题目要求计算在两人都采取最优策略的情况下,Aoki需要执行多少次移动才能结束游戏。
# 解法
考虑记录所有点到
如果点
如果点
由于问题询问的是