-->

BZOJ 好题记录2

做一道好题 比做十道水题还要有意义
这些大多数都是大赛的题目
多做好题 好好总结 提升实力
一步一个脚印 !

16/?


bzoj4886: [Lydsy2017年5月月赛]叠塔游戏

好思路好题啊
其实我们一开始的想法 都是排个序贪心一下 好像不是很好搞?
换思路 我们可以简化一下题目
就是有很多个A和B 然后A不能相同 要B的总和最大 (当然A和B是可以互换的)
我们可以把A和B拆点 然后连上一条边 我们需要把这条边定个方向 这一条边指向谁代表谁是A
显然剩下的联通块 一定是一个树或者是一个环套树
简单的可以证明一下:
指向谁代表谁是A 因为要求A互补相同 所以每个点的入度至多为1
如果这个联通块有两个环 肯定存在N个点 N+1条边 也就肯定存在N+1个入度 根据鸽巢原理 至少有一个点的入度为2或以上

每个点的答案肯定是这个点的出度(B)自己的权值
D[i] 表示i个这点的度
如果是树:这个联通块的答案是 (D[i]-1)
Val[i]+mx[i] 只有一个点入度不为1 这个点是最大值答案最优 所以要加上1次
如果是一个环套树:这个联通块的答案是D[i]*Val[i] 很简单N条边N个点 每个点入度为1 减掉就好了


bzoj2653: middle

好像是CLJ的题 做法也很好
一个简单的发现:可以二分

我试过很多直接搞的方法 好像都不是很行
我们想想什么时候这个数可能是中位数 就是序列中大于等于这个数的个数多过小于这个数的个数
就是我们对于一个数x 小于x的数标为-1 大于x的数标为1
然后求区间和大于0 并且左端点在[a,b] 右端点在[c,d]中
(其实大于0这个数未必可以取到是序列的中位数 因为这个数太小了 但是比它大的数可能是中位数)

一个脑洞大开的想法 我们对每个数从大到小先排序 然后对于每个数都开一个以位置为下标的线段树
比这个数大的数(或者相同)的位置都是+1 小的位置都是-1
然后查找的时候 查找对应二分的数的那个线段树就好了


bzoj3192: [JLOI2013]删除物品

这道题想到了就不难
就是比如样例
1 4 5
2 7 3
我们把两个堆顶相对 然后拼成一个数组 变成了
5 4 1 2 7 3
然后维护左堆顶的位置就好了


bzoj4123: [Baltic2015]Hacker

这道题我们需要简化一下 假设第一个人选定了一个位置为x 他可以选择数的个数为k
那么他肯定可以选择一个区间[a,a+k-1]使得
$$ x \in [a,a-k+1] $$
但是别人的目的就是可以使得所有的[a,a+k-1]的区间内 他的获益是最小的
然后维护个以某个位置结束的后缀和 然后用单调队列维护一下所有的区间就好了


bzoj2662: [BeiJing wc2012]冻结

裸的分成图最短路


bzoj4558: [JLoi2016]方

好麻烦的一道题 一开始以为这个正方形不能旋转…
发现可以旋转之后心态很崩溃的
首先我们可以用容斥 这是个大题思路 因为是计数题
为了简述 我们可以把删掉的点叫做黑点 其余的点叫做没点
就是
$$ Ans= 没有黑点的正方形 - 至少一个黑点的正方形 + 至少两个黑点的正方形 - 至少三个黑点的正方形 + 四个黑点的正方形$$
我们可以再仔细想想
一个正方形
%—–%
|—–|
|—–|
%—–%
这样的正方形 至少一个黑点的正方形算了4次 而至少两个黑点的正方形算了6次 至少三个黑点的正方形算了4次 四个黑点的算了1次
其实减掉的只有4+4-6-1=1 次
为什么这样 就是以包含每个顶点为一个集合 然后画四个圆圈的容斥

接下来我们来讨论怎么算上面式子需要的东西:

1.没有黑点的正方形
我们先考虑正的正方形
枚举正方形长度为L一共有(N-L+1)*(M-L+1) 的正方形
然后在正方形里面 可以画出(L-1)个斜的正方形
所以这一部分的答案就是
$$ Ans = \sum\limits_{L} L(N-L+1)(M-L+1) $$

