[BZOJ1566]NOI2009管道取珠

Solution

状态$F[i_1,j_1,i_2,j_2]$可以表示为取珠方法$X$状态为$(i_1,j_1)$,取珠方法$Y$状态为$(i_2,j_2)$,$X,Y$的输出序列相同的有序对$(X,Y)$的数量。设$U[i]$为上管道第$i$个珠子,$L[i]$为下管道第$j$个珠子。则状态$F[i_1,j_1,i_2,j_2]$可以更新的状态为:
$$\mathrm { F } \left[ \mathrm { i } _ { 1 } , \mathrm { j } _ { 1 } , \mathrm { i } _ { 2 } , \mathrm { j } _ { 2 } \right] \rightarrow \left\{ \begin{array} { l } { \mathrm { F } \left[ \mathrm { i } _ { 1 } + 1 , \mathrm { j } _ { 1 } , \mathrm { i } _ { 2 } + 1 , \mathrm { j } _ { 2 } \right] \left| \mathrm { U } \left[ \mathrm { i } _ { 1 } + 1 \right] = \mathrm { U } \left[ \mathrm { i } _ { 2 } + 1 \right] \right. } \\ { \mathrm { F } \left[ \mathrm { i } _ { 1 } + 1 , \mathrm { j } _ { 2 } , \mathrm { i } _ { 2 } , \mathrm { j } _ { 2 } + 1 \right] \left| \mathrm { U } \left[ \mathrm { i } _ { 1 } + 1 \right] = \mathrm { L } \left[ \mathrm { j } _ { 2 } + 1 \right] \right. } \\ { \mathrm { F } \left[ \mathrm { i } _ { 1 } , \mathrm { j } _ { 1 } + 1 , \mathrm { i } _ { 2 } + 1 , \mathrm { j } _ { 2 } \right] \left| \mathrm { L } \left[ \mathrm { j } _ { 1 } + 1 \right] = \mathrm { U } \left[ \mathrm { i } _ { 2 } + 1 \right] \right. } \\ { \mathrm { F } \left[ \mathrm { i } _ { 1 } , \mathrm { j } _ { 1 } + 1 , \mathrm { i } _ { 2 } , \mathrm { j } _ { 2 } + 1 \right] \left| \mathrm { L } \left[ \mathrm { j } _ { 1 } + 1 \right] = \mathrm { L } \left[ \mathrm { j } _ { 2 } + 1 \right] \right. } \end{array} \right.$$
由于$X,Y$应当同步,所以当$i_1,j_1,i_2$都确定以后$j_2$可以被表示为$i_1 + j_1 – i_2$,于是状态表示可以减少一维。




0

「BZOJ1911」[Apio2010] 特别行动队 – 斜率优化

dp方程:\(f[i]=max(f[j]+a*(sum[i]-sum[j])^2+b*(sum[i]-sum[j])+c)\)

如果\(j>k\)且\(j\)比\(k\)更优

\(f[j]-f[k]+a*sum[j]^2-a*sum[k]^2+b*(sum[k]-sum[j])>2*a*(sum[j]-sum[k])*sum[i]\)

所以拿一个单调队列维护斜率

话说BZOJ的老爷机老爷一点也就算了,还tm这么不稳定,我开了O2之后跑的更慢了,玄学 继续阅读 「BZOJ1911」[Apio2010] 特别行动队 – 斜率优化

5+

1030总结

T1

这一题太水了,然而还是写错了 TwT 以后要认真读题

T2

答案是

\[ \frac { \left[ \sum _ { i = 1 } ^ {  { k } } \sum _ { j = 1 } ^ {  { k } } \operatorname { dis } \left( d _ { i } , d _ { j } \right) \right] \times ( k – 1 ) ! } { k ! }\]

然后\( O(n)\)树形dp即可

T3

考虑从每个点向外出发,状压一个\(S\)表示\(4P+1 \sim 4P+3\)步走到的点。
然后bfs即可。
检验某个点是否被覆盖\(k\)次,如果是则符合题意。
\(O(k(n+m))\),实际上还要带个常数\(16\)

0

1031总结

T1

考虑概率=合法方案数/所有方案数
所有方案数\(n^n\)
合法方案数:\(f_n = f_{n-1} + (n-1) f_{n-2}\)
打表就可以发现这个规律
然后就没了

T2

考虑分治,每次预处理mid向左向右的背包
然后每次处理跨中点的询问
\(O((NM+Q)\log N+QM)\)

T3

满分做法:
考虑错位排列的方案数定义
\[ \text{subfactorial}_n = n! \sum _{k=0}^n \frac{(-1)^k}{k!}\]
概率就是除掉n!
显然\(\displaystyle \sum _{k=0}^n \frac{(-1)^k}{k!} \) 收敛于 \( \dfrac{1}{e}\)
树链剖分维护(大到一定值(大概25左右)就不用修改了),均摊线段树

0

[JZOJ4756]幻象

Problem

这题挺短的就不概括题意了…

phantom是一位爱思考的哲♂学家。
最近phantom得到了森の妖精的真传。在他练功的时候, 每秒他的思绪中都有一定的概率浮现出奇♂异的幻象,持续\(x\)秒的幻象将产生\(x^2\) 的幻象值。
phantom练功发自真心,他想知道,在\(N\)秒内他期望产生的幻象值是多少。

继续阅读 [JZOJ4756]幻象

0

[JZOJ4765]Crisis

Problem

最近几年,一场新的金融危机爆发了,这场危机使得很多人陷入的经济问题的困境。一些X公司的员工试图通过要求加薪度过这一难关。
X公司有着严格的等级制度,除了公司所有者小H以外,其他人都有一个直属上司。没有下属的员工称为工人,其他人则称为领导者。
为了加薪,工人们都会向他们的上司提交请愿书。当然,每个领导者都希望自己的下属能够尽可能快乐的工作,所以当至少有T%的下属提交请愿书时,那么这个领导者就会向自己的上司提交请愿书。计算百分比时,领导者只会计算直属上司是他的下属,当然,他也只会提交一次请愿书。
如果最会小H收到了超过T%的请愿书,那么他将为所有工人们加薪。现在给出公司的构架和T的数值,你需要计算至少有多少工人提交请愿书才能使得小H给工人加薪。
\( 1≤N≤100000,1≤T≤100\)
继续阅读 [JZOJ4765]Crisis

0