Loi_Vampire's Blog

自己选择的路,就算跪着也要走完

02/24
07:53
图论 网络流

BZOJ 1221 [HNOI2001] 软件开发 网络流-费用流

Description

某软件公司正在规划一项n天的软件开发计划,根据开发计划第i天需要ni个软件开发人员,为了提高软件开发人员的效率,公司给软件人员提供了很多的服务,其中一项服务就是要为每个开发人员每天提供一块消毒毛巾,这种消毒毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有两种,A种方式的消毒需要a天时间,B种方式的消毒需要b天(b>a),A种消毒方式的费用为每块毛巾fA, B种消毒方式的费用为每块毛巾fB,而买一块新毛巾的费用为f(新毛巾是已消毒的,当天可以使用);而且f>fA>fB。公司经理正在规划在这n天中,每天买多少块新毛巾、每天送多少块毛巾进行A种消毒和每天送多少块毛巾进行B种消毒。当然,公司经理希望费用最低。你的任务就是:为该软件公司计划每天买多少块毛巾、每天多少块毛巾进行A种消毒和多少毛巾进行B种消毒,使公司在这项n天的软件开发中,提供毛巾服务的总费用最低。

Input

第1行为n,a,b,f,fA,fB. 第2行为n1,n2,……,nn. (注:1≤f,fA,fB≤60,1≤n≤1000)

Output

最少费用

Sample Input

4 1 2 3 2 1

8 2 1 6

Sample Output

38

HINT

 

Source

 

Solution

所有的毛巾可以分为两类:第i天要用的 和 第i天用完的。

第i天用完的毛巾可以以后处理,即向i+1(1≤i+1≤n)天连一条流量为INF,花费为0的边;也可以采用A种方式清洗,即向i+a+1+n(1≤i+1+a≤n)天连一条流量为INF,花费为fa的边;同理采用B种方式清洗也是这么处理。

第i天要用的毛巾也可以直接购买,由超级源s直接连一条流量为INF,花费为f的边。

超级源向每个点i连一条流量为ni,花费为0的边,每个点i+n向t连一条流量为ni,花费为0的边,限制流量。

 

02/22
15:22
图论 网络流

BZOJ 1834 [ZJOI2010]network 网络扩容 网络流-费用流

Description

给定一张有向图,每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求: 1、 在不扩容的情况下,1到N的最大流; 2、 将1到N的最大流增加K所需的最小扩容费用。

Input

输入文件的第一行包含三个整数N,M,K,表示有向图的点数、边数以及所需要增加的流量。 接下来的M行每行包含四个整数u,v,C,W,表示一条从u到v,容量为C,扩容费用为W的边。

Output

输出文件一行包含两个整数,分别表示问题1和问题2的答案。

Sample Input

5 8 2

1 2 5 8

2 5 9 9

5 1 6 2

5 1 1 8

1 2 8 7

2 5 4 9

1 2 1 1

1 4 2 1

Sample Output

13 19

30%的数据中,N<=100

100%的数据中,N<=1000,M<=5000,K<=10

HINT

 

Source

Day1

Solution

对于第一问,直接跑最大流算法即可。

对于第二问,在残量网络上建边,每一条边的流量为inf,费用为w,超级源跟1建边,流量为k,费用为0, 再跑最小费用最大流就好了。

(为什么可以这样? 在残量网络上,那些不需要扩容的边花费为0,所以必定会选中,不需要花费额外的花费)

 

02/22
10:52
图论 网络流

BZOJ 1877 [SDOI2009]晨跑 网络流-费用流

Description

Elaxia最近迷恋上了空手道,他为自己设定了一套健身计划,比如俯卧撑、仰卧起坐等 等,不过到目前为止,他坚持下来的只有晨跑。 现在给出一张学校附近的地图,这张地图中包含N个十字路口和M条街道,Elaxia只能从 一个十字路口跑向另外一个十字路口,街道之间只在十字路口处相交。Elaxia每天从寝室出发 跑到学校,保证寝室编号为1,学校编号为N。 Elaxia的晨跑计划是按周期(包含若干天)进行的,由于他不喜欢走重复的路线,所以 在一个周期内,每天的晨跑路线都不会相交(在十字路口处),寝室和学校不算十字路 口。Elaxia耐力不太好,他希望在一个周期内跑的路程尽量短,但是又希望训练周期包含的天 数尽量长。 除了练空手道,Elaxia其他时间都花在了学习和找MM上面,所有他想请你帮忙为他设计 一套满足他要求的晨跑计划。

