bzoj 2160: 拉拉队排练 (回文自动机+快速幂)

2160: 拉拉队排练

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 1938  Solved: 743
[Submit][Status][Discuss]

Description

艾利斯顿商学院篮球队要参加一年一度的市篮球比赛了。拉拉队是篮球比赛的一个看点,好的拉拉队往往能帮助球队增加士气,赢得最终的比赛。所以作为拉拉队队长的楚雨荨同学知道,帮助篮球队训练好拉拉队有多么的重要。拉拉队的选拔工作已经结束,在雨荨和校长的挑选下,n位集优秀的身材、舞技于一体的美女从众多报名的女生中脱颖而出。这些女生将随着篮球队的小伙子们一起,和对手抗衡,为艾利斯顿篮球队加油助威。一个阳光明媚的早晨,雨荨带领拉拉队的队员们开始了排练。n个女生从左到右排成一行,每个人手中都举了一个写有26个小写字母中的某一个的牌子,在比赛的时候挥舞,为小伙子们呐喊、加油。雨荨发现,如果连续的一段女生,有奇数个,并且他们手中的牌子所写的字母,从左到右和从右到左读起来一样,那么这一段女生就被称作和谐小群体。现在雨荨想找出所有和谐小群体,并且按照女生的个数降序排序之后,前K个和谐小群体的女生个数的乘积是多少。由于答案可能很大,雨荨只要你告诉她,答案除以19930726的余数是多少就行了。

Input

输入为标准输入。第一行为两个正整数n和K,代表的东西在题目描述中已经叙述。接下来一行为n个字符,代表从左到右女生拿的牌子上写的字母。

Output

输出为标准输出。输出一个整数,代表题目描述中所写的乘积除以19930726的余数,如果总的和谐小群体个数小于K,输出一个整数-1。

Sample Input

5 3
ababa

Sample Output

45
【样例说明】
和谐小群体女生所拿牌子上写的字母从左到右按照女生个数降序排序后为ababa, aba, aba, bab, a, a, a, b, b,前三个长度的乘积为。

HINT

总共20个测试点,数据范围满足: 

 

 

思路:

直接PAM.

需要注意的是,PAM构建之后,再按照逆拓扑序更新一遍得到的cnt才是实际的cnt

需要注意的是,PAM构建之后,再按照逆拓扑序更新一遍得到的cnt才是实际的cnt

需要注意的是,PAM构建之后,再按照逆拓扑序更新一遍得到的cnt才是实际的cnt

BZOJ 2565: 最长双回文串 (回文自动机)

Description

顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串,而abc不是(abc的顺序为“abc”,逆序为“cba”,不相同)。
输入长度为n的串S,求S的最长双回文子串T,即可将T分为两部分X,Y,(|X|,|Y|≥1)且X和Y都是回文串。

Input

一行由小写英文字母组成的字符串S

Output

一行一个整数,表示最长双回文子串的长度。

Sample Input

baacaabbacabb

Sample Output

12

HINT

样例说明

从第二个字符开始的字符串aacaabbacabb可分为aacaa与bbacabb两部分,且两者都是回文串。

对于100%的数据,2≤|S|≤10^5

2015.4.25新加数据一组

Source

 

 

思路:

我们考虑增量构建PAM的时候

构建到pos,当前的状态的len其实就是到以pos位置结尾的最长回文串的长度。

那么我们只需要正着做一遍,再倒着做一遍,然后枚举断点就行了。

时间复杂度O(n)

 

BZOJ 1230: [Usaco2008 Nov]lites 开关灯 (线段树区间修改,区间查询)

 

1230: [Usaco2008 Nov]lites 开关灯

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 1676  Solved: 874
[Submit][Status][Discuss]

Description

