Post 11

Veröffentlicht am

我想看一场盛大的流行陨落的过程、我要一直不停许愿、许到沧海桑田瞬息万变直到靠近你微笑淡晴的脸。 —From Zyf 学姐

[SHOI2007]园丁的烦恼

题目描述

很久很久以前，在遥远的大陆上有一个美丽的国家。统治着这个美丽国家的国王是一个园艺爱好者，在他的皇家花园里种植着各种奇花异草。

有一天国王漫步在花园里，若有所思，他问一个园丁道： “最近我在思索一个问题，如果我们把花坛摆成六个六角形，那么……”

“那么本质上它是一个深度优先搜索，陛下”，园丁深深地向国王鞠了一躬。

“嗯……我听说有一种怪物叫九头蛇，它非常贪吃苹果树……”

“是的，显然这是一道经典的动态规划题，早在N元4002年我们就已经发现了其中的奥秘了，陛下”。

“该死的，你究竟是什么来头？”

“陛下息怒，干我们的这行经常莫名其妙地被问到和OI有关的题目，我也是为了预防万一啊！” 王者的尊严受到了伤害，这是不可容忍的。

看来一般的难题是难不倒这位园丁的，国王最后打算用车轮战来消耗他的实力： “年轻人，在我的花园里的每一棵树可以用一个整数坐标来表示，一会儿，我的骑士们会来轮番询问你某一个矩阵内有多少树，如果你不能立即答对，你就准备走人吧！”说完，国王气呼呼地先走了。

这下轮到园丁傻眼了，他没有准备过这样的问题。所幸的是，作为“全国园丁保护联盟”的会长——你，可以成为他的最后一根救命稻草。

输入输出格式

输入格式：

第一行有两个整数n，m（0≤n≤500000，1≤m≤500000）。n代表皇家花园的树木的总数，m代表骑士们询问的次数。

文件接下来的n行，每行都有两个整数xi，yi，代表第i棵树的坐标（0≤xi，yi≤10000000）。

文件的最后m行，每行都有四个整数aj，bj，cj，dj，表示第j次询问，其中所问的矩形以（aj，bj）为左上坐标（cj，dj）为右下坐标。

输出格式：

共输出m行，每行一个整数，即回答国王以（aj，bj）和（cj，dj）为界的矩形里有多少棵树。

输入输出样例

输入样例#1：

1
2
3
4
5
3 1
0 0 
0 1
1 0
0 0 1 1

输出样例#1：

1
3

题解

首先可以将查询离线，然后用扫描线降维。

首先统计个数显然满足可减性，因此就可以把每个询问看成是两个横坐标左端点是1的差。

对纵坐标离散化后使用权值树状数组将点一个一个插进去，由于横坐标排序后升序，所以用一个指针表示当前处理到的询问，假如当前点横坐标大于询问的横坐标，就先查询询问的答案。