Input

第一行:两个数N,M。表示十字路口数和街道数。 接下来M行,每行3个数a,b,c,表示路口a和路口b之间有条长度为c的街道(单向)。

Output

两个数,第一个数为最长周期的天数,第二个数为满足最长天数的条件下最短的路程长 度。

Sample Input

7 10

1 2 1

1 3 1

2 4 1

3 4 1

4 5 1

4 6 1

2 5 5

3 6 6

5 7 1

6 7 1

Sample Output

2 11

HINT

对于30%的数据,N ≤ 20,M ≤ 120。 对于100%的数据,N ≤ 200,M ≤ 20000。

Source

Day1

Solution

拆点网络流……

 

02/21
10:17
可持久化数据结构 数据结构

BZOJ 3166 [Heoi2013]Alo 可持久化trie

Description

Welcome to ALO ( Arithmetic and Logistic Online)。这是一个VR MMORPG , 如名字所见,到处充满了数学的谜题。 现在你拥有n颗宝石,每颗宝石有一个能量密度,记为ai,这些宝石的能量 密度两两不同。现在你可以选取连续的一些宝石(必须多于一个)进行融合,设为 ai, ai+1, …, a j,则融合而成的宝石的能量密度为这些宝石中能量密度的次大值 与其他任意一颗宝石的能量密度按位异或的值,即,设该段宝石能量密度次大值 为k,则生成的宝石的能量密度为max{k xor ap | ap ≠ k , i ≤ p ≤ j}。 现在你需要知道你怎么选取需要融合的宝石,才能使生成的宝石能量密度最大。

Input

第一行,一个整数 n,表示宝石个数。 第二行, n个整数,分别表示a1至an,表示每颗宝石的能量密度,保证对于i ≠ j有 ai ≠ aj。

Output

输出一行一个整数,表示最大能生成的宝石能量密度。

Sample Input

5

9 2 1 4 7

Sample Output

14

HINT

【样例解释】

选择区间[1,5],最大值为 7 xor 9。

对于 100%的数据有 1 ≤ n ≤ 50000, 0 ≤ ai ≤ 10^9

Source

加强型数据By Hta

Solution

窝真是太弱了……看了 黄学长的题解 才会做……

大体思路就是:

按照权值从大到小,把每个数的位置插入到set中去。

对于当前的数字x,在set中查询它的前驱的前驱,以及后继的后继,x的可行区间就为[前驱的前驱+1,x]和[x,后继的后继-1]。(为什么?这样的话,x在这两个区间内都是次大值)

然后就可以合并为一个区间啦,在可持久化trie中查询即可。

 

02/20
10:42
可持久化数据结构 数据结构

BZOJ 4546 codechef XRQRS 可持久化trie

Description

给定一个初始时为空的整数序列(元素由1开始标号)以及一些询问: 类型1:在数组后面就加入数字x。 类型2:在区间L…R中找到y,最大化(x xor y)。 类型3:删除数组最后K个元素。 类型4:在区间L…R中,统计小于等于x的元素个数。 类型5:在区间L…R中,找到第k小的数。

Input

输入数据第一行为一个整数q,表示询问个数,接下来q行,每行一条询问 对应题目描述。 类型1的询问格式为“1 x”。 类型2的询问格式为“2 L R x”。 类型3的询问格式为“3 k”。 类型4的询问格式为“4 L R x”。 类型5的询问格式为“5 L R k”。

Output

对于每个2、4、5询问输出一行对应答案

Sample Input

10

1 8

5 1 1 1

1 2

2 2 2 7

2 2 2 7

1 1

4 2 2 2

2 1 2 3

4 1 3 5

1 6

Sample Output

8

2

2

1

8

2

HINT

令N表示每次询问前数组中元素的个数

1<=L<=R<=N

1<=x<=500,000

对于第三类询问 1<=k<=N

对于第五类询问 k<=R-L+1

1<=N<=500,000

Source

 

Solution

