linkfqy-CSDN博客

原创再见，CSDN

CSDN的体验越来越糟糕了博客迁移至Github 以后可能偶尔会来这里更新吧……============Update=============已将博客迁至oi.linkfqy.top

2018-02-25 11:03:36 758

原创【CDQ分治】BZOJ2683 简单题

题面在这里把每个询问操作Q分为4个（容斥）然后对于每个Q，要求出tA<tQ,xA≤xQ,yA≤yQt_A<t_Q,x_A\le x_Q,y_A\le y_Q的wAw_A之和直接CDQ分治就好了示例程序：

2018-02-24 10:15:57 375

原创【CDQ分治】BZOJ3295 [Cqoi2011]动态逆序对

题面在这里删除操作一共有3个属性：时间t，位置p，值x考虑到一个元素仅在被删除之前有贡献那么只需要统计t<t′,p>p′,x<x′t<t',p>p',x<x'的三维偏序即可CDQ分治解决t（注意是标记后半段为有贡献）排序解决p，树状数组解决x注意：1.一个删除操作对之前所有的时间都有贡献，所以最后一定要求前缀和才是答案2.被删除的元素有可能是逆序对的前者，也有可能是后者，所以要向前找大的，向后找小的

2018-02-23 14:11:44 338

原创【CDQ分治】 BZOJ3262 陌上花开

题面在这里最经典的三位偏序问题x用CDQ分治，y排序，z树状数组维护示例程序：

2018-02-22 21:18:38 296

原创【LCT维护生成树】BZOJ3669 [Noi2014]魔法森林

题面在这里考虑枚举a的最大值那么只需要让1→n1→n1\rightarrow n的最大值最小即可这样其实就是在做生成树，若当前构成环，则删去环中的最大边如果1到n联通就更新答案了具体实现可以按a排序，枚举每条边作为最大边用LCT维护生成树，其中最大值信息需要保存边的标号然后因为这道题是边权，所以要将边转化为点处理示例程序：#include<cstdio&g...

2018-02-12 12:21:39 314

原创【LCT】BZOJ2843 极地旅行社

题面在这里直接LCT就好了示例程序：#include<cstdio>#include<algorithm>using namespace std;inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fre...

2018-02-11 16:02:35 329

原创【LCT】BZOJ2049 [Sdoi2008]Cave 洞穴勘测

题面在这里LCT模板题，没什么好说的判断是否联通只需要判断根是否相同即可暴力往上找根是可行的，因为树的均摊深度是lognlognlogn示例程序：#include<cstdio>#include<algorithm>using namespace std;inline char nc(){ static char buf[100000],*...

2018-02-11 14:19:39 253

原创【LCT】BZOJ2002 [Hnoi2010]Bounce 弹飞绵羊

题面在这里LCT模板题，支持join,cutjoin,cut\text {join,cut}操作即可示例程序：#include<cstdio>#include<algorithm>using namespace std;inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; re...

2018-02-10 14:40:51 251

原创【斜率优化DP】BZOJ4518 [Sdoi2016]征途

题面在这里把m2m^2乘进去，答案其实就是m∑a2i−S2nm\sum a_i^2-S_n^2其中aia_i是第i天走的路程那么就是一个最显然的平方和模型，直接斜率优化DP示例程序：#include#include#include#define cl(x,y) memset(x,y,sizeof(x))using namespace std;typedef long

2018-01-04 20:53:29 498

原创【拓扑】BZOJ4010 [HNOI2015]菜肴制作

题面在这里首先要明确，题意不等价于求最小字典序例如：n=4,3→1,2→4n=4,3\rightarrow 1,2\rightarrow 4此时应输出31243124因为题目要求的是在保证1…i1\dots i先完成的情况下，再考虑i+1i+1所以求反图的最大拓扑字典序即可示例程序：

2018-01-04 18:48:51 532

原创【组合数学】BZOJ3505 [Cqoi2014]数三角形

