-->

BZOJ 冬天计划

一双冷眼,一腔热血,一颗平常心!!

以后一个100题为一个小目标吧
这次主要是锻炼做难题的能力

32/100


bzoj2115: [Wc2011] Xor

这道题是做过的啊
就是每次,其实走一个环是有贡献的 ,我们不妨把这些环的路线找出来
而且每个环可以单独计算,你想一下,走去那个环里面,绕一圈然后再走回来,其实就是只取这个环的贡献
那么的话,如果你有两条路径走到同一个点的话,必然构成一个环,设这个环的异或和为x
然后如果你走的路径异或和为a 另外一条路径就是b=x^a
综上所述,你只要跑一边dfs,走出一条路径,然后把所有环的贡献做一次线性基就好了
其实环的个数不多,我们找的时候也有一个技巧:
如果一条边是dfs树上的反主边的话,就记录下这个环,其他的小环必然是这些环异或出来的结果


bzoj1270: [BeijingWc2008]雷涛的小猫

很简单就想到了O(N^3)的做法,枚举高度树和转移的树
我们不用管从哪一棵树转移过来,直接记录从转移过来的那层,整层的最大值就好了


bzoj1271: [BeiJingWc2008]秦腾与教学评估

这道题不会做我心里是很崩溃的。
我一开始以为每次保留堆里面的20w个,也就是对于每一小组用尺举法插入,复杂度就是10^8,忽略了插入一个数是log的时间复杂度
因为只有一个是奇数,所有有一个性质,前缀和是一段偶数,一段奇数
我们找到奇数的一段就可以了,奇数一段的开头就是那个数,前缀和可以通过O(N)快速计算


bzoj1272: [BeiJingWc2008]Gate Of Babylon

这道题简直就是套路题啊。经典套路
做过51nod 1667就知道是什么回事
其实就是一个
$$x_1 + x_2 + \cdots + x_n = M$$
其中有一些有上限,有一些没有上限
容斥一波把上限去掉就好了 去掉上限后最后的数假设是lst
然后就变成了

$$\sum\limits_{m=0}^{lst} \binom{m+n-1}{n-1} = \binom{lst+n}{n}$$
然后接下来就是Lucas或exp解决了


bzoj1273: [BeiJingWc2008]序列

简单的,我们对一个位有影响,取决于这个位及以后的数是什么
建一个以每个位为后缀的权值线段树就好了


bzoj1976: [BeiJing2010组队]能量魔方 Cube

简单的网络流建图,经典
首先二分图染色,然后统计总花费,减掉最小割流量,就是答案
最小割的流量就是当两个相同的时候就要流1,代表要减掉1的贡献
具体如图


bzoj1978: [BeiJing2010]取数游戏 game

太搞笑了这道题从后往前递推就好了


bzoj1977: [BeiJing2010组队]次小生成树 Tree

简单的找一条边换了就行,不能直接找最大的,还要找次大的,因为最大的可能和这条边相同,这是你就替换掉最大的就好了
这条边也不可能比最大的小,不然就不要最大的要这条边,这条边在生成树上了
倍增一下跑个ST表


bzoj2253: [2010 Beijing wc]纸箱堆叠

简单的CDQ,把中点挪一下就好了


bzoj2252: [2010Beijing wc]矩阵距离

打了个K-Dtree爽了一下


bzoj2251: [2010Beijing Wc]外星联络

打了个SAM爽了一下


bzoj2321: [BeiJing2011集训]星器

神tm结论题??
神tm势能分析??
答案就是前面的(i^2+j^2)x - 后面的(i^2+j^2)x


bzoj2322: [BeiJing2011]梦想封印

