• 等级
  • 71296 访问
  • 272 原创
  • 4 转发
  • 16685 排名
  • 14 评论
  • 23 获赞

[BZOJ2138]stone Hall定理+线段树

假设把每堆石子拆成AiAiA_i个点,每个询问拆成KiKiK_i个点,就相当于每次添加KiKiK_i个点,然后询问此时的最大匹配能增加多少。通过Hall定理可以判断匹配的合法性。但因为本题的区间没有包含,把询问按照LiLiL_i排序,RiRiR_i是递增的,在剔除掉没有被任一区间覆盖的石子堆之后,一段询问区间对应的石子也是一段连续的区间,我们不需要判断每个子集,而只需要判断每个区间是否满足Ha...

2018-07-06 21:52:44

[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

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

[联合集训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

[联合集训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

[联合集训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

[联合集训6-22] 路灯 整体二分+扫描线树状数组

先给每个点重新设一个坐标(就是把给定的两个边界强行定成横纵坐标找),这个坐标可以直接通过和两个边界叉积得到。于是点iii的答案就是其左下方所有点答案的第kikik_i小值,如果不足kikik_i个点答案就是iii。于是我们可以考虑整体二分,二分一个时间MidMidMid,把编号≤Mid≤Mid\leMid的点强行点亮,看剩下的点中有多少个也能跟着亮。这个二维数点可以横纵坐标分别为一二关键...

2018-06-22 22:12:20

[联合集训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

[联合集训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\choosei}{c_0\choosek-i}。FFT即可。代码:#inclu...

2018-06-22 21:18:26

[联合集训6-21] 最小拓扑序 贪心

首先可以发现对于每个点vvv最多添加一条边指向它,假设添加了边x→v,y→v(x>y)x→v,y→v(x>y)x\tov,y\tov(x>y)换成x→y,y→vx→y,y→vx\toy,y\tov不会更劣。我们贪心选点加入拓扑序。那么考虑当前局面一个入度为000的点的集合,我们会在当前可添加边数允许的情况下,尽可能选择一个编号大的点放入拓扑序,假设我们选择点iii,那么对...

2018-06-21 22:16:02

[联合集训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

[联合集训6-19] K小数查询 分块+二分答案

有一种常数比较小的O(nn−−√log2n)O(nnlog2⁡n)O(n\sqrtn\log^2n)的做法。分块,每个块维护一个其中元素排好序之后的数组。修改的时候零散块直接重构,整块打标记。询问的时候先二分答案midmidmid,那么就转化成求小于等于midmidmid的数的个数,对于零散的块重构后暴力数,整块的如果标记≤mid≤mid\lemid答案就是块大小,否则直接在数组上二分...

2018-06-21 21:36:58

[联合集训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

[联合集训6-19] 新干线 猜测题意+拆点网络流

题意还有一些细节如下:1.同一站点同一轨道同一时刻最多只能发一列货车2.直接经过的列车不占用停车位3.每条轨道上不允许发生客车超过货车的情况,但同时出发或同时到达某站是合法的,而且不占用该站台的停车位,就算客车货车速度相同且同时出发仍然算合法的4.求能发出货车且在MaxtimeMaxtimeMaxtime内到达终点的最大值。题中说到不能影响客车运行,也就是每列客车中...

2018-06-20 21:33:55

[联合集训6-18] 栈 吉司机线段树

这个做法很巧妙。考虑一个单调栈的插入过程。假如把插入的数倒过来,依次和栈底元素chkmax,如果chkmax成功就把它放入栈底,最终等效于顺序插入的结果。于是我们把所有操作倒序处理,假如一个单调栈被询问了xxx次,我们就在线段树上给其分配xxx个下标,也就是说最后线段树一共是询问个数个下标,每个下标对应的是某个单调栈的某次询问。那么用吉司机线段树维护区间chkmax,遇到一个询问就把对...

2018-06-20 21:22:00

[联合集训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\choosex}。对...

2018-06-20 21:05:29

[联合集训6-18] 奥妮的大楼

问题转化就是给定nnn个二元组,每组中选出一个使得其互不相同,最大化另一个的和。那么对于每个二元组我们对这两个值连一条无向边,现在的问题就是对每一条边定向使得每个点出度≤1≤1\le1,并最大化每个点乘上其入度的和。那么有解一定是若干个树和环套树,对于环套树的情况定向方式是唯一的,这样每个点贡献degi−1degi−1deg_i-1次,degidegideg_i表示其度数;对于树的情况根...

2018-06-20 20:54:11

[联合集训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)\bmodm=n^{f(n-1)\bmod\varphi(m)+\varphi(m)}\bmodm。直接递归即可,递归...

2018-06-20 20:45:59

[联合集训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\le3的情况。那么能表示成ab2ab2ab^2的很好求,就是∑n13a=1μ2(a)(⌊na−−√⌋−a)∑a=1n13μ2(a)(⌊na...

2018-06-20 20:37:24

[联合集训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

DOFYPXY

关注
  • 学生
  • 中国 江西省 赣州市
奖章
  • 持之以恒