Farmer John尝试通过和奶牛们玩益智玩具来保持他的奶牛们思维敏捷. 其中一个大型玩具是牛栏中的灯. N (2 <= N <= 100,000) 头奶牛中的每一头被连续的编号为1..N, 站在一个彩色的灯下面.刚到傍晚的时候, 所有的灯都是关闭的. 奶牛们通过N个按钮来控制灯的开关; 按第i个按钮可以改变第i个灯的状态.奶牛们执行M (1 <= M <= 100,000)条指令, 每个指令都是两个整数中的一个(0 <= 指令号 <= 1). 第1种指令(用0表示)包含两个数字S_i和E_i (1 <= S_i <= E_i <= N), 它们表示起始开关和终止开关. 奶牛们只需要把从S_i到E_i之间的按钮都按一次, 就可以完成这个指令. 第2种指令(用1表示)同样包含两个数字S_i和E_i (1 <= S_i <= E_i <= N), 不过这种指令是询问从S_i到E_i之间的灯有多少是亮着的. 帮助FJ确保他的奶牛们可以得到正确的答案.

Input

* 第 1 行: 用空格隔开的两个整数N和M

* 第 2..M+1 行: 每行表示一个操作, 有三个用空格分开的整数: 指令号, S_i 和 E_i

Output

第 1..询问的次数 行: 对于每一次询问, 输出询问的结果.

Sample Input

4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4
输入解释:
一共有4盏灯; 5个指令. 下面是执行的情况:

1 2 3 4
Init: O O O O O = 关 * = 开
0 1 2 -> * * O O 改变灯 1 和 2 的状态
0 2 4 -> * O * *
1 2 3 -> 1 输出在2..3的范围内有多少灯是亮的
0 2 4 -> * * O O 改变灯 2 ,3 和 4 的状态
1 1 4 -> 2 输出在1..4的范围内有多少灯是亮的

Sample Output

1
2
考虑一次翻转对区间[L,R]的贡献
开着的灯数等于当前区间长度减去之前区间[L,R]内开着的灯数
也就是tree[rt].sum = r-l+1-tree[rt].sum;
对于lazy标记,无非是从0变到1,从1变到0.
手误写错了一个地方,2A

 

bzoj 1059: [ZJOI2007]矩阵游戏 (匈牙利算法)

1059: [ZJOI2007]矩阵游戏

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 5251  Solved: 2512
[Submit][Status][Discuss]

Description

  小Q是一个非常聪明的孩子,除了国际象棋,他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N
*N黑白方阵进行(如同国际象棋一般,只是颜色是随意的)。每次可以对该矩阵进行两种操作:行交换操作:选择
矩阵的任意两行,交换这两行(即交换对应格子的颜色)列交换操作:选择矩阵的任意行列,交换这两列(即交换
对应格子的颜色)游戏的目标,即通过若干次操作,使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑
色。对于某些关卡,小Q百思不得其解,以致他开始怀疑这些关卡是不是根本就是无解的!!于是小Q决定写一个程
序来判断这些关卡是否有解。

Input

  第一行包含一个整数T,表示数据的组数。接下来包含T组数据,每组数据第一行为一个整数N,表示方阵的大
小;接下来N行为一个N*N的01矩阵(0表示白色,1表示黑色)。

Output

  输出文件应包含T行。对于每一组数据,如果该关卡有解,输出一行Yes;否则输出一行No。

Sample Input

2
2
0 0
0 1
3
0 0 1
0 1 0
1 0 0

Sample Output

No
Yes
【数据规模】
对于100%的数据,N ≤ 200
思路:
纠结了一下建图,由于每个黑点可以按照行换,也可以按照列换。所以我建了一个1..n到1..2n的二分图做匹配。
左边集合是n个对角线上的点,右边集合是行号+列号。
但是每次匹配的时候,一个对角线上的点会同时消耗到匹配的行号和列号。。感觉不是很对啊。。。
实际上发现,我们只需要建立一个n到n的二分图就行了。
原因是,如果有解,那么只需要行或者列的一种变换,就可以达到规定的图案。
比如现在(2,5)是1,(2,2)和(5,5)是0,我们只需要连一条边表示(2,5)可以换到(2,2)即可,不需要连表示(2,5)可以换到(5,5)的边
原因是,如果(2,5)换到(5,5),那么(2,2)也跟着换到了(5,2),我们不考虑之前的(2,2)是什么,被换之后的(2,2)必须是1才符合题意,也就是换之前的(5,2)必须是1.
既然(5,2)是1,那么从(5,2)换到(5,5)即可符合条件。

 

