- 博客(151)
- 收藏
- 关注
RSS订阅
4原创 bzoj 2730: [HNOI2012]矿场搭建
Solution先 tarjantarjantarjan 求点双。对于每一个连通块，如果其中没有割点，则说明需要在其中建立两个出口；只有一个割点，那么就需要在非割点处选一个建立出口；如果有大于等于两个割点，则不需要建立出口Code#include <cstdio>#include <cstring>#include <stack>#include ...
2018-09-21 10:34:08
203
原创 bzoj1879 SDOI2009]Bill的挑战 （状压dp）
Problem求 nnn 个模式串，能匹配其中 kkk 个的字符串的个数匹配的含义为 若为 “?” 则与所以字母都匹配，若为字母，则需相同Solution首先看的 nnn 很小，然后可能使用状压 dpdpdp 来解决a[i][j]a[i][j]a[i][j] 表示第 iii 位这 nnn 个模式串在这一位是 ′a′&#x27;a&#x27;′a′+jjj 的程度f[i]...
2018-09-21 10:33:34
196
原创 bzoj1096: [ZJOI2007]仓库建设 （斜率优化dp）
Problem先有一些工厂，每个工厂有一些成品。先要在其中一些工厂的位置建立仓库，建立仓库会有一定的费用。每个没设立仓库的地方将成品运送至下面的仓库，费用为成品数乘距离。山脚一定有一个仓库。问最少需要的花费是多少工厂 iii 距离工厂 111 的距离 xix_ixi（其中 x1=0x_1=0x1=0）;工厂 iii 目前已有成品数量 pip_ipi;在工厂 iii 建立仓库的费用 c...
2018-09-19 00:07:49
229
原创 bzoj1911: [Apio2010]特别行动队 （斜率优化dp）
Solution首先可以得到 dpdpdp 方程 f[i]=max(f[j]+a(sum[i]−sum[j])2+b(sum[i]−sum[j])+c)f[i]=max(f[j]+a(sum[i]-sum[j])^2+b(sum[i]-sum[j])+c)f[i]=max(f[j]+a(sum[i]−sum[j])2+b(sum[i]−sum[j])+c)f[i]=f[j]+a⋅sum[i]2...
2018-09-18 22:19:33
157
原创 bzoj3261: 最大异或和（可持久化字典树）
Problem给定一个非负整数序列 a{a}a，初始长度为 nnn。有M个操作，有以下两种操作类型：1、A1、A1、A $ x$：添加操作，表示在序列末尾添加一个数 xxx ，序列的长度 n+1n+1n+1。2、Q2、Q2、Q $ l$ $ r$ $ x$：询问操作，你需要找到一个位置 ppp，满足 l&amp;lt;=p&amp;lt;=rl&amp;lt;=p&amp;lt;=rl&l...
2018-09-18 21:28:05
205
原创 bzoj1010: [HNOI2008]玩具装箱toy （斜率优化）
Solutionf[i]=min(f[j]+(i−j−1+sum[i]−sum[j]−L)2)f[i]=min(f[j]+(i-j-1+sum[i]-sum[j]-L)^2)f[i]=min(f[j]+(i−j−1+sum[i]−sum[j]−L)2)为了方便计算，我们定义 a[i]=i+sum[i]a[i]=i+sum[i]a[i]=i+sum[i] ， b[i]=i+sum[i]+1+Lb...
2018-09-18 21:15:45
124
原创 bzoj4361: isn （dp+树状数组+容斥）
Problem给你一个序列，若此时这个序列不是非降的，那么从中删除一个数，知道删到非降为止。问有多少种操作方案Solution定义 f[i]f[i]f[i] 表示长度为 iii 的非降子序列个数容斥一下， ans=∑f[i]∗(n−i)!−f[i+1]∗(n−i−1)!∗(i+1)ans=\sum f[i]*(n-i)!-f[i+1]*(n-i-1)!*(i+1)ans=∑f[i]∗(n...
2018-09-18 19:01:10
181
原创 bzoj2144: 跳跳棋 （lca+思维）
Problem有三个棋子在一个一条数轴上，可以使其中一枚为轴，另一枚跳过去，但跳的过程中不能越过第三枚棋子。给定初始状态，问能否达到最终状态，如果可以最少需要几步Solution首先先判断可不可以。我们可以讲初末状态都转变成不能再走的状态，显然对于每种情况这种状态只有一个。那如果不能再继续的状态一样，说明他们肯定是可以通过变换得到的；反之，最终状态都不同，显然不能跳出来…这样我们记录...
2018-09-17 20:51:13
254
原创 bzoj5190: [Usaco2018 Jan]Stamp Painting （dp）
Problem用 MMM 种长为 KKK 的印章（每种颜色均不同），给长为 NNN 的纸条盖章。问最后会得到多少种不同的状态。Solution反过来想，答案就是总数减去不合法情况。总数也就是每个块随便选颜色，即 mnm^nmn而每个印章长度为 KKK ，因此如果最长的一段相同颜色的长度小于 KKK ，那么就说明此情况不合法。那么我们现在的认为就是求不合法的情况。定义 f[i]f[i...
2018-09-17 20:50:26
186
原创 bzoj5189: [Usaco2018 Jan]Cow at Large（树形dp）
ProblemBessieBessieBessie 站在一个点，每个叶节点可以放一个士兵，士兵和 BessieBessieBessie 都可以随意走动。如果士兵和 BessieBessieBessie 在同一点，那么 BessieBessieBessie 就被抓住。而 BessieBessieBessie 如果到达叶节点且一路上没有被士兵抓住，则算 BessieBessieBessie 出逃...
2018-09-17 20:49:32
256
原创 bzoj5188: [Usaco2018 Jan]MooTube （离线+并查集）
Problem给定一棵树，边有边权，定义两点之间距离为两点路径上的最小值。QQQ 次询问，每次询问 ki、vik_i、v_iki、vi，问从 viv_ivi 出发到达每个点时，距离大于等于 kik_iki 的点有多少个Solution将边权、询问中的 kik_iki 从大到小排序。每次将边连起来，并查集合并。询问中，与此点联通的点的个数即为答案Code#include &...
2018-09-17 20:48:53
232
原创 洛谷 P4181 [USACO18JAN]Rental Service （贪心）
Problemnnn 头牛，每头牛能产 cic_ici 加仑的奶。mmm 家商店，每家商店会以 pip_ipi 每加仑的价格进至多 qiq_iqi 加仑奶。rrr 个邻居，每个人会以 wiw_iwi 的价格租一头牛每头牛只能产奶或者租给邻居。问最大收益为多少Solution贪心就好啦把奶牛按产奶量、商店按价格、邻居按价格从大到小排序因为没有特定限制，因此牛肯定产奶越多的用...
2018-09-17 20:48:04
270
原创 洛谷P3806【模板】点分治1 （点分治）
Problem求是否存在权值和等于 KKK 的路径。Solution点分治啊记录路径和为 xxx 的路径的个数容斥一下Code#include <cstdio>#include <algorithm>using namespace std;#define N 10010#define K 10000000#define inf 0x3f3f3f3f...
2018-09-17 20:46:31
224
原创 洛谷 P4188 [USACO18JAN]Lifeguards （线段树）
#Problem给 nnn 个区间，请你删去一个区间，问剩下区间并集最长为多少#Solution线段树维护区间覆盖长度…然后每次删去一个区间看剩下的并集长度，再加上那个这个区间…注意：线段树求区间长度，要把区间定义为左闭右开，这样好做只会插入线段，删去原有线段，因此不需要下放标记什么的updateupdateupdate 时要判断此节点是不是被完全覆盖，而不能直接用左加右。因为没...
2018-09-17 20:45:55
361
原创 洛谷 P1377 [TJOI2011]树的序
Problem求能够生成题目中给的生成二叉查找树的生成序列中字典序最小的Solution最小的显然是把这个二叉查找树生成以后的中序遍历然后我们不能直接插入生成二叉查找树啊…会被卡…方法一：平横树记录有什么树即他的位置，然后查前驱后继，直接连即可方法二：笛卡尔树O(n)O(n)O(n) 建立笛卡尔树…代码如下…Code#include <cstdio>#inclu...
2018-09-17 20:45:20
187
原创 【BZOJ 1468】Tree （点分治）
Problem给你一棵TREE,以及这棵树上边的距离。问有多少对点它们两者间的距离小于等于KSolution点分第一道【捂脸】点分的基本操作就是找重心，做与这个重心相关的信息容斥…Code#include <cstdio>#include <cstring>#include <queue>#include <algorithm>...
2018-09-17 20:44:33
165
原创 bzoj2599：[IOI2011]Race （点分治）
#Problem求权值和等于 KKK 的路径中，边数的最小值。#Solution点分治…用 tmp[i]tmp[i]tmp[i] 表示到重心距离为 iii 的最短边数那么 ans=min(ans,tmp[k−dsum[i]]+d[i])ans=min(ans,tmp[k-dsum[i]]+d[i])ans=min(ans,tmp[k−dsum[i]]+d[i])因此每次求答案，再把结...
2018-09-17 20:42:53
118
原创 bzoj1040: [ZJOI2008]骑士（树形dp）
Problem每个人有一个战斗力值，有一个敌对对象。 每个人不能和他的敌对对象在一个军团。 问选出来的人组成一个军团且不存在敌对对象的最大战斗力和为多少Solution显然会出环（nnn 个点 nnn 条边），假如不考虑环的出现，就是相邻两点不能同时选的树形 dpdpdp 。加上环呢？ 对应本题，会发现之多有一个环…读题可知… 因此 dfsdfsdfs 找到非树边 然...
2018-09-14 20:11:15
113
原创 bzoj1729：[Usaco2005 dec]Cow Patterns 牛的模式匹配（kmp+思维）
Problem有一个 nnn 个数的数列 AAA，其数字范围为 111~k(k<=25)k(k<=25)k(kmmm 个数 BBB。 问从数列 nnn 数列取出连续 mmm 个数，排名与 BBB 中排名一致的情况有多少种Solution我们考虑这个 BBB，将其变成所以可能的序列，然后和原串进行 kmpkmpkmp 可能的序列可以用递归求解… 然而这样肯定复杂度大...
2018-09-14 18:52:16
383
原创 bzoj3306：树（dfn序+线段树+倍增）
Problem支持换根、修改权值的子树最小值查询Solution不考虑换根就是线段树模板题了.. 那么加上换根呢 我们发现换完根，对于原图中大部分子树的最小值是没有关系的 只有 111 到新根上面的点会有变换 新根：为所有点最小值 除新根外此链上的点：除去新根这个外枝的其他所有点…（emmm画个图看一下） 做法就是 dfndfndfn 序建立线段树…倍增找到要除去的部分...
2018-09-14 18:30:45
270
原创 bzoj4069（UOJ110）【APIO2015】Bali Sculptures （数位dp）
Problem把 nnn 个数分成 xxx 组，求每组和的最小按位或值（A&amp;lt;=x=BA&amp;lt;=x=BAf[i][j]f[i][j]f[i][j] 表示前 iii 个数，分成 jjj 段的最小按位或值 f[i][j]=min(f[k][j−1]|sum(k+1,i))f[i][j]=min(f[k][j−1]|sum(k+1,i))f[i][j]=min(f[k][j-1]|sum(...
2018-09-14 18:30:02
143
原创 bzoj4071(UOJ112)【APIO2015】Palembang Bridges （权值线段树）
Problemnnn 个人，住在 AAA 或 BBB 岸，在 AAA 或 BBB 岸上班，距离为坐标相减（如需过河则加一）。 可以修建 k(k<=2)k(k<=2)k(kkkk 只有两种取值，我们分别讨论。k=1k=1k=1 时当我们选择 pospospos 为桥时，所得的结果是 ans=∑i=1nabs(xi−pos)+abs(yi−pos)ans=∑i=1nabs...
2018-09-14 18:29:42
165
原创 bzoj4070(UOJ111)【APIO2015】Jakarta Skyscrapers （拆点+spfa）
Problemmmm 只 dogedogedoge 分布在 nnn 个楼上（均从 000 编号） 每只 dogedogedoge 初始在 bibib_i ，弹跳能力为 pipip_i 如过这只狗在 xxx 的位置，则它可以选择跳到 x+pix+pix+p_i 或 x−pix−pix-p_i 现在 000 这只 dogedogedoge 知道一个信息，想要传给 111 号 dogedoge...
2018-09-14 18:29:22
164
原创 bzoj5195: [Usaco2018 Feb]Directory Traversal（树形dp）
Solution对于每个点，我们给一个权值 viviv_i (文件夹为长度，文件为长度-1) 然后dp就行了.. 转移要向上和向下分别考虑Code#include &lt;cstdio&gt;#include &lt;cstring&gt;#include &lt;algorithm&gt;using namespace std;#define N 100010#...
2018-09-14 18:28:56
190
原创 洛谷P4514 上帝造题的七分钟（二维树状数组）
Solution二维树状数组 求 (x1,y1)(x1,y1)(x_1,y_1) 到 (x2,y2)(x2,y2)(x_2,y_2) 的和 sum=sum[x2][y2]−sum[x1−1][y2]−sum[x2][y1−1]+sum[x1−1][y1−1]sum=sum[x2][y2]−sum[x1−1][y2]−sum[x2][y1−1]+sum[x1−1][y1−1]sum=sum[x...
2018-09-14 18:28:11
210
原创 bzoj5194: [Usaco2018 Feb]Snow Boots （二分+并查集）
Problem有 nnn 块砖，上面有厚度为 aiaia_i 的积雪 有 BBB 双靴子，他能走 didid_i 步，能走积雪小于 viviv_i 的积雪Solution我们可以对于每一双靴子，将积雪量大于靴子能承受的给 111,其余给 000。每个靴子能走 didid_i 步，因此最长连续 111 的长度大于靴子的步数就说明不能走到；反正可以。 问题转化为求最长连续 1...
2018-09-14 18:27:10
155
原创 bzoj 5196: [Usaco2018 Feb]Taming the Herd （dp）
Solution f[i][j]f[i][j]f[i][j] 表示前 iii 天经历出逃了 jjj 次，且第 i+1i+1i+1 天进行了出逃 f[i][j]=min(f[k][j−1]+count(k+1,i))f[i][j]=min(f[k][j−1]+count(k+1,i))f[i][j]=min(f[k][j-1]+count(k+1,i)) 其中 count(x,y)count(x...
2018-09-14 18:26:25
142
原创 牛客网NOIP赛前集训营-提高组（第一场）
题目链接~A 中位数（二分）Problem 求所有大于等于 lenlenlen 的区间的中位数最大可以是多少Solution 我们二分一个答案，对于序列中大于的给 111 ,小于的给 −1−1-1。 若存在某一段的值大于等于 000，则说明这个答案成立 这个问题可以用前缀和来维护Code#include &lt;cstdio&gt;#include &lt;m...
2018-09-12 11:02:49
267
原创 bzoj1181: [CROATIAN2009]IZBROI选举（二分+dp）
Problem一共有 VVV 张投票，nnn 个政党，mmm 个席位。现在每个政党有 aiaia_i 张票。对于每个政党，问通过给这个 nnn 个政党分配剩下的票，使得这个政党得到最多、最少席位是多少个。 席位得分配：对于所有政党，计算一次值：票数÷÷\div(席位数+1+1+1)，然后给值最大的政党一个席位（若值相同，则编号小的政党获得）。重复此过程，直到席位分配完。Solutio...
2018-09-11 15:41:33
335
原创 【51nod 1412】金牌赛事 (线段树优化dp)
problemnnn 条道路每条道路有一个花费，mmm 场比赛，第 iii 场比赛需要用到第 li−rili−ril_i-r_i 条道路，如果这些道路都建立了，可以得到一个花费 问选择其中的一些道路，得到的最大花费是什么题解设 f[i]f[i]f[i] 表示选择选择第 iii 条道路的最大值 因此 f[i]=max(f[j]−cost(j+1,i)+pay(j+1,1))f[i...
2018-09-11 07:56:35
171
原创 bzoj2811: [Apio2012]Guard（二分+差分）
Problem有 nnn 个灌木丛，其中有 kkk 个后面有士兵 mmm 个区间，每个区间zhi’shaSolution首先，我们可以把是 000 的区间删去，然后对序列进行重标号 做法：差分/线段树重标号后，nnn 发生变换 此时这 nnn 个点都是可以放士兵的 那么我们可以特判掉 n=kn=kn=k 的情况然后我们发现如果又两个区间 (l1,r1),(l2,r...
2018-09-11 07:39:31
173
原创 【LightOj 1027】 A Dangerous Maze(II) （概率、dp）
题意同LightOJ 1027 只不过添加一个条件：可以知道前 kkk 个是走的哪个房间 问出去的期望时间题解知道前 kkk 个的意思为走了 kkk 个负数以后，这 kkk 个可以不必走 定义 dp[i]dp[i]dp[i] 表示已经记录 iii 个负数的期望时间 答案即为 dp[0]dp[0]dp[0]下面的讨论中，我们定义 sum1sum1sum1 为正数和， su...
2018-09-11 07:38:57
151
原创 【LightOj 1265】 Island of Survival （概率）
代码#include <cstdio>int T,n,m;int main(){ scanf("%d",&T); for(int tt=1;tt<=T;tt++){ scanf("%d%d",&n,&m); if(n%2) printf("Case %d: 0\n",tt); el..
2018-09-11 07:38:27
117
原创 【LightOj 1030】 Discovering Gold （概率+dp）
题意有 nnn 个格子，每个格子有一个 aiaia_i 值，每次掷筛子（1-6），走相应的步数，问最后得到的期望题解dp[i]=(dp[i+1]6+dp[i+2]6+⋯+dp[i+6]6)+a[i]dp[i]=(dp[i+1]6+dp[i+2]6+⋯+dp[i+6]6)+a[i]dp[i]=(\frac{dp[i+1]}{6}+\frac{dp[i+2]}{6}+\cdots+\f...
2018-09-11 07:37:57
100
原创 bzoj2306: [Ctsc2011]幸福路径 （概率+dp）
题解设 f[t][i][j]f[t][i][j]f[t][i][j] 表示从 iii 到 jjj 走 2t2t2^t 步的最优解 会得到 f[t][i][j]=max(f[t−1][i][k]+f[t−1][k][j]∗p2t−1)f[t][i][j]=max(f[t−1][i][k]+f[t−1][k][j]∗p2t−1)f[t][i][j]=max(f[t-1][i][k]+f[t-1]...
2018-09-11 07:37:30
144
原创 【LightOj 1027】 A Dangerous Maze(II) （概率、dp）
题意同LightOJ 1027 只不过添加一个条件：可以知道前 kkk 个是走的哪个房间 问出去的期望时间题解知道前 kkk 个的意思为走了 kkk 个负数以后，这 kkk 个可以不必走 定义 dp[i]dp[i]dp[i] 表示已经记录 iii 个负数的期望时间 答案即为 dp[0]dp[0]dp[0]下面的讨论中，我们定义 sum1sum1sum1 为正数和， su...
2018-09-10 15:22:28
140
原创 bzoj4318: OSU! （概率+dp）
题解设 f[i]f[i]f[i] 为以 iii 结尾的后缀1长度 g[i]g[i]g[i] 为以 iii 结尾的后缀1长度的平方 h[i]h[i]h[i] 为以 iii 的答案f[i]=(f[i−1]+1)∗p[i]f[i]=(f[i−1]+1)∗p[i]f[i]=(f[i-1]+1)*p[i] 因为 (x+1)2=x2+2x+1(x+1)2=x2+2x+1(x+1)^2=x^2+2...
2018-09-10 15:21:57
115
原创 【LightOj 1038】 Race to 1 Again （概率+dp）
题意有一个数 DDD 每次除以他的一个因数得到一个新的 D′D′D'，问 DDD 变成1的次数的期望题解dp[i]=dp[k]约数个数+1kdp[i]=dp[k]约数个数+1kdp[i]=\frac{dp[k]}{约数个数}+1 \quad k为 iii 的约数 (1−1约数个数)dp[i]=dp[k]约数个数+1k(1−1约数个数)dp[i]=dp[k]约数个数+1k(1-\f...
2018-09-10 15:20:50
92
原创 【LightOj 1027】 A Dangerous Maze （概率）
题意n个点，每个的如为 +x+x+x，则可用 xxx 的时间出去，如为 −x−x-x，则可用 xxx 的时间回到原点。每次随机选一个，问出去的期望时间题解分别考虑出去和回到原点的情况，设总期望为 EEE 一次出去：P1=n正nP1=n正nP_1=\frac{n_{正}}{n} T1=∑x正n正T1=∑x正n正T_1=\frac{\sum{x_正}}{n_{正}} 期望为 P1∗...
2018-09-10 15:20:12
346
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人