这道题算是一道好题啊 bzoj2115加强版!
首先分析这道题要我们干什么:
删边可以理解为倒着加边,加边就会新产生环,也有可能产生新的路径
答案就是:
$$ Ans = 本质不同的路径 * 2^{本质不同的环} $$
考虑本质不同的环就是放在线性基中不会被消掉的
本质不同的路径是在环的线性基消完后,剩下的结果(当然不用消路径,路径是只能用一个的)
然后讨论三种情况
如果加一条边,假设端点为a,b,他们被访问的情况分别是vis[a]和vis[b]
1.vis[a] && vis[b] 直接加一条边就成环了,那么如果这个环是本质不同的环,我们就插入线性基,而且还要一个操作
把之前的本质不同的路径也消一遍,这里我们用一个set操作一下就好了
2.vis[a] || vis[b] 就把一个联通块给合并上来,DFS未访问的联通块,如果有环像操作1一样处理就好了
3.!vis[a] && !vis[b] 这个直接加一条边挂机等以后来访问就好了


bzoj2351: [BeiJing2011]Matrix && bzoj2462: [BeiJing2011]矩阵模板

这两道题其实我用了两种做法写
第一题我看到给了20s 直接10^8不怂,其实就是维护每行的前缀和,然后再一行一行的合并
所以时间复杂度是O(NMA)的,而且我还加上了一个Hash查表和双Hash,空间是O(NM)的
然后交去第二题,发现过不了,是因为时间卡了
后来发现有种更厉害的二维Hash的方法,其实也是差不多累计前缀和,只是累计完行的再统计列的
于是写了过了第二题,但是第一题WA了,因为我第二种写法没有查表,直接用bool判断


bzoj2457: [BeiJing2011]双端队列

画图可知,这样的双向队列有几个性质:
1.一定是确定的一段的数,并且越多越好(反证法)
2.如果考虑每个数只能用一次的情况,我们从小到大填数,他们的位置肯定会先减小,再增大
如果是有相同的数的话,这个数最大的位置和最小的位置组成的区间关系也类似如此
然后把值从小到大的插进去就好了


bzoj2461: [BeiJing2011]符环

