7.4测试总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
--------------------------------------------------------------------------------
好难啊..QAQ
昨天我和shy说要难一点,结果今天就成这样了...
--------------------------------------------------------------------------------
T1:
题意是说一个序列划成k段,每段的代价是∑(i=l,r)1/a[i]∑(j=l,i)a[j]
随便推一下就是裸的斜率优化
好像还可以用决策单调性做:
[l,r]的mid可以O(r-l)更新一下
嗯..
--------------------------------------------------------------------------------
T2:
题意是说给你一个无向图,每条边长度是2^x[i],x[i]<=10^5,求s到t的最短路
dij即可,主要问题是判断大小和更新
用可持久化线段树
每次给一个位置加1,然后考虑进位
找到后面第一个0,中间区间赋0,后面那个0改为1
然后每个位置维护一下哈希值,比较的时候哈希二分答案即可
--------------------------------------------------------------------------------
T3:
题意是有n个发电站,每个的值要在[l[i],r[i]]之间,除此之外还有m个限制,每个形如u[i]>=v[i]+d[i],然后每个人取值x的时候价值是fi(x),求最大价值
最小割,建图如下
--------------------------------------------------------------------------------
评论 (0)
