blog原题整理

NOI复习计划

---

idea&考试策略

不管是什么考试都需要先把暴力分写满 即使发现正解就在身边（必须督促自己完成
知识点：线段树分治（填坑，天坑
线段树分治大约看了看 没写题 很虚毕竟自己菜
仔细阅读题面 不懂提问
如果发现需要spj的题目需要手写 请仔细检查spj是否写挂 有关数据边界如0 一定特判！
思考题目 如果没有做法 捡分一定写
在思考的时候 如果有一些条件没有很好的利用 就考虑跳出思维圈 所有暴力先打 验证读题
注意dp的时候不能超过n+1 尤其是多组数据的时候有可能会越界 越界到上一次算过的地方
有一些noip的题只是大略看了看就没放在这里了

动态规划

补充：
暴力dp的是否如果发现复杂度不对可以考虑我需要统计的是不是一个前缀和 可以考虑用前缀最大值或者
数据结构维护我的dp数组！！ 状压dp的时候不仅可以开一个数组表示两个状态是否可行 而且可以
直接开一个数组表示 当前状态s是否可行 避免dp时候的复杂度增加
bzoj 1026 [SCOI2009]windy数
数字太大发现无法直接做 于是发现仅仅和位数有关

bzoj1096 [ZJOI2007]仓库建设 斜率优化dp

预处理trick cost[i]从1～i需要的花费
把j+1~i全部搬到i的代价是多少 就是
cost[i]-cost[j]-sw[j]*(x[i]-x[j])
AtCoder Regular Contest 068 F - Solitaire

发现这是一个v字形 所以 取数字一定是两条递降的序列 那么dp求k-1的方案数
dp[i][j]前i个数字 最小的数字是j的方案数 然后后半部分直接 $2^{n-k-1}$即可
poj1141 Brackets Sequence

设dp[i][j]表示将区间i,j满足条件的最小代价 枚举中间补括号的地方
noi1997 积木游戏

设f[i][j][k]表示 我当前处在第i堆 然后我现在用到第j个积木 然后我现在在处理第j个积木的第k个平面
bzoj1609 [Usaco2008 Feb]Eating Together麻烦的聚餐

设f[i][num]表示我现在处于第i号位置 我选的数是num的代价是多少
bzoj1616 [Usaco2008 Mar]Cow Travelling游荡的奶牛

时间暴力转移
poj1050 To the Max
把列压在一起按照一行的做
poj1160 Post Office
一个邮局一定放在中间最合适
dp[i][k]表示前1~i个位置中我放了k个邮局的最小代价是多少 然后o(n^2*m)
URAL 1143 Electric Path

凸包性质求哈密顿路径最小 类似区间dp即可
bzoj1222 [HNOI2001]产品加工

枚举一种机器做了i时长求另一个机器花费最小时间
codeforces 833B The Bakery

考虑将式子放在线段树叶子节点 每次新增加一个数字会对Pre[i]~i-1产生贡献
codeforces 835D Palindromic characteristics

区间dp枚举长度
bailian4122 切割回文

记忆非常深dp[i]表示前i个的最小代价 暴力转移即可
poj1548 Robots

捡一个偏序集合 那么n^2 Dilworth
codeforces 913C Party Lemonade

先dp最小代价 然后按位置贪心即可
bzoj1131 [POI2008]Sta

考虑在子树转移的时候 我们转移之后会有什么影响 然后每次往哪个方向转移的时候计算即可
bzoj2201 彩色圆环

dp[i][0/1]表示前i个珠子 首尾颜色是否相同答案的期望是多少
转移的时候枚举前面一段的长度是多少 分别算一下这个长度相同的概率即可 如首尾不相同则方案有(m-2)/m的概率
如首尾相同则只有1/m的概率
bzoj3029 守卫者的挑战

内存开不下于是发现当背包容量超过200其实就不行了
bzoj4318 OSU!

把平方的期望单独提取出来计算即可
bzoj3470 Freda’s Walk

让我回想起了 期望倒着算的这句名言
倒着求每个点到终点的期望边数 正着拓扑每个点从1到这里的概率 然后枚举删除每条边的针对答案重新计算即可
bzoj1296 [SCOI2009]粉刷匠

dp之后再dp 分别预处理每行我需要涂多少次我可以涂对的数量 然后因为一行只能刷一次所以再在行之间转移的时候
就设dp[i][j]表示前i行刷了j行的代价即可
poj2392 Space Elevator

完全背包的应用 多记录一些东西即可
poj1737 Connected Graph

$f[n]=\sum_{k=1}^{n-1}f[k]*f[n-k]*C_{n-2}^{k-1}*(2^{k}-1)$
bzoj3257 树的难题

