3 linkfqy

尚未进行身份认证

我要认证

A link to FQY.

等级
TA的排名 1w+

再见,CSDN

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

2018-02-25 11:03:36

【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

【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

【CDQ分治】 BZOJ3262 陌上花开

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

2018-02-22 21:18:38

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

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

2018-02-12 12:21:39

【LCT】BZOJ2843 极地旅行社

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

2018-02-11 16:02:35

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

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

2018-02-11 14:19:39

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

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

2018-02-10 14:40:51

【斜率优化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

【拓扑】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

【组合数学】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

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

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

2017-12-26 20:33:34

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

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

2017-12-26 18:11:05

【分数规划+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

【带限制最短路】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

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

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

2017-12-14 20:43:58

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

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

2017-12-12 21:23:17

【莫比乌斯反演+数位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

【欧拉函数】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

【递推+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

查看更多

勋章 我的勋章
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!