3 sunshiness_s

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 5w+

bzoj 2730: [HNOI2012]矿场搭建

Solution先 tarjantarjantarjan 求点双。对于每一个连通块,如果其中没有割点,则说明需要在其中建立两个出口;只有一个割点,那么就需要在非割点处选一个建立出口;如果有大于等于两个割点,则不需要建立出口Code#include <cstdio>#include <cstring>#include <stack>#include ...

2018-09-21 10:34:08

bzoj1879 SDOI2009]Bill的挑战 (状压dp)

Problem求 nnn 个模式串,能匹配其中 kkk 个的字符串的个数匹配的含义为 若为 “?” 则与所以字母都匹配,若为字母,则需相同Solution首先看的 nnn 很小,然后可能使用状压 dpdpdp 来解决a[i][j]a[i][j]a[i][j] 表示第 iii 位这 nnn 个模式串在这一位是 ′a′'a'′a′+jjj 的程度f[i]...

2018-09-21 10:33:34

bzoj1096: [ZJOI2007]仓库建设 (斜率优化dp)

Problem先有一些工厂,每个工厂有一些成品。先要在其中一些工厂的位置建立仓库,建立仓库会有一定的费用。每个没设立仓库的地方将成品运送至下面的仓库,费用为成品数乘距离。山脚一定有一个仓库。问最少需要的花费是多少工厂 iii 距离工厂 111 的距离 xix_ixi​(其中 x1=0x_1=0x1​=0);工厂 iii 目前已有成品数量 pip_ipi​;在工厂 iii 建立仓库的费用 c...

2018-09-19 00:07:49

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

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<=p<=rl<=p<=rl&l...

2018-09-18 21:28:05

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

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

bzoj2144: 跳跳棋 (lca+思维)

Problem有三个棋子在一个一条数轴上,可以使其中一枚为轴,另一枚跳过去,但跳的过程中不能越过第三枚棋子。给定初始状态,问能否达到最终状态,如果可以最少需要几步Solution首先先判断可不可以。我们可以讲初末状态都转变成不能再走的状态,显然对于每种情况这种状态只有一个。那如果不能再继续的状态一样,说明他们肯定是可以通过变换得到的;反之,最终状态都不同,显然不能跳出来…这样我们记录...

2018-09-17 20:51:13

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

bzoj5189: [Usaco2018 Jan]Cow at Large(树形dp)

ProblemBessieBessieBessie 站在一个点,每个叶节点可以放一个士兵,士兵和 BessieBessieBessie 都可以随意走动。如果士兵和 BessieBessieBessie 在同一点,那么 BessieBessieBessie 就被抓住。而 BessieBessieBessie 如果到达叶节点且一路上没有被士兵抓住,则算 BessieBessieBessie 出逃...

2018-09-17 20:49:32

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

洛谷 P4181 [USACO18JAN]Rental Service (贪心)

Problemnnn 头牛,每头牛能产 cic_ici​ 加仑的奶。mmm 家商店,每家商店会以 pip_ipi​ 每加仑的价格进至多 qiq_iqi​ 加仑奶。rrr 个邻居,每个人会以 wiw_iwi​ 的价格租一头牛每头牛只能产奶或者租给邻居。问最大收益为多少Solution贪心就好啦把奶牛按产奶量、商店按价格、邻居按价格从大到小排序因为没有特定限制,因此牛肯定产奶越多的用...

2018-09-17 20:48:04

洛谷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

洛谷 P4188 [USACO18JAN]Lifeguards (线段树)

#Problem给 nnn 个区间,请你删去一个区间,问剩下区间并集最长为多少#Solution线段树维护区间覆盖长度…然后每次删去一个区间看剩下的并集长度,再加上那个这个区间…注意:线段树求区间长度,要把区间定义为左闭右开,这样好做只会插入线段,删去原有线段,因此不需要下放标记什么的updateupdateupdate 时要判断此节点是不是被完全覆盖,而不能直接用左加右。因为没...

2018-09-17 20:45:55

洛谷 P1377 [TJOI2011]树的序

Problem求能够生成题目中给的生成二叉查找树的生成序列中字典序最小的Solution最小的显然是把这个二叉查找树生成以后的中序遍历然后我们不能直接插入生成二叉查找树啊…会被卡…方法一:平横树记录有什么树即他的位置,然后查前驱后继,直接连即可方法二:笛卡尔树O(n)O(n)O(n) 建立笛卡尔树…代码如下…Code#include <cstdio>#inclu...

2018-09-17 20:45:20

【BZOJ 1468】Tree (点分治)

Problem给你一棵TREE,以及这棵树上边的距离。问有多少对点它们两者间的距离小于等于KSolution点分第一道【捂脸】点分的基本操作就是找重心,做与这个重心相关的信息容斥…Code#include <cstdio>#include <cstring>#include <queue>#include <algorithm>...

2018-09-17 20:44:33

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

bzoj1040: [ZJOI2008]骑士(树形dp)

Problem每个人有一个战斗力值,有一个敌对对象。 每个人不能和他的敌对对象在一个军团。 问选出来的人组成一个军团且不存在敌对对象的最大战斗力和为多少Solution显然会出环(nnn 个点 nnn 条边),假如不考虑环的出现,就是相邻两点不能同时选的树形 dpdpdp 。加上环呢? 对应本题,会发现之多有一个环…读题可知… 因此 dfsdfsdfs 找到非树边 然...

2018-09-14 20:11:15

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

bzoj3306:树(dfn序+线段树+倍增)

Problem支持换根、修改权值的子树最小值查询Solution不考虑换根就是线段树模板题了.. 那么加上换根呢 我们发现换完根,对于原图中大部分子树的最小值是没有关系的 只有 111 到新根上面的点会有变换 新根:为所有点最小值 除新根外此链上的点:除去新根这个外枝的其他所有点…(emmm画个图看一下) 做法就是 dfndfndfn 序建立线段树…倍增找到要除去的部分...

2018-09-14 18:30:45

查看更多

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