• 等级
  • 97020 访问
  • 654 原创
  • 1 转发
  • 4719 排名
  • 142 评论
  • 28 获赞

洛谷 P4581 [BJOI2014]想法 随机化

题目描述 小强和阿米巴是好朋友。小强要出一套题目。 他的题目以涉及面广(偏)、考察深入(怪)、思维强度大(难)著称。他为了出题,一共攒了M个本质不同的想法,每个想法形成了一个题目。不过,他觉得拿这些题目去考察选手会把比赛搞的太过变态,所以,想请阿米巴来帮忙调整一下他的题目。 阿米巴指出,为了让一场考试的题目的考察点尽量全面,有一个通用的做法叫做“组合”。如果把两个题目A和B组合在一起,那么组合而成...

2019-01-11 18:41:01

bzoj 4305: 数列的GCD 莫比乌斯反演

Description 给出一个长度为N的数列{a[n]},1<=a[i]<=M(1<=i<=N)。 现在问题是,对于1到M的每个整数d,有多少个不同的数列b[1], b[2], …, b[N],满足: (1)1<=b[i]<=M(1<=i<=N); (2)gcd(b[1], b[2], …, b[N])=d; (3)恰好有K个位置i使得a[i]&l...

2019-01-03 19:41:30

bzoj 3774: 最优选择 最小割

Description 小N手上有一个N*M的方格图,控制某一个点要付出Aij的代价,然后某个点如果被控制了,或者他周围的所有点(上下左右)都被控制了,那么他就算是被选择了的。一个点如果被选择了,那么可以得到Bij的回报,现在请你帮小N选一个最优的方案,使得回报-代价尽可能大。 Input 第一行两个正整数N,M表示方格图的长与宽。 接下来N行每行M个整数Aij表示控制的代价。 接下来N行每行M个...

2019-01-02 19:21:46

bzoj 3237: [Ahoi2013]连通图 并查集+线段树分治

Description Input Output Sample Input 4 5 1 2 2 3 3 4 4 1 2 4 3 1 5 2 2 3 2 1 2 Sample Output Connected Disconnected Connected HINT N<=100000 M<=200000 K<=100000 分析: 对于询问建一棵线段树,每个节点开一个vect...

2018-12-30 08:17:22

bzoj 4269: 再见Xor 线性基

Description 给定N个数,你可以在这些数中任意选一些数出来,每个数可以选任意多次,试求出你能选出的数的异或和的最大值和严格次大值。 Input 第一行一个正整数N。 接下来一行N个非负整数。 Output 一行,包含两个数,最大值和次大值。 Sample Input 3 3 5 6 Sample Output 6 5 HINT 100% : N <= 100000, 保证N个数不全...

2018-12-28 19:39:44

bzoj 2159: Crash 的文明世界 第二类斯特林数+树形dp

