la1la1la_-CSDN博客

原创 GYM100702 D

题意：有一个n个数字的可重集合，给出2n2^n个子集的和，最多10000种不同的值。问排序后字典序最小原集合。 n<=60#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#include<iostream>#include<algorithm>#define N 11000#define LL lo

2017-06-12 13:14:15 393 1

原创 bzoj3508

题意： T组数据。n个小灯泡，有L种操作方法，第i种表示你能将任意长度恰为Ai的连续一段灯泡的状态取反（灭变亮，亮变灭）。现给定K个点，要求这K个点发光，其余点必须保持熄灭状态。求达到目标状态的最小操作数。 T≤10，N≤10000，K≤10,L≤100,1≤A_i≤N#include<cstring>#include<cstdlib>#include<cstdio>#include<cm

2017-05-09 20:53:11 458

原创 bzoj3233

题意：小蛇是金融部部长。最近她决定制造一系列新的货币。假设她要制造的货币的面值为x1,x2,x3… 那么x1必须为1，xb必须为xa的正整数倍（b>a）。例如 1，5，125，250就是一组合法的硬币序列，而1，5，100，125就不是。不知从哪一天开始，可爱的蛇爱上了一种萌物——兔纸！从此，小蛇便走上了遇上兔纸娃娃就买的不归路。某天，小蛇看到了N只可爱的兔纸，假设这N 只兔纸的价钱分别是a1,

2017-05-09 08:38:28 398

原创 CF806 D

题意：给出n个点完全图，边有边权。枚举x=1~n，找出一棵以x为根的生成树，定义每个点到根的距离di为到根路径上最小的边权，生成树的花费为∑di∑di\sum di。对于每个x，找出最小花费。 n<=2000#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath...

2017-05-08 20:35:48 325

原创 bzoj2219

题意：对于给定的3个非负整数 A,B,K 求出满足 (1) X^A = B(mod 2*K + 1) (2) X 在范围[0, 2K] 内的X的个数 1 <= A, B <= 10^9, 1 <= K <= 5 * 10^8#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#include<iostream

2017-05-08 19:08:51 346

原创 bzoj4820

题意：给出n个互不相同长度为m的01串。有一个序列，初始为空。现在不停在序列尾部等概率添加一个0或1，直到序列后缀匹配n个串中的一个。对于每个01串sis_i，询问序列以sis_i结尾的概率。 n,m<=300#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#include<iostream>#defi

2017-04-23 20:42:42 828

原创 CF607 E

题意：给出平面上n条直线，记它们交点的的点集为s(可重)。给出点p(x,y)，询问s中与p欧几里得距离前m近的点和p的距离和。 n<=50000 m<=30000000#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#include<iostream>#include<algorithm>#defi

2017-04-23 11:39:27 427

原创 CF650 E

题意：给出两棵树，要求将第一棵变成第二棵。可以进行的操作是删除一条边，再加入一条边。要求每次操作后仍是一棵树。问最小操作次数和方案。 n<=500000#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#include<iostream>#include<vector>#define N 510000

2017-04-20 11:22:04 460

原创 bzoj3677

题意：在达芬奇时代，有一个流行的儿童游戏称为连珠线。当然，这个游戏是关于珠子和线的。线是红色或蓝色的，珠子被编号为 1 到 n。这个游戏从一个珠子开始，每次会用如下方式添加一个新的珠子： Append(w, v)：一个新的珠子 w 和一个已经添加的珠子 v 用红线连接起来。 Insert(w, u, v)：一个新的珠子 w 插入到用红线连起来的两个珠子 u,v 之间。具体过程是删去 u,v

2017-04-20 09:35:53 494 3

原创 bzoj3467

题意： n<=100000#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#include<iostream>#include<algorithm>#define N 110000#define maxd 16#define base 233#define lowbit(x) (x&(-x))

2017-04-19 16:29:15 360

原创 CF800 C

题意：在模m的意义下，ban掉n个数。构造一个最长的数列，使得： 1、前缀之积两两不等 2、前缀之积不能出现n个被ban的值 n< m<=200000#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#include<iostream>#include<vector>#define N 410000

2017-04-17 10:08:05 346

原创 GYM100524 H

题意：给一棵n个点二叉树，要求支持删除叶节点同时维护轻重链剖分。m表示依次删除m个叶节点，删除每个节点后输出重孩子的标号和。 m< n<=200000#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#include<iostream>#define N 210000#define LL long lo

2017-04-11 19:24:05 408

原创 GYM100608 J

