- 博客(42)
- 收藏
- 关注
RSS订阅转载 51Nod 1778 小Q的集合
题解： 感觉这题很妙，来搬运一波题解。 拆式子看起来很暴力，但是细想一下其实非常自然。 方差是数值与期望差的平方的期望。由对称性显然有期望为0。只需要求： 首先模数很小，自然想到卢卡斯定理：C(n,m)=C(n/p,m/p)*C(n%p,m%p) (mod p) C(n,i...
2018-03-31 20:29:58
339
原创 Codeforces 193D. Two Segments
题意： 给定一个全排列，求有多少个区间[l,r]，使得可以在全排列中选择两个连续序列，使得两个序列合并并排序后恰好是[l,r]。题解： 记f(l,r)表示要在全排列中恰好选到[l,r]区间的数，至少要多少个连续序列。显然，当f(l,r)<=2且l<r时是合法区间。 考虑从f(l,r)转移到f(l,r+1)。 若(r+1)不和f...
2018-03-30 20:56:17
291
原创 Codeforeces 957E. Contact ATC
题意： 有n架飞机，第i架飞机位于x[i]，速度为v[i]，x[i]*v[i]<0。当风速为t时，这架飞机速度为(v[i]+t)。给定t的取值范围[-w，w]，abs(w)<min(abs(v[i]))。求有多少对飞机存在满足条件的风速，使这对飞机同时飞过原点。题解： 首先要糊一个结论：对于一对飞机，如果风速分别为w和-w时，两个飞机分别先到达原点，那么存在风速...
2018-03-26 21:09:21
437
原创 Codeforces 955C. Sad powers
题意： 给定L，R，求[L，R]内有多少个数x满足存在a>0,p>1使得x=a^p。题解： 明明很简单的一道题，比赛的时候意识模糊被卡精+卡常卡到死。 记f(x)为[1,x]的答案，a[i]表示x以内，i次方数的个数，然后暴力莫比乌斯函数跑容斥就OK。 说说死在哪里了：这题的log是1e18的，如果求a[i]的时候用二分会TLE（开O(松...
2018-03-26 20:59:34
365
原创 Codeforces510E Fox And Dinner
题意： 有n(不大于200)只狐狸，每只狐狸有权值(2到10000)。将所有狐狸分配到若干圆桌上，使得每个圆桌上至少坐三只狐狸，且相邻狐狸权值和为质数。如果可行逆时针输出方案。题解： 奶了一口Div2怎么会考网络流，然后就…… 由于权值大于1，为保证相邻权值和为质数，所以每个圆桌上必然是奇数、偶数相邻坐。即：每个奇数要匹配两个偶数，每个偶数要匹配两个奇数。那么按...
2018-03-17 12:14:37
202
1
原创 BZOJ4504 K个串
Description兔子们在玩k个串的游戏。首先，它们拿出了一个长度为n的数字序列，选出其中的一个连续子串，然后统计其子串中所有数字之和（注意这里重复出现的数字只被统计一次）。兔子们想知道，在这个数字序列所有连续的子串中，按照以上方式统计其所有数字之和，第k大的和是多少。Input第一行，两个整数n和k，分别表示长度为n的数字序列和想要统计的第k大的和接下里一行n个数a_i，表示这个数字序列Ou...
2018-03-16 16:37:38
206
原创 BZOJ4502 串
Description兔子们在玩字符串的游戏。首先，它们拿出了一个字符串集合S，然后它们定义一个字符串为“好”的，当且仅当它可以被分成非空的两段，其中每一段都是字符串集合S中某个字符串的前缀。比如对于字符串集合{"abc","bca"}，字符串"abb"，"abab"是“好”的"abb"="ab"+"b",abab="ab"+"ab&quo
2018-03-16 07:46:34
258
原创 BZOJ3451 [Tyvj1953] Normal
Description某天WJMZBMR学习了一个神奇的算法：树的点分治！这个算法的核心是这样的：消耗时间=0Solve(树 a) 消耗时间 += a 的 大小 如果 a 中 只有 1 个点 退出 否则在a中选一个点x，在a中删除点x 那么a变成了几个小一点的树，对每个小树递归调用Solve我们注意到的这个算法的时间复杂度跟选择的点x是密切相关的。如果x是树的重心，那么时间复杂度就是O(nlog...
2018-03-14 15:19:35
366
原创 BZOJ2658 [ZJOI2012]小蓝的好友(mrx)
Description终于到达了这次选拔赛的最后一题，想必你已经厌倦了小蓝和小白的故事，为了回馈各位比赛选手，此题的主角是贯穿这次比赛的关键人物——小蓝的好友。在帮小蓝确定了旅游路线后，小蓝的好友也不会浪费这个难得的暑假。与小蓝不同，小蓝的好友并不想将时间花在旅游上，而是盯上了最近发行的即时战略游戏——SangoCraft。但在前往通关之路的道路上，一个小游戏挡住了小蓝的好友的步伐。“国家的战争其...
2018-03-13 19:22:16
214
原创 BZOJ3598 [Scoi2014]方伯伯的商场之旅
Description方伯伯有一天去参加一个商场举办的游戏。商场派了一些工作人员排成一行。每个人面前有几堆石子。说来也巧，位置在 i 的人面前的第 j 堆的石子的数量，刚好是 i 写成 K 进制后的第 j 位。现在方伯伯要玩一个游戏，商场会给方伯伯两个整数 L,R。方伯伯要把位置在 [L, R] 中的每个人的石子都合并成一堆石子。每次操作，他可以选择一个人面前的两堆石子，将其中的一堆中的某些石子移...
2018-03-09 14:08:44
267
原创 BZOJ3597 [Scoi2014]方伯伯运椰子
Description Input 第一行包含二个整数N，M接下来M行代表M条边，表示这个交通网络每行六个整数，表示Ui,Vi,Ai,Bi,Ci,Di接下来一行包含一条边，表示连接起点的边Output一个浮点数，保留二位小数。表示答案，数据保证答案大于0Sample Input5 101 5 13 13 0 4122 5 30 18 396 1481 5 33 31 0 394 5 22 4 0 ...
2018-03-09 12:10:09
162
原创 BZOJ1503 [NOI2004]郁闷的出纳员
DescriptionOIER公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。这本来是一份不错的工作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。工资的频繁调整很让员工反感，尤其是集...
2018-03-06 21:11:27
128
原创 BZOJ4681 [Jsoi2010]旅行
DescriptionWJJ喜欢旅游，这次她打算去一个据说有很多漂亮瀑布的山谷玩。WJJ事先得到了一张地图，上面标注了N(1< = N< = 50)个小动物的聚居地，也就是一个个的小村落。其中第1个村庄是WJJ现在住的地方，第N个村庄是WJJ打算去的地方。这些村庄之间有M(1< = M< = 150)条双向道路连接着，第j条双向道路恰好直接连接两个小村庄A，B，长度为C(1...
2018-03-03 10:57:04
328
原创 BZOJ2325 [ZJOI2011]道馆之战
Description口袋妖怪(又名神奇宝贝或宠物小精灵)红/蓝/绿宝石中的水系道馆需要经过三个冰地才能到达馆主的面前，冰地中的每一个冰块都只能经过一次。当一个冰地上的所有冰块都被经过之后，到下一个冰地的楼梯才会被打开。三个冰地分别如下：当走出第三个冰地之后，就可以与馆主进行道馆战了。馆主发现这个难度太小，导致经常有挑战者能通过，为了加大难度，将道馆分成了n个房间，每个房间中是两个冰块或障碍，表示...
2018-02-27 16:44:50
453
原创 BZOJ2324 [ZJOI2011]营救皮卡丘
Description皮卡丘被火箭队用邪恶的计谋抢走了！这三个坏家伙还给小智留下了赤果果的挑衅！为了皮卡丘，也为了正义，小智和他的朋友们义不容辞的踏上了营救皮卡丘的道路。火箭队一共有N个据点，据点之间存在M条双向道路。据点分别从1到N标号。小智一行K人从真新镇出发，营救被困在N号据点的皮卡丘。为了方便起见，我们将真新镇视为0号据点，一开始K个人都在0号点。由于火箭队的重重布防，要想摧毁K号据点，必...
2018-02-26 18:51:40
172
原创 BZOJ2323 [ZJOI2011]细胞
Description2222年，人类在银河系外的某颗星球上发现了生命，并且携带了一个细胞回到了地球。经过反复研究，人类已经完全掌握了这类细胞的发展规律：这种细胞最初的形态是“长条形”，一端是头，一端是尾，中间是躯干。细胞内部含有一列密码（你可以认为它是这种细胞的DNA）。密码是一个长度为n的数字串，且仅含有1~9这9种数字，沿着细胞的躯干从头到尾排列着。首先，细胞会经历一次分裂。细胞将沿躯干方向...
2018-02-26 18:26:05
213
原创 POJ 1275 Cashier Employment
题意： n个人应聘出纳员，每个人从t[i]开始工作8小时结束。给你每个小时至少需要的人数r[i]，问最少招聘的人数题解： 差分约束+建模。 由于需要考虑的是时间段，于是运用前缀和将时间点转化为时间段，令s[i]表示1时至i时招聘的总人数。 令t[i]表示应聘i时的人数，r[i]表示i时需要的人数，时间为0时到24时，根据题意就有： ...
2018-02-26 13:04:39
168
原创 BZOJ 2768 [JLOI2010]冠军调查
题解： 一道挺水的最小割，然而并不会做。 建立超级源汇点，希望切尔西赢的从S向它连容量为1的边，希望切尔西输的从它向T连容量为1的边。在朋友之间连一条双向边，答案就是最小割。 如果存在一条从S到T的路径，相当于产生了冲突。必须说谎（割掉到S或T的边）或者与朋友意见不统一（割掉和朋友的边）#include<set>#include<map>...
2018-02-24 14:59:06
169
转载 Codeforces 935E Fafa and Ancient Mathematics
题意： 给定一个只含一位数和问号的表达式，在问号中填入共p个+和m个-，求表达式的最大值，min(p,m)<=100。题解： 从http://blog.csdn.net/Charlie_jilei/article/details/79343580看来的。 比赛的时候看出来是树形DP，但是码力太差打不出来，这个实现比较精巧。 先用表达式树把它变成...
2018-02-23 11:37:24
392
原创 CodeForces 367C Sereja and the Arrangement of Numbers
题意： 给出m个不同的数，并且每个数都有个费用，现在要在m个数中选择一些数（每个数可使用任意多次），用这些数组成一个长度为n的数列，并且满足任意两个不同种类的数都相邻。问最大的费用是多少。题解： 关键在于确定：使数列中有k个不同的数，数列的最小长度是多少。由于任意两个不同种类的数都相邻，联想到完全图的欧拉回路，即走过多少条边可以使每条边都经过一次，显然次数+1就是最小长度。...
2018-02-10 21:20:33
201
原创 Codeforces 686D. Kay and Snowflake
题意： 给定一颗n个节点的树，q次询问，每次询问以节点x为根的子树的重心。n,q<=300000题解： 又糊了一个和标算不一样的做法。 标算：根据重心的一个性质：把两棵树通过某一点相连得到一颗新的树，新的树的重心必然在连接原来两棵树重心的路径上。对于我们从点1开始往下进行遍历，返回的时候就可以可以看成一颗树与另一颗树相连求重心。 我的算法：考虑...
2018-02-10 21:03:24
289
原创 POJ 3131 Cubic Eight-Puzzle
题意： 给你八个正方体，放于九宫格内，每个正方体相对面同色。每次可以将一个正方体翻滚到相邻空位，求使从高处向下看为给定的目标状态的最小移动次数。如果30步内不能到达判定无解。题解： 三维八数码问题，明显是一道搜索题。 先考虑状态数：空位有9种位置，每个正方体有6种放置方法，共15116544种状态。如果只有一组数据的话广搜就可以直接搜过去。 那么可以...
2018-02-09 18:06:59
255
2
原创 SGU 189 Perl-like Substr
题意：http://blog.csdn.net/qq_20118433/article/details/42618825题解： 一道比杀蚂蚁清真到不知道哪去的字符串模拟题。 一开始读入字符串的时候整行读入，然后扫一遍去掉空格、分号和换行符。 代码中最核心的是string Substring(string &sx,int l,int r)函数，它将sx字符串...
2018-02-08 21:38:21
217
1
原创 HDU 6212 Zuma
题意： 给你一个只有01的祖玛，问最少几步可以全部消完。题解： 明显是区间DP。先将所有相邻的01合并，得到一个12串，用f[i][j]表示将区间[i,j]消完的最小代价。 下面考虑转移。一开始考虑枚举区间[i,j]内所有点，选择一点k，再讨论是将其左右两边分别消掉，还是将其暴力消去，预处理其左右两边会消掉的长度t，然后将[i,k-t-1]和[k+t+1,...
2018-02-08 07:47:00
188
原创 [SDOI2009]SuperGCD
题解：今天XJ考试的时候放了这道题的削弱版：n后来看了一下题解，有一个有用的性质，正确性非常显然：a % 2 = 0， b % 2 = 0，则(a,b)=2*(a/2,b/2)a % 2 = 0， b % 2 = 1，则(a,b)=(a/2,b)a % 2 = 1， b % 2 = 0，则(a,b)=(a,b/2)a % 2 = 1， b % 2 = 1，则(a,b)=(b
2018-02-05 15:22:29
243
原创 POJ 1475 Pushing Boxes
题意： 给你一张地图，把箱子推到目的地，要求在推箱子次数最少的前提下最小化走的路程。输出方案。题解： 这题网上有很多A*和嵌套bfs的做法。事实上Dijkstra解决这道题也十分优越。 用状态dis[a][b][c][d]表示人处于(a,b)这个点，箱子处于(c,d)这个点的最小费用。费用的定义是推箱子的费用+人行走的费用。我们将一次推箱子的费用设置成10000，而人走一次的费
2018-02-04 11:19:19
254
原创 HDU 4424 Conquer a New Region
题意： 给定一棵带边权的树，任选一个起点，定义其余所有的点权为起点到该点路径中最短边的长度，最大化点权和。题解： 点权由最短边决定，所以考虑将边从大到小排序。每加入一条边就是合并两个连通块。设这两个连通块分别为A、B，则合并后的连通块C价值为：max(val[A]+length*size[B],val[B]+length*size[A])。用并查集维护一下即可.#include
2018-02-03 18:26:47
150
原创 [ZJOI2008] 杀蚂蚁(BZOJ上未过)
dark模拟题。 计算几何一片空白判线段和圆是否相交来来回回改了五六次，代码也写得很长（还有一部分原因是码风问题233） 提交记录非常鬼畜：先在Codevs上WA40，把inline全部去掉就AC了；再到洛谷上还是WA40，把O2关掉变成80，数组开大点就AC了。但是BZOJ上还是WA。 如果哪位大佬帮我看出哪里有点问题（也有可能是比较危险的未定义行
2018-01-09 13:39:02
210
原创 BZOJ 1997 [Hnoi2010] Planar
校内讲课被分到图的连通性算法了。学算法+做PPT搞了一个星期……题解： 首先平面图的一个性质：E 每一条边，只有从环外走和从环内走两种选择。如果两条边都从环内走会相交，那么必然有一条边要从环外走。从而这道题被转化成了2-SAT。#include#include#include#include#include#include#include#
2018-01-04 11:35:04
162
原创 Good Bye 2017
前记 到了该和2017说告别的时候。也许这是我长大以来经历的最多的一年吧。好好回望一下2017，希望在2018收获一个更好的自己。回忆一、 初二上的期末考后吧。靠着普及混的二等奖搞到一个考湖创班的名额。能跟初三的抢名额好开心啊。期末考试前两个星期开始学习化学……并没有告诉班主任要去考试的事情，认真地备考期末，考湖创前发现连硫酸的化学式都不会（yeah）。期末考混了个年级前十...
2017-12-29 22:56:44
356
2
原创 BZOJ1002 [FJOI2007]轮状病毒
题解：限于我的水平，推导可能会有纰漏，欢迎批评指正一点想法：这题的推导并不困难，所用的行列式内容也只是基础。蒟蒻在花了两天学习了行列式基础（一天在暑假，一天是今天），远不及行列式的精髓内容，但已经能够独立推导出这道题。但即便这样，这题的行列式推导解法却也是寥寥无几(orz VFK大佬)(似乎也有巧妙的DP解法)。诚然，这题用打表比推式子计算要快得多，考试的时候是首选。但是如果在平时的训练中也只是一...
2017-12-22 21:38:33
200
原创 BZOJ1001 [BeiJing2006]狼抓兔子
题解：明显是求最小割。但点数1e6正解显然不是直接上网络流。于是学习了一发s-t平面图的最小割.(2008集训队论文 周冬《两极相通——浅析最大—最小定理在信息学竞赛中的应用》)大致是将原平面图的每个面作为对偶图的一个点，每条边变为连接左右两个面的边，那么对偶图中的一个环就对应原图的一个割（相当于把几个点切下来）。给定源汇点后，在平面图从s向t连一条长为inf的边，这条边与原边会形成一个面，对应对...
2017-12-21 19:16:17
161
原创 HDU5314 Happy King
题意：给定一颗树，每个点有点权，求有多少个点对(u,v)满足u到v的路径中点权最大值与最小值之差不大于D被题意杀了一天......一开始以为(u,v)和(v,u)算一种，(u,u)也算一种方案，样例过了结果wa了一天。实际上是前者算两种后者不算题解：应该是一个很裸的点分治+二维偏序吧统计答案是记录分治中心到每个点的最大最小值，然后相当于对于每个点（mini,maxi）统计有多少个点对j满足（min...
2017-12-19 09:18:25
223
原创 Codevs1227 方格取数2
周六zrf要讲网络流啊，像我这种蒟蒻不预习一下肯定全程掉线。题解：首先是一种建模的思想：将每个点拆成出入两个点。取k次，相当于流出一条大小为k的流。流过一个点即将这个点的数取走。因为每个点可以流经多次，但只能产生一次贡献，所以我们从所有入点向所有出点连一条容量为1的边，价值为点的权值。然后将出入点都向右边和下方的点的入点连一条容量为inf，价值为0的边，跑最小费用最大流即可。几个细节：1、有两个源...
2017-12-15 19:24:36
215
2
原创 HDU6231 K-th Number
给定一个长为n的序列,对于每个长度大于等于k的区间,取出其第k大的元素,问所有取出的元素中,第m大的那个是多少考虑二分答案x，则问题转化为求是否有不少于m个区间满足：不少于k个数大于等于x。考虑使用尺取法做这个判断。枚举左端点l，找出一个最小的r使其满足条件，则[r,n]中所有点都是符合条件的右端点。由于r的选择具有单调性，我们就可以在O（n）的时间内完成判断。复杂度O(n*log)（突然感觉改了...
2017-11-18 01:49:00
270
原创 BZOJ3594 [Scoi2014]方伯伯的玉米田
题目描述题解: 先考虑ＤＰ：f[i][j][k]表示第ｉ株玉米，用了ｊ次拔高，第ｉ株玉米高度为ｋ的连续玉米数是多少，转移O(n)，复杂度O(n^3*k) 注意到很明显的一个贪心：如果我们要拔高一列玉米，其右端点必然是最后一株玉米，因为如果不在最后一株玉米，我们将它移至最后一株玉米，将两株相连的费用不会增加。 换言之，拔高玉米只会对左端点的相对顺序产生影响。...
2017-11-10 15:16:13
289
原创 HDU4429
一道水题调了两天，被自己蠢哭题解：由题意明显有一个矩形和他分割后的矩形形成类似二叉树中父亲与孩子的关系，根据图把树建出来暴力LCA即可我是怎么把自己蠢哭的QAQ：卡常习惯/2使用>>1,结果这题有负数……
2017-11-02 14:47:25
202
原创 [SDOI2010]地精部落,HDU4055
博客弃坑好久了。最近接连做到有关全排列的DP，觉得还是该整理一下[SDOI2010]地精部落题解：看到全排列第一反应是状压DP，但是数据范围显然不允许。感觉到全排列个数的增加对答案的贡献有一些共性但是不知道怎么利用就看了一发题解。 对于前i个数，不必关心每个数具体是多少，只需知道相对大小即可。设 f[i][j]表示前i个数的排列中，第一个数是第 j 大，且a[1]>a[2]的方...
2017-10-31 20:36:15
215
原创 Noip2000，方格取数题解（DP）
（题目描述截自洛谷）标签：二维DP题解： 假定是两个速度相同的人分别从A走到B，由于题目的数据规模很小，可以用f[x1,y1,x2,y2]表示第一个人走到(x1,y1)，第二个人走到(x2,y2)时可取到的最大值，四维状态。但是注意到x1+y1=x2+y2，所以用记k=x1+y1=x2+y2，将状态就可以压缩为f[k,x1,x2]。这是通常的做法。我的做法是将x1+y1=k的点从右上到左下依次...
2017-02-02 13:33:06
375
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人