可持久化trie,写法和主席树差不多,注意数组大小。

 

02/19
15:16
可持久化数据结构 数据结构

BZOJ 3261 最大异或和 可持久化trie

Description

给定一个非负整数序列 {a},初始长度为 N。
有 M个操作,有以下两种操作类型:

1 、A x:添加操作,表示在序列末尾添加一个数 x,序列的长度 N+1。 2 、Q l r x:询问操作,你需要找到一个位置 p,满足 l<=p<=r,使得:

a[p] xor a[p+1] xor ... xor a[N] xor x 最大,输出最大是多少。

Input

第一行包含两个整数 N ,M,含义如问题描述所示。
第二行包含 N个非负整数,表示初始的序列 A 。

接下来 M行,每行描述一个操作,格式如题面所述。

Output

假设询问操作有 T个,则输出应该有 T行,每行一个整数表示询问的答案。

Sample Input

5 5

2 6 4 3 6

A 1

Q 3 5 4

A 4

Q 5 7 0

Q 3 6 6

对于测试点 1-2,N,M<=5 。

对于测试点 3-7,N,M<=80000 。

对于测试点 8-10,N,M<=300000。

其中测试点 1, 3, 5, 7, 9保证没有修改操作。

对于 100%的数据,0<=a[i]<=10^7。

Sample Output

4

5

6

HINT

对于 100% 的数据, 0<=a[i]<=10^7 。

Source

 

Solution

可持久化trie……写法和主席树差不多。

首先定义一个bi为前i个数字的异或和,询问max(b[n]^x^b[p]) l ≤ p ≤ r。

把b数组插入到trie中,查询的时候很容易想到贪心的做法。

在数组前放一个0,会更好处理

 

02/10
22:37
莫队算法

BZOJ 3236 [Ahoi2013]作业 莫队

Description

Input

Output

Sample Input

3 4

1 2 2

1 2 1 3

1 2 1 1

1 3 1 3

2 3 2 3

Sample Output

2 2

1 1

3 2

2 1

HINT

N=100000,M=1000000

Source

By wangyisong1996加强数据

Solution

这题基本上和3809没什么两样,同样是对权值分块+莫队。

详细解法

听说这题树状数组+莫队可以卡过。毕竟100s时限……

 

02/9
14:14
分块

BZOJ 3720 Gty的妹子树 树分块

Description

我曾在弦歌之中听过你, 檀板声碎,半出折子戏。 舞榭歌台被风吹去, 岁月深处尚有余音一缕…… Gty神(xian)犇(chong)从来不缺妹子…… 他来到了一棵妹子树下,发现每个妹子有一个美丽度…… 由于Gty很哲♂学,他只对美丽度大于某个值的妹子感兴趣。 他想知道某个子树中美丽度大于k的妹子个数。 某个妹子的美丽度可能发生变化…… 树上可能会出现一只新的妹子…… 维护一棵初始有n个节点的有根树(根节点为1),树上节点编号为1-n,每个点有一个权值wi。 支持以下操作: 0 u x 询问以u为根的子树中,严格大于x的值的个数。(u^=lastans,x^=lastans) 1 u x 把u节点的权值改成x。(u^=lastans,x^=lastans) 2 u x 添加一个编号为"当前树中节点数+1"的节点,其父节点为u,其权值为x。(u^=lastans,x^=lastans) 最开始时lastans=0。

Input

输入第一行包括一个正整数n(1<=n<=30000),代表树上的初始节点数。 接下来n-1行,每行2个整数u,v,为树上的一条无向边。 任何时刻,树上的任何权值大于等于0,且两两不同。 接下来1行,包括n个整数wi,表示初始时每个节点的权值。 接下来1行,包括1个整数m(1<=m<=30000),表示操作总数。 接下来m行,每行包括三个整数 op,u,v: op,u,v的含义见题目描述。 保证题目涉及的所有数在int内。

Output

对每个op=0,输出一行,包括一个整数,意义见题目描述。

Sample Input

2
1 2
10 20
1
0 1 5

Sample Output

2

HINT

 

Source

By Autumn

Solution

按照size分块,看父节点所在的块的大小是否超过√n, 没有就加入,否则新建一块。块与块之间也是树形结构,同样用邻接表存起来。

