3 愤怒的愣头青

尚未进行身份认证

暂无相关简介

等级
TA的排名 1w+

【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

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

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

2018-01-26 18:47:12

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

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

2018-01-26 12:54:16

【bzoj4894】天赋 矩阵树定理

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

2018-01-26 12:19:20

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

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

2018-01-25 18:57:24

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

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

2018-01-24 22:56:28

【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

【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

【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

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

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

2018-01-23 20:35:40

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

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

2018-01-23 19:10:35

【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

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

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

2018-01-21 23:13:36

扩展中国剩余定理

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

扩展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

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

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

2018-01-19 18:31:58

【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

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

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

2018-01-15 08:44:27

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

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

2018-01-14 20:00:05

【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

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!