「清华集训2016」汽水-二分+点分治

发布于 8 天前

Description 给定一棵树,有边权。 找到一条路径,使得经过的平均边权与$k$最接近。 $n \leq 50000,5s$ Solution 二分答案。设当前二分值为$p$,一条路径满足...


「CTSC2008」图腾-树状数组

发布于 10 天前

Description 给定一个$1~n$的排列,至于求什么看下面。 $n \leq 200000$ Solution $$f[1324]-f[1243]-f[1432]&=(f[1x2x]-f[1423])+(f[12xx]-f[1234])+(...


「nowcoder 271D」风斩冰华-DP+贪心

发布于 11 天前

Description 咕咕咕。 Solution 设$f_{i,0,1,2}$分别表示以$u$为根的子树中$u$没有删除,在其父亲之前删除,再其父亲之后删除的答案。 $f_{u,0}$很好求。 $$f_{...


「nowcoder 271C」左方之地-概率期望

发布于 11 天前

Description 左方之地是全宇宙最帅的男人,由于有人嫉妒他的帅气,他决定出一道题考一考这些嫉妒他帅气的人。 左方之地现在手上有$n$件不同的灵装,第$i$件灵...


「Codechef」STREDUC-DP

发布于 2018-10-25

Description 给定一个字符串 $s$ 和一个字符串集合,每次操作是在$s$中找到一个在字符串集合出现过的子串,然后删去这个子串。剩下的串会拼在一起。 求删去后...


「Codechef」PRUNING-树形DP

发布于 2018-10-25

Description 给定一棵树,要求砍去边权总和最小的边,使得这分割出的每棵树满足: 在这棵树能找到一个点,使得其他点到它的距离 $\leq d$。 $n \leq 100, d \...


「ZJOI2010」贪吃的老鼠-二分+最大流

发布于 2018-10-20

Description 有 $m$ 个老鼠,$m$块奶酪,第$i$块奶酪耐久度为$p_i$,要求在时间$[l_i,r_i]$内吃完。第$j$个老鼠每秒可以吃$s_j$蛋糕。要求保证 在任一时刻,...