愤怒的愣头青-CSDN博客

原创【洛谷P3372】【模板】线段树 1

题目描述如题，已知一个数列，你需要进行下面两种操作：将某区间每一个数加上 kk。求出某区间每一个数的和。输入格式第一行包含两个整数 n, mn,m，分别表示该数列数字的个数和操作的总个数。第二行包含 nn 个用空格分隔的整数，其中第 ii 个数字表示数列第 ii 项的初始值。接下来 mm 行每行包含 33 或 44 个整数，表示一个操作，具体如下：1 x y k：将区间 [x, y][x,y] 内每个数加上 kk。2 x y：输出区间 [x, y][x,y] 内每个数的和。输出格式输出

2020-07-10 15:52:45 225

原创【bzoj2865】字符串识别后缀自动机+线段树

DescriptionXX在进行字符串研究的时候，遇到了一个十分棘手的问题。在这个问题中，给定一个字符串S，与一个整数K，定义S的子串T=S(i, j)是关于第K位的识别子串，满足以下两个条件： 1、i≤K≤j。 2、子串T只在S中出现过一次。例如，S=”banana”，K=5，则关于第K位的识别子串有”nana”，”anan”，”anana”，”nan”，”banan”和”ban

2018-01-26 19:35:53 770

原创【bzoj3659】Which Dreamed It 矩阵树定理+Best-Theorem

Description有n个房间，每个房间有若干把钥匙能够打开特定房间的门。你会做这么件事情：最初你在房间1。每当你到达一个房间，你可以选择该房间的一把钥匙，前往该钥匙对应的房间，并将该钥匙丢到垃圾桶中。你希望：最终回到房间1，且垃圾桶中有所有的钥匙。求方案数。两组方案不同，当且仅当使用钥匙的顺序不同。注意，每把钥匙都是不同的。 Input有多组数据。对于

2018-01-26 18:47:12 862 1

原创【bzoj3534】[Sdoi2014]重建矩阵树定理

DescriptionT国有N个城市，用若干双向道路连接。一对城市之间至多存在一条道路。在一次洪水之后，一些道路受损无法通行。虽然已经有人开始调查道路的损毁情况，但直到现在几乎没有消息传回。辛运的是，此前T国政府调查过每条道路的强度，现在他们希望只利用这些信息估计灾情。具体地，给定每条道路在洪水后仍能通行的概率，请计算仍能通行的道路恰有N-1条，且能联通所有城市的概率。

2018-01-26 12:54:16 408 1

原创【bzoj4894】天赋矩阵树定理

Description小明有许多潜在的天赋，他希望学习这些天赋来变得更强。正如许多游戏中一样，小明也有n种潜在的天赋，但有一些天赋必须是要有前置天赋才能够学习得到的。也就是说，有一些天赋必须是要在学习了另一个天赋的条件下才能学习的。比如，要想学会”开炮”，必须先学会”开枪”。一项天赋可能有多个前置天赋，但只需习得其中一个就可以学习这一项天赋。上帝不想为难小明，于是小明天生就已经习得

2018-01-26 12:19:20 395

原创【bzoj4031】[HEOI2015]小Z的房间矩阵树定理模板

Description你突然有了一个大房子，房子里面有一些房间。事实上，你的房子可以看做是一个包含n*m个格子的格状矩形，每个格子是一个房间或者是一个柱子。在一开始的时候，相邻的格子之间都有墙隔着。你想要打通一些相邻房间的墙，使得所有房间能够互相到达。在此过程中，你不能把房子给打穿，或者打通柱子（以及柱子旁边的墙）。同时，你不希望在房子中有小偷的时候会很难抓，所以你希望任意两个房间之间都只

2018-01-25 18:57:24 330

原创【hihocoder1457】后缀自动机四·重复旋律7 后缀自动机

描述小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一段音乐旋律可以被表示为一段数构成的数列。神奇的是小Hi发现了一部名字叫《十进制进行曲大全》的作品集，顾名思义，这部作品集里有许多作品，但是所有的作品有一个共同特征：只用了十个音符，所有的音符都表示成0-9的数字。现在小Hi想知道这部作品中所有不同的旋律的“和”（也就是把串看成数字，在十进制下的求和，允许有前导0）。答案有可能很大，我们

2018-01-24 22:56:28 494

原创【bzoj2671】Calc 莫比乌斯函数

Description　　给出N，统计满足下面条件的数对(a,b)的个数：　　1.1　　2.a+b整除a*b 　 Input　一行一个数N　 Output　一行一个数表示答案Sample Input15Sample Output4HINT数据规模和约定Test N Test N 1 2 3 4 5 6 7 8

2018-01-24 21:35:48 289

原创【bzoj3939】[Usaco2015 Feb]Cow Hopscotch cdq分治

