本周无团队训练

没有专题

没有比赛

没有专题

没有比赛

CF 1268E Happy Cactus tag: 仙人掌 cactus

题意

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

做法

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

conment：sad cactus

abc176f brave chain

题意：长$3n(n<2000)$的数列$a,1\leq a_i \leq n$，每次操作可以从最左选5个任意排序并选出3个除去，若3个数相同得一分，直到最后剩下3个数。若他们也都相同，得一分。求可能的最大得分。

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)$

comment:本周做的比较有意思的题