BZOJ 1191: [HNOI2006]超级英雄Hero (匈牙利)

1191: [HNOI2006]超级英雄Hero

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 5221  Solved: 2356
[Submit][Status][Discuss]

Description

现在电视台有一种节目叫做超级英雄,大概的流程就是每位选手到台上回答主持人的几个问题,然后根据回答问题的多少获得不同数目的奖品或奖金。主持人问题准备了若干道题目,只有当选手正确回答一道题后,才能进入下一题,否则就被淘汰。为了增加节目的趣味性并适当降低难度,主持人总提供给选手几个“锦囊妙计”,比如求助现场观众,或者去掉若干个错误答案(选择题)等等。 这里,我们把规则稍微改变一下。假设主持人总共有m道题,选手有n种不同的“锦囊妙计”。主持人规定,每道题都可以从两种“锦囊妙计”中选择一种,而每种“锦囊妙计”只能用一次。我们又假设一道题使用了它允许的锦囊妙计后,就一定能正确回答,顺利进入下一题。现在我来到了节目现场,可是我实在是太笨了,以至于一道题也不会做,每道题只好借助使用“锦囊妙计”来通过。如果我事先就知道了每道题能够使用哪两种“锦囊妙计”,那么你能告诉我怎样选择才能通过最多的题数吗?

Input

输入文件的一行是两个正整数n和m(0 < n <1001,0 < m < 1001)表示总共有n中“锦囊妙计”,编号为0~n-1,总共有m个问题。
以下的m行,每行两个数,分别表示第m个问题可以使用的“锦囊妙计”的编号。
注意,每种编号的“锦囊妙计”只能使用一次,同一个问题的两个“锦囊妙计”可能一样。

Output

第一行为最多能通过的题数p

Sample Input

5 6
3 2
2 0
0 3
0 4
3 2
3 2

Sample Output

4
思路: 从题目向2条锦囊妙计连边,注意判重。由于有一道题答错比赛就结束,因此在hung的过程中一旦不能find就直接break掉。

bzoj 1901: Zju2112 Dynamic Rankings (可持久化线段树,区间动态第k大)

Description

给定一个含有n个数的序列a[1],a[2],a[3]……a[n],程序必须回答这样的询问:对于给定的i,j,k,在a[i],a[i+1
],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1),并且,你可以改变一些a[i]的值,改变后,程序还能针对改
变后的a继续回答上面的问题。

Input

第一行有两个正整数n(1≤n≤10000),m(1≤m≤10000)。
分别表示序列的长度和指令的个数。
第二行有n个数,表示a[1],a[2]……a[n],这些数都小于10^9。
接下来的m行描述每条指令
每行的格式是下面两种格式中的一种。
Q i j k 或者 C i t
Q i j k (i,j,k是数字,1≤i≤j≤n, 1≤k≤j-i+1)
表示询问指令,询问a[i],a[i+1]……a[j]中第k小的数。
C i t (1≤i≤n,0≤t≤10^9)表示把a[i]改变成为t
m,n≤10000

Output

 对于每一次询问,你都需要输出他的答案,每一个输出占单独的一行。

Sample Input

5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3

Sample Output

3
6

思路:

现在我们已经会了用可持久化线段树,去做静态区间第k大的问题。

考虑一次修改,修改的元素会影响后面所有建好的线段树,时间代价是无法承受的。

我们考虑root[i]表示的这颗线段树,它保存的是从第一个元素开始插入到第i个元素后的数字区间。也就是说每次我们进行线段树区间相减时,我们是对两个前缀和[1, l – 1]和[1, r]进行了相减。

所以我们需要的是,以一个可以接受的时间代价,维护一个前缀和。

显然是用BIT来维护。