题意：在一个n*m的四联通网格中有一个凸的联通块。当一个联通块与每行每列的交都是线段时，我们称它是凸的。对于两个点x和y，J(x,y)表示从x到y最少拐几个弯。询问max(J(x,y))。 n,m<=2000#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#include<iostream>#defin

2017-04-11 12:57:41 458

原创 GYM100524 G

题意： Alice和Bob在玩一个在链上染色的游戏。A能把点染成黑色，B能染成白色。A先手。两人轮流选一个当前没有染色的点染，要求相邻两点颜色不同，不能操作输。现在有n条链，第i条长度为ai，从中选出m条来玩，问有多少种选法先手必胜。 m<=n<=100 ai<=10^9#include<cstring>#include<cstdlib>#include<cstdio>#include<

2017-04-10 09:41:17 372

原创 GYM100524 E

题意：在数轴上有n个村子感染了ebola，你要去治疗他们。具体来说，一开始你在1号村子。每天，如果你在村子x，你可以选择治疗村子x的人，或移动到x-1或x+1。每天结束时，如果村子i没有被治疗过，这个村会有ai人死亡。特别的，如果某天你选择了跨过一个没治疗的村子，那你下一次回头时一定要回来治疗这个村子。就是去的时候治疗了2和4，那第一次回头后，在治疗1和3前不能再回头。问最少死亡人数

2017-04-10 08:37:57 354

原创 bzoj4147

题意： Euclid和Pythagoras在玩取石子游戏，一开始有n颗石子。 Euclid为先手，他们按如下规则轮流操作： ·若为Euclid操作，如果n< p，则他只能新放入p颗石子，否则他可以拿走p的倍数颗石子。 ·若为Pythagoras操作，如果n< q，则他只能新放入q颗石子，否则他可以拿走q的倍数颗石子。拿光所有石子者胜利。假设他们都以最优策略操作，那么获胜者是谁？第一行

2017-04-07 08:33:53 370

原创 GYM101002 A

题意：有n个物品，m个商店。每个物品会在两个商店x，y中按不同价钱p，q出售。现在最多能去k个商店，问每个物品买一件最少要多少钱。无解输出-1。 1<=x,y<=n<=100 k<=m<=40 p,q<=10^7#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#include<iostream>#d

2017-04-05 19:49:27 380

原创 AGC007 E

题意：给出一棵n个节点树，除了叶节点，每个节点恰好有两个孩子。边上有边权。第一天根开始走，每天选一个叶节点，从当前点走到叶节点，最后一天走回根节点。要求每条边经过两次，每个叶节点被选一次。花费就是除了第一天和最后一天走的路程最远那一天的路程。问最小花费。 2< n< 131,072#include<cstring>#include<cstdlib>#include<cstdio>#inc

2017-04-02 10:17:46 704

原创 CF500 G

题意：有一棵树，n个点，边长为1，m个询问。每个询问(x,y,u,v)表示一个人从x开始，不停的在(x,y)间往返跑，另一个人从u开始在(u,v)间往返跑，两人每秒的速度都是1，问什么时候第一次在某个节点上相遇。 n,m<=200000#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#include<io

2017-03-31 17:39:48 375

原创 AGC006 C

题意：从前数轴上有n只兔子，第i只的位置在xi。定义一个set包含m个操作，每个操作ai表示第ai只兔子在ai+1a_{i+1}和ai−1a_{i-1}中等概率选一只兔子，记为x，然后跳到关于x的对称点。问进行k个set的操作后，每只兔子的期望位置。 n,m<=100000 k<=10^18 xi<=10^9 2<=ai<=n-1#include<cstring>#include<cs

2017-03-31 08:59:40 410

原创 AGC006 D

题意：给出一个长度为2*n-1的排列，将除了头尾两个数变为相邻3个数的中位数，重复n-1次。像这样问最上面的数字是多少。 n<=100000#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#include<iostream>#define N 210000using namespace s

2017-03-30 22:02:34 902

原创 AGC006 E

题意：有3行n列的格子，里面的数是1~3n。每次可以选一个3*3的格子旋转180度。给出初始状态，问能不能变成第i行第j列是3*(j-1)+i的状态。 n<=100000#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#include<iostream>#include<algorithm>#defi

2017-03-30 20:08:54 745

原创 CF500 F

题意：给出n，p。表示n个物品，每个物品有ci，hi，ti表示花费ci，价值hi，从时刻ti开始可以买。所有物品的出售时间都是[ti,ti+p-1]。然后m个询问，每个询问ai，bi表示ai时刻去购物，有bi的钱，最大价值是多少? n<=4000 p,ti<=10000 ai,m<=20000 bi<=4000#include<cstring>#include<cstdlib>#in