题目大意: 给你一棵nnn个点的树,边权都为1。 对于每一个点iii,s(i)=∑j=1ndis(i,j)ks(i)=\sum_{j=1}^{n}dis(i,j)^ks(i)=∑j=1n​dis(i,j)k。 其中kkk给定常数,求所有点的s值。 n≤50000,k≤150n≤50000,k≤150n≤50000,k≤150 分析: 根据斯特林数的一个性质, mn=∑i=1mS(n,i)∗P(m,...

2018-12-28 19:11:07

bzoj 1901 Zju2112 Dynamic Rankings 树状数组套线段树

题目大意: 维护一个数列,要求单点修改以及求区间第kkk大。 n≤104,m≤104,ai∈[0,109]n≤10^4,m≤10^4,a_i\in[0,10^9]n≤104,m≤104,ai​∈[0,109] 分析: 对每一个位置维护一颗权值线段树,然后外面套树状数组即可。 修改直接在数状数组对应位置的线段树修改。查询同主席树。 代码: /*****************************...

2018-12-26 16:48:30

bzoj 3674: 可持久化并查集加强版 主席树

题目大意: 要求维护三种操作。 1 x y1\ x\ y1 x y:合并xxx和yyy所在集合。 2 k2\ k2 k:回到第kkk个操作后的状态。 3 x y3\ x\ y3 x y:询问xxx和yyy是否在一个集合。 强制在线。 n,q≤2∗105n,q≤2*10^5n,q≤2∗105 分析: ...

2018-12-19 17:22:39

bzoj 4327: JSOI2012 玄武密码 AC自动机

题目大意: 给你一个长度为nnn的模板串。qqq个询问,每个询问给一个长度为mmm的字符串,求最长的前缀能在模板串中匹配。 n≤107,q≤105,m≤100n≤10^7,q≤10^5,m≤100n≤107,q≤105,m≤100。 分析: 对每一个串来匹配模板串是O(nq)O(nq)O(nq)的,显然不可行。 考虑用模板串来匹配询问串。对所有询问串建AC自动机,然后把模板串拿上去跑。每走到一个点...

2018-12-18 20:51:32

bzoj 1497: [NOI2006]最大获利 最小割

Description 新的技术正冲击着手机通讯市场,对于各大运营商来说,这既是机遇,更是挑战。THU集团旗下的CS&T通讯公司在新一代通讯技术血战的前夜,需要做太多的准备工作,仅就站址选择一项,就需要完成前期市场研究、站址勘测、最优化等项目。在前期市场调查和站址勘测之后,公司得到了一共N个可以作为通讯信号中转站的地址,而由于这些地址的地理位置差异,在不同的地方建造通讯中转站需要投入的成本...

2018-12-18 17:58:19

bzoj 4592: [Shoi2015]脑洞治疗仪 线段树

Description 曾经发明了自动刷题机的发明家SHTSC又公开了他的新发明:脑洞治疗仪–一种可以治疗他因为发明而日益增大的脑洞的神秘装置。 为了简单起见,我们将大脑视作一个01序列。1代表这个位置的脑组织正常工作,0代表这是一块脑洞。 1 0 1 0 0 0 1 1 1 0 脑洞治疗仪修补某一块脑洞的基本工作原理就是将另一块连续区域挖出,将其中正常工作的脑组织填补在这块脑洞中。 (所以脑洞治...

2018-12-14 18:16:49

bzoj 3251: 树上三角形 lca

Description 给定一大小为n的有点权树,每次询问一对点(u,v),问是否能在u到v的简单路径上取三个点权,以这三个权值为边 长构成一个三角形。同时还支持单点修改。 Input 第一行两个整数n、q表示树的点数和操作数 第二行n个整数表示n个点的点权 以下n-1行,每行2个整数a、b,表示a是b的父亲(以1为根的情况下) 以下q行,每行3个整数t、a、b 若t=0,则询问(a,b) 若t=...

2018-12-11 21:03:09

bzoj 5072: [Lydsy1710月赛]小A的树 dp

题目大意: 给你一棵有nnn个节点的树,每个点是黑点或白点。qqq次询问,询问是否存在一个连通块满足大小为xix_ixi​,有恰好yiy_iyi​个黑点。 n≤5000n≤5000n≤5000,q≤105q≤10^5q≤105,yi≤xi≤ny_i≤x_i≤nyi​≤xi​≤n 分析: 对于每一个点的为根的连通块进行讨论。 设f[i][j]f[i][j]f[i][j]为以iii为根的子树,有jjj...

2018-12-10 21:26:10

bzoj 5073: [Lydsy1710月赛]小A的咒语 后缀数组+dp

题目大意: 给出一个长度为nnn的字符串AAA和一个长度为mmm的字符串BBB。询问是否能从AAA中取出不多于kkk段,使得这些段按原来顺序拼接可以变成字符串BBB。多组数据。 m≤n≤105m≤n≤10^5m≤n≤105,k≤100k≤100k≤100,T≤10T≤10T≤10 分析: 我们设f[i][j]f[i][j]f[i][j]表示用AAA的前iii个字符,取出jjj段,可以拼出的BBB的...

2018-12-10 20:17:54

bzoj 3714: [PA2014]Kuglarz 最小生成树

Description 魔术师的桌子上有n个杯子排成一行,编号为1,2,…,n,其中某些杯子底下藏有一个小球,如果你准确地猜出是哪些杯子,你就可以获得奖品。花费c_ij元,魔术师就会告诉你杯子i,i+1,…,j底下藏有球的总数的奇偶性。 采取最优的询问策略,你至少需要花费多少元,才能保证猜出哪些杯子底下藏着球? Input 第一行一个整数n(1<=n<=2000)。 第i+1行(1&l...

2018-12-10 18:29:20

bzoj 3601: 一个人的数论 莫比乌斯反演+高斯消元

题目大意: 给定n=p1α1∗p2α1∗...∗pwαwn=p_1^{\alpha_1}*p_2^{\alpha_1}*...*p_w^{\alpha_w}n=p1α1​​∗p2α1​​∗...∗pwαw​​和ddd,求 ∑i=1nid[gcd(i,n)==1]\sum_{i=1}^{n}i^d[gcd(i,n)==1]i=1∑n​id[gcd(i,n)==1] 其中,d≤100d≤100d≤10...

2018-12-08 10:17:48

洛谷 P3377【模板】左偏树

题目描述 如题,一开始有N个小根堆,每个堆包含且仅包含一个数。接下来需要支持两种操作: 操作1: 1 x y 将第x个数和第y个数所在的小根堆合并(若第x或第y个数已经被删除或第x和第y个数在用一个堆内,则无视此操作) 操作2: 2 x 输出第x个数所在的堆最小数,并将其删除(若第x个数已经被删除,则输出-1并无视删除操作) 输入输出格式 输入格式: 第一行包含两个正整数N、M,分别表示一开始小根...

2018-12-07 21:50:21

bzoj 3683: Falsita 树链剖分+线段树

Description 描述 到海边了呢… 如果没有那次选择,现在是不是会好些呢… 都过去了。 仰望着星空,迎面吹过一阵阵海风,倚靠着护栏,Fine 在海边静静地伫立着,在一个个无际的长夜后,Fine 终于放下了往事的痛楚,得到了治愈。 但是作为 Fine 的另一重人格的 Falsita 就没那么幸运了。她仍然被各种繁忙的事务困扰着。 虽然同在一副躯体中,Fine 与 Falsita 的精神世界却...

2018-12-07 19:20:44

bzoj 4015: [FJOI2014]树的重心 dp

Description 给定一个n个点的树,每个点的编号从1至n,问这个树有多少不同的连通子树,和这个树有相同的重心。 其中n个点的树指的是n个点的最小连通图,显然n个点的树有n-1条边,去掉这n-1条边中的任何一条,原图都不再联通,任意两个点之间由唯一一条路径相连。 对于一个树,树的重心定义为:删掉某点i后,若剩余k个连通分量,那么定义d(i)为这些连通分量中点的个数的最大值,所谓重心,就是使得...

2018-12-06 20:00:06

bzoj 4002: [JLOI2015]有意义的字符串 数论+矩阵乘法

题目大意: 给出b,d,nb,d,nb,d,n,求 (b+d2)n(\frac{b+\sqrt{d}}{2})^n(2b+d​​)n 其中, 分析: 对于一个数列ana_nan​,满足 an=pan−1+qan−2a_n=pa_{n-1}+qa_{n-2}an​=pan−1​+qan−2​ 则有 an+μan−1=(p+μ)(an−1+μan−2)a_n+\mu a_{n-1}=(p+\mu)(...

2018-12-05 20:44:08

Amber_lylovely

关注
  • 学生
  • 中国 广东省 东莞市
奖章
  • 持之以恒