所以带修改的可持久化线段树,本质上应该是BIT套可持久化线段树。

 

 

 

BZOJ 3262: 陌上花开 (cdq分治模板题,三维偏序)

Description

有n朵花,每朵花有三个属性:花形(s)、颜色(c)、气味(m),又三个整数表示。现要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽,当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然,两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。

Input

第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。
以下N行,每行三个整数si, ci, mi (1 <= si, ci, mi <= K),表示第i朵花的属性

Output

包含N行,分别表示评级为0…N-1的每级花的数量。

Sample Input

10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1

Sample Output

3
1
3
0
1
0
1
0
0
1

HINT

1 <= N <= 100,000, 1 <= K <= 200,000

 

思路:

第一发cdq分治,果然很好写。

cdq分治学习笔记

题目很裸,好像没什么好分析的。

代码风格的话,我是看lwt菊苣代码长大的

 

 

BZOJ 2648: SJY摆棋子 (动态kd-tree,插入,曼哈顿距离,输入挂)

Description

这天,SJY显得无聊。在家自己玩。在一个棋盘上,有N个黑色棋子。他每次要么放到棋盘上一个黑色棋子,要么放上一个白色棋子,如果是白色棋子,他会找出距离这个白色棋子最近的黑色棋子。此处的距离是 曼哈顿距离 即(|x1-x2|+|y1-y2|) 。现在给出N<=500000个初始棋子。和M<=500000个操作。对于每个白色棋子,输出距离这个白色棋子最近的黑色棋子的距离。同一个格子可能有多个棋子。

Input

第一行两个数 N M
以后M行,每行3个数 t x y
如果t=1 那么放下一个黑色棋子
如果t=2 那么放下一个白色棋子

Output

对于每个T=2 输出一个最小距离

Sample Input

2 3
1 1
2 3
2 1 2
1 3 3
2 4 2

Sample Output


1
2
其实就是BZOJ2716 的双倍经验题
写出来是因为,这道题要加输入挂才可以过orz

 

BZOJ 2716: [Violet 3]天使玩偶 (动态kd-tree,带插入,曼哈顿距离模板题)

题目链接

Description

Input

Output

 

样例太长了,就不写了。

题意是说,现在有n个在二维平面,m个操作,2种类型,一种是加入一个点,另一种是对于一个定点,询问距离其最近的点的距离。

动态kd-tree的模板题,带插入操作。

插入其实就是直接暴力插的。

需要注意的是,这道题的距离度量是曼哈顿距离,略麻烦。

对于每个点,我们需要维护四个方向的极值。也就是kd-tree中某个节点所代表的空间,能管到的上下左右的最大(最小)坐标。

题解参考了iwtwiioi大爷的博客

代码风格参考了【bzoj 2716】[Violet 3]天使玩偶a  

 

 

 

 

BZOJ 2480: Spoj3105 Mod (扩展BSGS算法,模板)

Description

已知数a,p,b,求满足a^x≡b(mod p)的最小自然数x。

Input

    每个测试文件中最多包含100组测试数据。
    每组数据中,每行包含3个正整数a,p,b。
    当a=p=b=0时,表示测试数据读入完全。

Output

    对于每组数据,输出一行。
    如果无解,输出“No Solution”(不含引号),否则输出最小自然数解。

Sample Input

5 58 33
2 4 3
0 0 0

Sample Output

9
No Solution

HINT

  100%的数据,a,p,b≤1e9。
2016.3.29新加数据一组 by  1430586275

 

思路:BSGS算法,需要注意这里没有保证(a,p)=1,因此不能直接使用BSGS算法。

我们称之为扩展BSGS算法…

但是其实并不是什么新东西,不过是几次gcd,将条件转化成满足BSGS算法的情况

 

BZOJ 2748: [HAOI2012]音量调节 (dp)

2748: [HAOI2012]音量调节

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 1814  Solved: 1148
[Submit][Status][Discuss]

Description

