【LGR-071】洛谷 4 月月赛 MdOI Round 2 Div.2 总结
【LGR-071】洛谷 4 月月赛 & MdOI Round 2 Div.2 总结
作者：linweitong2020
这次比赛我考了220220220分，还是考的不错，就是第二道题没有拿满分，看了题解后觉得是垃圾。
直接输出111111 1 1 1 111111
对于子任务222：直接对最后一位进行判断。
对于子任务333：直接从后往前遍历整个字符串，找到数字并判断即可。
得分情况比赛时100100100分。
第二题： 『MdOIR2』『MdOI R2』『MdOIR2』MayuriMayuriMayuri 解题思路这道题的解题思路是贪心。
对于子任务1 to 41\:to\:41to4：直接暴力即可
对于子任务555：每次贪心选取最小的，每次选完可将数模aaa，否则会超出整形范围。
得分情况比赛时808080分，可能是因为超出整形了。
时间竟然没有超限——我用的是递归枚举。
改题后满分。
这道题目的解题思路是动态规划。
可以知道有向无环图是DAGDAGDAG，可以利用拓扑排序进行dpdpdp。
因为k=1k=1k=1，所以直接dpdpdp即可，不用判断。
直接记忆化搜索+动态规划，可以知道fx=fy+dis(x,y)f_x=f_y+dis(x,y)fx=fy+dis(x,y)。
注：dis(x,y)dis(x,y)dis(x,y)表示xxx到yyy的距离。
时间复杂度为O(m)O(m)O(m)。
直接暴力搜索就行了。
首先可以预处理bkb_kbk表示xkx^kxk。
然后判断时只要二分答案，看一下你这个数是否在bbb数组里面。
时间复杂度很高，可以卡过。
比赛时404040分。
第四题： 『MdOIR2』『MdOI R2』『MdOIR2』ResurrectionResurrectionResurrection 解题思路没有看题目。
得分情况比赛时000分。
未完待续……作者：linweitong2020