对于每个询问,块内二分,块外暴力。

然而我太菜了,写错了好几次……好在最终还是过了 o( ̄▽ ̄)ブ

PS:听说这题有更优的分块大小,可以自己去看~

 

02/8
11:00
分块

BZOJ 1086 王室联邦 树分块

Description

“余”人国的国王想重新编制他的国家。他想把他的国家划分成若干个省,每个省都由他们王室联邦的一个成 员来管理。他的国家有n个城市,编号为1..n。一些城市之间有道路相连,任意两个不同的城市之间有且仅有一条 直接或间接的道路。为了防止管理太过分散,每个省至少要有B个城市,为了能有效的管理,每个省最多只有3B个 城市。每个省必须有一个省会,这个省会可以位于省内,也可以在该省外。但是该省的任意一个城市到达省会所经 过的道路上的城市(除了最后一个城市,即该省省会)都必须属于该省。一个城市可以作为多个省的省会。聪明的 你快帮帮这个国王吧!

Input

第一行包含两个数N,B(1<=N<=1000, 1 <= B <= N)。接下来N-1行,每行描述一条边,包含两个数,即这 条边连接的两个城市的编号。

Output

如果无法满足国王的要求,输出0。否则输出数K,表示你给出的划分方案中省的个数,编号为1..K。第二行输 出N个数,第I个数表示编号为I的城市属于的省的编号,第三行输出K个数,表示这K个省的省会的城市编号,如果 有多种方案,你可以输出任意一种。

Sample Input

8 2

1 2

2 3

1 8

8 7

8 6

4 6

6 5

Sample Output

3

2 1 1 3 3 3 3 2

2 1 8

HINT

 

Source

 

Solution

一道有意思的树分块的题目。

维护一个栈,在dfs的时候,先遍历一遍所有的儿子节点,再把当前点压入栈内,每次自下向上更新,如果≥B个城市,就放在同一个省里,由当前子树的根节点做省会。

可是这样就会有一个问题,如果一棵子树内的元素数不足B个,再去搜索下一棵子树的时候,合并的块可能不联通。

在dfs开始维护一个栈底,每次只能计算栈底以上的元素个数,每次合并也是只能合并栈底以上的元素,这样就可以啦。o( ̄▽ ̄)ブ

对于最后剩下的块,合并到最后一个块内即可。

 

Orz PoPoQQQ

 

02/7
14:51
莫队算法

BZOJ 3809 Gty的二逼妹子序列 莫队

Description

Autumn和Bakser又在研究Gty的妹子序列了!但他们遇到了一个难题。 对于一段妹子们,他们想让你帮忙求出这之内美丽度∈[a,b]的妹子的美丽度的种类数。 为了方便,我们规定妹子们的美丽度全都在[1,n]中。 给定一个长度为n(1<=n<=100000)的正整数序列s(1<=si<=n),对于m(1<=m<=1000000)次询问“l,r,a,b”,每次输出sl...sr中,权值∈[a,b]的权值的种类数。

Input

第一行包括两个整数n,m(1<=n<=100000,1<=m<=1000000),表示数列s中的元素数和询问数。 第二行包括n个整数s1...sn(1<=si<=n)。 接下来m行,每行包括4个整数l,r,a,b(1<=l<=r<=n,1<=a<=b<=n),意义见题目描述。 保证涉及的所有数在C++的int内。 保证输入合法。

Output

对每个询问,单独输出一行,表示sl...sr中权值∈[a,b]的权值的种类数。

Sample Input

10 10

4 4 5 1 4 1 5 1 2 1

5 9 1 2

3 4 7 9

4 4 2 5

2 3 4 7

5 10 4 4

3 9 1 1

1 4 5 9

8 9 3 3

2 2 1 6

8 9 1 4

Sample Output

2

0

0

2

1

1

1

0

1

2

HINT

样例的部分解释:

5 9 1 2

子序列为4 1 5 1 2

在[1,2]里的权值有1,1,2,有2种,因此答案为2。

3 4 7 9

子序列为5 1

在[7,9]里的权值有5,有1种,因此答案为1。

4 4 2 5

子序列为1

没有权值在[2,5]中的,因此答案为0。

2 3 4 7

子序列为4 5

