2020-2021:teams:acm_life_from_zero:8.29-9.03
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:acm_life_from_zero:8.29-9.03 [2020/09/04 18:00] lak [李元恺] |
2020-2021:teams:acm_life_from_zero:8.29-9.03 [2020/09/04 18:10] (当前版本) lak [姜维翰] |
||
|---|---|---|---|
| 行 19: | 行 19: | ||
| ===== 题目 ===== | ===== 题目 ===== | ||
| - | ====== 本周推荐 ====== | + | ====== 本周推荐 ======= |
| ===== 李元恺 ===== | ===== 李元恺 ===== | ||
| - | 2020TCO3B 500 ShortBugPaths | + | CF1299D Around the World |
| - | tag:模拟 | + | 题意 |
| + | 给你一个图，所有过1号点的简单环大小不超过3，可以任意删去与1号点相连的边，求有多少种删法使任意通过一号点的平凡环边权异或和不为0（边权小于32）.平凡环：从某个点出发，经过任意多点最终回到起始点，过程中边和点都可以重复经过，但是必须有某条边只经过了奇数次。 | ||
| - | 题意：一个N*N的网格($N \le 1e9$) ，可以从任意格子出发，每步可以从(x1,y1)移动到(x2,y2) iff $|x1-x2|+|y1-y2| \in D$(D是一个集合 其内元素小于等于10)，共走k步($k \leq 10$)，问有多少种不同路径。 | + | 思路 |
| - | + | 首先可以看出大概是以1号点为根分成若干枝，每个枝有1个或两个相邻点与1有边。每次从1出发走任意多个分支回到1，但是每个分支只能由一个简单环产生作用。到此可以确定思路为dp。考虑状态：首先可以dfs每个分支，只需考虑返祖边代表的环（任意一个简单环一定可以由若干返祖边代表的环的异或和得到）。于是可以得到每个分支所能贡献的异或和的种类（可以理解为返祖边所构成的向量空间），有两个与1相连的点的分支有2种状态，其他1种。考虑5维向量空间的子空间只有374种（一开始以为是$2^{32}$,思考了一下大概$32^4$,后来我跑了一下按照线性基状压，发现要大概3W个状态，看了题解发现如果按照向量空间种类计算只有374个不同状态），可以提前预处理转移，预处理用map的话是O($1024S^2logS$)。总复杂度O($SN+1024S^2logS$) | |
| - | 做法：可以发现一条路径在两个方向的跨度均不会超过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$) | + | |
| + | comment:来不及写题解了 推荐一个以前做过的有一定难度的题 | ||
| ===== 姜维翰 ===== | ===== 姜维翰 ===== | ||
| - | 链接：https://atcoder.jp/contests/agc047/tasks/agc047_b | + | CF 1268E Happy Cactus |
| - | agc047 b | + | tag: 仙人掌 cactus |
| - | 题意：给n个全小写的字符串，可以删除一个字符串中前两个字母中的任意一个，问这n个字符串中，有多少的字符串对，其中一个串经过任意次操作后可以变成另一个串 | + | 题意 |
| - | 标签：字典树 | + | 一棵n点m边仙人掌，每条边有1到m的互不相同的权 |
| + | 点u可以到达点v的条件是存在一条u到v的路径，路径上边权递增 | ||
| - | 题解：很显然，串S在经过多次操作后，相当于从S的前缀中选一个字母出来，与S剩下的部分拼在一起，也就是说，A想变成B，B去掉首字母之后必然是A的后缀，且B首字母在A去掉该后缀后的部分出现过 | + | 做法 |
| - | 于是先把所有串的反串建一个trie，对一个串S1来说，一边从叶子向上走一边记录出现过哪些字母，如果到达一个节点p，当前出现过的字符集是Q，就看一下在p的后面接上Q中的字符能不能到达某个串S2的末端（因为插的是反串，所以对应的是串的首字母），能的话就说明S1能变成S2 | + | 如果是树就直接按边权递减遂一合并就行，但是题中给的是仙人掌，这样可能会发生重复计数（因为在连接某条边之前，该边的两端点就可能到达同一个点） |
| + | 需要按照300iq题解里提到的方法去重，具体做法是，如果端点a和b可以同时到达环上的另一个点p（可能为a和b），那么p可到达的部分就被重复计数了，要减去 | ||
| - | 评论：我就是菜.jpg，想到做法的时候已经来不及写了 | + | conment：sad cactus |
| ===== 袁熙 ===== | ===== 袁熙 ===== | ||
| + | 2020 TCO round 2B | ||
| - | [[https://atcoder.jp/contests/abc176/tasks/abc176_f|abc176f brave chain]]\\ | ||
| - | 题意：长$3n(n<2000)$的数列$a,1\leq a_i \leq n$，每次操作可以从最左选5个任意排序并选出3个除去，若3个数相同得一分，直到最后剩下3个数。若他们也都相同，得一分。求可能的最大得分。\\ | + | 题意 求1000*1000的网格中，某些点不能画线，能生成的‘s’型数量 |
| - | tag:dp\\ | + | tag：dp |
| - | 题解：考虑dp(i,x,y)，表示进行第i次操作时，从5个数中留下了x,y 两个数后，已得分的最大值。直接dp状态数会很多，但发现在i和i+1时可能存在的x,y的状态差的不多，可以考虑滚动掉第一维。考虑对i和i+1时x,y变化进行讨论。若i+1时存在三个数相同，可以贪心地直接将这三个数删除；若$x_1,y_1$中有一个/两个数被更换为$x_2，y_2$；有一个数被更换时，$dp_{i+1}(x_1,y_2)$只需要从$dp_i(y_2,*)$更新，两个数都被更换时，仅更新$dp(x_2,y_2)$的最大值。这样每轮处理的状态数是$O(n)$的，复杂度$O(n^2)$\\ | + | 思路：考虑dp i,j,k,代表 第i条线最后在第j,k点结束的数量，用前缀和优化dp |
| - | comment:本周做的比较有意思的题 | + | comment：本周看到的比较有意思的题 |
2020-2021/teams/acm_life_from_zero/8.29-9.03.1599213602.txt.gz · 最后更改: 2020/09/04 18:00 由 lak