2017-03-30 14:56:57 421

原创 AGC005 D

题意：给出n，k，问有多少个长度为n的排列满足abs(ai−i)!=kabs(a_i-i)!=k。 n<=2000 1<=k<=n-1#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#include<iostream>#define N 2100#define mmod 924844033usin

2017-03-29 15:17:16 853

原创 AGC005 E

题意： n个点，n-1条红边，n-1条蓝边。红边构成一棵树，蓝边构成一棵树。开始时，A在点x，B在点y。两人轮流操作，A先手。A可以不动或沿红边走，B可以不动或沿蓝边走。当A、B走到同一个点时游戏结束。A想玩的尽量久，B想尽量快。问会进行多少轮，无限输出-1。 n<=200000题解：先把以y为根把B的树建出来。对于A的一条边(x,y)，x和y在B的树上距离>2，如果A走到x或y之前或下一轮

2017-03-29 11:43:46 637

原创 AGC004 F

题意：给出一个无向无自环无重边连通图，n个点，m条边。有黑白两种颜色，初始全白。每次操作选相邻的两个同色点，把他们变成另一种颜色。现在要将所有点变成黑色，问是否有解。如果有，问最少操作次数。 n<=10^5 m=n或m=n-1题解：出题人脑洞好大。。先考虑树的情况，转换一下模型。由于树是二分图，我们可以给每个点标上0或1。然后发现原操作就变成了交换两个相邻的0和1，目标是让原来为0的

2017-03-28 15:08:45 905 1

原创 AGC003 E

题意：有一个长度为n的序列，初始为1~n。m个操作，每个操作ai表示把当前序列复制无限次，然后取前ai个数作为新序列。问最终序列里1~n各出现多少次。 n,m<=10^5 ai<=10^18题解：感觉做法很不显然，真不知道出题人怎么想的。。最开始先取一次n，方便处理。发现如果ai>=ai+1a_i>=a_{i+1}那么ai是无效的，把序列变成严格上升的。然后令t[i]为第i

2017-03-28 09:25:55 742

原创 hdu5803

题意：给出A、B、C、D。问有多少(a,b,c,d)，满足： a+c>b+d && a+d≥b+c && 0≤a≤A && 0≤b≤B && 0≤c≤C && 0≤d≤D T≤1000 0≤A,B,C,D≤10^18题解：一开始觉得是分类讨论，化柿子化得有点想吐。。然后看了题解，说可以数位dp，那就dp吧。。注意10^4枚举每位太慢，转成二进制后就是2^4的了

2017-03-07 21:07:21 409

原创 hdu5798

题意：给出一个n个数数列A，让你选一个数x，把ai变成ai xor x，使： ∑n−11|ai−ai+1|\sum_1^{n-1}|a_i-a_{i+1}|最小 n<=10^5,ai<=2^20题解：一开始看错题了，以为每个数可以选择变不变，看题解的时候一脸懵逼。。我怎么觉得这题比5796、5797难啊这题挺不错的，就是考虑拆开绝对值算贡献 ai和ai+1的绝对值怎么拆是在最高的一

2017-03-06 22:13:12 420

原创 hdu5797

题意：有一个n*m的网格。对于i=1~n，给出Li，Ri，表示第i行的Li到Ri列涂成黑色。保证Li≤Li+1,Ri≤Ri+1。问最少选多少个格子，能让每个黑色的格子，要么同一行选了至少一个格子，要么同一列选了至少一个格子。 n,m<=100题解：贪心选最右端是错的～～反例就是从这个栗子也可以看出，对于一行，如果我们没在这行中选，那么一定是前面的覆盖了他的前缀，后面的覆盖了他的后缀

2017-03-06 19:15:13 383

原创 hdu5796

题意：给出n个二进制数，第i个数是ai，长度是i。然后跑这个：又给出q个二进制数，第i个数是ci，长度是leni。再然后跑这个(代码中n其实是q)：对于每个d，问有多少个二进制位为1 n,q<=5000题解：看懂题意后容易想到传递闭包，就是把or改成and，上bitset的话O(n332)O(\frac{n^3}{32})。似乎不是很资磁就膜了题解。。考虑构造一颗树，节

2017-03-06 18:09:39 441

原创 bzoj3565

