[待完善] BZOJ 2330~2335——SCOI 2011
BZOJ 屯题计划 第二波

BZOJ 屯题计划 #1

RXDoi posted @ 2015年4月05日 21:09 in BZOJ , 363 阅读

[4.5] 四月到了,我还是这么弱……还是得多刷题。感觉开几场屯题会比较爽?期望两周一场吧。

[4.9] 半完结撒花~

[4.14] 完结撒花~感觉好累,晚上CF也不想打了……明天把题目交一下。

[4.15] 居然只完成了48道……两个WA一个CE……有点伤心……算了下次再战!

Counter:50
 
 

4.14:

2127:happiness:最小割。连边比较巧妙。S表示文,T表示理,单独文/理贡献正常连,两个人都选文的话得不到同选理的贡献,因此两个人向T各连(同选理)/2,另一边同理。当两个人不同科的时候也不会得到同文/同理贡献,因此再补上同文同理各一半。注意要连双向边,因为一条路径会被割掉。把边权全部*2最后/2。

2982:combination:Lucas定理……[刷水]

2962:序列操作:有点神的题。注意到c<=20,那么线段树每个节点存0..20的答案。这个东西可以区间合并。f[c]=∑Lsn.f[i]*Rsn.f[c-i]。区间取反则把奇数答案取反。至于区间加,比如原来某一项是abc,修改后变成(a+T)*(b+T)*(c+T)。暴力展开推一推,发现乘的系数是(n个数选k个数,其中i个固定的方案数)。然后随意维护下即可。调了一中午是因为算组合数的时候我直接循环到20而不是min(i,20)……结果前一维爆负溢出溢到了奇怪的地方……感觉是今天做的最有价值的题目。

2440:[中山市选2011] 完全平方数。二分答案,变成统计[1,a]有多少个无平方因子数。考虑容斥。设f(x)=a/x,即x的倍数个数,那么Ans=f(1)-f(2^2)-f(3^2)-f(5^2)……+f((2*3)^2)+f((2*5)^2)+f((3*5)^2)……-f((2*3*5)^2)……发现系数就是mu[i]。这道题手贱用大号交掉了……

3813:奇数国:两棵线段树分别维护区间积以及区间内每个质因子是否出现过。用sqrt(n)的那种筛phi法做就行了。

1996:[HNOI2010] 合唱队:区间DP。[刷水]

3907;网格:网上的题解大部分是错的……先去百度 卡特兰数的证明,看完后来看这道题,不同之处就在于这道题是在x=y线上也合法。把网格左边延伸一列,作出直线y=x+1,然后发现每一种合法的原图上的解都对应了新图上的 不能碰到线 的解。就好了。我抄了个python上去。

3329:xorequ:其实好像不是很难,做的时候被吓住了。有x xor 2x=3x && x+2x=3x。观察两个数a,b,a xor b=a+b,当且仅当它们二进制某位都是1的时候不合法,因为这一位加起来会进位,高一位就跪掉了……那么要求的就是x and (x<<1)=0的数个数,即没有相邻的1。设f(n)为n位,最高位为0的方案数,g(n)为最高位为1。f(n+1)=f(n)+g(n),g(n+1)=f(n)。然后Task1数位DP,Task2矩乘就行了。要注意搞搞0的情况。Task1里最后-1,Task2里最后-1再加上刚好2^n的情况。


4.13:

2741:[Fotile模拟赛] L:分块,搞出sqrt(n)个“关键点”,把这些点到后面所有点的答案都先求出来。询问的时候只要再询问零散部分的贡献。函数式Trie随便搞搞。分块的边界细节搞了半天……另外此题复杂度更优的离线解法我不会……咨询孟爷,他表示也不甚清楚……

3931:[CQOI2015] 网络吞吐量:跑出最短路图,拆点最大流。

3930:[CQOI2015] 选数:设f[n]为选出数gcd=n的方案数,F[n]为n|gcd的方案数。那么显然有f[n]=F[n]-∑f[i*n](i>=2)。然后又注意到F[n]只要选出的每个数都是n的倍数就行了,就是(R/n-(L-1)/n)^N。由于我们只要求f[K],可以只做所有K的倍数的f和F。然而这样最坏复杂度还是10^9的。我们需要利用题目中R-L<=10^5这个信息。当n>10^5的时候,L..R之间最多只有1个n的倍数,即f[n]最多为1,选出所有数都相同。那么我们可以修改状态,f[n]表示选出gcd=n,且选出的数不全部相同的方案数。F[n]同理。求F[n]的时候减掉(R/n-(L-1)/n),最后加上所有数都=K的方案数即可。

3932:[CQOI2015] 任务查询系统:把每个事件拆成In、Out,构出函数式线段树,然后走一遍就可以了。