权值在[4,7]中的有4,5,因此答案为2。

建议使用输入/输出优化。

Source

 

Solution

我好菜…… 首先,莫队+树状数组的做法是比较显然的,每次询问、修改时间复杂度都是 O(log n) 的,总的时间复杂度 O(m√nlog n) ,据说可以卡时过,然而蒟蒻人傻常数大,卡不过…… 关于正解,把树状数组改为分块做法,每次修改时间复杂度为 O(1) ,每次询问时间复杂度 O(√n),总的时间复杂度 O(m√nlog n).可以过啦 ( •̀ ω •́ )y

先贴一份树状数组的超时代码

 

分块的代码

 

02/7
14:18
莫队算法

BZOJ 2038 [2009国家集训队]小Z的袜子(hose) 莫队

Description

作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天,小Z再也无法忍受这恼人的找袜子过程,于是他决定听天由命…… 具体来说,小Z把这N只袜子从1到N编号,然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双,甚至不在意两只袜子是否一左一右,他却很在意袜子的颜色,毕竟穿两只不同色的袜子会很尴尬。 你的任务便是告诉小Z,他有多大的概率抽到两只颜色相同的袜子。当然,小Z希望这个概率尽量高,所以他可能会询问多个(L,R)以方便自己选择。

Input

输入文件第一行包含两个正整数N和M。N为袜子的数量,M为小Z所提的询问的数量。接下来一行包含N个正整数Ci,其中Ci表示第i只袜子的颜色,相同的颜色用相同的数字表示。再接下来M行,每行两个正整数L,R表示一个询问。

Output

包含M行,对于每个询问在一行中输出分数A/B表示从该询问的区间[L,R]中随机抽出两只袜子颜色相同的概率。若该概率为0则输出0/1,否则输出的A/B必须为最简分数。(详见样例)

Sample Input

6 4

1 2 3 3 3 2

2 6

1 3

3 5

1 6

Sample Output

2/5

0/1

1/1

4/15

 

【样例解释】

询问1:共C(5,2)=10种可能,其中抽出两个2有1种可能,抽出两个3有3种可能,概率为(1+3)/10=4/10=2/5。

询问2:共C(3,2)=3种可能,无法抽到颜色相同的袜子,概率为0/3=0/1。

询问3:共C(3,2)=3种可能,均为抽出两个3,概率为3/3=1/1。

注:上述C(a, b)表示组合数,组合数C(a, b)等价于在a个不同的物品中选取b个的选取方案数。

【数据规模和约定】

30%的数据中 N,M ≤ 5000;

60%的数据中 N,M ≤ 25000;

100%的数据中 N,M ≤ 50000,1 ≤ L < R ≤ N,Ci ≤ N。

HINT

 

Source

版权所有者:莫涛

Solution

这是真正意义上的第一道莫队题吗。莫涛由此提出了莫队算法?Orz

直接上莫队……

 

02/7
13:52
莫队算法

BZOJ 3781 小B的询问 莫队

Description

小B有一个序列,包含N个1~K之间的整数。他一共有M个询问,每个询问给定一个区间[L..R],求Sigma(c(i)^2)的值,其中i的值从1到K,其中c(i)表示数字i在[L..R]中的重复次数。小B请你帮助他回答询问。

Input

第一行,三个整数N、M、K。 第二行,N个整数,表示小B的序列。 接下来的M行,每行两个整数L、R。

Output

M行,每行一个整数,其中第i行的整数表示第i个询问的答案。

Sample Input

6 4 3

1 3 2 1 1 3

1 4

2 6

3 5

5 6

Sample Output

6

9

5

2

HINT

对于全部的数据,1<=N、M、K<=50000

Source

 

Solution

很裸的题,再次证明我是zz…… 直接上莫队

 

02/7
13:30
KMP NOI 字符串

BZOJ 3670 [Noi2014]动物园

Description

近日,园长发现动物园中好吃懒做的动物越来越多了。例如企鹅,只会卖萌向游客要吃的。为了整治动物园的不良风气,让动物们凭自己的真才实学向游客要吃的,园长决定开设算法班,让动物们学习算法。

某天,园长给动物们讲解KMP算法。

