4 Hany01

尚未进行身份认证

菜得一匹~

等级
TA的排名 1w+

【POJ1322】Chocolate (生成函数)

Description有ccc种颜色的巧克力, 每种颜色有无限个. 现在每次取出一个巧克力, 其颜色等概率为1…c1\dots c1…c中的一种.问最终有mmm种颜色的巧克力个数为奇数的概率.n≤106,c≤100n\le 10^6, c\le 100n≤106,c≤100Solution睿智dp题。设fi,jf_{i,j}fi,j​表示当前取了iii个、有jjj种颜色是奇数个的概率,...

2018-11-18 22:57:29

NOIP2018咕咕记

这个博客诈尸了这篇游记咕咕咕了

2018-11-15 16:51:06

【AGC002D】Stamp Rally(整体二分)

Description给定一个图和很多次询问xi,yi,zix_i,y_i,z_ixi​,yi​,zi​,问两个人分别从xi,yix_i,y_ixi​,yi​出发,一共经过了ziz_izi​个不同的节点,需要经过的边的最大编号最小是多少。Solution裸的整体二分题。用并查集维护,查一下xi,yix_i,y_ixi​,yi​所在联通块大小即可。Code/*************...

2018-10-11 21:55:03

【BZOJ4870】【六省联考2017】组合数问题(矩阵快速幂)

Description计算:(∑i=0+∞(nkik+r)) mod p\left( \sum_{i=0}^{+\infty} \binom{nk}{ik+r} \right)\bmod p(i=0∑+∞​(ik+rnk​))modpn≤109,0≤r<k≤50,2≤p≤230−1n\le 10^9, ...

2018-10-09 16:55:26

【BZOJ2639】矩形计算(四维偏序)

Description输入一个n*m的矩阵,矩阵的每一个元素都是一个整数,然后有q个询问,每次询问一个子矩阵的权值。矩阵的权值是这样定义的,对于一个整数x,如果它在该矩阵中出现了p次,那么它给该矩阵的权值就贡献p2。Solution由于出现ppp次的元素的贡献是p2p^2p2,我们可以看做每一对相同的元素可以产生111的贡献。我们定一个SSS,大概为404040。对于出现次数大于SSS...

2018-10-03 08:27:51

【Luogu3733】【HAOI2017】八纵八横(线段树分治,线性基)

Descriptionhttps://www.luogu.org/problemnew/show/P3733Solution如果只有插入,我们可以搞出一棵生成树,记录每个点到根的异或和dis[u]dis[u]dis[u],对于边(u,v)(u,v)(u,v),将dis[u] xor dis[v] xor wdis[u]\ xo

2018-09-28 23:52:22

【BZOJ5293】【BJOI2018】求和(LCA,树上差分)

Descriptionmaster 对树上的求和非常感兴趣。他生成了一棵有根树,并且希望多次询问这棵树上一段路径上所有节点深度的k 次方和,而且每次的k 可能是不同的。此处节点深度的定义是这个节点到根的路径上的边数。他把这个问题交给了pupil,但pupil 并不会这么复杂的操作,你能帮他解决吗?Solution树上差分傻逼题。对于不同的kkk分别处理,直接累一个到根的前缀...

2018-09-28 23:52:10

【BZOJ4196】【NOI2015】软件包管理器(树链剖分,线段树)

DescriptionLinux用户和OSX用户一定对软件包管理器不会陌生。通过软件包管理器,你可以通过一行命令安装某一个软件包,然后软件包管理器会帮助你从软件源下载软件包,同时自动解决所有的依赖(即下载安装这个软件包的安装所依赖的其它软件包),完成所有的配置。Debian/Ubuntu使用的apt-get,Fedora/CentOS使用的yum,以及OSX下可用的homebrew都是优秀的软...

2018-09-28 23:52:01

【BZOJ4195】【NOI2015】程序自动分析(并查集)

Description在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。考虑一个约束满足问题的简化版本:假设x1,x2,x3,…代表程序中出现的变量,给定n个形如xi=xj或xi≠xj的变量相等/不等的约束条件,请判定是否可以分别为每一个变量赋予恰当的值,使得上述所有约束条件同时被满足。例如,一个问题中的约束条件为:x1=x2,x2=x3,x3=x4,x1≠x4,这些约...

2018-09-28 23:51:53

【清橙A1212】剪枝(树形DP)

Descriptionhttp://www.tsinsen.com/A1212Solution对于每一个叶子节点,它到根的路径上存在且仅存在一个点作为最终答案中的叶子节点。 我们从左向右考虑每一条路径,设dp[u]dp[u]dp[u]表示将路径上的uuu的下面剪掉获得的最大价值。 我们从左向右转移,对于相邻的两个叶子节点,我们只需考虑它们LCA以下的节点。 如果我们对于右...

2018-09-28 23:50:44

【BZOJ4013】【HNOI2015】实验比较(树形DP,组合)

Descriptionhttps://www.lydsy.com/JudgeOnline/problem.php?id=4013Solution先将相等的都丢进一个并查集,又因为有条件:“小 D 都最多只记住了某一张质量不比 i 差的另一张图片 Ki”,我们对大小关系进行建图后是一棵树(如果是森林,我们新建一个点连接所有根节点即可)。 设dp[u][i]dp[u][i]dp[...

2018-09-28 23:50:37

【51nod1743】雪之国度(并查集,Kruskal)

Description雪之国度有N座城市,依次编号为1到N,又有M条道路连接了其中的城市,每一条道路都连接了不同的2个城市,任何两座不同的城市之间可能不止一条道路。 雪之女王赋予了每一座城市不同的能量,其中第i座城市被赋予的能量为Wi。 如果城市u和v之间有一条道路,那么只要此刻雪之女王的能量不小于|Wu-Wv|,这条道路就是安全的。 如果城市u和v之间存在两条没有重复道路的安全路径(其...

2018-09-28 23:50:29

【BZOJ4784】【ZJOI2017】【UOJ290】仙人掌(DP)

Descriptionhttp://uoj.ac/problem/290Solution首先判断是不是一个仙人掌/树,如果不是,直接输出0. 然后将返祖边所覆盖的边删掉,形成了一个森林,我们就只要算在这个森林中连边的方案。 设g[i]g[i]g[i]表示一个点有iii个儿子,可以将儿子两两配对(允许不配对)的方案,那么显然有: g[i]=g[i−1]+g[i−2]∗(i−...

2018-09-28 23:50:17

【BZOJ1132】【POI2008】Tro(计算几何)

Description平面上有N个点. 求出所有以这N个点为顶点的三角形的面积和 N<=3000Solution将点按yyy排序,枚举一个点,将在它后面的点以它为原点极角排序,用前缀和计算叉积即可。Code/************************************************ * Au: Hany01 * Prob: triangle * Em...

2018-09-28 23:49:23

【BZOJ2253】纸箱堆叠(CDQ分治,DP)

Descriptionhttps://www.lydsy.com/JudgeOnline/problem.php?id=2253Solution只有三维严格小于另一个箱子才可以转移,直接CDQ分治即可。Code/************************************************ * Au: Hany01 * Date: Sep 26th, 2018...

2018-09-28 23:48:51

【BZOJ1176】【Balkan2007】Mokia(CDQ分治)

Description维护一个W*W的矩阵,初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000.Solution好多年没写过CDQ分治了。。CDQ分治模板题。将操作顺序看做另一维,将矩阵询问用前缀和拆成4个,就变成了三维偏序问题了。Code/***************...

2018-09-28 23:48:40

【BZOJ2803】【POI2012】PRE-Prefixuffix

Descriptionhttps://www.luogu.org/problemnew/show/P3546Solution循环同构的前后缀一定可以表示成:AB...BA我们设fif_ifi​表示去掉串长度为iii的前后缀后,最长的前后缀相同的部分。性质:fi≥f(i−1)−2f_i\ge f(i-1)-2fi​≥f(i−1)−2大概是酱紫的:i-1:xxxabcde…abcde...

2018-09-28 23:48:20

【BZOJ1124】【POI2008】Maf 枪战(贪心)

Description有n个人,每个人手里有一把手枪。一开始所有人都选定一个人瞄准(有可能瞄准自己)。然后他们按某个顺序开枪,且任意时刻只有一个人开枪。因此,对于不同的开枪顺序,最后死的人也不同。你要求最后死亡数目的最小和最大可能Solution最多死亡数:对于一个环,只有一个人幸存;对于一个基环树,只有入度为0的人幸存。最少死亡数:入度为0的人活下来,他指向的人死亡,死亡的人指向的人...

2018-09-28 23:47:55

【51nod1074】约瑟夫环

Descriptionhttp://www.51nod.com/onlineJudge/questionCode.html#!problemId=1074Solution约瑟夫问题模板。我们设fif_ifi​表示iii个人、报数报到mmm时的答案,那么有转移:fi=(fi−1+m−1) mod i+1f_i = (...

2018-09-28 23:47:47

【BZOJ5068】【WC2005】友好的生物(约束放宽)

Descriptionhttps://www.luogu.org/problemnew/show/P4131Solution将式子写成:∣Ai,1−Aj,1∣+∣Ai,2−Aj,2∣+…|A_{i,1}-A_{j,1}|+|A_{i,2}-A_{j,2}|+\dots∣Ai,1​−Aj,1​∣+∣Ai,2​−Aj,2​∣+…如果没有最后的第KKK个属性,那么我们可以直接2K−12^{K-...

2018-09-28 23:47:38

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得