二轮前水题计划
二轮前水题记
4.26
BZOJ4145: [AMPPZ2014]The Prices
f[sta][i]表示买完sta中集合中的物品，当前在i号城市的最小代价
转移的时候枚举一下最后买的物品以及从哪儿买
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。前缀和优化一下
复杂度O(n2^mm)
cf 1129 E. Legendary Tree
每次可以给定两个不相交且非空的点集以及一个常数({S}, {T}, p)，系统会返回(u∈S, v∈T)且(u, v)经过p的点的对数。
需要在11111次操作后还原出树的形态
n <= 500
首先转化为有根树，假设1是根。根据题目描述我们实际上得到了几个操作
1.询问点集S中有多少在p的子树内 - ({S}, {1}, p)即可
2.询问某个点p的子树大小 - {{2, 3, 4, 5}, {1}, p}
接下来考虑怎么还原出一棵树，显然我们只要维护出父子关系就行了
首先询问出所有点的siz，从小到大排序，那么此时每个点的孩子一定在它左边。接下来动态的从做往右扫，实时维护一下没有找到父亲的所有节点。
然后直接在点集中二分就行了。
UOJ #311. 【UNR #2】积劳成疾
每个长度为k的区间都是独立的，所以我们直接对着最大值dp
f[i][j]表示长度为i的序列，最大值为<=j时 的所有答案，也就是对整体进行dp
转移的时候只需要考虑第一个j在哪儿，其余的可以通过f[i][j - 1]转移
icpc 2018 焦作 I
给出数轴上\(n\)个点，要求选出\(k\)个点，最大化两两的距离，对于所有的\(k=1, 2, 3, \dots n\)都要输出答案
有点小神仙，推出来感觉还是很有成就感的qwq
手玩一下不难得到最优策略：
偶数往两边放，同时维护任意对称点之间的距离
奇数往没放过的点放，往哪里放的贡献都是一样的，是上一次偶数放的两个点之间的距离
CometOJ#2 C
枚举独立集的大小是多少。那么最终答案是\(\sum_{i=1}^n C_{n}^i * (\frac{x}{y})^{\frac{i(i-1)}{2}}\)
更多精彩
