本周无团队训练

题目： AGC047 BC

没有专题

没有比赛

没有专题

没有比赛

2020TCO3B 500 ShortBugPaths

tag:模拟

题意：一个N*N的网格($N \le 1e9$) ，可以从任意格子出发，每步可以从(x1,y1)移动到(x2,y2) iff $|x1-x2|+|y1-y2| \in D$(D是一个集合 其内元素小于等于10)，共走k步($k \leq 10$)，问有多少种不同路径。

做法：可以发现一条路径在两个方向的跨度均不会超过10k，考虑用dpijk表示第k步后在(i,j)的方案数，当N远大于k时（$N \ge 20k$），固定k，可以发现dpij按照取值规律整个N*N的表格分为9部分，四个角上边长为10*k的正方形、宽为10*k长为N-2*10*k的四个矩形和中间部分。中间部分取值全部一样，长方形中每个长为N-2*10*k的列取值相同。并且四个正方形和四个矩形取值中心对称。于是我们维护一个角上的小矩形的dp值和一个长方形的每列的取值即可。时间复杂度O($|D|^4k^3$)

如果不满足N远大于k的条件，此时$N \le 200$,此时直接暴力模拟即可，时间复杂度O($k^3*|D|^2$)

链接：https://atcoder.jp/contests/agc047/tasks/agc047_b

agc047 b

题意：给n个全小写的字符串，可以删除一个字符串中前两个字母中的任意一个，问这n个字符串中，有多少的字符串对，其中一个串经过任意次操作后可以变成另一个串

标签：字典树

题解：很显然，串S在经过多次操作后，相当于从S的前缀中选一个字母出来，与S剩下的部分拼在一起，也就是说，A想变成B，B去掉首字母之后必然是A的后缀，且B首字母在A去掉该后缀后的部分出现过

于是先把所有串的反串建一个trie，对一个串S1来说，一边从叶子向上走一边记录出现过哪些字母，如果到达一个节点p，当前出现过的字符集是Q，就看一下在p的后面接上Q中的字符能不能到达某个串S2的末端（因为插的是反串，所以对应的是串的首字母），能的话就说明S1能变成S2

评论：我就是菜.jpg，想到做法的时候已经来不及写了