ICPC2018 Qingdao

评论

B.Kawa Exam

Problem - B - Codeforces

取图的任意一个生成树，对于关键树边，我们需要求其两端的子树中，出现次数最多的数字的出现次数，DSU统计子树内信息和子树外信息即可；对于非关键树边，删掉它没有影响

如何统计出现次数最多的数字呢？设f[i]表示数字i出现了多少次，g[i]表示有多少个数字出现了i次即可

C.Flippy Sequence

Problem - C - Codeforces

把s和t序列异或一下，得到一个新序列w，讨论这个序列w中全1段的数量

  • ，那么答案是
  • ，那么答案是（是全1段的长度）
  • ，那么答案是
  • 否则，答案是

D.Magic Multiplication

Problem - D - Codeforces

发现确定了一个后，数字相当于确定了，数字也可以随之确定

枚举就行了

E.Plants vs. Zombies

Problem - E - Codeforces

二分一个目标防御值D，然后检验能不能在m次move后让所有植物的防御值

检验的时候因为每次浇水前都需要移动机器人，贪心来看，机器人会左右横跳浇水，直到一株植物达到要求后，再继续往后浇水

F.Tournament

Problem - F - Codeforces

对于一个集合，要求一个二阶置换群，满足且

想到可以构造满足题意

J.Books

Problem - J - Codeforces

差点想二分所携带的钱，然后看能否购买对应本书，但是此题并没有二分性，例如4 1 2，3能购买两本书，而只能购买一本书，并不是带的钱越多购买的书就越多

把去掉0$的所有书，在花钱最多的情况下，对剩下的书的购买一定是：分割书的序列为前一部分和后一部分，前一部分全必能买，后一部分全都没钱买

L.Sub-cycle Graph

Problem - L - Codeforces

个点条边，有条链各自组成了连通块（至少有两个点），则有个点从属于连通块，个点是孤立点，这样的图的数量可以这样统计： 先选个点当孤立点，然后对于条链，从个点中选出个点作为链的端点，链的端点匹配过程中就是每次选一个编号最小的点，和剩下的个点进行匹配

最后再把连通块中的，不在链端点处的个点放到链上

M.Function and Function

Problem - M - Codeforces

注意到函数值很快就变成0，并且在0和1之间左右横跳

whoseJam