Posts
jjikkollp
Cancel

dp选做1 By Oscar

1528E 题意 输入 $n$ ,求有多少无标号有向树满足下列条件: 每个点入度+出度不超过3 任意两个点要么存在公共祖先,要么存在公共后代 直径为 $n$ $1\leq n\leq 10^6$ 题解 性质:树的形态一定是先收缩至一条链再散开 如果有链部分,那么每个点度数不超过2,否则根(只有收缩部分则根看作收缩终点)度数不超过3,其余点度数不超过2 dp 求...

CF1479Div1

D 给一棵树,有点权,$q(q\le 3\times10^5)$组询问$(u,v,l,r)$,问在$(u,v)$这条链上,是否存在权值在$l,r$之间,且出现奇数次的点,输出任意一个符合要求的权值,不存在输出-1。 考场写了个俩log的,T掉了,呜呜。 给每个点权分配一个$[0,2^{64}-1]$内的随机数,这样子我们可以用一堆东西的异或判断是否存在出现奇数次的点。 每个节...

CF1481Div2

E 给一个数组,每次操作可以把一个数字移到最右边,问最少操作多少次能让数组中一样的数字都在一起,如2211333。 注意到操作顺序是任意的,我们只要决定哪些数字要移到最右边就行了。那么问题就变成了,最多留下多少个数字,他们是符合要求的。 那么我们从左到右dp,如果当前位置是某种数字的最右边,那么我们考虑将所有这种数字留下,$dp[i]=dp[l[a[i]]-1]+cnt[a[i...

一月总结

一. 光速预习了大雾和复变,考完分还可以,然后就放大假了。 贰. 放假还是咕,补了一下之前的题,自己打了一场vp,组队打了一场,题还没补。 叁. 给队里寒假训练的题单没搞好,要抓紧搞搞。 肆. 大概看了一下课设要干啥,把神秘论文看了一遍,感觉不是很难写orz。 伍. 打块瞎打打,lpm接近60了(40L:1:00.8),然后练极简之后巨难受+巨慢,强烈建议不要等打多了了再练。 陆....