- 博客(276)
- 收藏
- 关注
RSS订阅原创 [BZOJ2138]stone Hall定理+线段树
假设把每堆石子拆成AiAiA_i个点，每个询问拆成KiKiK_i个点，就相当于每次添加KiKiK_i个点，然后询问此时的最大匹配能增加多少。 通过Hall定理可以判断匹配的合法性。但因为本题的区间没有包含，把询问按照LiLiL_i排序，RiRiR_i是递增的，在剔除掉没有被任一区间覆盖的石子堆之后，一段询问区间对应的石子也是一段连续的区间，我们不需要判断每个子集，而只需要判断每个区间是否满足Ha...
2018-07-06 21:52:44
575
原创 [2018江苏省队集训] value 值域分块+斜率优化
先考虑a=ba=ba=b的情况。 我们按aiaia_i从小到大排序，枚举iii并令x=aix=aix=a_i，那么[i,n][i,n][i,n]都是xxx的贡献，接下来就是找一个最大的bj⋅(i−j),(j∈[1,i−1])bj⋅(i−j),(j∈[1,i−1])b_j\cdot (i-j),(j\in[1,i-1])，看成关于iii的函数就是bj⋅i−bj⋅jbj⋅i−bj⋅jb_j\cdot...
2018-07-06 21:17:42
679
原创 min_25筛学习小记
终于在考试中碰到了一题不能用杜教筛的函数，被迫来学这个。。。概述首先这个函数f(x)f(x)f(x)要求是积性函数，而且f(p)f(p)f(p)和f(pc)f(pc)f(p^c)都要很好计算，设一个“假的”f′(x)f′(x)f'(x)表示把xxx直接当成质数时的f(x)f(x)f(x)，f′(x)f′(x)f'(x)是（或者能拆成）完全积性函数（比如说简单多项式），且∑ni=1f′(...
2018-07-04 22:02:41
647
1
原创 [联合集训6-26] 树上染色 决策单调性
我们设cost(y,x)cost(y,x)cost(y,x)表示从yyy刷到xxx的代价，设du=h−depth(u),du=h−depth(u),d_u=h-depth(u),。 cost(y,x)=Cy⋅(dx(dx+1)2−dy(dy−1)2)+C2y⋅(dx−dy+1)−Hycost(y,x)=Cy⋅(dx(dx+1)2−dy(dy−1)2)+Cy2⋅(dx−dy+1)−Hycost(y...
2018-07-02 21:17:27
430
原创 [联合集训6-25] 蓝雨 线段树+主席树+hash
先考虑p=qp=qp=q的情况，习惯先把求第kkk大变成求第kkk小。 那么我们逐个确定第kkk小的串每种数字包含了多少个。假设当前我们已经确定了x−1x−1x-1之前的数的个数，此时对于每个左端点iii，合法的右端点都是一个区间[li,ri][li,ri][l_i,r_i]。现在考虑二分确定xxx的个数，我们把序列中为xxx的位置单独挑出来，这些位置把序列分成若干段，假如二分有midmidmi...
2018-06-26 20:46:05
371
原创 [联合集训6-26] 盒子 莫比乌斯反演+杜教筛
题目就是求∑ni=1∑nj=1i+jgcd(i,j)−2n2∑i=1n∑j=1ni+jgcd(i,j)−2n2\sum_{i=1}^n\sum_{j=1}^n\frac{i+j}{\gcd(i,j)}-2n^2 枚举d=gcd(i,j)d=gcd(i,j)d=\gcd(i,j)， ∑d=1n∑i=1n∑j=1n[gcd(i,j)=d]i+jd∑d=1n∑i=1n∑j=1n[gcd(i,j)=d...
2018-06-26 20:28:13
346
原创 [联合集训6-22] 路灯 整体二分+扫描线树状数组
先给每个点重新设一个坐标（就是把给定的两个边界强行定成横纵坐标找），这个坐标可以直接通过和两个边界叉积得到。 于是点iii的答案就是其左下方所有点答案的第kikik_i小值，如果不足kikik_i个点答案就是iii。 于是我们可以考虑整体二分，二分一个时间MidMidMid，把编号≤Mid≤Mid\le Mid的点强行点亮，看剩下的点中有多少个也能跟着亮。这个二维数点可以横纵坐标分别为一二关键...
2018-06-22 22:12:20
272
原创 [联合集训6-22] monkey_sort 概率与期望+矩阵快速幂+树状数组
根据期望的线性性，我们只需对于每两个位置(i,j)(i,j)(i,j)计算出其相对位置改变的概率，并根据aiaia_i和ajaja_j的大小关系统计贡献即可。于是我们不难得到一个O(n2k)O(n2k)O(n^2k)的DP。设fi,j,kfi,j,kf_{i,j,k}表示当前(i,j)(i,j)(i,j)两个位置再进行kkk步交换操作使得i>ji>ji>j的概率（边界就是fi,j,...
2018-06-22 21:58:08
413
原创 [联合集训6-22] 疑惑 位运算+FFT
根据期望的线性性，我们可以对每一位分别考虑其为111的概率。那么假设一位有c0c0c_0个000，c1c1c_1个111，选kkk个xor和为111的方案数显然为∑c1i=0[i|2](c1i)(c0k−i)∑i=0c1[i|2](c1i)(c0k−i)\sum_{i=0}^{c_1}[i|2]{c_1\choose i}{c_0\choose k-i}。FFT即可。 代码：#inclu...
2018-06-22 21:18:26
385
原创 [联合集训6-21] 最小拓扑序 贪心
首先可以发现对于每个点vvv最多添加一条边指向它，假设添加了边x→v,y→v(x>y)x→v,y→v(x>y)x\to v,y\to v(x>y) 换成x→y,y→vx→y,y→vx\to y,y\to v不会更劣。 我们贪心选点加入拓扑序。那么考虑当前局面一个入度为000的点的集合，我们会在当前可添加边数允许的情况下，尽可能选择一个编号大的点放入拓扑序，假设我们选择点iii，那么对...
2018-06-21 22:16:02
307
原创 [联合集训6-21] LiaPo 矩阵快速幂
奇数的很显然是(m−1)n−(−1)n(m−1)(m−1)n−(−1)n(m−1)(m-1)^n-(-1)^n(m-1)。 对于偶数的情况，假设先不考虑对称不同的限制，我们可以DP的时候只需要关心当前为是否与第一位相同。那么考虑到对称不同的限制，我们可以两个两个填（也就是iii与i+n2i+n2i+\frac{n}{2}一起填），那么我们只要关心当前的两个位置和1,n2+11,n2+11,\fr...
2018-06-21 21:54:34
311
原创 [联合集训6-19] K小数查询 分块+二分答案
有一种常数比较小的O(nn−−√log2n)O(nnlog2n)O(n\sqrt n \log^2 n)的做法。 分块，每个块维护一个其中元素排好序之后的数组。修改的时候零散块直接重构，整块打标记。询问的时候先二分答案midmidmid，那么就转化成求小于等于midmidmid的数的个数，对于零散的块重构后暴力数，整块的如果标记≤mid≤mid\le mid答案就是块大小，否则直接在数组上二分...
2018-06-21 21:36:58
326
原创 [联合集训6-19] 山洞 点分树
一句话题意就是求点分树最小深度。 点分树有一个性质：我们称点iii在点分树上距叶子的距离为其权值wiwiw_i，那么对于两个点u,vu,vu,v满足wu=wv=kwu=wv=kw_u=w_v=k，在原树路径(u,v)(u,v)(u,v)上一定存在点ttt使得wt>kwt>kw_t>k，证明很显然。 我们对每个点iii求出一个二进制状态，二进制第kkk位表示该点子树中存不存在一个wj...
2018-06-21 21:27:39
357
原创 [联合集训6-19] 新干线 猜测题意+拆点网络流
题意还有一些细节如下： 1. 同一站点同一轨道同一时刻最多只能发一列货车 2. 直接经过的列车不占用停车位 3. 每条轨道上不允许发生客车超过货车的情况，但同时出发或同时到达某站是合法的，而且不占用该站台的停车位，就算客车货车速度相同且同时出发仍然算合法的 4. 求能发出货车且在MaxtimeMaxtimeMaxtime内到达终点的最大值。题中说到不能影响客车运行，也就是每列客车中...
2018-06-20 21:33:55
301
原创 [联合集训6-18] 栈 吉司机线段树
这个做法很巧妙。 考虑一个单调栈的插入过程。假如把插入的数倒过来，依次和栈底元素chkmax，如果chkmax成功就把它放入栈底，最终等效于顺序插入的结果。 于是我们把所有操作倒序处理，假如一个单调栈被询问了xxx次，我们就在线段树上给其分配xxx个下标，也就是说最后线段树一共是询问个数个下标，每个下标对应的是某个单调栈的某次询问。 那么用吉司机线段树维护区间chkmax，遇到一个询问就把对...
2018-06-20 21:22:00
537
原创 [联合集训6-18]不同班级 容斥+分治NTT
我们设f(x)f(x)f(x)是至少有xxx个人与本班人匹配的方案数，那么根据容斥就有Ans=∑mi=0(−1)if(i)(n−i)!Ans=∑i=0m(−1)if(i)(n−i)!Ans=\sum_{i=0}^m (-1)^if(i)(n-i)! ai=bi=1ai=bi=1a_i=b_i=1的时候是经典的错排问题，f(x)=(nx)f(x)=(nx)f(x)={n\choose x}。 对...
2018-06-20 21:05:29
302
原创 [联合集训6-18] 奥妮的大楼
问题转化就是给定nnn个二元组，每组中选出一个使得其互不相同，最大化另一个的和。 那么对于每个二元组我们对这两个值连一条无向边，现在的问题就是对每一条边定向使得每个点出度≤1≤1\le 1，并最大化每个点乘上其入度的和。 那么有解一定是若干个树和环套树，对于环套树的情况定向方式是唯一的，这样每个点贡献degi−1degi−1deg_i-1次，degidegideg_i表示其度数；对于树的情况根...
2018-06-20 20:54:11
258
原创 [联合集训6-18]指阶数乘 扩展欧拉定理
设f(n)=n(n−1)(n−2)...f(n)=n(n−1)(n−2)...f(n)=n^{(n-1)^{{(n-2)}...}}，那么f(n)modm=nf(n−1)modφ(m)+φ(m)modmf(n)modm=nf(n−1)modφ(m)+φ(m)modmf(n) \bmod m=n^{f(n-1)\bmod \varphi(m)+\varphi(m)}\bmod m。直接递归即可，递归...
2018-06-20 20:45:59
274
原创 [联合集训6-15] 盟誓的文艺复兴 数论
若c=2kc=2kc=2k，abc=a(bk)2abc=a(bk)2ab^c=a(b^k)^2；若c=2k+1c=2k+1c=2k+1,abc=(ab)(bk)2abc=(ab)(bk)2ab^c=(ab)(b^k)^2。所以我们只需要考虑c≤3c≤3c\le 3的情况。 那么能表示成ab2ab2ab^2的很好求，就是∑n13a=1μ2(a)(⌊na−−√⌋−a)∑a=1n13μ2(a)(⌊na...
2018-06-20 20:37:24
704
原创 [联合集训6-15]相互再归的鹅妈妈 数位DP+斯特林反演
问题要求无序方案数，可以转化成求有序方案数再除以n!n!n!即可。 先考虑去掉互不相同的限制，最后用斯特林数容斥掉即可。 可以发现从高往低扫，假如出现RRR有一位是111，而且有一个数这位填了000，那么剩下的数就可以再RRR的范围内随便填，因为最后都可以通过这个数把异或和调成000。于是我们可以通过枚举是哪一位最初发生了这种情况，求出g(i)g(i)g(i)表示选出iii个数异或和为000的...
2018-06-20 19:41:32
1029
原创 [联合集训6-14] 一道很好玩的几何题
设ki,jki,jk_{i,j}表示i,ji,ji,j连线的斜率，viviv_i表示第iii个关键点。 给出一个结论：∀i,f(vi)=vi+1∀i,f(vi)=vi+1\forall i,f(v_i)=v_{i+1}。假设该结论成立，那么就有kvi−1,vi>kvi,vi+1kvi−1,vi>kvi,vi+1k_{v_{i-1},v_i}>k_{v_i,v_i+1}。 考虑证明这...
2018-06-20 19:16:33
247
原创 [联合集训6-12] String 后缀树
先考虑假设我们把所有后缀建成一个Trie树，那么一个后缀字典序能成为最大就会带来一些限制，具体地就是从根出发遍历这个串，遍历的边上的字母映射的值要大于其他边上的字母。我们只要对于每个后缀带来的限制判一下环即可，复杂度O(n2c)O(n2c)O(n^2c)，其中ccc为字符集大小。 可以利用后缀树的性质优化上面的操作，也就是把只有一条出边的点压缩起来，其中第一条边的字母充当压缩后的边上的字母即可。...
2018-06-20 18:53:31
237
原创 [联合集训6-12] Mirror 状压DP
因为光路是可逆的，不闭合的光路都会被算进答案，所以可以把问题转化为最大化闭合光路长度，答案就是4nm4nm4nm减掉其两倍。 首先考虑如果两个闭合光路共用一个镜子，那么把这个镜子拿走答案不变，所以存在一种最优方案使得每行每列的镜子都是偶数个，而且一定是相邻两个配对。于是状压每一行镜子的奇偶性， 并记录当前镜子数量，一列一列填镜子即可。 因为镜子数量最多为2(n+m−2)2(n+m−2)2(n+...
2018-06-14 22:08:17
255
原创 [联合集训6-12] Fraction 莫比乌斯反演+杜教筛+类欧几里得
因为区间可以差分成前缀，我们只用考虑≤ab≤ab\le \frac{a}{b}的最简真分数jiji\frac{j}{i}的个数。 Ans=∑1≤j<i≤n[j≤aib][gcd(i,j)=1]Ans=∑1≤j<i≤n[j≤aib][gcd(i,j)=1]Ans=\sum_{1\le j∑1≤j<i≤n[j≤aib]∑d|gcd(i,j)μ(d)=∑d=1nμ(d)∑i=1⌊nd...
2018-06-14 21:32:57
266
原创 [联合集训6-11] 期望题
因为A1A1A_1是必须要减完的，所以我们只要求出对于Ai(i=2...n)Ai(i=2...n)A_i(i=2...n)在A−1A−1A-1减完前期望被减了多少次，最后加上A1A1A_1即可。因为期望的线性性，我们只需要分别考虑每一个AiAiA_i即可。 不妨以考虑A1,A2A1,A2A_1,A_2为例。我们可以把其看成二维平面上的一个点(A1,A2)(A1,A2)(A_1,A_2)，每次分别...
2018-06-14 21:15:44
243
原创 [联合集训6-11] 数数题 多项式+自然数幂和
因为保证了Bi<Ai+1Bi<Ai+1B_iiii位的111分配给第i−1i−1i-1位变成AiAiA_i，求一共有多少种分配方法。 那么我们设ft(n)ft(n)f_t(n)表示假设第ttt位上是nnn（i=1..t−1i=1..t−1i=1..t-1位都是BiBiB_i），有多少种分配方案，那么枚举分给下一位多少，就有 ft(n)=∑i=0nft−1(iAt+Bt−1)ft(n...
2018-06-14 20:48:38
242
原创 [联合集训6-9]Congroo 二进制分组+凸包上二分
查询叉积最大值就是找该向量切凸包上的切点。因为只有在末尾加入删除的操作，我们利用二进制分组，维护loglog\log个凸包，询问的时候在每个凸包上二分找切点即可。 要注意要分别对上下凸壳二分，因为凸包是一个环但二分其实是对一个序列二分，所以直接二分会挂。 程序里还有几个复杂度不对的地方： 1. 二进制分组应该有四个相同的才把前两个合并，而不是有两个相同就合并，否则每次加入/删除第2k2k2^...
2018-06-14 20:29:18
539
原创 [联合集训6-9] Psy 组合数学+杜教筛
显然，符合条件的数必须满足任何长度的后缀字典序必须严格大于全串。 假设一个串TTT可以由几个相同的串sss拼接而成，我们称TTT为循环串。显然所有循环串都是不满足条件的。 那么对于非循环串，那么其所有循环表示（就是切下一个前缀拼在后面）都是互不相同的。给出一个结论：一个合法串和一个环的最小循环表示串一一对应。 先证明一个合法串一定是最小循环表示串。（以下PxPxP_x表示长度为xxx的前缀，...
2018-06-13 22:55:52
285
原创 [联合集训6-9] El 点分治+哈希表
转化题意，就是根据题目所给的式子定义颜色，求同色三角形的个数。 有一个经典结论：完全图同色三角形个数=总三角形个数-异色角个数/2。因为每个异色三角形都恰有两个异色角。 在有向完全图中结论依然成立，但这里的异色角就要分别统计两出，一入一出，两出三种情况。我们只需要分别知道每个点进/出的红/绿路径数量即可。这个可以用点分治解决。 具体地，对于一个分治中心rootrootroot，我们求出它到该...
2018-06-10 21:55:23
280
原创 [JZOJ5749] 小J真爱粉交流群 博弈
首先不难发现： B只会在A所在位置下面选择建墙或者不建； 如果选择不建A一定会向下走。 那么就可以推导出B在某一行建的墙一定是A移动的区间。 那么我们设fi,l,rfi,l,rf_{i,l,r}表示B在第iii行的[l,r][l,r][l,r]下有墙，A在l−1l−1l-1时的分数，gi,l,rgi,l,rg_{i,l,r}则表示A在r+1r+1r+1的分数。 两者转移类似，我们考虑ff...
2018-06-01 18:24:52
404
原创 [JZOJ5748] 小Y增员操直播群 递推+分治
题目中是把所有而不是一部分互膜记录给出了。。。 注意到原本在一个子群的成员到最后一定是一个连续的区间，假设我们在已知[l,r][l,r][l,r]是一个群，考虑如何分裂它。设与rrr相连的最小点是xxx，当区间长度为偶数且x=l+r−12x=l+r−12x=\frac{l+r-1}{2}时左右大小相同，xxx即为左半部分右端点，否则r−x+l−1r−x+l−1r-x+l-1相连的点一定就是左半部...
2018-06-01 18:10:09
399
原创 [JZOJ5745]幂 数论阶
首先考虑当nnn有平方因子p2p2p^2时，取a=pa=pa=p就无解了，所以我们只考虑μ2(n)=1μ2(n)=1\mu^2(n)=1的情况。 考虑中国剩余定理，只要保证对于nnn的每个因子pipip_i满足对于所有aaa，求最小的kkk，使得ank≡a(modpi)ank≡a(modpi)a^{n^k}\equiv a \pmod {p_i}，即nk≡1(modpi−1)nk≡1(modpi...
2018-05-28 11:33:05
598
原创 [JZOJ5746]和 自然数幂和+中国剩余定理
{nj}{nj}\begin{Bmatrix} n\\j \end{Bmatrix} 首先考虑计算模质数下的自然数幂和，通过stirling数转化成下降幂， ∑i=0nik=∑i=0n∑j=0k{kj}ij–=∑j=0k{kj}∑i=0nij–∑i=0nik=∑i=0n∑j=0k{kj}ij_=∑j=0k{kj}∑i=0nij_\sum_{i=0}^n i^k=\sum_{i=0}^n\sum...
2018-05-27 21:42:19
318
原创 [JZOJ5728] 简单计数|| 容斥+处理环上问题
先考虑链上的做法。 先预处理fi,jfi,jf_{i,j}表示iii个元素分到jjj个集合中，所有集合大小之积的和，fi,j=k⋅fi−k,j−1fi,j=k⋅fi−k,j−1f_{i,j}=k\cdot f_{i-k,j-1}。 那么假如第iii种数字的cicic_i个被分成了aiaia_i个，那么问题就转化成有nnn种颜色的球，第iii种球有aiaia_i个，求排列这些球使得相邻球不同色的...
2018-05-24 11:47:24
413
原创 [JZOJ5727] [色]和[流泪]||
我们把把一个游戏看成在二维平面上玩，一开始在(0,0)(0,0)(0,0)，从左边删x+1x+1x+1，从右边删y+1y+1y+1。 那么假如左边删xxx个，右边删yyy个，那么SG(x,y)=0SG(x,y)=0SG(x,y)=0，我们称之为终止态，那么和终止态相邻且不为终止态的点SG=1SG=1SG=1，称其为边界态。 不难发现对于一个xxx，终止态只有一个，而且随着xxx增大yyy是单调...
2018-05-24 11:05:06
336
原创 [BZOJ5333][SDOI2018]荣誉称号 树型DP
首先发现最终的aiaia_i一定和a⌊i2k+1⌋a⌊i2k+1⌋a_{\lfloor\frac{i}{2^{k+1}}\rfloor}同余。 那么只要把第k+1k+1k+1层及其之后的代价统计进前kkk层即可，也就是预处理出vi,jvi,jv_{i,j}表示前kkk层中的aiaia_i在模mmm调整至jjj的代价。 然后只要设fi,jfi,jf_{i,j}表示点iii到第kkk层的路径上aa...
2018-05-24 10:37:00
365
原创 [Codeforces963] E-Circles of Waiting 网格图高斯消元
好像四联通八联通的网格图消元都可以那么干，以下是四联通的，具体地就是每条方程都只和(x,y),(x−1,y),(x+1,y),(x,y−1),(x,y+1)(x,y),(x−1,y),(x+1,y),(x,y−1),(x,y+1)(x,y),(x-1,y),(x+1,y),(x,y-1),(x,y+1)四个未知量有关。 对于这样的高斯消元，我们可以选择从(0,0),(1,0),(2,0)...(...
2018-05-24 10:30:40
379
原创 [JZOJ5739]毒奶 子集DP
这里讲的是O(3n⋅n)O(3n⋅n)O(3^n\cdot n)的可以过的暴力，正解不会。。。 把问题转化成给了nnn个白点，nnn个黑点，给定了n−1n−1n-1条白白边和黑黑边，求再填nnn条黑白边使之联通的方案数。 先用给定的边缩点，记下缩点后每个大点的sizesizesize，然后随意钦定一个白点当根，剩下就是要求一层黑一层白的填，直接子集DP即可。 具体地，设FS,c,iFS,c,...
2018-05-24 09:44:45
457
原创 [JZOJ5740]幻想世界 快速数论变换
首先发现α,βα,β\alpha,\beta的贡献和ak,bkak,bka_k,b_k的贡献是可以分开计算的，把一个DP状态看成是二维坐标上的一个点，转移就是每次从左边(x−1,y)(x−1,y)(x-1,y)或者从下面(x,y−1)(x,y−1)(x,y-1)转移。 先考虑计算α,βα,β\alpha,\beta的贡献。 考虑枚举两个点(x1,y1),(x2,y2)(x1≤x2,y1≤y2)...
2018-05-24 09:24:47
420
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人