dp[i][j][k]表示当前在i子树内 黑色有j个 白色有k个的代价 然后枚举每种状态尝试背包转移即可
bzoj2287 【POJ Challenge】消失之物

先dp出最简单的那个东西 然后我们可以再dp一下考虑容量为x的方案实际上是由$x-v_i$这个容量不包含 i物品的东西加上i物品会增加一些方案数我们只需要把他们减去即可
bzoj3437 小P的牧场

斜率优化 同：锯木厂选址
bzoj1492 [NOI2007]货币兑换

cdq分治解决斜率不单调的dp 维护一个凸包 然后每次要找个和凸包相切的决策点来转移
bzoj3672 [Noi2014]购票

对于dp式子的化简还是不长记性…看到一些无关的项可以分类一下也许就好维护了
dp[i]=min{dp[j]+(dis[i]-dis[j])*p[i]+q[i]}
dp[i]=q[i]+dis[i]*p[i]+min{dp[j]-dis[j]*p[i]}
bzoj4518 [Sdoi2016]征途

似乎可以wqs二分 做到复杂度非常优秀 这里写的是$n^2$做法
$s^{2}=\sum\limits_{i=1}^{n}(x[i]-\bar{x})^{2}$
$s^{2}=m*\sum\limits_{i=1}^{n}x[i]^{2}-sum[i]^{2}$
bzoj1097 [POI2007]旅游景点atr

对于k个点的状态状压做 然后枚举经过所有点之后 在最后停留在某个点的最小距离再加上 这个点到终点的最小距离即可
对于最短路我们可以知道有常用套路 枚举一个点然后把两段路径拼接起来
bzoj1855&luogu2569 股票交易 单调队列优化

化简 然后发现式子有个常数项和 上一个决策点的位置有关单调队列化简
bzoj1076 [SCOI2008]奖励关

设dp[i][s]表示我1-i-1轮已经获得了s状态的宝物 那么我一直做完K轮我的期望是多少 期望倒着做 因为正着可能从无效状态转移
bzoj2073 [POI2004]PRZ

状压dp 设dp[s]表示s状态我已经搬运完了 的最小时间是多少 首先预处理time&ww数组 然后枚举子集进行转移 注意转移的时候我有可能我自己这一次就是将他们全部搬运完的那一次因为我的枚举子集的方法无法枚举到0 所以我拎出来特判写一写的
bzoj3675&UOJ104 [Apio2014]序列分割

$$\begin{aligned} f[i-1][k1]+sum[k1]*(sum[j]-sum[k1]) &< f[i-1][k2]+sum[k2]*(sum[j]-sum[k2]) \\ sum[j]*(sum[k1]-sum[k2]) &< f[i-1][k2]-f[i-1][k1]+sum[k1]^2-sum[k2]^2 \\ sum[j] &> \frac{f[i-1][k2]-f[i-1][k1]+sum[k1]^2-sum[k2]^2}{sum[k1]-sum[k2]} \end{aligned}$$
发现这个sum是具有单调性的 且或的分数和切割顺序是无关的（这一点一定要认真分析dp
bzoj3831 [Poi2014]Little Bird

维护这一个区间内的体力最小值 Notice：在维护单调队列的时候如果体力值相同记得按照高度递减来维护
bzoj4011 [HNOI2015]落忆枫音

对于DAG上的生成树来说 每个点的入度只能是1 那么我们直接统计每个非根节点的度数即可 但是用重复的怎么办 统计每个环除了环上的点 度数的乘积然后减去即可
bzoj5108 [CodePlus2017]可做题

因为位与位之间是互不影响的 做的时候就递推直接搞就可以 但是注意 如果前一位是空的我随意添加数字来构造 注意我存在我当前位置和前一个位置只差一个的情况 这样的话我就需要特判 避免我这一位同时被我钦定为1或者0 （其实并不能算作dp 只能说是递推
luogu4187 [USACO28JAN]Stamp Painting

先用排列组合算出没有k这个限制条件的所有可能方案，即n的m次方。再算出不符合方案的情况，也就是没有一个长度至少为k的相同颜色的块减去即可。想要算出不符合的方案总数也很简单，一个简单的一维DP就行了，因为我们规定不能有长度超过k的块，所以最多只有连续k-1个格子颜色相同
bzoj1495 [NOI2006]网络收费

不确定lca的状态所以需要dfs一下lca的状态然后根据每个lca的状态背包dp 神题 看其他大佬题解吧
bzoj4027 [HEOI2015]兔子与樱花

给儿子排序然后贪心从小到大删除 似乎很有作用
bzoj4813 [Cqoi2017]小Q的棋盘

f[x][j]=max(f