DescriptionJust like humans enjoy playing the game of Hopscotch, Farmer John’s cows have invented a variant of the game for themselves to play. Being played by clumsy animals weighing nearly a ton,

2018-01-24 19:43:12 297

原创【bzoj3998】[TJOI2015]弦论后缀自动机

Description对于一个给定长度为N的字符串，求它的第K小子串是什么。Input第一行是一个仅由小写英文字母构成的字符串S第二行为两个整数T和K，T为0则表示不同位置的相同子串算作一个。T=1则表示不同位置的相同子串算作多个。K的意义如题所述。 Output输出仅一行，为一个数字串，为第K小的子串。如果子串数目不足K个，则输出-1Sample Inputaabc

2018-01-23 21:55:44 214

原创【hihocoder1449】后缀自动机三·重复旋律6 后缀自动机

描述小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为一段数构成的数列。现在小Hi想知道一部作品中所有长度为K的旋律中出现次数最多的旋律的出现次数。但是K不是固定的，小Hi想知道对于所有的K的答案。解题方法提示输入共一行，包含一个由小写字母构成的字符串S。字符串长度不超过 1000000。输出共Length(S)行，每行一个整数，表示答案。样例输入

2018-01-23 20:35:40 528

原创【hihocoder1445】后缀自动机二·重复旋律5 后缀自动机模板

描述小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为一段数构成的数列。现在小Hi想知道一部作品中出现了多少不同的旋律？解题方法提示输入共一行，包含一个由小写字母构成的字符串。字符串长度不超过 1000000。输出一行一个整数，表示答案。样例输入 aab 样例输出 5题解每个节点的maxlen[i]-maxlen[suf[i]]之和即为

2018-01-23 19:10:35 369

原创【uoj34】NTT模板

转载质数原根表： http://blog.miskcoo.com/2014/07/fft-prime-table#include#include#include#define ll long longusing namespace std;inline int read(){ int x=0,f=1;char ch=getchar(); while (ch'0'|

2018-01-22 23:14:22 455

原创【bzoj2142】礼物扩展Lucas定理+中国剩余定理

Description一年一度的圣诞节快要来到了。每年的圣诞节小E都会收到许多礼物，当然他也会送出许多礼物。不同的人物在小E 心目中的重要性不同，在小E心中分量越重的人，收到的礼物会越多。小E从商店中购买了n件礼物，打算送给m个人，其中送给第i个人礼物数量为wi。请你帮忙计算出送礼物的方案数（两个方案被认为是不同的，当且仅当存在某个人在这两种方案中收到的礼物不同）。由于方案数可能会很

2018-01-21 23:13:36 265

原创扩展中国剩余定理

http://blog.csdn.net/litble/article/details/75807726#include#include#include#include#include#define ll long longusing namespace std;inline int read(){ int x=0,f=1;char ch=getchar();

2018-01-21 22:16:20 280

原创扩展BSGS模板

#include#include#include#include#include#include#define ll long longusing namespace std;inline int read(){ int x=0,f=1;char ch=getchar(); while (ch'0'||ch>'9'){if (ch=='-') f=-1;ch=ge

2018-01-19 20:39:16 416

原创【bzoj3884】上帝与集合的正确用法扩展欧拉定理

Description根据一些书上的记载，上帝的一次失败的创世经历是这样的：第一天，上帝创造了一个世界的基本元素，称做“元”。第二天，上帝创造了一个新的元素，称作“α”。“α”被定义为“元”构成的集合。容易发现，一共有两种不同的“α”。第三天，上帝又创造了一个新的元素，称作“β”。“β”被定义为“α”构成的集合。容易发现，一共有四种不同的“β”。第四天，

2018-01-19 18:31:58 250

原创【bzoj4082】[Wf2014]Surveillance 倍增

Description给你一个长度为len的环，以及n个区间，要你选择尽量少的区间，使得它们完全覆盖整个环。问最少要多少个区间。Input输入数据的第一行是两个整数len和n，代表环的长度以及区间个数。之后n行描述的是n个区间，每个区间分别用一对数字(a,b)表示，若a≤b则表示这个区间覆盖的是[a,b]部分，否则表示这个区间覆盖的是除掉[a+1,b-1]以外的其他部分。Outpu

2018-01-15 08:48:05 520

原创【bzoj3566】[SHOI2014]概率充电器树形DP

Description著名的电子产品品牌 SHOI 刚刚发布了引领世界潮流的下一代电子产品——概率充电器: “采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI 概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧! ” SHOI 概率充电器由 n-1 条导线连通了 n 个充电元件。进行充电时,每条导线是否可以导电以概率决定,每一个充电元件自身是否直接进

2018-01-15 08:44:27 247

