一些杂题也放到这里好了
其实是因为可以不贴代码只口胡
CF#185C 给出n个a[i],b[i]<=10^18 ，再给出1个c[1]<=10^4.接下来有三种操作：
1）加入一个c[i].<=10^18 保证该类操作<=20个
2）给b[x]-=y
3）询问最大的b[i],使得a[i]可以表示为sigma（v[i]*c[i]) v[i]为非负整数
题解：
其实根本性的问题就是判断某个a[i]能否被表示出来，知道这个以后其他操作用堆随便搞一搞就可以了。
我们发现这像一个判定性背包问题。但有一个特殊的性质就是保证有一个c[1]<=10^4而其他的c[i]可能都很大
不妨记h=c[1]
所以我们 可以考虑 模h意义下。如果能到达某个a[i]%h,那么加减h就可以得到a[i]。
所以我们 构图： 对于0<=i<h，对每个c[i]，连边(i,(i+c[i]))%h,c[i])之后求0到每个点的最短路。
对于一个 点i，如果a[i]>=d[a[i]%h]，那么说明a[i]是可以到达的。
这样就可以过了。
CF#196E 给出a[1……n],b[1……m]并且m<=n。求出满足下列的j的个数:
1）取c[1……m]=a[j+1……j+m]
2）若c[k]+b[p]>=H,连边（k，p）
3）c与b有完备匹配。
题解：
判定有没有完备匹配当然不能匈牙利啦！
有hall定理：
在左部中任意取k个点，导出子图中有>=k个右部点。
对于此题 来说，只要 我们把左部的点排序，只要每个前缀满足条件即可。（易得）
不妨认为最大的为a[i],那么他能匹配的b部节点有w[i]个，那么w[i]就是前缀i的导出子图的右部节点的个数。
只要 判断这个w[i]和i的 关系即可。
当然 这个i是指 在取出的c中从小到大排完序后的第i个。
现在我们要多次做：需要查询rank，区间修改，查询全局最小值，插入，删除。
spaly大法好。splay。。。其实写起来还是很蛋疼的
后来发现权值线段树比较好写。
Orz！先离散化就ok了！！！（注意相同的权值要有不同的rank）
2520: [Shoi2010]扫雷机器人
给出n个地雷，有参数（pi，di）。一个地雷引爆后可以使位置处于[pi-di,pi+di]的地雷引爆。
求最少需要引爆多少颗地雷，最多需要引爆多少颗地雷。
n<=100W
题解：考虑如果i能引爆j，那么连边（i，j）。那么在这张有向图上缩点。显然每个强连通分量只要引爆一个就好了。所以最少为入度为0的强连通分量个数，最多为强连通分量个数。
这样是n^2的。考虑到每次都是向一段区间里的点连边，所以我们可以类似与A+B problem里的方法，用线段树优化连边。这样就ok了。
由于多了一些辅助边，所以要把没用的强连通分量去掉。（其实只要线段树用动态开点就可以了，其他就不用特判了。）
一看bzoj 妈呀上次提交居然是前年的。赶紧写上去A掉，结果被卡空间。。。
本地ans是对的
2883GSS2加强版
3754最小方差树 暴力枚举ave，然后mst一下，肯定能得到最优解。比起今天的某题弱多了。。。
评论 (0)