2.至少一个黑点的正方形
我们同样 也先考虑正的正方形
假设这个点 左右还有l,r的空位(包括黑白点) 上下还有u,d的空位
那么答案就是以这个点为原点画坐标轴 然后直线y=x 和y=-x 的整点
所以这一部分的答案是
$$ Ans = \Sigma min(u,r)+min(r,d)+min(l,d)+min(l,u) $$

考虑斜的正方形 这是比较麻烦的
我们可以先考虑固定一个点 然后对角点在这个点上方的情况 而在左边,下边,右边的同理计算嘛
我们发现这样的斜的正方形个数和上面所说的u,l,r的值有关
然后找规律 假设l>r l< r 可以交换等价的嘛

u=1 没有斜的正方形
u=2 1个
…..
u=r r-1个
u=r+1 r个
u=r+2 r个
u=r+3 r个
…..
u=l r个
u=l+1 r个
u=l+2 r-1个
…..
u=l+r 1个
u=l+r+1 0个
下面的都是0个

这个要仔细的自己画一画吧 我有绝佳的解释 但是这里写不完
发现这个序列是递增-平-递减的
我们可以分三种情况讨论
1.u<=r+1
2.u<=l+1
3.u>l+r

然后就可以了

3.至少两个黑点以上的正方形
其实两个点已经可以确定一个正方形了 然后就可以分别讨论两个点是临边和对角线的情况就好了
剩下的两个点 可以用向量的加减法算出
随便统计一下就可以知道两个点 三个点 四个点的情况

这道题要手写Hash 不能用map


bzoj2648: SJY摆棋子 && bzoj2716: [Violet 3]天使玩偶

新学了一个算法叫做K-Dtree 其实找答案就是一个暴力+一个估价函数
这个估价函数就是这个点离一个矩阵至少有多远
模板题


bzoj2850: 巧克力王国

简单的K-Dtree练习 每一次就加上剪枝 如果整个矩阵范围内都是
$$ Ax+By \geq C $$ 就跳出来
如果所有都满足
$$ Ax+By < C $$ 就整个一起统计咯


bzoj1941: [Sdoi2010]Hide and Seek KDtree

简单的枚举点 然后像bzoj2648一样跑个最小值 然后再跑一次最大值 只要不是当前点就记录一下
取最小值就可以了


bzoj4520: [Cqoi2016]K远点对 KDtree

很套路啊枚举点拿一个set记录一下所有前K远点就好了 时间好像再kdtree上面带多一个log?


bzoj3053: The Closest M Points KDtree

这道题好像是正版的KDtree 也是很套路
常规的我们注意几个点就好了:
1.用set存答案,每一次和set里面的最大值比较
2.不能跑到树外 也就是不能用 0 0 0 0 0的点
3.不够K个的时候也是要搜进去的


bzoj4154: [Ipsc2015]Generating Synergy KDtree

好题啊 首先这道题很难看出是KD-tree
我们可以把dfs序和dep看作两维 然后来维护每个点的col值
当然了 kd-tree肯定也资瓷 push_up 和 push_down啊
改和问时间都是一样就好了


bzoj4170: 极光

直接插入单点就好了 有点像第一道例题 然后插入用一个栈维护一下对数即可


bzoj4031: [HEOI2015]小Z的房间

第一道矩阵树定理:
具体的定理不想说了 值得一提的是带Mod的消元
比如
3 2
2 1
可以变成
2 1
1 1
再变成
1 1
0 -1
就是像欧几里得一样 用多一个log的时间
每一次交换两行 行列式的值要取一个符号
就可以了


bzoj4766: 文艺计算姬

矩阵树定理 && 行列式

好爽啊最喜欢数学题了
首先看到数字很大 首先用矩阵树裸上打个表
1 1 1 1 1 1 1 1 1
1 4 12 32 80 192 448 1024 2304
1 12 81 432 2025 8748 35721 139968 531441
1 32 432 4096 32000 221184 1404928 8388608 47775744
1 80 2025 32000 390625 4050000 37515625 320000000 562890625
1 192 8748 221184 4050000 60466176 784147392 172942848 179645184
1 448 35721 1404928 37515625 784147392 841287201 886856192 651608241
1 1024 139968 8388608 320000000 172942848 886856192 46511104 904034304
1 2304 531441 47775744 562890625 179645184 651608241 904034304 188851841
怎么,你还没有发现吗????????
表是对称的 观察对角线位置
1 4 81 4096
1 2 9 64
1^0 2^1 3^2 4^3
进一步再猜一手 答案就是
$$ Ans = n^{m-1} m^{n-1} $$

