博客
归档
友链
关于
博客
归档
友链
关于
BZOJ 3133 [Baltic2013]ballmachine
传送门 注意到题目条件如果同时有多个点可以走,那么会选择编号最小的节点所在路径的方向。 不妨考虑对树的节点进行一些安排,使得我们按照dfsdfsdfs顺序找到的第一个点就是球落到的点。 不要考虑编号最小的节点在的方向,而是考虑从一个点下落的时候,他会选择哪一条边,使得这条路径可以到达编号最小的点。 没错,假设现在的节点是uuu,它的子节点为vvv,它选择的路径就是子树最小值最小的vvv 于是...
2019-09-15
阅读全文
LOJ 6435.「PKUSC2018」星际穿越
传送门 为了方便,定义a[i]=g[i]a[i]=g[i]a[i]=g[i]。 首先做一次差分,将∑y=lrdist(y,x)\sum _{y=l} ^r dist(y,x)∑y=lrdist(y,x)变成∑y=lxdist(y,x)−∑y=r+1xdist(y,x)\sum _{y=l}^x dist(y,x) - \sum _{y=r+1}^x dist(y,x)∑y=lxdist(...
2019-09-14
阅读全文
P2048 [NOI2010]超级钢琴
传送门 强烈谴责出题者,题面都花了好几分钟读。 题意: 给你Ai\\{ A_i\\}Ai,让你从集合S={x∣x=∑k=ijA[k],j−i+1∈[L,R]}S=\{x|x= \sum _{k=i} ^{j} A[k] , j-i+1 \in[L,R] \}S={x∣x=∑k=ijA[k],j−i+1∈[L,R]}选出kkk个数,使他们的和尽可能大。 首先考虑一件事,如何表示[i,j]...
2019-09-13
阅读全文
P3295 [SCOI2016]萌萌哒
传送门 首先考虑暴力的做法,不要把注意力放在字串上面,考虑Sl1Sl1+1Sl1+2⋯Sr1==Sl2Sl2+1Sl2+2⋯Sr2S_{l_1}S_{l_1+1}S_{l_1+2} \cdots S_{r_1} == S_{l_2}S_{l_2+1}S_{l_2+2} \cdots S_{r_2}Sl1Sl1+1Sl1+2⋯Sr1==Sl2Sl2+1Sl2+2⋯S...
2019-09-13
阅读全文
P5075 [JSOI2012]分零食
ProProPro 你可以把一个数mmm分成不超过nnn个数aia_iai,每一种方案对答案的贡献是∏f(ai)\prod f(a_i)∏f(ai),求最后的贡献值。 SolSolSol 很容易列出O(nm2)O(nm^2)O(nm2)的dpdpdp方程 dp[i][y]=∑dp[i−1][y−x]+f[x]dp[i][y]=\sum dp[i-1][y-x]+f[x]dp[i][y...
2019-08-29
阅读全文