这道水题就做完了。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 500005
struct Node
{
	int x , y;
	bool operator<(const Node& p)const{
		return x < p.x;
	}
}p[maxn];
struct Query
{
	int x , y1 , y2, type ,k;
	bool operator<(const Query& p)const{
		return x < p.x;	
	}
}q[maxn<<1];
struct T{
	int v , k ,type;
	bool operator<(const T& x)const{
		return v < x.v;
	}
}o[maxn<<3];
struct Fenwick_tree
{
	int tr[maxn<<2] , range;
	inline int query(int x){
		if(x==0) return 0;
		int ans = 0;
		for(int i = x ; i ; i -= i & -i)
			ans += tr[i];
		return ans;
	}
	inline void update(int p , int v){
		for(int i = p ; i <= range ; i += i & -i)
			tr[i] += v;
	}
}tr;
int ans[3][maxn] , n , m , num , tot , cnt;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d%d",&p[i].x,&p[i].y);
	for(int i = 1 ; i <= m ; ++i){
		int x1 , y1 , x2 , y2;
		scanf("%d%d%d%d",&x1,&y1 ,&x2, &y2);
		q[++num].x = x1 -1, q[num].type = 1 , q[num].y1 = y1 , q[num].y2 = y2 , q[num].k = i;
		q[++num].x = x2 , q[num].type = 2 , q[num].y1 = y1 , q[num].y2 = y2 , q[num].k = i;
	}
	std::sort(q+1,q+num+1);
	std::sort(p+1,p+n+1);
	for(int i = 1; i <= n ; ++i){
		o[++cnt].v = p[i].y;
		o[cnt].k = i;
		o[cnt].type = 1;
	}
	for(int i = 1 ; i <= num ; ++i)
	{
		o[++cnt].v = q[i].y1;
		o[cnt].k = i;
		o[cnt].type = 2;
		o[++cnt].v = q[i].y2;
		o[cnt].k = i;
		o[cnt].type = 3;
	}
	std::sort(o+1,o+cnt+1);
	o[0].v = 19260817;
	for(int i = 1 ; i <= cnt ; ++i)
	{
		if(o[i].v != o[i-1].v) ++tot;
		if(o[i].type == 1) p[o[i].k].y = tot;
		else if(o[i].type == 2) q[o[i].k].y1 = tot;
		else q[o[i].k].y2 = tot;
	}
	tr.range = tot;
	int L = 1;
	for(int i = 1 ; i <= n ; ++i)
	{
		if(p[i].x > q[L].x){
			while(q[L].x < p[i].x && L <= 2*m)
				ans[q[L].type][q[L].k] = tr.query(q[L].y2) - tr.query(q[L].y1-1) , ++L;
		}
		tr.update(p[i].y,1);
	}
	for(int i = L ; i <= 2*m ; ++i)
		ans[q[i].type][q[i].k] = tr.query(q[i].y2) - tr.query(q[i].y1-1);
	for(int i= 1;  i <= m ; ++i)
		printf("%d\n",ans[2][i] - ans[1][i]);
}

准备学习后缀数组，看的同时突然领悟道夏令营讲的那个双关键字桶排其实就是类似于后缀数组（当然不完全一样），于是写了个基数排序。。（stacall小姐姐真强）

基数排序

原理就是对当前关键字进行桶排并对应其排名。对于当前关键字，如果我们倒着扫就相当于已经利用了前面的关键字的排序结果，然后按照现在的关键字为第一关键字，前面所有为第二关键字来排序。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 10000005
const int base = (1 << 16) - 1;
const int bits = 16;
int a[maxn] , b[maxn] , tot[base+1] , n;
inline int getKey(int x , int isFir){
	return (x>>(isFir*bits)) & base;
}
inline void Radix_sort()
{
	int *x = a , *y = b;
	for(int key = 0 ; key < 2 ; ++key)
	{
		for(int i = 0 ; i <= base ; ++i)
			tot[i] = 0;
		for(int i = 0 ; i < n ; ++i)
			tot[getKey(x[i] , key)] ++;
		for(int i = 1 ; i <= base ; ++i)
			tot[i] += tot[i-1];
		for(int i = n - 1 ; ~i ; --i)
			y[--tot[getKey(x[i],key)]] = x[i];
		std::swap(x,y);
	}
	for(int i = 0 ; i < n ; ++i)
		printf("%d ",a[i]);
}


int main()
{
	scanf("%d",&n);
	for(int i = 0 ; i < n ; ++i)
		scanf("%d",&a[i]);
	Radix_sort();
}

这个程序非常易懂，并且如果想要更大数据范围排序只需要改成4关键字循环即可。

后缀数组

上一张浅显易懂清晰的图

SA4

设k是当前倍增的值

对于

到n这部分，显然是没有第二关键字的，把它们先都加进y数组中

然后对于

，都可以作为

的第二关键字。

上一次处理的就是第一关键字，然后基数排序即可。

剩下的就是代码实现了，不算很难。

