NOIP 2014 要滚啦~\(≧▽≦)/~

好感人(ノ｀Д)ノ

• BZOJ 3062

膜拜了一下官方题解……第二种比较好理解。因为我们要把所有路径的终点都要找到一个起点与之匹配。为了方便就加一条M->0的路径。这样的最小匹配就是不带着奶牛需要走的最短路径。

贪心的策略显然是把起点[tex]s_i[/tex]和终点[tex]e_i[/tex]都从小到大排序，然后取[tex]\sum{|s_i-e_i|}[/tex]。

如果匹配出来的是两条路径，显然我们可以调整走法合并成一条路径。所以这样一定是答案。

• BZOJ 3302 & 2103 & 2447

考虑到如果中心从根x往下移到y的话，减小的量是sum[x]-2*sum[y]。所以对每个点找到子树里最大的sum的位置。然后O(nh)暴力一下就好了。

• BZOJ 3076

考虑到线段不相交，所以他们之间的关系是可以传递的。用叉积重载一下比较函数。然后扫描线+set即可。

• BZOJ 3049

两两岛屿之间bfs一下或者最短路处理一下距离，然后状压dp即可。

• BZOJ 3061

二分答案显然。然后[tex]2^n[/tex]暴力枚举列的划分情况，然后贪心列至少要切的刀数。

• BZOJ 1701

显然先把原序列按[tex]\frac{T_i}{P_i}[/tex]从小到大排序。

令[tex]A=\frac{\sum{T_i}}{\sum{P_i}}[/tex]，那么我们有[tex]\sum{T_i-AP_i}=0[/tex]。

然后对于每一个i，我们要求出[tex]\text{max}(T_j-AP_j)(1\leq j\leq i)[/tex]和[tex]\text{min}(T_j-AP_j)(i<j\leq n)[/tex]，如果前者比后者大，那显然交换这两个test会比老师的答案更优。

使用CDQ分治可以在[tex]O(n\text{log}^2n)[/tex]的时间内完成。

• BZOJ 1700

[tex]f[i][j][/tex]表示第一种付到第i天，第二种付到第j天的最小月数。

• BZOJ 2376

第一步是最后要加若干个零。

然后状态时[tex]f[i][j][/tex]表示用了[tex]i[/tex]次球棒，一定要打掉第[tex]j[/tex]个球的最大价值。

直接转移是[tex]O(n^2k)[/tex]的，交到BZOJ上竟然卡过了？用单调队列优化其中的一个转移可以做到[tex]O(nk)[/tex]。

• BZOJ 1737

用[tex]f[i][j][0..1][/tex]表示现在在第[tex]i[/tex]天，已经休息[tex]j[/tex]天了，01表示这天有没有休息。

然后就可以转移了。

因为是环，所以枚举一下第一天的状态即可。

• BZOJ 1989

对每条边考虑贡献。就是经过这条边的路径总数/路径总数就行了。

• CF 451E(div2)

求[tex]x_1+x_2+\cdots+x_s=n(s\leq 20,0\leq n\leq 10^{14})[/tex]的非负解个数，并且对于[tex]x_i[/tex]，有[tex]0\leq x_i \leq f_i[/tex]。

用生成函数就很好做辣，暴力乘起来。

一个比较重要的式子就是[tex]\frac{1}{(1+x)^n}=\sum_{r=0}^{\infty}\binom{n+r-1}{r}x^r[/tex]

• SRM 305 Div.1 500pt

[tex]f[i][j][k][l][/tex]表示用了第一个串的[tex][i,j)[/tex]和第二个串的[tex][k,l)[/tex]可以拼出回文串。

这样就可以通过dfs（dp?）继续更新状态。

• SRM 305 Div.1 900pt

好像容斥比较显然？然后就是求n的k次方根下取整。

用了long double本地不会挂精度可是tc上挂了。。好逗。。

只能手写二分。。每次暴力乘就好。

• SRM 512 Div.1 512pt

枚举子序列的开头是X，假设第二位是Y。

那么这个序列长的就是这样：

[tex]X,Y,X+Y,X+2Y,2X+3Y,3X+5Y,\cdots,fib_{i}X+fib_{i+1}Y[/tex]

然后枚举其中的一位是[tex]A=fib_{i}X+fib_{i+1}Y[/tex]，那么[tex]Y=\frac{A-fib_{i}X}{fib_{i+1}}[/tex]。

算出来之后判断一下有多少个数可以在这个序列中即可。

• SRM 512 Div.1 1024pt

令[tex]g[i][/tex]为长度为i的合法序列。

总共有[tex]a[i]^i[/tex]种序列使得每一位都有[tex]b[j]\leq a[j][/tex]。

减去其中不合法的。

令[tex]b[i][j][/tex]表示长度为i的序列最早在第j位有违反[tex]b[j]\leq a[j][/tex]的序列个数。

那么有[tex]j-1[/tex]个数是合法的，然后有[tex]\binom{i}{j-1}[/tex]种放置方法，剩下的不合法的数都是要大于[tex]a[j][/tex]的，

于是有[tex]b[i][j]=g[j-1]\binom{i}{i-j+1}(a[i]-a[j])^{i-j+1}[/tex]。

[tex]g[i]=a[i]^i-\sum_{j=1}^{i-1}b[i][j][/tex]

答案就是[tex]g[n][/tex]了。

• SRM 520 Div.1 500pt

比较简单？dp一下方案数就好了。

• SRM 520 Div.1 1000pt

把人分成三类。一种只cha。一种只被cha。一种两种都有。

把这个cha序列看成许多行A->B，表示A cha B。

那么显然第一种人只出现在左边，第二种人只出现在右边，第三种人两边都出现，而且出现在左边早于出现在右边。

假设三种人分别有A,B,C个人。

那么总共就有A+C行，我们要做的是把C个人放入两边，所以我们可以先统计这个方案数。

[tex]f[i][j][/tex]表示把j个C类人放进[tex]2 \times i[/tex]的方格里。

转移的时候考虑第一行第一个格子，如果没有C类的人，那[tex]f[i][j]+=f[i-1][j][/tex]

如果有C类的人，那我们可以新开一行，那么右边有本身有[tex]i-1[/tex]个空位，已经放了[tex]j-1[/tex]个位了，所以有[tex]i-j[/tex]个空位，于是[tex]f[i][j]+=(i-j) \times f[i-1][j-1][/tex]

这步计算完的答案就是[tex]f[A+C][C][/tex]。

之后计算其他的贡献。这A个人cha的对象还没确定，可以有[tex]\binom{A}{B}[/tex]种选择方法，剩下的空位都有[tex]n-1[/tex]种选择（失败的cha）。

最后乘上[tex]A!B!C![/tex]即可。

• 相关文章