- 简要总结
- A Chuanpai
- K K-skip Permutation
- D Rock Paper Scissors
- H Nihongo wa Muzukashii Desu
- B Hotpot
- M True Story
- L Spicy Restaurant
- J Ants
简要总结
总的来说，这次的成绩还算令人满意。13道题拿到8个气球，最后还有一个绝杀，不错了。
唯一的遗憾就是F没做出来，lsw五分钟暴切，神。
按照做题顺序排序
A Chuanpai
题目大意
输入一个整数\(k\)，求\(x+y=k\)方案数，\(x≤y≤6\)。
Sol
太水了，直接暴力枚举
K K-skip Permutation
题目大意
输入两个整数\(k,n\),构造一个\(n\)的排列，使得满足\(a_{i+1}-a_i==k\)的数量最大化。
Sol
还是水，直接\(1\)到\(k\)循环，每个循环里面不断加\(k\)循环即可
D Rock Paper Scissors
题目大意
两人玩石头剪子布，现给出每人每种总共出了多少次（保证加起来相同），求出一种出拳顺序下，\(B\)获胜减去\(A\)获胜的最大值。
Sol
依然水，能赢的都赢，然后更新一遍。接下来能平的都平，又更新一遍。最后减去输的即可。
令人裂开的是\(zyw\)写了一遍，\(WA\)了，我重构代码一遍，又\(WA\)了。让票池查错，
\("long\ long\)开了吗\("\)
......
H Nihongo wa Muzukashii Desu
题目大意
给定一大堆日语中动词词缀\(masu\)的转换法则，输入一系列词，让你输出转换后的词。
Sol
一堆\(if\)就完了，字符串要注意下标问题。
B Hotpot
题目大意
\(n\)个人按照一定的顺序不断循环一共进行\(m\)次操作。
这\(n\)个人都有一个对应的喜爱的食物(可重复)，对于第\(i\)个人的操作，如果火锅里有他喜欢的食物，那他就会把它吃完并获得\(1\)快乐值，否则会把这种食物加入火锅。
初始时火锅是空的，问\(m\)次操作以后每个人的快乐值是多少？
\(m\)是\(10^9\)的范围；\(n\)是\(10^5\)的范围
Sol
进行\(2*n\)次操作的时候，火锅一定是空的
那就直接模拟\(+\)循环部分直接乘\(+\)特判剩余部分即可
M True Story
题目大意
\(n\)个人在离登机口\(x_0\)的地方，登机口将在\(p_0\)的时候关闭。
但是，有\(m\)次延误通知
第\(i\)次通知在\(t_i\)时公布，将关闭登机口的时间改为\(p_i\)，数据保证\(t_i>t_{i-1}\;;\;p_i>p_{i-1}\)
第\(i\)个人有一个速度\(s_i\)，当他估计自己赶不上飞机时他就会停在原地停止思考。反之则会行动去赶飞机
求最终有多少人能赶上飞机
Sol
一旦一个人开始行动，他一定能到达终点。
所以每次将关闭时间和通知时间求差取最大值即可。
然后比较一下加个统计就完事了。
此时\(zyw\)在吃他的早餐三明治，票池在吃他的蒜蓉面包，我直接处于两面包夹芝士。
L Spicy Restaurant
题目大意
给定一个有\(n\)个点\(m\)条边的无向图，每个点有一个点权\(w_i\)，现在有\(q\)次询问，对于每次询问给定两个数\(p_i\)和\(a_i\)。
对于第\(i\)次询问，求出以\(p_i\)为源点，满足\(w_k≤a_i\)的所有点中的最短路长度。
\(1≤n,m≤10^5\ ,\ 1≤q≤5×10^5\)
\(1≤w_i,p_i,a_i≤100\)
Sol
前面水题水傻了，望着题干发神发了半天，此时票池在刚\(E\)题，\(zyw\)也在发神。
想了很多\(O(n^2)\)级别的算法，然而肯定都不行。
然后跑到窗子旁边清新空气下想了一会儿，想出来了。
因为\(w_i\)的值很小，所以枚举\(w\)的值搜索。
对于每次枚举先遍历所有的点，如果\(w_i≤w\)，那么就将这个点加入队列，然后\(BFS\)即可。总时间复杂度\(O(w*(n+m))\)
这个时候午餐送过来了，双神又开始吃午餐，持续两面包夹芝士。
午餐质量挺高的，有从没见过的两块肉的桃李三明治、牛奶和水果，针不戳。
J Ants
题目大意
一根长为\(l_0=10^9+1\)的木头上有\(n\)只蚂蚁，对于每只蚂蚁给定\(a_i,d_i\)，分别表示这只蚂蚁的初始位置和初始方向（\(d_i=0\)为左，\(d_i=1\)为右）。
木头的两端各有一块挡板，挡板有耐久度\(l,r\)，表示左板蚂蚁撞\(l\)次会坏掉，右板蚂蚁撞\(r\)次会坏掉。
蚂蚁在撞到挡板或其他蚂蚁时都会调头，注意把挡板撞坏的那只蚂蚁也会调头。如果蚂蚁走到了已经被撞坏的挡板时，它就会离开木头。
每只蚂蚁的速度都是\(1\)，求多久以后所有蚂蚁全部离开木头。
Sol
可以先看一下独木桥。
两只蚂蚁是完全相同的，所以相撞以后调头可以视为没有调头。
那么在经过\(2l_0\)的时间以后所有蚂蚁和初始状态一样，与\(B\)题相似，先暴力模拟一遍然后维护此期间挡板每次被撞的时间。
有一个重要的性质是当一块挡板被撞破，至多再过\(2l_0\)所有蚂蚁就会全部离开（撞坏那只蚂蚁跑完整根木头）
如果撞坏挡板的蚂蚁跑到另一端时挡板也坏了，那么它会直接掉下去。此时时长只需要加上\(l_0\)。
分别处理左右挡板被撞坏的时间\(t_l,t_r\)，若\(abs(t_l-t_r)≤l_0\)，那么\(ans=max(t_l,t_r)+l_0\)。否则\(ans=min(t_l,t_r)+2l_0\)（可以模拟一下帮助理解）。
于是这道题就\(O(n)\)处理完了，事实上如果用二分答案就会\(TLE\)，出题人评讲时专门有提到。出题人的标程怎么这么复杂，我直接暴踩好吧