下面就是用线性代数来证明了:
我们把样例改成2 4
中可以得到一个基尔霍夫矩阵的代数余子式 设消去最后一行和最后一列

$$
C=\left\vert\begin{matrix}
m && 0 && -1 && -1 && -1 \\
0 && m && -1 && -1 && -1 \\
-1 && -1 && n && 0 && 0 \\
-1 && -1 && 0 && n && 0 \\
-1 && -1 && 0 && 0 && n \\
\end{matrix}\right\vert
$$
化简一下有
$$
C=\left\vert\begin{matrix}
m && 0 && -1 && -1 && -1 \\
0 && m && -1 && -1 && -1 \\
0 && 0 && n-\frac{n}{m} && -\frac{n}{m} && -\frac{n}{m} \\
0 && 0 && -\frac{n}{m} && n-\frac{n}{m} && -\frac{n}{m} \\
0 && 0 && -\frac{n}{m} && -\frac{n}{m} && n-\frac{n}{m} \\
\end{matrix}\right\vert
$$
我们看到左下角一大堆0 然后套路一波 把这个行列式拆成两个
$$
C1=\left\vert\begin{matrix}
m && 0 \\
0 && m \\
\end{matrix}\right\vert
$$
$$
C2=\left\vert\begin{matrix}
n-\frac{n}{m} && -\frac{n}{m} && -\frac{n}{m} \\
-\frac{n}{m} && n-\frac{n}{m} && -\frac{n}{m} \\
-\frac{n}{m} && -\frac{n}{m} && n-\frac{n}{m} \\
\end{matrix}\right\vert
$$
$$
C=C1C2
$$
容易发现 这两个行列式也很好求 C1直接就可以看出来 C2发现对角线的数是一样的 其他又是一样的
想到了书本的例题 套路的把下面的行加到第一行那里 然后提出来 再用第一行乘个倍数加下面的行
所以有
$$
C1=m^n
$$
$$
C2=
\left\vert\begin{matrix}
n-\frac{(m-1)n}{m} && n-\frac{(m-1)n}{m} && n-\frac{(m-1)n}{m} \\
-\frac{n}{m} && n-\frac{n}{m} && -\frac{n}{m} \\
-\frac{n}{m} && -\frac{n}{m} && n-\frac{n}{m} \\
\end{matrix}\right\vert
$$
$$
C2=(n-\frac{(m-1)n}{m})
\left\vert\begin{matrix}
1 && 1 && 1 \\
-\frac{n}{m} && n-\frac{n}{m} && -\frac{n}{m} \\
-\frac{n}{m} && -\frac{n}{m} && n-\frac{n}{m} \\
\end{matrix}\right\vert
$$
$$
C2=(n-\frac{(m-1)n}{m})
\left\vert\begin{matrix}
1 && 1 && 1 \\
0 && n && 0 \\
0 && 0 && n \\
\end{matrix}\right\vert
$$
$$
C2=(n-\frac{(m-1)n}{m}) n^{m-2}
$$
$$
C=C1C2=m^n(n-\frac{(m-1)n}{m}) n^{m-2}=m^{n-1}n^{m-1}
$$


bzoj3534: [Sdoi2014]重建

矩阵树定理
这道题好像又要用到一个结论啊

基尔霍夫矩阵的任意一个代数余子式是所有生成树的边权积的和

这句话怎么理解呢 很好吧 就是平常的最小生成树边权积都是1 所以和就是计数个数啦
那么现在这个怎么办呢 其实我们以为是
$$ \Pi Pi , i \in E$$
其实不是的 如果边不在生成树上也有一个概率
$$ \Pi Pi \Pi(1- Pj) , i \in E , j \notin E$$
那么我们考虑怎么办 首先我们可以先每条边除去(1-Pi)的概率 然后后面计算答案的时候就乘回去
即:
$$A[i][j] = \frac{P(i,j)}{1-P(i,j)}$$
$$temp = \Pi P(i,j) $$
$$Ans = temp * Det() $$
用上前面的定理 每一次就是一个生成树的边权积的和
在生成树上的权可以最后乘上temp抵消 不在的话也可以通过乘上temp来调节