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:08] lak [本周推荐] |
2020-2021:teams:acm_life_from_zero:8.29-9.03 [2020/09/04 18:10] (当前版本) lak [姜维翰] |
||
|---|---|---|---|
| 行 21: | 行 21: | ||
| ====== 本周推荐 ======= | ====== 本周推荐 ======= | ||
| ===== 李元恺 ===== | ===== 李元恺 ===== | ||
| + | CF1299D Around the World | ||
| + | |||
| + | 题意 | ||
| + | 给你一个图，所有过1号点的简单环大小不超过3，可以任意删去与1号点相连的边，求有多少种删法使任意通过一号点的平凡环边权异或和不为0（边权小于32）.平凡环：从某个点出发，经过任意多点最终回到起始点，过程中边和点都可以重复经过，但是必须有某条边只经过了奇数次。 | ||
| + | |||
| + | 思路 | ||
| + | 首先可以看出大概是以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$) | ||
| + | |||
| + | comment:来不及写题解了 推荐一个以前做过的有一定难度的题 | ||
| ===== 姜维翰 ===== | ===== 姜维翰 ===== | ||
| CF 1268E Happy Cactus | CF 1268E Happy Cactus | ||
| + | |||
| tag: 仙人掌 cactus | tag: 仙人掌 cactus | ||
2020-2021/teams/acm_life_from_zero/8.29-9.03.1599214125.txt.gz · 最后更改: 2020/09/04 18:08 由 lak