题面在这里首先会发现直接算很难算那么就考虑计算三点共线的方案吧由于两直角边分别为a,ba,b的三角形，斜边上整点数为gcd(a,b)+1gcd(a,b)+1然后中间点要共线就只有gcd(a,b)−1gcd(a,b)-1种可能然后把斜边遍历整个网格图(n−a+1)⋅(n−b+1)(n-a+1)\cdot(n-b+1)最后注意一下这个斜边是可以对称翻转的示例程序：

2018-01-02 18:43:31 539

原创【二分+线段树】BZOJ4552 [Tjoi2016&Heoi2016]排序

题面在这里首先想到二分然后就可以把整个序列转化成01序列（0比mid小，1比mid大）这样排序的操作就可以用线段树区间覆盖来实现最后判断KK这个位置是0还是1，就完成了二分的验证竟然1A了，好高兴示例程序：

2017-12-26 20:33:34 512

原创【水】BZOJ1121 [POI2008]激光发射器SZK

题面在这里由于从一个顶点出发，最后一定会到另一个顶点所以答案就是n2\frac n2 示例程序：

2017-12-26 18:11:05 379

原创【分数规划+DFS序上DP】BZOJ4753 [Jsoi2016]最佳团体

题面在这里这个题一看就要二分吧……然后可以用DP验证其实就是树上取最大和但是如果定义不好的话会被卡常……可以DFS序上DP，常数较小fi,jf_{i,j}表示DFS序上前i-1个点，取了j个的最大值然后fi,j→fi+1,j+1 (取i)f_{i,j} \rightarrow f_{i+1,j+1} \text{ } \tag {取i} fi,j→fout(i),j (不取i)f_

2017-12-24 19:25:28 516

原创【带限制最短路】BZOJ1922 [Sdoi2010]大陆争霸