3933:[CQOI2015] 多项式:把公式化开来,得到一坨东西,然后高精度暴算。

2822:[AHOI2012] 树屋阶梯:卡特兰数。

3544:[ONTAK2010] Creative Accounting:贪心,维护模域下前缀和后,对于某个前缀和,应该找它模域下比它大的最小值。set搞搞。


4.12:

3530:[SDOI2014] 数数:AC自动机+数位DP,处理出从某个点开始走k步都是合法的方案数。然后数位DP。

1807:[IOI2007] 彼此能听得见的动物对数:比较好的题。标程的思路很具有启发性可惜空间开不下。一维直接排个序维护一个队列即可。二维把点搞成(x+y,x-y),两个点的曼哈顿距离就是max(|x1-x2|,|y1-y2|)。一维排序队列维护,一维BIT维护即可。然后三维,官方题解给的做法是:把每个点搞成四维:(x+y+z,x+y-z,x-y+z,-x+y+z),然后两个点的曼哈顿距离就是每一维距离的最大值。然后一维排序队列维护,剩下三维用3D BIT维护。我很开心地写了树套树套树,发现空间怎么开都开不下……最后放弃治疗去问灿爷。只要把(y,z)按照二维的方式改下坐标,暴力枚举x,用二维前缀和查询就行了。复杂度O(m^3+nm)。

3246:[IOI2013] Dreaming:比较好的题,xhr的题解很清楚了。设某个点的Dis()为其到树中最远点的距离,选出连边的点叫“接口”,那么1.每棵树有且仅有一个接口,2.这个接口一定是Dis()最小的点。然后比较显然的,最终的图一定是Dis()最大的那个接口拎出来,其它的Dis()都朝它连边。然后就没了。

3626:[LNOI2014] LCA:非常好的题。考虑求Deep(LCA(a,b)),可以把a到根的链上+1,求b到根的链上和。那么要求∑Deep(LCA(i,z)),可以把所有i到根链上加1后求z到根的链上和。然后比较显然的,把询问[L,R]拆成两个,按右端点排序离线做。树剖或者LCT都行。我觉得树剖两个log常数小,应该比LCT一个log快,就写了树剖,还顺手把标记永久化了,但是排在很后面……观察到范围是50000,平方后稍微超过int范围一点点,于是我机智地改成unsigned int,把树剖和线段树里的取模都去掉,快了近30%……

1129:[POI2008] Per:模拟赛现场AC超感动。把公式化一化,然后把模数拆成质数分别做,CRT合并。做的时候每推进一位就乘一个数除一个数,把和这个质数有关的项提出算幂次,其它部分直接算就行了。


4.11:

2594:[WC2006] 水管局长数据加强版:同魔法森林,离线倒着做就变成加边了。随意维护下。我没把所有边(x,y)都搞成x<y导致边的编号乱掉了233。

3613:[HEOI2014] 南园满地堆轻絮:把所有的逆序对都搞掉就行了。答案就是(最大逆序对差+1)/2。证明很简单。把一个逆序对(x,y),x-|x-y+1|/2,y+|x-y+1|/2,得到的(x,y)一定在原[y,x]中。因此不会产生新的逆序对。也就是每个逆序对都是独立的。


4.10:

白天还做了两道函数式Trie、一道分块。交掉了……

灿爷给了我一大堆水(shen)题,感觉有事情干了……

2435:[NOI2011] 道路修建:给出的已经是一棵树了……就变成直接计算了……DFS实现,但是莫名RE。交换了两句普通的话的顺序就过了。匪夷所思。

2563:阿狸和桃子的游戏:智商题。由于我们要求差值,一条边如果两个点都被同一个人选就会产生边权贡献,否则不会,所以把边权/2均摊到点权上。从大到小排序依次选即可。

2956:模积和:分配率,然后就变成余数之和了……i=j的部分减掉就行了。

2819:Nim:随意做。懒的写树剖LCT,考虑到xor运算满足区间减法,树的形态又不会改变,就维护每个点到根的xor值,修改变成子树修改。和POI大都市几乎一样。


4.9:

3669:[NOI2014] 魔法森林:把边按照a排序,做b的最小瓶颈生成树,做法是出现环就替换环上最大边。这样可以保证最大边最小。最小瓶颈生成树不一定是MST而MST一定是最小生成树(感觉好高端,第一次知道这个概念)。用LCT实现。找根的时候我居然没有Access……调了半天……

2668:[CQOI2012] 交换棋子:有点厉害的费用流。网上的题解都是互抄的……什么拆三个点,我拆两个点就行了……问题相当于把一些黑子换到目标状态的一些位置。每个格子有交换次数限制。一条交换路径上,除了起点和终点,其它点都要经过两次(入&出),所以一个点的容量是c/2。起点和终点只经过一次,所以容量是(c+cnt)/2。cnt表示它在两个状态中出现次数之和。一个点拆成In、Out,连边跑费用流就行了。可能有某个点在初始和目标状态都是黑点,没有关系,相当于不动,直接流过去1的流量,容量限制还是对的。

