BZOJ3597【SCOI2014】方伯伯运椰子 <费用流>
BZOJ3594【SCOI2014】方伯伯的玉米田 <树状数组优化DP>
Problem
【SCOI2014】方伯伯的玉米田
TimeLimit:60Sec
MemoryLimit:128MB
Description
方伯伯在自己的农田边散步,他突然发现田里的一排玉米非常的不美。
这排玉米一共有N株,它们的高度参差不齐。
方伯伯认为单调不下降序列很美,所以他决定先把一些玉米拔高,再把破坏美感的玉米拔除掉,使得剩下的玉米的高度构成一个单调不下降序列。
方伯伯可以选择一个区间,把这个区间的玉米全部拔高1单位高度,他可以进行最多K次这样的操作。拔玉米则可以随意选择一个集合的玉米拔掉。
问能最多剩多少株玉米,来构成一排美丽的玉米。
Input
第1行包含2个整数N,K,分别表示这排玉米的数目以及最多可进行多少次操作。
第2行包含N个整数,第i个数表示这排玉米,从左到右第i株玉米的高度ai。
Output
输出1个整数,最多剩下的玉米数。
BZOJ4443【SCOI2015】小凸玩矩阵 <二分+网络流>
BZOJ3998【TJOI2015】弦论 <后缀自动机>
BZOJ4516【SHOI2016】生成魔咒 <后缀自动机>
Problem
【SHOI2016】生成魔咒
TimeLimit:10Sec
MemoryLimit:256MB
Description
魔咒串由许多魔咒字符组成,魔咒字符可以用数字表示。例如可以将魔咒字符 1,2 拼凑起来形成一个魔咒串 [1,2]。
一个魔咒串 S 的非空字串被称为魔咒串 S 的生成魔咒。例如 S=[1,2,1] 时,它的生成魔咒有 [1],[2],[1,2],[2,1],[1,2,1] 五种。S=[1,1,1] 时,它的生成魔咒有 [1],[1,1],[1,1,1] 三种。
最初 S 为空串。共进行 n 次操作,每次操作是在 S 的结尾加入一个魔咒字符。每次操作后都需要求出,当前的魔咒串 S 共有多少种生成魔咒。
Input
第一行一个整数 n。
第二行 n 个数,第 i 个数表示第 i 次操作加入的魔咒字符
1≤n≤100000,用来表示魔咒字符的数字 x 满足 1≤x≤109
Output
输出 n 行,每行一个数。第 i 行的数表示第 i 次操作后 S 的生成魔咒数量
BZOJ4569【SCOI2016】萌萌哒 <并查集+ST表>
Problem
【SCOI2016】萌萌哒
TimeLimit:20Sec
MemoryLimit:256MB
Description
一个长度为n的大数,用S1S2S3⋯Sn表示,其中Si表示数的第i位,S1是数的最高位,告诉你一些限制条件,每个条件表示为四个数,l1,r1,l2,r2,即两个长度相同的区间,表示子串Sl1Sl1+1Sl1+2⋯Sr1与Sl2Sl2+1Sl2+2⋯Sr2完全相同。比如n=6时,某限制条件l1=1,r1=3,l2=4,r2=6,那么123123,351351均满足条件,但是12012,131141不满足条件,前者数的长度不为6,后者第二位与第五位不同。问满足以上所有条件的数有多少个。
Input
第一行两个数n和m,分别表示大数的长度,以及限制条件的个数。接下来m行,对于第i行,有4个数li1,ri1,li2,ri2,分别表示该限制条件对应的两个区间。
1≤n≤105,1≤m≤105,1≤li1,ri1,li2,ri2≤n;并且保证ri1−li1=ri2−li2。
Output
一个数,表示满足所有条件且长度为n的大数的个数,答案可能很大,因此输出答案模109+7的结果即可。
BZOJ4407 于神之怒加强版 <莫比乌斯反演>
BZOJ3309 DZY Loves Math <莫比乌斯反演>
BZOJ2154 Crash的数字表格 <莫比乌斯反演>
Problem
Crash的数字表格
TimeLimit:20Sec
MemoryLimit:259MB
Description
今天的数学课上,Crash小朋友学习了最小公倍数(LeastCommonMultiple)。对于两个正整数a和b,LCM(a,b)表示能同时被a和b整除的最小正整数。例如,LCM(6,8)=24。回到家后,Crash还在想着课上学的东西,为了研究最小公倍数,他画了一张N×M的表格。每个格子里写了一个数字,其中第i行第j列的那个格子里写着数为LCM(i,j)。看着这个表格,Crash想到了很多可以思考的问题。不过他最想解决的问题却是一个十分简单的问题:这个表格中所有数的和是多少。当N和M很大时,Crash就束手无策了,因此他找到了聪明的你用程序帮他解决这个问题。由于最终结果可能会很大,Crash只想知道表格里所有数的和mod20101009的值。
Input
输入的第一行包含两个正整数,分别表示N和M。
Output
输出一个正整数,表示表格中所有数的和mod20101009的值。