- 博客(30)
- 收藏
- 关注
RSS订阅原创 BZOJ1228: [SDOI2009]E&D
题目描述小E 与小W 进行一项名为“E&D”游戏。游戏的规则如下：桌子上有2n 堆石子，编号为1..2n。其中，为了方便起见，我们将第2k-1 堆与第2k 堆（1 ≤ k ≤ n）视为同一组。第i堆的石子个数用一个正整数Si表示。一次分割操作指的是，从桌子上任取一堆石子，将其移走。然后分割它同一组的另一堆石子，从中取出若干个石子放在被移走的位置，组成新的一堆。操作完成后，所有堆的石子数...
2018-04-19 03:17:16
371
原创 BZOJ1823: [JSOI2010]满汉全席
题目描述算了太长了,就不复制了Solution对于每种食材,只有HM两种选择 考虑2-SAT,对于每种限制条件就相当于X or Y = 1. 建边就是X’->Y, Y’->X 第一次写2-SAT感觉还不错#include<cstdio>#include<cstring>#include<algorithm>usin...
2018-04-16 03:28:15
216
原创 POJ3352Road Construction
题目大意给定一个无向连通图,问至少加几条边使得图成为边双联通图样例输入Sample Input 1 10 12 1 2 1 3 1 4 2 5 2 6 5 6 3 7 3 8 7 8 4 9 4 10 9 10Sample Input 2 3 3 1 2 2 3 1 3样例输出Output for Sample Input 1 ...
2018-04-13 20:39:54
359
原创 BZOJ4152[AMPPZ2014]The Captain
题目描述给定平面上的n个点，定义(x1,y1)到(x2,y2)的费用为min(|x1-x2|,|y1-y2|)，求从1号点走到n号点的最小费用。输入第一行包含一个正整数n(2<=n<=200000)，表示点数。 接下来n行，每行包含两个整数x[i],yi，依次表示每个点的坐标。输出一个整数，即最小费用。Solution如果x1<=x2...
2018-04-13 00:02:38
148
原创 BZOJ3531: [Sdoi2014]旅行
题目描述S国有N个城市，编号从1到N。城市间用N-1条双向道路连接，满足 从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。为了方便，我们用不同的正整数代表各种宗教， S国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国政府为每个城市标定了不同的旅...
2018-04-12 01:38:16
116
原创 BZOJ4553: [Tjoi2016&Heoi2016]序列
输入佳媛姐姐过生日的时候，她的小伙伴从某宝上买了一个有趣的玩具送给他。玩具上有一个数列，数列中某些项的值可能会变化，但同一个时刻最多只有一个值发生变化。现在佳媛姐姐已经研究出了所有变化的可能性，她想请教你 ，能否选出一个子序列，使得在任意一种变化中，这个子序列都是不降的？请你告诉她这个子序列的最长长度即可 。注意：每种变化最多只有一个值发生变化。在样例输入1中，所有的变化是： 1 2...
2018-04-12 00:17:00
118
原创 BZOJ3653: 谈笑风生
题目描述设T 为一棵有根树，我们做如下的定义： ? 设a和b为T 中的两个不同节点。如果a是b的祖先，那么称“a比b不知道 高明到哪里去了”。 ? 设a 和 b 为 T 中的两个不同节点。如果 a 与 b 在树上的距离不超过某个给定 常数x，那么称“a 与b 谈笑风生”。 给定一棵n个节点的有根树T，节点的编号为1 到 n，根节点为1号节点。你需 要回答q 个询问，询问给定两个整数...
2018-04-11 16:56:22
215
原创 BZOJ3527: [Zjoi2014]力(卷积FFT)
题目描述给出n个数qi，给出Fj的定义如下： 令Ei=Fi/qi，求Ei.输入第一行一个整数n。 接下来n行每行输入一个数，第i行表示qi。 n≤100000，0< qi <1000000000.输出n行，第i行输出Ei。与标准答案误差不超过1e-2即可。Solution卷积FFT,很适合初学FFT做 一定要注意精度问题,1/(i∗i...
2018-04-05 01:48:55
124
原创 BZOJ1426收集邮票
题目描述有n种不同的邮票，皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买，每次只能买一张，并且 买到的邮票究竟是n种邮票中的哪一种是等概率的，概率均为1/n。但是由于凡凡也很喜欢邮票，所以皮皮购买第k 张邮票需要支付k元钱。现在皮皮手中没有邮票，皮皮想知道自己得到所有种类的邮票需要花费的钱数目的期望。输入一行,一个数字N, NNN<=100001000010...
2018-03-28 16:44:17
192
原创 BZOJ2326[HNOI2011]数学作业
题目描述小 C 数学成绩优异，于是老师给小 C 留了一道非常难的数学作业题：给定正整数 N 和 M 要求计算 Concatenate(1..N)Concatenate(1..N)Concatenate (1 .. N) ModModMod MMM 的值，其中 Concatenate (1 ..N)是将所有正整数1,2,…,N1,2,…,N1, 2, …, N顺序连接起来得到的数。 例如，...
2018-03-27 22:20:27
109
原创 BZOJ3236: [Ahoi2013]作业
题目描述输入输出Solution普通莫队,对每个区间用树状数组维护权值的前缀和 没有权值的范围,不离散化也能水过#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>using namespace std;...
2018-03-23 02:05:38
137
原创 高次不定方程BSGS算法
学习数学真是一件赛艇的事.BSGS名字听起来非常有意思,力拔山兮气盖世,北上广深,小步大步…算法其实更有意思,它是用来求解一个方程的Ax≡BmodPAx≡BmodPA^x≡B mod P是不是特别眼熟,有几个式子长的特别像,先观察一下:一:快速幂: 求ABmodPABmodPA^B mod P的值二:乘法逆元 A∗x≡1(modP)A∗x≡1(modP)A*x...
2018-03-17 16:33:06
286
原创 BZOJ3136: [Baltic2013]brunhilda
题目描述给定m个素数和Q个询问。每个询问有n个人，每次操作可以任意选择其中的一个素数p（素数可以重复使用），然后去掉剩余人数 mod p个人。对于每个询问，我们想知道，至少需要多少步操作才能去掉所有人。输入第一行：素数个数m和询问个数Q（1 <= m <= 100 000, 1 <= Q <= 100 000）第二行：m个素数pi （2 <= pi &...
2018-03-17 04:28:47
609
原创 BZOJ1798: [Ahoi2009]维护序列seq
BZOJ1798 [Ahoi2009]维护序列seq题目描述老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。 有长为N的数列，不妨设为a1,a2,…,aN 。有如下三种操作形式： (1)把数列中的一段数全部乘一个值; (2)把数列中的一段数全部加一个值; (3)询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模P的值。输入第一行两个整数N和P(1≤P...
2018-03-15 02:45:09
147
原创 BZOJ2243 [SDOI2011]染色
BZOJ2243: [SDOI2011]染色题目描述给定一棵有n个节点的无根树和m个操作，操作有2类： 1、将节点a到节点b路径上所有点都染成颜色c； 2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段）， 如“112221”由3段组成：“11”、“222”和“1”。 请你写一个程序依次完成这m个操作。输入第一行包含2个整数n和m，分别表示节点数和操作...
2018-03-14 21:59:51
117
原创 BZOJ1878: [SDOI2009]HH的项链
BZOJ1878: [SDOI2009]HH的项链题目描述HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步 完后，他都会随意取出一 段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此他的项链变得越来越长。有一天，他突然提出了一 个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答。。。因为项链实在是太长了。于是，他只 好求助睿智的你，...
2018-03-13 22:49:05
161
原创 luogu3796AC自动机模版
Luogu3796AC自动机模版题目描述有NN 个由小写字母组成的模式串以及一个文本串TT 。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串TT 中出现的次数最多。输入(样例) 2 aba bab ababababac 6 beta alpha haha delta dede tata dede...
2018-03-12 22:54:12
131
原创 BZOJ2251[2010Beijing Wc]外星联络
BZOJ2251[2010Beijing Wc]外星联络题目描述小 P 在看过电影《超时空接触》(Contact)之后被深深的打动，决心致力于寻 找外星人的事业。于是，他每天晚上都爬在屋顶上试图用自己的收音机收听外星 人发来的信息。虽然他收听到的仅仅是一些噪声，但是他还是按照这些噪声的高 低电平将接收到的信号改写为由 0 和 1 构成的串， 并坚信外星人的信息就隐藏在 其中。他认为...
2018-03-10 01:31:04
203
原创 BZOJ3238[Ahoi2013]差异
BZOJ3238[Ahoi2013]差异题目描述 n<=500000n<=500000n∑ni=1∑nj=i+1len(Ti)+len(Tj)=(n−1)∗n∗(n+1)2∑i=1n∑j=i+1nlen(Ti)+len(Tj)=(n−1)∗n∗(n+1)2\sum_{i=1}^{n}\sum_{j=i+1}^{n}len(T_i)+len(T_j)=\frac{(n-1)*n...
2018-03-09 21:38:21
168
原创 BZOJ2754 [SCOI2012]喵星球上的点名 后缀数组+暴力
BZOJ2754 [SCOI2012]喵星球上的点名 后缀数组题目描述a180285幸运地被选做了地球到喵星球的留学生。他发现喵星人在上课前的点名现象非常有趣。 假设课堂上有N个喵星人，每个喵星人的名字由姓和名构成。喵星球上的老师会选择M个串来点名，每次读出一个串的时候，如果这个串是一个喵星人的姓或名的子串，那么这个喵星人就必须答到。 然而，由于喵星人的字码过于古怪，以至于不能用ASC...
2018-03-09 12:04:02
179
原创 BZOJ4698 Sdoi2008 Sandy的卡片
BZOJ4698 Sdoi2008 Sandy的卡片题目描述Sandy和Sue的热衷于收集干脆面中的卡片。然而，Sue收集卡片是因为卡片上漂亮的人物形象，而Sandy则是为了积 攒卡片兑换超炫的人物模型。每一张卡片都由一些数字进行标记，第i张卡片的序列长度为Mi，要想兑换人物模型 ，首先必须要集够N张卡片，对于这N张卡片，如果他们都有一个相同的子串长度为k，则可以兑换一个等级为k的...
2018-03-08 00:04:01
115
原创 NOI2014动物园(BZOJ3670)
NOI2014动物园(BZOJ3670)题目描述近日，园长发现动物园中好吃懒做的动物越来越多了。例如企鹅，只会卖萌向游客要吃的。为了整治动物园的不良风气，让动物们凭自己的真才实学向游客要吃的，园长决定开设算法班，让动物们学习算法。某天，园长给动物们讲解KMP算法。园长：“对于一个字符串S，它的长度为L。我们可以在O(L)的时间内，求出一个名为next的数组。有谁预习了next数...
2018-03-06 16:30:52
164
原创 POJ2774 Long Long Message(后缀数组)
POJ2774 Long Long Message(后缀数组)题目描述The little cat is majoring in physics in the capital of Byterland. A piece of sad news comes to him these days: his mother is getting ill. Being worried about sp...
2018-03-05 20:29:28
173
原创 【模版】后缀数组(洛谷P3809)
【模版】后缀数组(洛谷P3809)洛谷上的模版题 模版的代码到处都是 模版各种详细的注释也到处都有 我偏偏看不懂 他们说要理解代码就要先学基数排序，我去学了，然后看懂了 回来理解后缀数组还是不会 听各种人给我讲每次都是一样的感觉，好像理解，突然又不会了 知道昨天早上LCA跟我语音终于把这个给讲明白了 最后发现问题还是处在基数排序基数排序这是一种稳定排序，就是这点让我...
2018-03-02 21:09:16
445
原创 网络流24题餐巾计划问题
网络流24题餐巾计划问题问题描述一个餐厅在相继的NNN天里,每天需用的餐巾数不尽相同。假设第iii天需要 ririr_i块餐巾( i=1,2,…,N)。餐厅可以购买新的餐巾,每块餐巾的费用为ppp分;或者把旧餐巾送到快洗部,洗一块需 m 天,其费用为 f 分;或者送到慢洗部,洗一块需nnn天(n>m),其费用为s(s<f)s(s<f)s(sNNN天中餐巾使用计划,使总...
2018-03-02 01:27:14
175
原创 网络流24题09方格取数问题
网络流24题09方格取数问题题目描述在一个有 m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘，按照取数要求编程找出总和最大的数。输入第 1 行有 2 个正整数 m 和 n，分别表示棋盘的行数和列数。接下来的 m 行，每行有 n 个正整数，表示棋盘方格...
2018-03-01 19:14:36
396
原创 最小费用最大流模版(zkw)洛谷3381
zkw费用流模版洛谷上可以测. 其实就是把dinic里的bfs换成了spfa,建图的时候把反向边的容量设为0，费用设为-c[i]. 然后跑一边模版。。#include<cstdio>#include<cstring>#include<queue>#include<algorithm>using namespace std;#de...
2018-03-01 17:10:15
643
原创 网络流24题07:试题库问题
网络流24题07：试题库问题题目描述假设一个试题库中有n道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取m 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。对于给定的组卷要求，计算满足要求的组卷方案。输入第1行有2个正整数k和n (2 <=k<= 20, k<=n<= 1000)k 表示题库中试...
2018-02-27 14:17:59
213
原创 BZOJ1001狼抓兔子(网络流最小割）
BZOJ1001 狼抓兔子题目描述现在小朋友们最喜欢的”喜羊羊与灰太狼”,话说灰太狼抓羊不到，但抓兔子还是比较在行的， 而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对下面这样一个网格的地形： 左上角点为(1,1),右下角点为(N,M)(上图中N=4,M=5).有以下三种类型的道路 1:(x,y)<==>(x+1,y) 2:(x,y)<==&g...
2018-02-27 00:31:51
172
原创 Bzoj2038小Z的袜子
Bzoj 2038 小Z的袜子题目描述作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命…… 具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。 ...
2018-02-14 09:56:00
168
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人