一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量,所以他决定每一首歌之前他都要改变一次音量。在演出开始之前,他已经做好了一个列表,里面写着在每首歌开始之前他想要改变的音量是多少。每一次改变音量,他可以选择调高也可以调低。
音量用一个整数描述。输入文件中给定整数beginLevel,代表吉他刚开始的音量,以及整数maxLevel,代表吉他的最大音量。音量不能小于0也不能大于maxLevel。输入文件中还给定了n个整数c1,c2,c3…..cn,表示在第i首歌开始之前吉他手想要改变的音量是多少。
吉他手想以最大的音量演奏最后一首歌,你的任务是找到这个最大音量是多少。

Input

第一行依次为三个整数:n, beginLevel, maxlevel。
第二行依次为n个整数:c1,c2,c3…..cn。

Output

输出演奏最后一首歌的最大音量。如果吉他手无法避免音量低于0或者高于maxLevel,输出-1。

Sample Input

3 5 10
5 3 7

Sample Output

10

HINT

1<=N<=50,1<=Ci<=Maxlevel 1<=maxlevel<=1000

0<=beginlevel<=maxlevel

思路:
一看数据范围…长着一张dp的脸…
dp[i][j]表示经过i次调整后能否达到音量j.
初始化dp[0][beginlevel] = true.
按顺序转移就好了.
复杂度O(n*MAXlevel)

 

BZOJ 2257: [Jsoi2009]瓶子和燃料 (裴蜀定理)

2257: [Jsoi2009]瓶子和燃料

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 1246  Solved: 756
[Submit][Status][Discuss]

Description

jyy就一直想着尽快回地球,可惜他飞船的燃料不够了。
有一天他又去向火星人要燃料,这次火星人答应了,要jyy用飞船上的瓶子来换。jyy
的飞船上共有 N个瓶子(1<=N<=1000) ,经过协商,火星人只要其中的K 个 。 jyy
将 K个瓶子交给火星人之后,火星人用它们装一些燃料给 jyy。所有的瓶子都没有刻度,只
在瓶口标注了容量,第i个瓶子的容量为Vi(Vi 为整数,并且满足1<=Vi<=1000000000 ) 。
火星人比较吝啬,他们并不会把所有的瓶子都装满燃料。他们拿到瓶子后,会跑到燃料
库里鼓捣一通,弄出一小点燃料来交差。jyy当然知道他们会来这一手,于是事先了解了火
星人鼓捣的具体内容。火星人在燃料库里只会做如下的3种操作:1、将某个瓶子装满燃料;
2、将某个瓶子中的燃料全部倒回燃料库;3、将燃料从瓶子a倒向瓶子b,直到瓶子b满
或者瓶子a空。燃料倾倒过程中的损耗可以忽略。火星人拿出的燃料,当然是这些操作能
得到的最小正体积。
jyy知道,对于不同的瓶子组合,火星人可能会被迫给出不同体积的燃料。jyy希望找
到最优的瓶子组合,使得火星人给出尽量多的燃料。

Input

第1行:2个整数N,K,
第2..N 行:每行1个整数,第i+1 行的整数为Vi

Output

仅1行,一个整数,表示火星人给出燃料的最大值。

Sample Input

3 2
3
4
4

Sample Output

4

HINT

选择第2 个瓶子和第 个瓶子,火星人被迫会给出4 体积的容量。

思路:

思路完全错掉了orz…想去贪心来着….

因为自己脑算的例子错掉了…容量3和容量7的瓶子,能得到的最小是1不是2(因为忘了可以从瓶子中倒回燃料库的操作)…

样例一错毁所有orz..

正确的思路是,容量为a,b的两个瓶子能鼓捣出的体积一定是ax+by的形式

根据裴蜀定理,ax+by能得到的最小正数解就是(a,b),也就是gcd(a,b)

由此可以推广到多个瓶子,容量分别为x1,x2,…xn,能得到的最小体积就是gcd(x1,x2..xn)

(能推广的原因还是多说一句吧,假设现在只有两个瓶子x1,x2,称出了gcd(x1,x2),那么其实和只有一个容量为gcd(x1,x2)的瓶子在效果上是等价的)