题面在这里设摧毁x城市的时间为dst(x)dst(x)，则有： dst(x)=max(Max{dst(y)},Max{dst(s)+ws,x})dst(x)=max(Max\{ dst(y) \},Max\{ dst(s)+w_{s,x} \}) 其中yy是保护xx的点，ss是连向xx的点那么就可以直接刷DijstraDijstra了注意为了使dst(y)dst(y)在dst(x)dst(x

2017-12-17 20:13:24 327

原创【贪心】BZOJ3668 [Noi2014]起床困难综合症

题面在这里按位贪心就好了示例程序：

2017-12-14 20:43:58 243

原创【李超线段树】BZOJ3165 [Heoi2013]Segment

题面在这里李超线段树的裸题，不解释示例程序：

2017-12-12 21:23:17 365

原创【莫比乌斯反演+数位DP】2017 计蒜之道复赛 A.阿里云秘钥池

题面在这里首先容斥一下，变为求[1,n][1,n]有多少数在PP进制下相邻位互质然后就可以DPDP了：fi,jf_{i,j}表示前ii位，最高位上是jj的方案数 fi,j=∑k=1P−1 [gcd(j,k)=1]fi−1,k=∑k=1P−1fi−1,k∑d|j,d|kμ(d)=∑d|jμ(d)∑dt≤P−1fi−1,dtf_{i,j}=\sum_{k=1}^{P-1} \ [gcd(j,k)=1

2017-12-11 06:56:39 269

原创【欧拉函数】BZOJ2705 [SDOI2012]Longge的问题

题面在这里考虑如下： ∑i=1n(i,n)=∑d|nd∑id≤n[(id,n)=d]=∑d|nd∑i=1nd[(i,nd)=1]=∑d|nd⋅φ(nd)\sum_{i=1}^n (i,n) \\=\sum_{d|n}d\sum_{id\le n} [(id,n)=d] \\=\sum_{d|n}d\sum_{i=1}^{\frac n d} [(i,\frac n d)=1] \\=

2017-12-10 19:08:29 250

原创【递推+lucas定理】BZOJ2111 [ZJOI2010]Perm 排列计数

题面在这里可以发现，此数列恰好满足堆性质可以把它看做小根堆的数组储存形式然后就可以愉快的DP了： fi=Csize lsonsize ifi∗2fi∗2+1f_i=C_{size\ i}^{size\ lson} f_{i*2}f_{i*2+1} 注意当n>pn>p时，可能不存在(n!)−1 (mod p)(n!)^{-1}\ \ \ (mod\ p)所以lucas定理就可以了示例程序

2017-12-05 21:13:32 774

原创【lucas定理】BZOJ2982 combination

题面在这里不说了，直接lucas示例程序：

2017-12-05 19:57:12 188

原创【lucas定理】BZOJ4403 序列统计

题面在这里首先元素大小在[L,R][L,R]等价于[1,R−L+1][1,R-L+1]那么长度为i，元素大小[1,M][1,M]的非降序列方案数为CM−1i+M−1C_{i+M-1}^{M-1}所以答案就是： ∑i=1NCM−1i+M−1=(∑i=1NCM−1i+M−1)+CMM−1=(∑i=2NCM−1i+M−1)+CMM+1−1=(∑i=3NCM−1i+M−1)+CMM+2−1…=CMN+M−

2017-12-05 19:38:11 276

原创【贪心+最小割】BZOJ2521 [Shoi2010]最小生成树

题面在这里考虑把图分成含A和含B的两个联通块中间用给定的那条边联系那么所有比他小的边都要进行操作（一次操作等价于给一条边权值+1）那么其实就是最小割了示例程序：

2017-12-03 21:25:25 257

原创【二分+最大流】BZOJ1305 [CQOI2009]dance跳舞

题面在这里考虑把每个人拆成自己xix_i和不喜欢自己yiy_i如果ii喜欢jj，那么连边(xi,xj,1)(x_i,x_j,1)，否则连边(yi,yj,1)(y_i,y_j,1)最多和讨厌的人跳K次舞，连边(xi,yi,k)(x_i,y_i,k)最后验证(S,xi,mid)(S,x_i,mid)是否满流即可示例程序：

2017-12-03 20:28:26 261

原创【二分+贪心】BZOJ1816 [Cqoi2010]扑克牌

题面在这里没什么好说的，直接二分答案就好了示例程序：

2017-12-03 14:12:44 327

原创【持续更新】莫比乌斯反演简明教程

前言开始学省选算法了……感觉莫比乌斯反演好厉害的样子，就先学习一下一入反演深似海……相关的东西太多了，以后会不定期更新前置技能莫比乌斯函数莫比乌斯函数μ(n)\mu(n)的定义如下：设n=pk11⋅pk22…pkmmn=p_1^{k_1}\cdot p_2^{k_2} \dots p_m^{k_m} μ(n)=⎧⎩⎨1(−1)m0n=1∏mi=1ki=1otherwise(ki>1)\begin

2017-11-30 21:09:53 2887

原创【莫比乌斯反演】BZOJ2818 Gcd

题面在这里反演裸题不解释示例程序：

2017-11-30 20:07:58 897

原创【莫比乌斯反演】BZOJ1101 [POI2007]Zap

题面在这里没什么好说的，反演裸题示例程序：

2017-11-28 20:45:46 792

原创【莫比乌斯反演】51Nod 1678 lyk与gcd

题面在这里一开始不会做，在Lynstery大佬的点拨下秒懂了……首先推柿子： ∑j=1n[gcd(i,j)=1]aj⇒∑j=1naj∑d|(i,j)μ(d)⇒∑d|iμ(d)∑d|jaj\sum_{j=1}^n[gcd(i,j)=1]a_j \\\Rightarrow \sum_{j=1}^n a_j \sum_{d|(i,j)} \mu(d) \\\Rightarrow \sum_{d

2017-11-28 20:18:23 779

原创【莫比乌斯反演】BZOJ2820 YY的GCD

题面在这里与这道题类似。先考虑枚举质数p，答案就是： ∑p∑dμ(d)⌊npd⌋⌊mpd⌋\sum_p \sum_d \mu(d) \lfloor \frac n {pd} \rfloor \lfloor \frac m {pd} \rfloor 设T=pdT=pd，考虑枚举TT，则有： ∑Tmin{n,m}⌊nT⌋⌊mT⌋∑p|Tμ(Tp)\sum_T^{min\{ n,m \}} \

2017-11-26 20:57:21 477

原创【容斥+莫比乌斯反演】BZOJ2301 [HAOI2011]Problem b

题面在这里首先容斥，把问题转化为求 ∑i=1n∑j=1m[gcd(i,j)=k]⇒∑i=1⌊nk⌋∑j=1⌊mk⌋[gcd(i,j)=1]\sum _{i=1}^n \sum _{j=1}^m [gcd(i,j)=k] \\\Rightarrow \sum _{i=1}^{\lfloor \frac n k \rfloor} \sum _{j=1}^{\lfloor \frac m k \r

2017-11-26 19:49:47 415

原创【二分+莫比乌斯函数】BZOJ2440 [中山市选2011]完全平方数

题面在这里显然需要二分……问题转化为求[1,⌊n√⌋][1,\lfloor \sqrt n \rfloor ]中无平方因子数的个数根据容斥原理，显然答案为n−奇数个质数乘积的平方倍数+偶数个质数乘积的平方倍数n-奇数个质数乘积的平方倍数+偶数个质数乘积的平方倍数如果枚举这个乘积i，根据莫比乌斯函数的定义，答案为： ∑i=1⌊n√⌋μ(i)⋅⌊ni2⌋\sum_{i=1}^{\big\lfloor

2017-11-26 11:18:27 840

原创 NOIP2017滚粗记

Day 1一早就到了学校，和大家一起嘻嘻哈哈的但是心里总有点发慌……一进考场，就迅速敲好了板子，坐等密码8：30后，开始看题三题都过了一遍后心里很虚：T1不是一眼题，T2是个比较麻烦的模拟感觉要写炸，T3什么鬼啊是DAG上DP吗然后就杠T1一开始以为是exgcd，想了很久发现是错的然后整个人就方了，因为之前以为NOIP不会考很难的数论的，就没有复习……越方越坚信这是一道数论题……后来只剩2个小时了，

2017-11-11 17:46:23 3507 1

原创【期望DP】HDU4405 Aeroplane chess

题面在这里还是期望DP的老套路……从后往前DP，fif_i表示i到终点的期望值，然后XJB转移就好了还有题意貌似是能飞就必须飞？没讲清楚啊示例程序：

2017-11-09 20:17:24 249

原创【期望DP】HDU3853 LOOPS

题面在这里显然直接倒推就好了示例程序：

2017-11-08 21:46:22 238

原创【概率DP】51Nod 1398 等公交

题面在这里考虑fif_i表示用了i时间，用了任意辆车概率之和然后就好了示例程序：

2017-11-04 16:17:01 550

原创【DP】RQNOJ #107 Ural的鹰蛋实验

题面在这里实在不懂为什么如此经典的题目只能在这种SBOJ上做……显然可以这样DP：fi,jf_{i,j}表示有i个蛋，要判断j层楼的最少次数枚举在哪一层楼扔鸡蛋 fi,j=Min{Max{fi−1,k−1,fi,j−k}+1} (1≤k≤j)f_{i,j}=Min\{ Max\{f_{i-1,k-1},f_{i,j-k} \}+1 \}\ \ \ \ \ \ \ \ \ \le

2017-11-03 18:12:03 606

原创【单调队列】BZOJ 1047 [HAOI2007]理想的正方形

题面在这里很显然可以使用单调队列。先只考虑正方形的行限制，处理出每个位置的最大/小值然后对最大/小值再刷一次单调队列，得到含有列限制的答案示例程序：

2017-11-02 21:38:51 734

原创【二分+最小生成树】BZOJ2654 tree

题面在这里其实非常简单：发现恰有need条边很难控制，但是边的优先级很好控制所以考虑给每个白色边加上某个权值使得求最小生成树时刚好取了need条边然后发现这个加上的权值与白色边的条数刚好满足单调所以直接二分加上的权值就好了示例程序：

2017-11-02 20:25:25 604

原创【状压DP】51Nod 1779 逆序对统计

题面在这里很水的状压DP……fsf_s表示s这个状态的最大逆序对数显然按照顺序去处理M个数，用于修正后面的转移的权值其实就是算有几个比当前大的示例程序：

2017-10-31 09:32:01 1088

周东《浅析最大最小定理在信息学竞赛中的应用》

空空如也