Codeforces Round #617 (Div. 3)题解
d2总是掉分的，只有打打d3才能维持一下基础分这样子
注意本文所有代码均为Python3
A. Array with Odd Sum（奇数和数列）
题目大意：给定长为n的数列，可以在数列中选择任意两个数，使第一个覆盖另外一个。问在任意次操作后，能不能使得数列总和不可被2整除。
没必要的题解：把问题所给数列的每个数抽象为奇数和偶数，我们只需要判断数列里面有没有偶数以及有没有奇数，如果都有，显然我们可以构造出一个满足条件的数列。如果只有奇数，我们的操作没有意义，这时判断一下序列的长度如果是奇数那直接满足题意，其余情况就都是NO了。
附上代码：
B. Food Buying（买嘢吃）
题目大意：你去超市消费碰上满十返一（返现）活动，问你可以在花光现有所有钱的情况下达到花多少钱的效果。
题解：当现有钱大于等于10时，一定可以得到返利。我们做个循环，每次取现有钱整除以10的结果，这部分就是返利，令现有的钱减去这部分已经参与返利的钱并把它计入结果，再把返利加回现有钱数，直到现有钱小于10就行了。
附上代码：
C. Yet Another Walking Robot（走路机器人）
题目大意：机器人被按照ULRD四个字符为方向安排一个路线（不是玩游戏用的WASD但可以这么理解）。你的任务是从这个路线中选择连续且最短的一段进行删除，使得机器人的行进路线不变。如果存在无法删除的情况，输出-1（那既然删还要最短一开始就别让我删啊）。对于每组数据，输出格式是【起始删除下标】【空格】【结束删除下标】。
题解：py体现优势的地方来力对于每一步移动，更新它的当前坐标值，看看之前有没有来过这个坐标，来过的话答案就产生了一个。如果当前下标减去之前来过时的下标比当前答案还要小的话，目前的答案就是更优的答案。
怎么记这个坐标呢，其实因为要求最短且连续的移动序列，对于每个坐标只需要记录最近一次来过的时候对应的移动控制字符的下标即可。
附上代码：
D. Fight with Monsters（打怪）
题目大意：你和友仔一起回合制地打怪，每次碰到一个新的怪物总是你先动手，然后轮到友仔再轮到你如此交替直到怪死（怪物单方面挨打，不用考虑怪物的攻击）。你希望尽可能多的收掉怪物的人头，于是你想办法开挂跳过友仔的回合，但是你最多只能开k次挂。现在已知你和你友仔的攻击，开挂次数k和每个怪物的血量，问你最多能拿到几个人头。
输入第一行分别是怪物数n，你的攻击力a，友仔的攻击力b，开挂次数上限k。
第二行分别是每个怪物的血量。
题解：对每个怪物，由于你和友仔轮流攻击，可以先对怪物血量对攻击力总和即a+b求模，模的结果如果在区间[1,a]内那显然这个怪物不开挂也可以被你收掉。反之让模的结果-1再去整除以a的结果就是需要开多少次挂才能收掉这个怪物。特判一下模的结果为0时怪物恰好被友仔掐死，那我们就加回b，恢复到被友仔怼前怪物剩余血量再整除以a处理。把剩余的这些结果统计起来塞进一个新的列表，排序后贪心地选择前几个开挂次数最少就可以拿到的怪物即可。
附上代码：
E. String Coloring（字符串染色）
题目大意：现给一字符串，你可以给每个字符染上一种颜色，注意只有异色相邻的两个字符才能互换位置，你希望在染色后通过若干换位操作使得字符串恢复为字典序。
E1：字符串长度不超过200，且只能染为0和1两种颜色。如果存在可行染色方案，输出YES并按字符顺序输出你的染色。如不行，输出NO。
E2：字符串长度不超过200000，找出一种最少颜色的染色方案，输出颜色数，并按字符输出对应的染色（编号从1起）。
题解：官方给的做法是动态规划。对于每个字符，统计该字符前并且字典序严格大于该字符的所有字符所占用最大颜色编号。该字符所占用颜色编号即为此编号+1。可以证明该字符必定需要且仅需要跟其前面字典序大于该字符的字符进行交换操作，而交换需要异色，故只有当前字符采用一种与前述字符都不重复的全新的颜色才能避免交换冲突。
如果当前字符前面已经没有字典序大于它的字符，即当前状态下无需交换，那么当前字符可以采用第一种颜色。
由于给定的是小写字符集，我们可以用一个26维的表来装每个字符对应的当前采用最大颜色序数。
时间复杂度为O(n)。
附上代码：
E1：
E2：
F. Berland Beauty（伯 兰 之 美）
题目大意：按邻接表给定一棵树，然后对于以下m条线路，按如下信息给出：
出发点a，到达点b，途经（最短路的途径）各边的最小边权g。
如果所给的m条信息中存在矛盾，输出-1。否则输出每条所给边的有效权值（如存在多个可能的值可以任意输出其中一个）。
输入数据的第一行表示所给树的节点数n。接下来的n-1行是这棵树的邻接表表示。
n∈[2,5000]
m∈[1,5000]
样例图解：
题解：首先，如果这题你有LCA做法那可以的话交流一下？
拿到树的图时，我们先花费n^2时间遍历这棵树获取每个节点的父节点，这里可以避免之后使用dfs来找路。这里以节点1作为整棵树的根节点。
我们可以初始化时把每条边的权值记为1（最小可能的权值），因为每次给的权值是所遍历的所有边中最小的，因此在处理共m次更新路径权值操作中就可以把两个点间的所有边的权值设为max{当前边权值，更新操作中所给权值g}。
那么怎么检测冲突呢？
对于共m条的每条更新路径，待所有上述更新操作完毕后再次对于每条路径进行遍历看看是否每条边的最小权值等于g即可。
py选手注意这道题的链状特殊数据会让dfs找父节点的操作爆栈。另外注意本代码的边权beauty记在父节点上。
不知道封面能不能补图= =