今天大脑有点不清醒，这么简单的都想了半天，所以今天好好学文化课得了。

好不容易边理解边写，交上去发现自己常数还挺小。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 1000006
char s[maxn];
int n , m , SA[maxn] , RK[maxn] , c[maxn] , x[maxn] , y[maxn];
inline void Suffix_Array()
{
	for(int i = 1 ; i <= n ; ++i)
		c[x[i] = s[i]] ++;
	for(int i = 1 ; i <= m ; ++i)
		c[i] += c[i-1];
	for(int i = n ; i >= 1 ; --i)
		SA[c[x[i]]--] = i;
	for(int k = 1 ; k <= n ; k <<= 1)
	{
		int num = 0;
		for(int i = n - k + 1 ; i <= n ; ++i)
			y[++num] = i;
		for(int i = 1 ; i <= n ; ++i)
			if(SA[i] > k) y[++num] = SA[i] - k;
		for(int i = 1 ; i <= m ; ++i)
			c[i] = 0;
		for(int i = 1 ; i <= num ; ++i)
			c[x[i]] ++;
		for(int i = 1 ; i <= m ; ++i)
			c[i] += c[i-1];
		for(int i = n ; i >= 1 ; --i)
			SA[c[x[y[i]]]--] = y[i] , y[i] = 0;
		std::swap(x,y);
		x[SA[1]] = 1; num = 1;
		for(int i = 2 ; i <= n ; ++i)
			x[SA[i]] = (y[SA[i]] == y[SA[i-1]] && y[SA[i]+k] == y[SA[i-1]+k]) ? num : ++num;
		m = num;
		if(num == n) break;
	}
	for(int i = 1 ; i <= n ; ++i)
		printf("%d ",SA[i]);
}
	
int main()
{
	scanf("%s",s+1);
	n = std::strlen(s + 1) , m = 122;
	Suffix_Array();
}

[TJOI2007]调整队形

题目背景

学校艺术节上，规定合唱队要参加比赛，各个队员的衣服颜色不能很混乱：合唱队员应排成一横排，且衣服颜色必须是左右对称的。

例如：“红蓝绿蓝红”或“红蓝绿绿蓝红”都是符合的，而“红蓝绿红”或“蓝绿蓝红”就不符合要求。

合唱队人数自然很多，仅现有的同学就可能会有3000个。老师希望将合唱队调整得符合要求，但想要调整尽量少，减少麻烦。以下任一动作认为是一次调整：

题目描述

1、在队伍左或右边加一个人（衣服颜色依要求而定）；

2、在队伍中任两个人中间插入一个人（衣服颜色依要求而定）；

3、剔掉一个人；

4、让一个人换衣服颜色；

老师想知道就目前的队形最少的调整次数是多少，请你编一个程序来回答他。

因为加入合唱队很热门，你可以认为人数是无限的，即随时想加一个人都能找到人。同时衣服颜色也是任意的。

输入输出格式

输入格式：

第一行是一个整数n(1<=n<=3000)。

第二行是n个整数，从左到右分别表示现有的每个队员衣服的颜色号，都是1到3000的整数。

输出格式：

一个数，即对于输入队列，要调整得符合要求，最少的调整次数。

输入输出样例

1
2
5
1 2 2 4 3
1
2

题解

这道题就是我凭感觉瞎写的转移啊。。。

显然题意没法让前i个最优，不是划分dp什么的，就试试区间dp。

对于当前区间，我们只需要确保两个端点被处理地最优（显然易得，不会证明）

要么我们删除左边，要么删除右边，要么改变下颜色呗（改变颜色并不需要考虑改变成哪边的颜色。。我一开始sb还考虑这个，后面转移自然包括改变左边或右边颜色。)