题意：超能粒子炮由垂直方向从上到下共 n 个超能粒子发射管构成,编号 1~n。所有的发射管都会在开火的一瞬间同时发射出强大的超能粒子流。为了彻底摧毁再生能力极强的邪恶宇宙怪物 CCM,地球联合军将 CCM 从上到下分为 m 个区域, 编号 1~m,分别进行打击。其中超能粒子炮的第 i 号发射管将会对准 f(i)号区域发射。f(i) 的公式如下: f(i) = (a * i + b) mod

2017-03-01 13:34:28 527

原创 hdu6017

题意：话的长度为n，语句里的字符不是2就是3。呃喵的智力非常有限，只有m点。她每次操作可以交换两个相邻的字符，然而代价是智力-2。现在问你，在使得自己智力不降为负数的条件下，呃喵最多能使这个字符串中有多少个子串”233”呢？如”2333”中有一个”233”，”232323”中没有”233” 1 <= n <= 100, 0 <= m <= 100题解：一看到正解是O(n4)O(

2017-02-27 15:44:03 450

题意: 话说Nan在海边等人，预计还要等上M分钟。为了打发时间，他玩起了石子。 Nan搬来了N堆石子，编号为1到N，每堆包含Ai颗石子。每1分钟，Nan会在编号在[Li,Ri]之间的石堆中挑出任意Ki颗扔向大海（好疼的玩法），如果[Li,Ri]剩下石子不够Ki颗，则取尽量地多。为了保留扔石子的新鲜感，Nan保证任意两个区间[Li,Ri]和[Lj,Rj] ，不会存在Li<=Lj & Rj<=Ri的情

2017-02-24 22:02:56 784

原创 bzoj1290

题意：对于100%的数据, N ≤ 500000, Q ≤ 109, 1≤ A, B ≤ Q。题解：看完题后我想起了这道http://codeforces.com/problemset/problem/280/E 都是单峰，这题还是一次的，不过不能写O(n2)O(n^2)的了好吧。。平衡树肝吧。。 %claris有一种很厉害的做法。。看不懂，似乎因为xi递增极值点也是递增的？

2017-02-24 12:32:48 376

原创 CF765 F

题意：给一个长度为n序列。m个询问(l,r)，询问min(abs(ai-aj))(l<=i< j<=r)。 n<=10^5 m<=3*10^5 题解：膜了题解。。讨论右端点较大的情况，左端点较大同理考虑右端点右移，维护所有左端点答案当移到位置i时，需要用ai去更新答案先找到离i最近的一个j，使ai>aj，这时ai-aj能用来更新[1,j] 再考虑j前面的一个k(j>k

2017-02-20 17:56:35 656

原创 CF765 D

题意：让[n]代表[1,n]的所有整数给出n与函数f的函数值。f定义域为[n]，值域属于[n] 求m，函数g，函数h，使得： 1、g的定义域为[m]，值域属于[n] 2、h的定义域为[n]，值域属于[m] 3、g(h(x))=x，对于x属于[m] 4、h(g(x))=f(x)，对于x属于[n] n<=10^5 题解：我觉得这题挺难的呀为什么比赛的时候那么多人会做。。首先

2017-02-16 18:32:06 520

原创 bzoj3711

题意：体育课上，n个小朋友排成一行（从1到n编号），老师想把他们分成若干组，每一组都包含编号连续的一段小朋友，每个小朋友属于且仅属于一个组。第i个小朋友希望它所在的组的人数不多于d[i]，不少于c[i]，否则他就会不满意。在所有小朋友都满意的前提下，求可以分成的组的数目的最大值，以及有多少种分组方案最大,对10^9+7取模。 1<=n<=1000000 题解：这题太神啦。。我

2017-02-07 22:45:22 1030 2

原创 CF388 D

题解：一个自然数集合SS，如果对于所有a∈S，b∈Sa\in S，b\in S都有(a(a xorxor b)∈Sb)\in S，则称S是perfect set。给出n，问有多少个perfect set元素都小于等于n。 n<=10^9 题解： O__O 每个perfect set都可以找出一组基是吧。。用一种奥妙重重的消元方式能使不同的perfect set消出不同且唯一的基(脑补

2017-01-25 17:07:10 1370

原创 CF757 E

题意：有函数f0,n=将n分解为两个互质的数的积的方案数f0,n=将n分解为两个互质的数的积的方案数f_{0,n}=将n分解为两个互质的数的积的方案数 fr,n=∑fr−1,u+fr−1,v2(uv=n)fr,n=∑fr−1,u+fr−1,v2(uv=n)f_{r,n}=\sum \frac{f_{r-1,u}+f_{r-1,v}}{2}(uv=n) m组询问，给出r，n，求fr,nfr,...

2017-01-15 09:17:05 1898

空空如也

空空如也