这道题一开始的dp想错了,很简单看出来是一道没有算法的题目
一开始的定义f[i][j][k][l]确定了前i个数,左半段的和为j,右半段最小值为k,然后右半段和为l
发现这样的空间是50^3 * 100 开LL会炸掉
看题解就是f[i][j][k][l]确定了前i个数,左半段’(‘未匹配数量 右半段’)’未匹配数量 和右半段 ‘(‘
其实就是优化掉我的右半段和,因为其实我们统计和是没有必要的,只要右半段的最小值等于左半段的和,而且后面没有’(‘就完事了嘛


bzoj2458: [BeiJing2011]最小三角形

beijing的都是什么题啊,好像都很喜欢乱jb搞?
反正就是大概分治一下,有一个剪枝很好用就是两边之和大于第三边,所以只要有一边就开始控范围了
分治下去先让小的更新答案,然后再让紧一点的答案去控制大的
大概就是先按x来排序,分两边做,再让y排序,然后有两种情况
1.2个点在左边,1个在右边
2.1个点在左边,2个在右边
然后其实求一下x和y分别的距离差,加上上面的剪枝,控一下随便就过了,好像很难卡?


bzoj2459: [BeiJing2011]神秘好人

很好的一道线段树题,虽然听cys说bzoj1018和这道题差不多?但是还是死磕出了这道题
首先很简单就可以想到用一个2 * 2 的矩阵来表示一个状态,认为起点的横坐标<终点的横坐标
然后起点有可能会向左走,也有情况是走到终点的右边再走到终点
所以还要记录一下起点往左,终点往右哪个拐点比较优
代码还是很好实现的


bzoj2352: [BeiJing2011]database

动态开点线段树


bzoj2553: [BeiJing2011]禁忌

这道题算是做回了,就是AC自动机上每个点转移概率,然后用矩阵乘法来转。
矩阵上预留一个位存答案,转移到每个字符串最后的时候统计一下概率,经典的套路模板题


bzoj3210: 花神的浇花集会

这道题讲道理开1s是要卡三分??
这个东西如果直观看是不一定满足单峰性了,但是推出正解就满足了
来一个曼哈顿距离变式……
$$|x1-x2| + |y1-y2| = max(|(x1+y1) - (x2+y2)|,|(x1-y1) - (x2-y2)|)$$
然后对比原式,你已经知道了x2+y2,x2-y2 然后你根据中点求得一个x1,y1,然后再把x1,y1带入到X和Y就好了


bzoj4590: [Shoi2015]自动刷题机

发现具有单调性,一个小于等于的二分求上界,大于等于二分求下界,二分的时候同时看看有无解就好了


bzoj4591: [Shoi2015]超能粒子炮·改

Lucas+数学推导
题目是要求
$$\sum\limits_{i=0}^{k} \binom{n}{i} \pmod p$$
$$=\sum\limits_{i=0}^{k} \binom{n \mod p}{i \mod p} \binom{n / p}{i / p} \pmod p$$
我们观察这个式子,对于每一个i/p的式子,它都要乘上一个i mod p的式子,而i mod p形成了循环,所以可以把i mod p的循环提出来
$$=\sum\limits_{i=0}^{p/k-1} \binom{n/p}{i} \sum\limits_{j=0}^{p-1} \binom{n\mod p}{j} + \binom{n/p}{k/p} \sum\limits_{i=0}^{k\mod p} \binom{n\mod p}{i}$$
这是我们发现,如果我们记
$$S(n,k) = \sum \limits_{i=0}^{k} C(n,i)$$
$$S(n,k)=S(n/p,k/p-1) \cdot S(n\% p,p-1) + C(n/p,k/p) \cdot S(n \%p,k \%p)$$
递归处理就好了


bzoj4592: [Shoi2015]脑洞治疗仪

复杂的线段树操作,只要支持询问最大连续区间,区间改,区间询问就好了


bzoj4593: [Shoi2015]聚变反应炉

不得不说这道是一道好题
正解的dp也是很难想到的
我们看maxc=1的Case1应该怎么做,这个我做出来了,很简单嘛,c最大等于,我画了几个图玩了一下
首先肯定是给那些c=1的点发精髓,先让他们炸没毛病
发现只要是互相有血的话,互相都是c=1,你把精髓发给谁都是一样的,因为最后都是
$$\Sigma d[i]-1$$
内在原因是因为一滴一滴的扣不存在那种爆到负血的情况,如果c>1的话可能把相邻的爆到负血
所以先把c=1的没有炸掉的放进队列,然后依次爆炸的放进队列,剩下c=0的最后再统计一下,就能拿到50分

然后Case2就去看题解了
我们设

f[i] 表示激发了i的父亲再激发i的代价
g[i] 表示激发了i再激发i的父亲的代价
t集合表示与i直接相连孩子,需要激发i的
k集合表示与i直接相连孩子,且激发自己的

然后我们发现
$$f[i]=\Sigma f[t] + \Sigma g[k] + d[i] - c[fa] - \Sigma c[k]$$
$$g[i]=\Sigma f[t] + \Sigma g[k] + d[i] - \Sigma c[k]$$
并且我们要保证
$$d[i] - c[fa] - \Sigma c[k] >= 0 $$
$$d[i] - \Sigma c[k] >=0 $$
之后就是一个背包的事了


bzoj4594: [Shoi2015]零件组装机

这道题看完之后就大概知道算是一道分治题
然而难的地方就是要找到割开成两个机器的分界点
假设这个点为p 那么0.1.2…p为1组,p+1,p+2….n-1为1组
而且他们对应的连边
那么我们先找到那些和0连边的,标记为true,代表他的前面都是连续的一段
然后如果下一个和1也连边的话,也标记为true
….
然后假设你认为的点p是分界点
必然p+p+1是true,并且最远连到p,代表p+1到p+p+1分别对应0到p
p+p+p+2是true,并且最远连到p
…..
然后如果所有的都是true,并且n也是true的话,那么就是p了
而且仅有一个p,不存在第二个p
然后删掉跨越的边,而且还有,后面的点如果存在同一个点两条跨越的边的话,肯定是不合法的(注意这里是n<=m,所以后面编号的点的块肯定大一点)
还要判断一下重边的情况,重边一定是不合法的


bzoj4595: [Shoi2015]激光发生器

超级恶心的计算几何模拟题诶,好险有硕爷爷在帮助我
首先,考虑一个向量射在一条直线上,我们要找到反射出的向量,就需要知道这个向量要顺时针旋转还是逆时针旋转
这时我们需要确定一个法线的方向

然后我们确定发现方向之前,还要确定线段的方向

就是要让有向线段逆时针转过来到点上。
如果不是的话,则交换线段的端点和改变这条线段有向向量的方向。
而有向线段逆时针旋转90度的方向就是我们需要的法线

然后,这里用到的就是叉积,求点是否在线段上,直线交点,向量旋转的基础几何知识,在这里就不再阐述了
还有就是要注意垂直射入的关系


bzoj1007: [HNOI2008]水平可见直线

这道题很久以前就做过了啊,但是可惜我现在就不是很会了
首先按照斜率k从小到大排序,维护一个栈,这个栈内的直线都互相不覆盖
如果你新加的一条覆盖了栈中的一条,必然有
$$getPos(i,s[top]) <= getpos(s[top],s[top-1])$$
上面的getpos也就是得到两直线焦点的横坐标,因为你知道直线的截距和斜率差
还有就是k相同的,b越大的覆盖小的


bzoj3190: [JLOI2013]赛车

跟上一题套路是一个样的,但是这题需要的是会有交点相同的情况,那么就不要pop掉保留就行
还有就是交点一定要在第一象限,还有直线可能重合的情况


bzoj2618: [Cqoi2006]凸多边形

看了一下论文,写了一下正版的半平面交
写起来还是很爽的嘛,写的时候要把线段给有向,一般取线段的左边为要选的区域,就当是一道模板题吧


bzoj1038: [ZJOI2008]瞭望塔

首先我们做一次半平面交,然后就会有很多交点。
那些高度最小的,肯定要不就是在输入的点往上的高度,要不就是交点的拐点处往下的高度
然后扫两边就好了


bzoj2732: [HNOI2012]射箭

首先二分答案出来,然后得到一些方程
$$Ax^2 + Bx >= y$$或者
$$Ax^2 + Bx <= y$$
然后我们知道x和y,考虑对A和B的取值,就是一个线性规划
$$\frac{y}{x} - Ax <= B$$
$$\frac{y}{x} - Ax >= B$$
然后再对这些方程求解,也就是半平面交后的区域。
而且我们还要注意范围是:
$$A<0 ,="" b="">0$$ 也就是在第二象限画个边界,然后如果最后跑出来只有一个交点,就不合法了
按照讨论区的方法卡卡精度?


待完成的题目

bzoj3207:花神的嘲讽计划Ⅰ
bzoj3208:花神的秒题计划Ⅰ
bzoj3209:花神的数论题
bzoj2594: [Wc2006]水管局长数据加强版
bzoj3040: 最短路(road)
bzoj3098: Hash Killer II
bzoj1178: [Apio2009]CONVENTION会议中心
bzoj2806: [Ctsc2012]Cheat
bzoj3796: Mushroom追妹纸
bzoj2345: [Batic 2011]Vikings
bzoj3347: Srm524 Axonometric Projection
bzoj3348: TCO11 Semifinal Orthogonal Anagram
bzoj2379: Tc2008 Championship Snake蛇
bzoj1034: [ZJOI2008]泡泡堂BNB
bzoj3130: [Sdoi2013]费用流
bzoj2905: 背单词
bzoj4297: [PA2015]Rozstaw szyn
bzoj3881: [Coci2015]Divljak
bzoj4669: 抢夺
bzoj4364: [IOI2014]wall砖墙
bzoj4874: 筐子放球
bzoj1835: [ZJOI2010]base 基站选址
bzoj5089: 最大连续子段和
bzoj2347: [Baltic2011]Meetings
bzoj3133: [Baltic2013]ballmachine
bzoj5088: HDU 6000 Wash
bzoj4596: [Shoi2016]黑暗前的幻想乡
bzoj3288: Mato矩阵