冰
注意到原问题等价于{1,3,7,15,31,...}的无限背包 暴力跑背包即可
证明:
令$a_1=v_1,a_2=v_2-2v_1,a_3=v_3-2v_2,...,a_m=v_m-2v_{m-1}$
带入得 $(2^m-1)a_1+...+3a_{m-1}+a_m=n$
其中 $a_1\ge 1$ $a_2,a_3,...,a_m\ge 0$
所以是一个{1,3,7,15,31,...}的无限背包
时间复杂度O(nlogn)
光
对时间建线段树 套线性基
对于每个光源 把它所有存在的时间放到线段树上 注意一直开到最后的光源也要加进去
这样一共是nlogn块存在时间
然后按dfs序遍历线段树来计算答案
进入一个节点的时候 复制当前的线性基 然后用节点中的光源更新线性基
如果到了底层就计算该节点的所有询问
退出一个节点的时候 用备份的线性基恢复原来的线性基
时间复杂度O(nlog^2n)
还有一个O(nlogn)的更优做法
维护一个动态线性基 优先程度为此数的删除时间
删除时间越靠后 优先级越高
删除的时候直接把那一位变成0即可
为了更清楚的理解这个O(nlogn)做法 你可以看这份代码 http://acm.nflsoj.com/submission/5980
影
B和C的贡献是确定的
用费用流计算A的贡献
对每个(i,j) 建一个点 连到t一个流量1费用0的边
如果f(i,j)=1 j向(i,j) 连到一个流量1费用0的边
如果f(i,j)=-1 i向(i,j) 连到一个流量1费用0的边
如果f(i,j)=0 i j各向(i,j) 连到一个流量1费用0的边
s向1-n每个点连n条边 流量都是1 费用都是{A,3A,5A,7A,...}
这样 任何一对(i,j) i和j中恰好一个的出现次数+1
而对i来说 出现k次费用刚好是Ak^2
时间复杂度O(费用流)