因为剩下我们要做的就是,统计每个容量的因子统计,找到最大的并且出现此处大于等于k次的…

 

 

BZOJ 1012: [JSOI2008]最大数maxnumber (线段树,,单点更新)

1012: [JSOI2008]最大数maxnumber

Time Limit: 3 Sec  Memory Limit: 162 MB
Submit: 9717  Solved: 4244
[Submit][Status][Discuss]

Description

  现在请求你维护一个数列,要求提供以下两种操作:1、 查询操作。语法:Q L 功能:查询当前数列中末尾L
个数中的最大的数,并输出这个数的值。限制:L不超过当前数列的长度。2、 插入操作。语法:A n 功能:将n加
上t,其中t是最近一次查询操作的答案(如果还未执行过查询操作,则t=0),并将所得结果对一个固定的常数D取
模,将所得答案插入到数列的末尾。限制:n是非负整数并且在长整范围内。注意:初始时数列是空的,没有一个
数。

Input

  第一行两个整数,M和D,其中M表示操作的个数(M <= 200,000),D如上文中所述,满足D在longint内。接下来
M行,查询操作或者插入操作。

Output

  对于每一个询问操作,输出一行。该行只有一个数,即序列中最后L个数的最大数。

Sample Input

5 100
A 96
Q 1
A 97
Q 1
Q 2

Sample Output

96
93
96
思路:线段树即可….
只是为了回忆一下..发现线段树还是没有忘记的23333

 

BZOJ 1303: [CQOI2009]中位数图(前缀/后缀和乱搞)

1303: [CQOI2009]中位数图

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 2480  Solved: 1529
[Submit][Status][Discuss]

Description

给出1~n的一个排列,统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后,位于中间的数。

Input

第一行为两个正整数n和b ,第二行为1~n 的排列。

Output

输出一个整数,即中位数为b的连续子序列个数。

Sample Input

7 4
5 7 2 4 3 1 6

Sample Output

4

HINT

第三个样例解释:{4}, {7,2,4}, {5,7,2,4,3}和{5,7,2,4,3,1,6}
N<=100000

思路:这道题的思路还是比较经典的…把大于b的数看成1,小于b的数看成-1..于是一段以b为中位数的连续的长度为奇数的数列的和为0.

那么从b往前做一个后缀和,往后做一个前缀和…然后统计每个前缀和/后缀和的值的个数..

然后枚举前缀和/后缀和可能的值(-n..n,由于负数不好处理,整体+n,变成0..2n)

具体见代码

 

 

BZOJ 1800: [Ahoi2009]fly 飞行棋 (尺取+数学)

 

1800: [Ahoi2009]fly 飞行棋

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 1530  Solved: 1220
[Submit][Status][Discuss]

Description

给出圆周上的若干个点,已知点与点之间的弧长,其值均为正整数,并依圆周顺序排列。 请找出这些点中有没有可以围成矩形的,并希望在最短时间内找出所有不重复矩形。

Input

第一行为正整数N,表示点的个数,接下来N行分别为这N个点所分割的各个圆弧长度

Output

所构成不重复矩形的个数

Sample Input

8
1
2
2
3
1
1
3
3
 

Sample Output

3

HINT

N<= 20

思路:一开始的想法是枚举四条边,如果a==c&&b==d,就认为是找到了一个矩形。

重点在于判重,非常不好判断。一开始想要根绝四条边的长度hash一下,但是设想一个所有弧长都相等,且弧长较多的情况。

此时所有矩形的边长长度都相同,但是显然是不同的矩形,因此这种判断方法是错误的。

比较棒的思路是:矩形的对角线一定是外接圆的直径。

因此只需要找有多少条执行,假设为c,那么答案就是c*(c-1)/2(因为任意两条对角线就可以构成一个矩形)

这种做法的好处很明显,不需要判重。

至于如何找直径,直径是把圆周等分的弦,所以尺取找一下就好了。

复杂度O(n)