当然这是在两边不相等的情况下，相等直接从里面的小区间转移就行。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 3005
int f[maxn][maxn] , n , p[maxn];
int main()
{
	std::memset(f,0x3f,sizeof(f));
	scanf("%d",&n);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&p[i]) ,f[i][i] = 0;
	for(int i = 1 ; i <= n ; ++i)
		for(int j = 1 ; j < i ; ++j)
			f[i][j] = 0;
	for(int k = 1 ; k < n ; ++k){
		for(int j = 1 ; j + k <= n ; ++j){
			int to = k + j;
			if(p[j] == p[to]) f[j][to] = f[j+1][to-1];
			else f[j][to] = std::min(f[j+1][to-1] + 1, std::min(f[j+1][to] + 1 , f[j][to-1] + 1));
		}
	}
	printf("%d",f[1][n]);
}

[TJOI2008]公共子串

题目描述

一个字符串的子串是在这个串基础上去掉0个或者若干个字符所形成的，例如abc, aa和abbc都是字符串aabbcc的子串，而aba不是。 现给你三个字符串，请问他们三个共同含有多少种子串（不算空串）?

注意： 有些相同的公共子串尽管出现在不同的位置，但仍算1种，详见样例。

输入输出格式

输入格式：

每组测试数据只有3行，每行都是一个只包含有小写字母的字符串。

输出格式：

输出3个字符串共有的公共子串种类数。

输入输出样例

输入样例#1：

1
2
3
apartment
apache
approach

输出样例#1：

1
6

说明

3个字符串共有的公共子串有： “a”, “p”, “ap”, “pa”, “aa”, “apa”。 其中子串 “a” 有多个，但由于统计的是公共子串种类，所以 “a” 只算1种子串。

100%的数据中，字符串的长度不超过100。字符串中只含有小写字母。

题解

一道很经典的方案数dp。

显然设

表示第一个字符串前i位，第二个前j位，第三个前k位本质不同子序列的个数。

但是要求不能重复。。。这个我不会了，然后去翻了翻题解qwq。

发现假如想去重，可以试着枚举每一个结尾字符$c$，然后在枚举三个字符串的同时记录每个字符串出现每个字符最后一次的位置。

加的1就是它自己，其他的方案由其前面的公共方案数组成，可以保证不重不漏。（需要想一想）

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 105
#define ll long long
ll f[maxn][maxn][maxn] , ls[3][maxn<<1];
int  l1 , l2 , l3;
char s1[maxn] , s2[maxn] , s3[maxn];
int main()
{
	scanf("%s",s1+1);
	scanf("%s",s2+1);
	scanf("%s",s3+1);
	int l1 = std::strlen(s1+1) , l2 = std::strlen(s2+1) , l3 = std::strlen(s3+1);
	for(int i = 1 ; i <= l1 ; ++i){
		ls[0][s1[i]] = i;
		std::memset(ls[1],0,sizeof(ls[1]));
		for(int j = 1 ; j <= l2 ; ++j){
			ls[1][s2[j]] = j;
			std::memset(ls[2],0,sizeof(ls[2]));
			for(int k = 1 ; k <= l3 ; ++k){
				ls[2][s3[k]] = k;
				for(int x = 'a' ; x <= 'z' ; ++x)
					if(ls[0][x] && ls[1][x] && ls[2][x])
						f[i][j][k] += f[ls[0][x]-1][ls[1][x]-1][ls[2][x]-1] + 1;
				}
			}
		}
	printf("%lld",f[l1][l2][l3]);
}

关于模板类Template的基本用法

一般用于函数，也可以用于类，主要关键字是typename

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn  100003
template<typename T>
inline void read(T& x)
{
	char ch = getchar();
	x = ch - 48;
}
template<typename T>
struct Stack
{
	T x[maxn];
	int tot;
	inline void push(T& g){
		x[++tot] = g;
	}
	inline T top(){
		return x[tot];
	}
};
Stack<int> st;
int main()
{
	int n;
	read<int>(n);
	st.push(n);
	std::cout<<st.top();
}

总结：dp水平远远不够啊。。