原创【bzoj4950】[Wf2017]Mission Improbable 二分图最大匹配

Description那是春日里一个天气晴朗的好日子,你准备去见见你的老朋友Patrick,也是你之前的犯罪同伙。Patrick在编程竞赛上豪赌输掉了一大笔钱,所以他需要再干一票。为此他需要你的帮助,虽然你已经金盆洗手了。你刚开始很不情愿, 因为你一点也不想再回到那条老路上了,但是你觉得听一下他的计划也无伤大雅。在附近的一个仓库里有一批货物, 包含一些贵重的消费性部件,Patrick企

2018-01-14 20:00:05 371

原创【bzoj1119】[POI2009]SLO

Description对于一个1-N的排列(ai)，每次你可以交换两个数ax与ay(xInput第一行N。第二行N个数表示wi。第三行N个数表示ai。第四行N个数表示bi。 2(bi) 样例中依次交换数字(2,5)(3,4)(1,5)Output一个数，最小代价。Sample Input62400 2000 1200 2400 1600 40001 4 5 3

2018-01-14 17:53:54 233

原创【bzoj3550】[ONTAK2010]Vacation 单纯形

Description有3N个数，你需要选出一些数，首先保证任意长度为N的区间中选出的数的个数Input第一行两个整数N，K。第二行有3N个整数。Output一行一个整数表示答案。Sample Input5 314 21 9 30 11 8 1 20 29 23 17 27 7 8 35Sample Output195HINT【数据范围】N

2018-01-14 10:22:55 188

原创【bzoj3126】[Usaco2013 Open]Photo 单调队列

DescriptionFarmer John has decided to assemble a panoramic photo of a lineup of his N cows (1 给你一个n长度的数轴和m个区间，每个区间里有且仅有一个点，问能有多少个点InputLine 1: Two integers N and M.Lines 2..M+1: Line i+1 co

2018-01-14 09:34:00 226

原创【bzoj4408】[Fjoi 2016]神秘数主席树

Description一个可重复数字集合S的神秘数定义为最小的不能被S的子集的和表示的正整数。例如S={1,1,1,4,13}，1 = 12 = 1+13 = 1+1+14 = 45 = 4+16 = 4+1+17 = 4+1+1+18无法表示为集合S的子集的和，故集合S的神秘数为8。现给定n个正整数a[1]..a[n]，m个询问，每次询问给定一个区间l,r

2018-01-13 16:40:42 204

原创【bzoj3498】PA2009 Cakes 判断三元环

DescriptionN个点m条边，每个点有一个点权a。对于任意一个三元环(j，j，k)（i为max(ai，aj，ak) 求所有三元环的贡献和。 NInputThe first line of the standard input contains two integers n and m (1Bi) separated by a single space. They d

2018-01-13 15:38:03 513

原创【bzoj4198】[Noi2015]荷马史诗哈夫曼树

Description追逐影子的人，自己就是影子。 ——荷马Allison 最近迷上了文学。她喜欢在一个慵懒的午后，细细地品上一杯卡布奇诺，静静地阅读她爱不释手的《荷马史诗》。但是由《奥德赛》和《伊利亚特》组成的鸿篇巨制《荷马史诗》实在是太长了，Allison 想通过一种编码方式使得它变得短一些。一部《荷马史诗》中有 n 种不同的单词，从 1 到 n 进行编号。其中第 i 种单词出现的

2018-01-13 13:54:15 255

原创【bzoj3527】[Zjoi2014]力 FFT

Description给出n个数qi，给出Fj的定义如下：令Ei=Fi/qi，求Ei. Input第一行一个整数n。接下来n行每行输入一个数，第i行表示qi。 n≤100000，0Outputn行，第i行输出Ei。与标准答案误差不超过1e-2即可。Sample Input54006373.88518415375036.4357591717456.4

2018-01-13 10:57:22 236

原创【bzoj2179】FFT快速傅立叶 FFT模板

Description给出两个n位10进制整数x和y，你需要计算x*y。 Input第一行一个正整数n。第二行描述一个位数为n的正整数x。第三行描述一个位数为n的正整数y。 Output输出一行，即x*y的结果。 Sample Input134Sample Output12数据范围：n题解 FFT模板（暂时只会递归版） http://www

2018-01-13 09:23:08 190

原创【bzoj3112】[Zjoi2013]防守战线单纯形

题面：http://img.d1kt.cn/programming/1347_1181.png 题解：对偶单纯形裸题。代码#include#include#include#include#include#define ll long long#define mod 10000007using namespace std;inline int read(){

2018-01-12 11:02:57 222

原创【bzoj3265】志愿者招募加强版单纯形

DescriptionInputOutputSample Input3 3 2 3 41 1 2 21 2 3 51 3 3 2 Sample Output14 HINT 题解单纯形裸题代码#include#include#include#include#include#define ll long long#def

2018-01-12 10:35:05 218

原创【bzoj1061】[Noi2008]志愿者招募单纯形

Description　　申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要N 天才能完成，其中第i 天至少需要 Ai 个人。布布通过了解得知，一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天，招募费用是每人Ci 元。新官上任三把火，为了出色地完

2018-01-12 10:32:00 225

原创【bzoj2820】YY的GCD 莫比乌斯函数

Description神犇YY虐完数论后给傻×kAc出了一题给定N, M,求1kAc这种傻×必然不会了，于是向你来请教…… 多组输入 Input第一行一个整数T 表述数据组数接下来T行，每行两个正整数，表示N, M OutputT行，每行一个整数表示第i组数据的结果 Sample Input2 10 10 100 100 Sample Output30

2018-01-12 09:09:28 208

原创【bzoj3143】[Hnoi2013]游走高斯消元+期望方程

Description一个无向连通图，顶点从1编号到N，边从1编号到M。小Z在该图上进行随机游走，初始时小Z在1号顶点，每一步小Z以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束，总分为所有获得的分数之和。现在，请你对这M条边进行编号，使得小Z获得的总分的期望值最小。Input第一行是正整数N和M，

2018-01-11 10:37:23 195

原创【bzoj3209】花神的数论题数位DP

Description背景众所周知，花神多年来凭借无边的神力狂虐各大 OJ、OI、CF、TC …… 当然也包括 CH 啦。描述话说花神这天又来讲课了。课后照例有超级难的神题啦…… 我等蒟蒻又遭殃了。花神的题目是这样的设 sum(i) 表示 i 的二进制表示中 1 的个数。给出一个正整数 N ，花神要问你派(Sum(i)),也就是 sum(1)—sum(N) 的乘积。

2018-01-11 09:50:42 264

原创【bzoj2160】拉拉队排练 manachar

Description艾利斯顿商学院篮球队要参加一年一度的市篮球比赛了。拉拉队是篮球比赛的一个看点，好的拉拉队往往能帮助球队增加士气，赢得最终的比赛。所以作为拉拉队队长的楚雨荨同学知道，帮助篮球队训练好拉拉队有多么的重要。拉拉队的选拔工作已经结束，在雨荨和校长的挑选下，n位集优秀的身材、舞技于一体的美女从众多报名的女生中脱颖而出。这些女生将随着篮球队的小伙子们一起，和对手抗衡，为艾利斯顿篮球队

2018-01-11 08:23:54 191

原创【bzoj3572】[Hnoi2014]世界树虚树+倍增lca+DP

Description世界树是一棵无比巨大的树，它伸出的枝干构成了整个世界。在这里，生存着各种各样的种族和生灵，他们共同信奉着绝对公正公平的女神艾莉森，在他们的信条里，公平是使世界树能够生生不息、持续运转的根本基石。世界树的形态可以用一个数学模型来描述：世界树中有n个种族，种族的编号分别从1到n，分别生活在编号为1到n的聚居地上，种族的编号与其聚居地的编号相同。有的聚居地之间有双向的道路相

2018-01-10 20:03:38 278

原创【bzoj4804】欧拉心算狄利克雷卷积

Description给出一个数字N Input第一行为一个正整数T，表示数据组数。接下来T行为询问，每行包含一个正整数N。 TOutput按读入顺序输出答案。 Sample Input110 Sample Output136题解给YZH dalao 跪烂烂烂烂烂 F(D)为欧拉函数和莫比乌斯函数的卷积代码#include#in

2018-01-10 16:16:03 385

原创【bzoj4802】欧拉函数 Pollard_Rho+Miller_Rabin

Description已知N，求phi(N) Input正整数N。NOutput输出phi(N) Sample Input8 Sample Output4 HINT题解 https://www.cnblogs.com/galaxies/p/bzoj4802.html模板#include#include#include#include#includ

2018-01-10 14:06:36 343 2

原创【bzoj2938】[Poi2000]病毒 AC自动机

Description二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。示例：例如如果{011, 11, 00000}为病毒代码段，那么一个可能的无限长安全代码就是010101…。如果{01, 11, 000000}为病

2018-01-09 19:14:27 214

原创【bzoj3275】Number 最小割

Description有N个正整数，需要从中选出一些数，使这些数的和最大。若两个数a,b同时满足以下条件，则a,b不能同时被选 1:存在正整数C，使a*a+b*b=c*c 2:gcd(a,b)=1Input第一行一个正整数n，表示数的个数。第二行n个正整数a1,a2,?an。Output最大的和。Sample Input53 4 5 6 7Samp

2018-01-08 20:20:55 245

动态树课件

空空如也