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:05] lak [姜维翰] |
2020-2021:teams:acm_life_from_zero:8.29-9.03 [2020/09/04 18:10] (当前版本) lak [姜维翰] |
||
|---|---|---|---|
| 行 19: | 行 19: | ||
| ===== 题目 ===== | ===== 题目 ===== | ||
| - | ====== 本周推荐 ====== | + | ====== 本周推荐 ======= |
| + | ===== 李元恺 ===== | ||
| + | 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 | ||
| 行 38: | 行 47: | ||
| conment：sad cactus | 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.1599213904.txt.gz · 最后更改: 2020/09/04 18:05 由 lak
