本周无团队训练

没有专题

没有比赛

没有专题

没有比赛

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

tag: 仙人掌 cactus

题意

一棵n点m边仙人掌，每条边有1到m的互不相同的权 点u可以到达点v的条件是存在一条u到v的路径，路径上边权递增

做法

如果是树就直接按边权递减遂一合并就行，但是题中给的是仙人掌，这样可能会发生重复计数（因为在连接某条边之前，该边的两端点就可能到达同一个点） 需要按照300iq题解里提到的方法去重，具体做法是，如果端点a和b可以同时到达环上的另一个点p（可能为a和b），那么p可到达的部分就被重复计数了，要减去

conment：sad cactus

2020 TCO round 2B

题意 求1000*1000的网格中，某些点不能画线，能生成的‘s’型数量

tag：dp

思路：考虑dp i,j,k,代表 第i条线最后在第j,k点结束的数量，用前缀和优化dp

comment：本周看到的比较有意思的题