园长:“对于一个字符串S,它的长度为L。我们可以在O(L)的时间内,求出一个名为next的数组。有谁预习了next数组的含义吗?”

熊猫:“对于字符串S的前i个字符构成的子串,既是它的后缀又是它的前缀的字符串中(它本身除外),最长的长度记作next[i]。”

园长:“非常好!那你能举个例子吗?”

熊猫:“例S为abcababc,则next[5]=2。因为S的前5个字符为abcab,ab既是它的后缀又是它的前缀,并且找不到一个更长的字符串满足这个性质。同理,还可得出next[1] = next[2] = next[3] = 0,next[4] = next[6] = 1,next[7] = 2,next[8] = 3。”

园长表扬了认真预习的熊猫同学。随后,他详细讲解了如何在O(L)的时间内求出next数组。

下课前,园长提出了一个问题:“KMP算法只能求出next数组。我现在希望求出一个更强大num数组一一对于字符串S的前i个字符构成的子串,既是它的后缀同时又是它的前缀,并且该后缀与该前缀不重叠,将这种字符串的数量记作num[i]。例如S为aaaaa,则num[4] = 2。这是因为S的前4个字符为aaaa,其中a和aa都满足性质‘既是后缀又是前缀’,同时保证这个后缀与这个前缀不重叠。而aaa虽然满足性质‘既是后缀又是前缀’,但遗憾的是这个后缀与这个前缀重叠了,所以不能计算在内。同理,num[1] = 0,num[2] = num[3] = 1,num[5] = 2。”

最后,园长给出了奖励条件,第一个做对的同学奖励巧克力一盒。听了这句话,睡了一节课的企鹅立刻就醒过来了!但企鹅并不会做这道题,于是向参观动物园的你寻求帮助。你能否帮助企鹅写一个程序求出num数组呢?

特别地,为了避免大量的输出,你不需要输出num[i]分别是多少,你只需要输出对1,000,000,007取模的结果即可。

Input

第1行仅包含一个正整数n ,表示测试数据的组数。随后n行,每行描述一组测试数据。每组测试数据仅含有一个字符串S,S的定义详见题目描述。数据保证S 中仅含小写字母。输入文件中不会包含多余的空行,行末不会存在多余的空格。

Output

包含 n 行,每行描述一组测试数据的答案,答案的顺序应与输入数据的顺序保持一致。对于每组测试数据,仅需要输出一个整数,表示这组测试数据的答案对 1,000,000,007 取模的结果。输出文件中不应包含多余的空行。

Sample Input

3

aaaaa

ab

abcababc

Sample Output

36

1

32

HINT

n≤5,L≤1,000,000

Source

 

Solution

还是有点糊涂……毕竟人太弱 沿着fail数组统计答案,时间复杂度做到 O(n)

 

01/11
11:08
AC自动机 字符串

BZOJ 3172 [Tjoi2013]单词 AC自动机-fail树

Description

某人读论文,一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次,现在想知道每个单词分别在论文中出现多少次。

Input

第一个一个整数N,表示有多少个单词,接下来N行每行一个单词。每个单词由小写字母组成,N<=200,单词长度不超过10^6

Output

输出N个整数,第i行的数字表示第i个单词在文章中出现了多少次。

Sample Input

3
a
aa
aaa

Sample Output

6
3
1

HINT

 

Source

Solution

朴素的做法是建好AC自动机之后,拿每一个串匹配,把路径上的点都cnt++,统计答案,然而会被卡死。 正解:将fail反向,成为一棵以0为根节点的fail树,然后向树根扫一遍,O(n)统计答案

 

01/10
21:37
KMP 字符串

BZOJ 1355 [Baltic2009]Radio Transmission KMP

Description

给你一个字符串,它是由某个字符串不断自我连接形成的。 但是这个字符串是不确定的,现在只想知道它的最短长度是多少.

Input

第一行给出字符串的长度,1 < L ≤ 1,000,000. 第二行给出一个字符串,全由小写字母组成.

Output

输出最短的长度

Sample Input

8

cabcabca

Sample Output

3

HINT

对于样例,我们可以利用"abc"不断自我连接得到"abcabcabc",读入的cabcabca,是它的子串

Source

Solution

用KMP来做……算是一个结论题吧……答案是n-fail[n]