2657:[ZJOI2012] 旅游:把相邻的三角形之间连边,显然是不会出现环的。出现环就要求凸多边形中间有一个点。所以是一棵树,跑最长链。

2809:[APIO2012] dispatching:题目看不懂系列。要在一棵子树内选若干个点,收获是(点数)*(子树根的领导力),要求选出的点权值和不大于M,求最大收获。我们可以DFS做,把一个点所有子树信息合并,然后不停删权值最大点直到和不大于M,更新答案。每个点只会被删一次。O(n log n)。用左偏树实现。

2096:[POI2010] Pilots:当右端点递增时,对应的最优左端点是不递减的。所以可以用一个单调的指针维护左端点。求最大最小值用单调队列。

3152:[CTSC2013] 组合子逻辑:题目看不懂系列。每次可以选一段区间[L..L+k],然后把这段区间并成一个数A[L]-k。求把所有数并成一个的最小步数。注意到如果选出若干个数,它们能并掉的数的个数是一定的,不会受到位置的影响。只要把选出的数从右往左依次并过去就行了。那么就可以贪心了。从左往右做,如果用完了就从左边没用过的数里找一个最大的开始并。边界搞搞。特判1。

2333:[SCOI2011] 棘手的操作:搞了一晚上……其实可并堆虽然合并复杂度是O(log n),但是其高度是O(n)的,然而……我好像除了暴力爬树高下传标记没有更好的办法……而这样就可以过……删掉一个节点再合并回去应该跟原来的根Merge而不是和它父亲Merge……没什么好讲的……大力码就行了……


4.8:

1765&1356:[Baltic2009] Rectangle:居然是三倍经验题,直接贴以前的代码了……枚举对角线。

1706:[USACO2007Nov] 奶牛接力跑:倍增。

3032:七夕祭:横纵向都做一遍环形均分纸牌就行了。证明充分性。考虑求出来的一个解,每次从一列往旁边一列移动1的时候,这两列点的个数肯定不同。那么一定能找到某一行,满足这一行中第一列有而第二列无。

2662:[Beijing WC2012] 冻结:最短路。

2763:[JLOI2011] 飞行路线:最短路。

1087:[SCOI2005] 互不侵犯:状压DP,模仿叶队CF某题的华丽位运算,447 Byte,翻了好几页好像都是最短的。


4.7:

上午学了下CDQ分治入门,刷了3道简单题,由于有点虚再加上是权限题,就直接交掉了……

1018:[SHOI2008] 堵塞的交通:这种两行很多列的题基本就是分治或者线段树。CF上也有类似的题。线段树维护区间四个端点的连通性,合并的时候讨论下,查询的时候要先看左边上面能否从左边绕一下走到左边下面,右边同理。我调了一下午居然是因为一个分类讨论的地方A打成B了……不甘心T_T。

3439:Kpm的MC密码:把串倒序插进Trie里就变成了子树第K小。主席树。我一开始居然在想Fail树的子树第K小(貌似出题人给的标解是Fail树)……

1098:[POI2007] 办公楼:问题等价于求补图的连通块,用链表优化BFS可做到约O(n+m)。每个点只会进队一次,总共只有O(m)次是搜到一个点不进队的。

1072:[SCOI2007] 排列:状压DP。据计算应该没有暴力快?


4.6:

2751:[HAOI2012] 容易题:分配率化开式子,变成每个位置的和的积,把有限制的离散下。其它一起做。

2768:[JLOI2010] 冠军调查:裸最小割,好像有一道一模一样的题。

2756:[SCOI2012] 奇怪的游戏:设最后变成x,则x=(sum[0]-sum[1])/(cnt[0]-cnt[1]),若棋盘大小是奇数,直接解出x验证,否则二分x,网络流验证。从S向白点连边,白点向相邻黑点,黑点向T。

1458:士兵占领:直接跑的话要上下界最小流,可以逆向思维,先放满,再求最多能删多少个,S向每行连这行能删掉多少个,每列向T连,每个非障碍格(x,y)的x向y连边1。表示可以不放这格。跑最大流。

1455:罗马游戏:左偏树。

3713:[PA2014]lloczyn:这种普及组题我居然看题解……Fib数列增长奇快所以10^9以内没几个。暴力。


4.5:

3529:[SDOI2014] 数表:“一种问题的简单形式”,没a的限制的话很简单,有限制的话把询问按a排序离线做,用O(n ln n)的那种方法筛g()函数,依次加入可行的f(),BIT维护g()的前缀和即可。


 


登录 *


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