A
(;)
给定(n)个字符串(a_1,a_2,cdots,a_n)和(b)，(q)次询问
每次询问给定(i_1,i_2,...,i_k)和(x,y) (i_1<i_2<cdots < i_k)
求出(a_{i_1}+a_{i_2}+cdots+a_{i_k}和b[x...y])的最长公共子序列
(nleq 10, |b|leq 10^3, qleq 10^6)
20s,2048MB
观察到(q)很大，说明我们不大可能对于每组询问再在线的去处理
可能是预处理一些东西，然后对于每组询问快速的得到答案
Step 1
(;)
不妨先去处理(v_{i,x,y})表示(a_i)与(b[x..y])的最长公共子序列
大概就是枚举一下(x)，然后在求一下(a_i)和(b[x;to;n])就可以了
时间复杂度：(O(n imes |b|^2 imes |a|))
上限是(10^9)，没有什么问题
(;)
Step 2
(;)
发现(n)很小，所以最多有1024种选法
设(f_{S,x,y})表示选了(S)这个状态的字符串集，匹配([x...y])的最优答案
但你会发现一件事情，这样会导致空间达到(10^9)，不行。
考虑优化空间。
既然全部存不下来，我们不妨去一半一半的存，所谓的折半搜索
在查询的时候，我们就只需枚举一下断点取最大值就可以了
怎么求(f)?
在(x,S)和最后一个字符串固定的情况下，现在相当于我们是(y)一直向右移动，现在想要找到一个断点使得答案更优
若直接暴力枚举转移，时间复杂度必然会多出一个(|b|^3)，还要乘上一堆东西，不行。
Step 3 (决策单调性)
(;)
考虑最优决策有什么性质，在(y)向右滑动的过程中，我们发现决策点也一定是单调不降的
设(ch_{i,j})表示([i...j])的最优决策在哪里，即有：(ch_{i,j+1}geq ch_{i,j})
这个真的需要非常感性的理解
我口胡一波：若加上(j+1)后，对决策点有影响，我们肯定是(a_i)的某个位置和(j+1)，且这个位置应该在原先匹配的几对点的最后面
若刨去这个点，单看前面，那么决策点就一定不会往左挪，但有可能往后挪，使得让左边更宽敞，且右边因为腾出去了一个位置，可能就会导致最左边的那个点向右移
(;)
然后就可以用决策单调性把(O(|b|^3))优化成(O(|b|^2 log|b|))
(;)
Code
http://noi.ac/submission/131764
B
(;)
现在有(n)个人，其中一些人可以进行搏斗，而搏斗关系构成了一张有向无环图，一条边((u,v,w))表示如果(v)打败了(u)，可以获得(w)的收益。
每个人有一个(a_i)，表示初始的经济是多少，且如果他这是第(x+1)次获胜，之前已获胜了(x)次，他会获得(n-x)的收益
设(X)为所有活下来的人的总收益，(Y)为一次都没赢过的人的数量，现在要最大化(frac{X^k}{Y},(kin {1,2}))
(nleq 150,;mleq 500,; a_ileq 10000, ;wleq 1000)
(;)
我们注意到一个人能干掉很多个人，但不能被很多人干掉。
所以这就出现了一个类似二分图匹配的东西（但其实不是二分图匹配）
考虑用网络流来做
(;)
Step 1 建图
(;)
将每个点拆成两个点(x,x')
因为一个人最多会被干掉一次，所以从源点(S)向(x)连一条容量为(1)，费用为(0)的边
考虑搏斗关系，显然会从(u)向(v')连一条容量为(1)，费用为(w)
然后考虑一个点胜利之后的收益，所以从(x')向汇点连容量为全为(1)，但费用是(n, n-1,n-2....)的边
然后我们直接跑一个最大费用流即可
(;)
Step 2 处理Y
(;)
我们发现这个(Y)非常的讨厌，比较难去维护它
有一种思路是：我们就去枚举(n-y)，即至少赢了一场的人的数量。
即：我们从(x')向伪汇点(T')连一条容量为1，费用为(INF+n)的边，然后从(x')向汇点(T)连(n-1,n-2...)的边，然后从(T')向(T)连一条容量为(y)的边
这样建有什么好处？
因为我们建了费用为正无穷的边，所以我们显然会贪心的把这些边给流满，也就说只要我们存在1种方案使得至少有(n-y)个人赢，我们的流一定会满足这种方案
而且在满足有(n-y)个人赢的情况下，因为跑的是最大流，我们显然会使其余的收益尽可能的大。
这样就满足了勒令(y)个人输，且求出在这种情况下最优收益是多少
Code
http://noi.ac/submission/131845
C
(;)
给定一个(1,n)的排列，设其最长上升子序列长度为(m)
每一次询问给出(k)
选出(i_1,i_2,cdots,i_m)，最大化(sum_{j=2}^m ln(a_{i_j}-a_{i_{j-1}}+k))
找特殊性质
(;)
设(f_i)表示以(i)为结尾的最长上升子序列的长度
发现，所有(f_i=x)的点，随着下标增大，(a_i)是递减的。
由于(x)层在最终的dp中一定是由第(x-1)层转移而来的
一种朴素想法就是暴力枚举转移，复杂度(O(n^2))
(;)
又是决策单调性
为什么这玩意的转移还是满足决策单调性的呢?
假如说对于(f_i=f_j=x,(i<j)),(i)的最优决策点是(k)，(j)的最优决策点(l)小于(k)
那么即可得到:(f_l+ln(a_j-a_l+k)geq f_k+ln(a_j-a_k+k))
但因为我们知道(f_l+ln(a_i-a_l+k)leq f_k+ln(a_i-a_k+k))
由于(ln)函数随着(x)增大增长的越来越慢，而两边(ln)里面相当于同时加上(a_j-a_i)
而又因为(a_l>a_k)，所以势必左边的增量会更少，那么出现矛盾了。
所以我们就可以用决策单调性解决这个问题
(;)