3
23
2015
0

一些杂题

一些杂题也放到这里好了  其实是因为可以不贴代码只口胡

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加强版

给你N个数,你需要支持一下两种操作。
U x y,讲第x个数修改成y;
Q x y,计算从第x个数至第y个数中不同数的和并输出。如对于一段数{1,2,3,2,7},它的值是13(1+2+3+7)。
题解:三维莫队?和糖果公园差不多就可以了。
 

 

3754最小方差树  暴力枚举ave,然后mst一下,肯定能得到最优解。比起今天的某题弱多了。。。

 

 

 

Category: 杂题 | Tags: | Read Count: 434

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com