思维之海

——在云端，寻找我的星匙。

CS挑战营

In

CS挑战营。

Pre-intro

数学在CS中的重要性。《程序员面试宝典》，《编程之美》。

推荐资源：

  • MIT-机器学习相关数学。（PPT-P20）
  • Video-计算机中的数学系列

Interesting：直径恒定的异体图形（挑战者号事故）

Trick：sizeof(dxy)/sizeof(dxy[0])获取数组元素数量

计算思维

Slides: L01-计算思维-CS精英挑战营

introduction

CS精英挑战营第1期，2019。

似乎使用雨课堂作为教学工具已成为主流。现在几乎所有的线下课都离不开雨课堂的辅作用。

似乎人们还在等待最终时刻的到来，只剩下最后一分钟。

嗯。

可计算性的歧义：机器可理解性到实际运行可期望（在有限、有效时间内求解问题）。

课程定位：理解一下背后的思想。

引例：楼梯

经典例题：下楼梯（动态规划）。——与或图。

  • 循环枚举法：语音识别例子，暴力匹配优化方法。可以写成迭代或递归。

热身完毕。

跳马

右向跳马。先数字化棋盘，使得位置可以被计算。同时操作的可计算化，坐标的增量变化。

将问题映射到数学空间中去！

确定：递归基+递归方程。

编程Tip：平行数组。两个数组，成对使用。用数组存储跳法，用循环实现遍历。

算无遗策！！！

另外，可以用结构数组代替平行数组。

重构！！！

分书

博弈与权衡。如何将问题数学化十分关键！

观察约束。获得二分图匹配。

回溯法实现遍历。（消除递归的耦合干扰）

通过临时变量（拷贝）分书方案状态，实现不用回溯。

八皇后

利用统计每行每列每对角线来判断是否合法。

人鬼渡河

建立数学模型！！！考察变化的量，寻找可算的量。状态数字化。

放球问题

Slides: here

抽象思维

Slides: L03-抽象思维-CS精英挑战营

容斥原理

Slides: day2-IEP.pdf

排序

Slides: 190516.排序.pdf

去重

Slides: 190517.去重.pdf

递推关系求解

选取

凸包

可持久化数据结构研究.pdf

OJ题集

过河问题

题目描述

农夫(Human)过河。一个农夫带着一只狼(Wolf)，一只羊(Sheep)和一些菜(Vegetable)过河。河边只有一条船，由于船太小，只能装下农夫和他的一样东西。在无人看管的情况下，狼要吃羊，羊要吃菜，请问农夫如何才能使三样东西平安过河?

输入格式

没有输入

输出格式

输出一行，为最终的过河方式，方案格式为 过河人员、回来人员、过河人员、回来人员、…、过河人员。

过去和回来的人员之间，用空格隔开。

以四个生物英文的首字母代指对应的生物(H->Human,W->Wolf,S->Sheep,V->Vegetable)

具体见样例输出。

输出任意可行方案即可。

样例输入

无

样例输出

1
HS H HW H

注释

时间限制：1 s

空间限制：512 MB

样例输出仅用于解释输出格式，非答案。

在此样例输出描述的方案为：

人和羊过去，人回来，人和狼过去，人回来，此时对岸狼把羊吃了，不符合题目要求，故非正确答案。

Code 打表

1
2
3
4
5
6
7
#include <bits/stdc++.h>
using namespace std;

int main(){
	printf("HS H HW HS HV H HS\n");
	return 0;
}

分水问题

题目描述

有A、B和C三个杯子，容量依次为80ml、50ml和30ml。现在A杯中装满了80ml的水，B和C都是空杯。A中的水可以倒入B杯或C杯中，反之，B和C也可以往A中倒，还可以互相倒来倒去。为了计量，对于某一个杯子而言，不是被倒满，就是被倒空。也就是说，要么倒水的杯子空了，要么被倒水的杯子满了，这次倒水操作才会停止。请你编一个程序，将原来的80ml的酒分别倒入A和B两个杯子中，各有40ml。输出每一步的操作。

输入格式

没有输入

输出格式

第一行输出一个整数n，表示步骤的数量。

之后有n行，每行表示一个操作，包含两个字母 x 和 y，表示将 x 杯的酒，倒入y中。

输出任意可行方案即可。

样例输入

无

样例输出

1
2
3
4
5
4
A B
A C
B A
C B

注释

时间限制：1 s

空间限制：512 MB

样例输出仅用于解释输出格式，非答案。

在此样例输出描述的方案为：

一共有4步

最初状态：（A:80, B:0, C:0）

  • A 倒入 B。（A:30, B:50, C:0)
  • A 倒入 C。（A:0, B:50, C:30)
  • B 倒入 A。（A:50, B:0, C:30)
  • C 倒入 B。（A:50, B:30, C:0)

最终，A中有50ml，B中有30ml，C中有0ml，不符合题目要求，故非正确答案。

Code 打表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;

int main(){
	printf("7\n");
	printf("A B\n");
	printf("B C\n");
	printf("C A\n");
	printf("B C\n");
	printf("A B\n");
	printf("B C\n");
	printf("C A\n");
	return 0;
}

带洞N皇后问题

题目描述

N皇后问题是一个经典的问题，其目标是在一个N*N的棋盘上的每一行放置1个皇后，并使其不能互相攻击（同一行、同一列、同一斜线上的皇后都会自动攻击）。

现在，我们将棋盘上的一些位置挖洞，挖洞的位置不能放置棋子。此时，问一共有多少种可能的放置方法？

输入格式

输入第一行有一个整数N，表示棋盘大小。 接下来会有N行，每行有N个被空格隔开的整数，表示该棋盘位置是否有洞。（0为正常，1为有洞）。

输出格式

输出一行，包含一个整数，表示当前N皇后的放置方案数。

样例输入

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

样例输出

1
1

数据范围

1 <= N <= 10

时间限制：1 s

空间限制：512 MB

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
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 11;

bool valid[MAX_N][MAX_N];  // 棋盘缺陷则为1
int Num; // 方案数
int N; // N 皇后

struct place_state{
	int Q[MAX_N];
	bool S[MAX_N], L[2 * MAX_N + 1], R[2 * MAX_N + 1];
};

bool IsValid(int col, int row){
	return valid[col][row];
}

bool IsSafe(int col, int row, place_state state){
	return state.S[row] && state.R[col + row] && state.L[col - row + N];
}

place_state GetNewState(int col, int row, place_state state){
	place_state next_state = state;
	next_state.Q[col] = row;
	next_state.S[row] = next_state.R[col + row] = next_state.L[col - row + N] = false;
	return next_state;
}

void PrintState(place_state state){
	cout<<"---------------"<<endl;
	for(int i = 1; i <= N; ++i)
		for(int j = 1; j <= N; ++j){
			if(!IsValid(i, j))
				cout<<"1";
			else if(state.Q[i] == j)
				cout<<"X";
			else 
				cout<<"0";
			cout<<" \n"[j==N];
		}
}


void Try(int col, place_state state){
	if (col == N + 1){ // 超限
		Num ++;
		// PrintState(state);
		return ;
	}
	for(int row = 1; row <= N; row++){
		if(IsValid(col, row)){
			if(!IsSafe(col ,row, state)) continue;
			Try(col + 1, GetNewState(col, row, state));
		}
	}

}

int main(){
	cin >> N;
	bool tmp;
	for(int i = 1; i <= N; ++i)
		for(int j = 1; j <= N; ++j){
			cin >> tmp;
			valid[i][j] = !tmp;
		}
	
	place_state _init;
	for(int i = 0; i < MAX_N; ++i) _init.S[i] = true;
	for(int i = 0; i < 2*MAX_N + 1; ++i) _init.L[i] = _init.R[i] = true;

	Try(1, _init);

	cout<< Num <<endl;

	return 0;
}

九连环

题面描述

九连环是一款经典的智力玩具，其规则与玩法见这里 。一个经典的九连环如下图所示。我们按下图的示意，将环从左到右编号。

img

小C拿个一个九连环玩了七七四十九天，将其中一些环解下了。现在，你拿着这个小C玩过的九连环，问最少需要多少步，可以将所有环解下？其中，一步指将一个环解下，或将一个环挂上。

输入描述

第一行一个正整数 n

，表示被解下环的数量。

第二行有 n

个正整数

xi

，表示被解下的环的编号。

输出描述

输出将环解下的最少步数

样例输入

1
2
8
2 3 4 5 6 7 8 9

样例输出

1
1

数据范围

0≤n≤9,1≤xi≤9

时间限制：1 s

空间限制：512 MB

Code

1

翻译机

题面描述

为了和外星人愉快的唠嗑，小C准备编写一个全能语言翻译机。他的目标是能够翻译世界上所有的语言，让全世界、全宇宙的生物都无障碍交流！在热血澎湃的思考了一周以后，他迈出了第一步。他准备先写一个简单的语言翻译机。

作为一个简单的翻译机，小C希望其能够帮助人类小A、计算机小B和小C进行愉快的交流。下面是几个常见的话题：

关于星期：

  • 人类小A：”Today is Monday/Tuesday/Wednesday/Thursday/Friday/Saturday/Sunday.”
  • 计算机小B：”Var day=1/2/3/4/5/6/7;”
  • 小C：”Oh, my god. that’s incredible. You know what? I just found that today is MMMonday/TTTuesday/WWWednesday/TTThursday/FFFriday/SSSaturday/SSSunday!”

关于今天的计划：

  • 人类小A：”I want to XXX.”
  • 计算机小B：”Var plan=”XXX”;”
  • 小C：”My god! What should I do today? Let me see. Well, I have an excellent idea! Let us go to XXX.”

其中XXX为一个由空格和大小写字母组成的字符串。

关于点餐：

  • 人类小A: “N XXX, please.”
  • 计算机小B: “Var item=”XXX”; Var num=N;”

  • 小C：”I want one XXX, and one more, and one more, and one more …, and one more.” (共N-1个”and one more”)

    其中N为一个整数，XXX为一个由空格和大小写字母组成的字符串。

现在，有小A、小B、小C中有两个相遇了，请你编写程序，将其中一位的话翻译给另外一位听。

输入格式

第一行为一个整数T，表示有T句话需要翻译。

接下来有T行，每行包含三个部分 X Y Z。其中X和Y为‘A’，’B‘，’C’中的一种，表示将X的话翻译到Y。(X,Y可能相同)。Z为一句由X说的话，格式如题意所述。

输出格式

对于每次翻译请求，输出翻译后的结果。

样例输入

1
2
3
4
5
6
7
8
9
10
9
A B Today is Monday.
A B I want to buy some eggs.
A B 2 cola, please.
B C Var day=3;
B C Var plan="shutdown";
B C Var item="battery"; Var num=3;
C A Oh, my god. that's incredible. You know what? I just found that today is MMMonday!
C A My god! What should I do today? Let me see. Well, I have an excellent idea! Let us go to eat the keyboard.
C A I want one mountain, and one more.

样例输出

1
2
3
4
5
6
7
8
9
Var day=1;
Var plan="buy some eggs";
Var item="cola"; Var num=2;
Oh, my god. that's incredible. You know what? I just found that today is WWWednesday!
My god! What should I do today? Let me see. Well, I have an excellent idea! Let us go to shutdown.
I want one battery, and one more, and one more.
Today is Monday.
I want to eat the keyboard.
2 mountain, please.

数据范围

T ≤ 30

时间限制：1 s

空间限制：512 MB

提示

按照英语语法，可数名词单复数形式应不同。此处为了简便，忽略该语法，直接照搬原话中的词即可。

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include <bits/stdc++.h>
using namespace std;

string weekTable[8] = {"", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};

class Idea{
public:
	string task; // week, plan, order
	int var;
	string varString, input;
	char varCharString[100];
	void GetIdea(char type){
		cin >> input;
		switch(type){
			case 'A': // human
				if(input == "Today"){ // week
					cin >> input; cin >> varString;
					varString = varString.substr(0, varString.length()-1);
					task = "week";
					for(int i = 1; i < 8; ++i)
						if(varString == weekTable[i]) var = i;
				}
				else if(input == "I"){ // plan
					cin >> input; cin >> input;
					char tmp;
					int i = 0; scanf("%c", &tmp);
					do{
						scanf("%c", &tmp);
						varCharString[i++] = tmp;
					} while(tmp !='.');
					varCharString[i - 1] = '\0';
					task = "plan";
				}
				else{ // order
					var = stoi(input);
					char tmp;
					int i = 0; scanf("%c", &tmp);
					do{
						scanf("%c", &tmp);
						varCharString[i++] = tmp;
					} while(tmp !=',');
					varCharString[i - 1] = '\0';
					cin >> input;
					task = "order";
				}
				break;
			case 'B': // computer
				char tmp;
				cin >> tmp;
				if(tmp == 'd'){ // week
					cin >> input;
					int pos1 = input.find('=');
					int pos2 = input.find(';');
					var = stoi(input.substr(pos1 + 1, pos2 - pos1 - 1));
					task = "week";
				}
				else if(tmp == 'p'){ // plan
					do{ cin >> tmp; } while(tmp !='"');
					int i = 0;
					do{
						scanf("%c", &tmp);
						varCharString[i++] = tmp;
					} while(tmp !='"');
					varCharString[i - 1] = '\0';
					do{ cin >> tmp; } while(tmp !=';');
					task = "plan";
				}
				else{ // order
					do{ cin >> tmp; } while(tmp !='"');
					int i = 0;
					do{
						scanf("%c", &tmp);
						varCharString[i++] = tmp;
					} while(tmp !='"');
					varCharString[i - 1] = '\0';
					do{ cin >> tmp; } while(tmp !=';');

					cin >> input; cin >> varString;
					int pos3 = varString.find('=');
					int pos4 = varString.find(';');
					var = stoi(varString.substr(pos3 + 1, pos4 - pos3 - 1));
					task = "order";
				}
				break;
			case 'C': // dummy
				if(input == "Oh,"){ // week
					do{cin >> input;} while(input != "is");
					cin >> varString;
					varString = varString.substr(2, varString.length()-1 - 2);
					task = "week";
					for(int i = 1; i < 8; ++i)
						if(varString == weekTable[i]) var = i;
					task = "week";
				}
				else if(input == "My"){ // plan
					do{cin >> input;} while(input != "to");
					int i = 0; scanf("%c", &tmp);
					do{
						scanf("%c", &tmp);
						varCharString[i++] = tmp;
					} while(tmp !='.');
					varCharString[i - 1] = '\0';
					task = "plan";
				}
				else{ // order
					do{cin >> input;} while(input != "one");
					int i = 0; scanf("%c", &tmp);
					do{
						scanf("%c", &tmp);
						varCharString[i++] = tmp;
					} while(tmp !=',' && tmp !='.');
					varCharString[i - 1] = '\0';

					var = 1;
					if(tmp != '.'){
						do{
							cin >> input;
							if(input == "and") var++;
						} while(input != "more.");
					}
					
					task = "order";
				}

				break;
		}

	}
	void Print(char type){
		switch(type){
			case 'A': // human
				if(task == "week"){
					cout<< "Today is "<< weekTable[var]<<"."<<endl;
				}
				else if(task == "plan"){
					cout<< "I want to "<< varCharString<<"."<<endl;
				}
				else{ // order
					cout<< var <<" "<< varCharString <<", please."<<endl;
				}
				break;
			case 'B': // computer
				if(task == "week"){
					cout<< "Var day="<< var<<";"<<endl;
				}
				else if(task == "plan"){
					cout<< "Var plan=\""<< varCharString<<"\";"<<endl;
				}
				else{ // order
					cout<< "Var item=\""<< varCharString <<"\"; Var num="<< var <<";"<<endl;
				}
				break;
			case 'C': // dummy
				if(task == "week"){
					cout<< "Oh, my god. that's incredible. You know what? I just found that today is "<< weekTable[var][0] << weekTable[var][0] << weekTable[var]<<"!"<<endl;
				}
				else if(task == "plan"){
					cout<< "My god! What should I do today? Let me see. Well, I have an excellent idea! Let us go to "<< varCharString<<"."<<endl;
				}
				else{ // order
					cout<< "I want one "<<varCharString;
					for(int i = 1; i < var; ++i) cout << ", and one more";
					cout<<"."<<endl;
				}
				break;
		}
	}


};

int main(){
	int n; cin>> n;
	Idea idea;
	for (int i = 0; i < n; ++i){
		char m, n;
		cin >> m >> n;
		idea.GetIdea(m);
		idea.Print(n);
	}
	return 0;
}

花里花哨的计算器

题目描述

有一个花里花哨的计算器，它可以在输入的时候，指定输入的字体。每种字体的对应如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
字体a：
	1234567890
字体b：
	!@#$%^&*()
字体c：
	qwertyuiop
字体d：
	asdfghjkl;
字体e：
	zxcvbnm,./
字体f：
    ... .-. .-. ... .-. .-. .-. .-. .-. .-.
    ..| ..| ..| |.| |.. |.. ..| |.| |.| |.|
    ... .-. .-. .-. .-. .-. ... .-. .-. ...
    ..| |.. ..| ..| ..| |.| ..| |.| ..| |.|
    ... .-. .-. ... .-. .-. ... .-. .-. .-.

现在告诉你输入的数字，以及每个数字所指定的字体。请显示正确的输出。

输入格式

第一行为一个数字T，表示有T组数据。

接下来有T行，每行有一个字符串，表示输入的数字以及每个数字对应的字体，格式为n_1 A_1 n_2 A_2 n_3 A_3 …，其中n_i 为数字（0~9），A_i为其前面那个数字的字体（a~f）。数字个数小于100。

输出格式

输出正确的显示。注意，f字体为多行字体，其他字体为单行字体。若所有数字的字体均为单行字体，则输出为单行。若其中存在一个或多个多行字体，则输出多行，所有单行字体显示在最低行，上方用’.’填充。

样例输入

1
2
3
2
1a2b3c4d5e
1a2b3c4d5e6f7a

样例输出

1
2
3
4
5
6
1@efb
......-..
.....|...
......-..
.....|.|.
1@efb.-.7

数据范围

T ≤ 5

时间限制：1 s

空间限制：512 MB

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
#include <bits/stdc++.h>
using namespace std;

class fontFamily{
	string a = "1234567890";
	string b = "!@#$%^&*()";
	string c = "qwertyuiop";
	string d = "asdfghjkl;";
	string e = "zxcvbnm,./";
	string f[10][5] = {
		{"...", "..|", "...", "..|", "..."},
		{".-.", "..|", ".-.", "|..", ".-."},
		{".-.", "..|", ".-.", "..|", ".-."},
		{"...", "|.|", ".-.", "..|", "..."},
		{".-.", "|..", ".-.", "..|", ".-."},
		{".-.", "|..", ".-.", "|.|", ".-."},
		{".-.", "..|", "...", "..|", "..."},
		{".-.", "|.|", ".-.", "|.|", ".-."},
		{".-.", "|.|", ".-.", "..|", ".-."},
		{".-.", "|.|", "...", "|.|", ".-."} };
};

void PrintFontF(){
	string a[10][5];
	for(int j = 0; j < 5; ++j)
		for(int i = 0; i < 10; ++i)
			cin >> a[i][j];
	cout<<"{";
	for(int i = 0; i < 10; ++i){
		cout<<"{";
		for(int j = 0; j < 5; ++j){
			cout<<"\""<< a[i][j] <<"\"";
			if(j==4) cout<<"}";
			if(i!=9 || j!=4) cout<<",";
			if(j!=4) cout<<" ";
		}
		if(i!=9) cout<<endl;
	}cout<<"};\n";
}

void Output(string input){
	char Out[5][305];
	fontFamily font;
	for(int i = 0; i < input.length(); ++i){
		
	}

}

int main(){
	// PrintFontF();
	int T; cin >> T;
	string a;
	for(int i = 0; i < T; ++i){
		cin>>a;
		Output(a);
	}
	return 0;
}

排序

问题描述

给出n个整数，将它们从小到大排序后输出。

输入格式

第一行为一个正整数n，第二行为n个整数。

输出格式

输出一行n个整数，表示排序后的n个整数。

样例1输入

1
2
5
5 4 2 3 -1

样例1输出

1
-1 2 3 4 5

样例2

点击下载

数据范围

对于前30%的数据，n ≤ 100，给出的n个整数的绝对值不超过10；

对于前60%的数据，n ≤ 5000，给出的n个整数的绝对值不超过10^9；

对于另20%的数据，n ≤ 500000，给出的n个整数的绝对值不超过10^5；

对于100%的数据，n ≤ 500000，给出的n个整数的绝对值不超过10^9。

时间限制：2 s

空间限制：256 MB

提示

大家不妨使用各种排序算法进行测试。

C++的同学，请注意一下输入输出：

若大家使用cin、cout进行输入输出，则需在main函数里的第一行加入ios::sync_with_stdio(false)，否则可能会超时。

推荐大家使用scanf和printf进行输入输出。

Python的同学，建议使用PyPy，具体使用方法请查看新手村的 a+b 那题。

Code $O(nlogn)$ 快速排序

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
#include <bits/stdc++.h>
using namespace std;
#define _OJ_ 

void quickSort(vector<int> &a,int b, int e){
    int i=b,j=e,x=a[(b+e)>>1];
    do{
        while(a[i]<x) i++;
        while(a[j]>x) j--;
        if(i<=j) swap(a[i++],a[j--]);
    }while(i<j);
    if(i<e) quickSort(a,i,e);
    if(b<j) quickSort(a,b,j);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
#ifndef _OJ_
    freopen("OJ.in", "r", stdin);
    freopen("OJ.out", "w", stdout);
#endif
    int n; cin >> n;
    vector<int> a;
    for(int i = 0; i < n; i++){
        int tmp; cin >>tmp;
        a.push_back(tmp);
    }
    quickSort(a, 0, a.size()-1);

    for(int i = 0; i < a.size(); ++i){
        cout<<a[i]<<" \n"[i==a.size()-1];
    }

    return 0;
}

间隙

问题描述

给定长度为 n 的数组 a，其中每个元素都为 [0,2^k) 之间的整数，请求出它们在实数轴上相邻两个数之间的最大值。

由于 n 可能很大，为了避免过大的输入、输出规模，我们会在程序内部生成数据，并要求你输出排序后序列的哈希值。具体方法如下（用c++代码展示）：

1
2
3
4
5
6
7
8
9
10
11
12
13
unsigned int nextInt(unsigned int x){
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    return x;
}

void initData(unsigned int *a, int n, int k, unsigned int seed){
    for (int i = 0; i < n; ++i) {
        seed = nextInt(seed);
        a[i] = seed >> (32 - k);
    }
}

输入将会给定 n, k, seed。

你可以调用 initData(a, n, k, seed) 来获得需要排序的 a 数组。

输入格式

一行 3 个用空格隔开的整数 n, k, seed，意义见题目描述。

输出格式

一行一个整数，表示最大间隙。

样例输入

1
5 4 233333

样例输出

1
5

样例解释

生成的序列应为 4 10 13 9 4，最大间隙为 9-4=5。

数据范围

本题共设置 4 组数据。

对于第 1 组数据，保证 n=1000，k=16。

对于第 2 组数据，保证 n=5*10^6，k=32。

对于第 3 组数据，保证 n=2^26=67108864，k=16。

对于第 4 组数据，保证 n=2^26=67108864，k=32。

保证给定的 seed 在 32 位无符号整数的范围内。

时间限制：5 s

空间限制：1 GB

Code $O(nlogn)$ 快排 50%

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
#include <bits/stdc++.h>
using namespace std;
#define _OJ_

unsigned int a[67108864 + 5];

unsigned int nextInt(unsigned int x){
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    return x;
}

void initData(unsigned int *a, int n, int k, unsigned int seed){
    for (int i = 0; i < n; ++i) {
        seed = nextInt(seed);
        a[i] = seed >> (32 - k);
    }
}

void quickSort(unsigned int *a,int b, int e){
    int i=b,j=e;
    unsigned int x=a[(b+e)>>1];
    do{
        while(a[i]<x) i++;
        while(a[j]>x) j--;
        if(i<=j) swap(a[i++],a[j--]);
    }while(i<j);
    if(i<e) quickSort(a,i,e);
    if(b<j) quickSort(a,b,j);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
#ifndef _OJ_
    freopen("OJ.in", "r", stdin);
    freopen("OJ.out", "w", stdout);
#endif
    int n, k ,seed;
    cin >> n >> k >> seed;
    initData(a,n,k,seed);
    quickSort(a, 0, n-1);
    unsigned int ans = 0;
    for(int i = 1; i < n; ++i){
        ans = max(ans, a[i] - a[i - 1]);
    }
    cout<<ans<<endl;

    return 0;
}

Code $O(n+m)$ 桶排

m为桶的个数。

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
#include <bits/stdc++.h>
using namespace std;

// ================= 代码实现开始 =================

typedef unsigned int u32;

// 以下代码不需要解释，你只需要知道这是用于生成数据的就行了

u32 nextInt(u32 x) {
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    return x;
}

void initData(u32* a, int n, int k, u32 seed) {
    for (int i = 0; i < n; ++i) {
        seed = nextInt(seed);
        a[i] = seed >> (32 - k);
    }
}

// 以上代码不需要解释，你只需要知道这是用于生成数据的就行了

const int N = 67108864;
const int m = 1 << 22; //桶的个数

//a：输入中给定的数组 
//l：每个“桶”中的最小值 
//r：每个“桶”中的最大值 
u32 a[N + 1]; //为了省去传入数据花费的时间，直接将需要求解的maxGap数组开设成了全局变量
u32 l[m + 1], r[m + 1]; // 本题的数据比较松

// 这是求解答案的函数，你需要对全局变量中的 a 数组求解 maxGap 问题
// n, k：意义与题目描述相符
// 返回值：即为答案（maxGap）
u32 maxGap(int n, int k) {
    //初始化
	memset(l, -1, sizeof(int) * m); // 将l中的所有位置赋值为-1
	memset(r, -1, sizeof(int) * m); // 将r中的所有位置赋值为-1
	
	const int _k = max(k -22, 0); //这是一个参数，辅助后续用位运算代替除法
	for(int i = 0; i < n; ++i) {
		u32 b1 = a[i] >> _k; //(这个式子等价于a[i]除以2的_k次幂)求出a[i]所在的桶
		//更新对应桶的l,r
		//cout<<"k="<<k<<"; _k="<<_k<<"; 第"<<b1<<"桶：["<<l[b1]<<","<<r[b1]<<"]"<<endl;
		if(l[b1] == -1/*1*/)
			l[b1] = r[b1] = a[i]/*2*/;  //当桶为空时，重设最大、最小元
		else if (a[i] < l[b1])
			l[b1] = a[i];
		else if (a[i] > r[b1])
			r[b1] = a[i];
		//cout<<"第"<<i+1<<"个数："<<a[i]<<"===>"<<"第"<<b1<<"桶：["<<l[b1]<<","<<r[b1]<<"]"<<endl; 
	}
	
	//统计答案
	u32 last = -1;
	u32 ans = 0;
	//cout<<"=========统计答案："<<endl;
	//for(int i = 0; i < n; ++i) cout<<"a["<<i<<"] = "<<a[i]<<"; "<<endl;
	for(int i = 0; i < m; ++i)
		if(l[i] != -1/*3*/){  //非空桶 
			//cout<<"第"<<i+1<<"轮：last = "<<last<<"; ans = "<<ans<<endl; 
			if(last > l[i])  //找最小元 
				last = l[i];
			if(l[i] - last/*4*/ > ans)
				ans = l[i] - last/*4*/;
			last = r[i];
		}
	return ans;
}

// ================= 代码实现结束 =================

int main() {
    int n, k;
    u32 seed;

    scanf("%d%d%u", &n, &k, &seed);
    initData(a, n, k, seed);

    u32 ans = maxGap(n, k);

    printf("%u\n", ans);
    return 0;
}

中位数

问题描述

给定长度为 2n−1

的数组，对于每个

k=1,2,…,n

，求出前

2k−1

个数的中位数。

输入格式

第一行一个正整数 n

。

接下来一行 2n−1

个正整数，表示所给数组。

输出格式

输出 n

行，第

i

行表示这个数组的前

2i−1

个数的中位数。

样例输入

1
2
3
8 7 6 9 9

样例输出

1
2
3
8
7
8

数据范围

对于 100% 的数据，n≤3×105

所有输入数据的数值都在 32 位整型范围内。

时间限制：1 s

空间限制：512 MB

Code $O(nlogn)$ 双堆 55%

拿55%的原因居然是因为输入输出？？？WTF（把cin、cout全换掉就OK了）

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
#include <bits/stdc++.h>
using namespace std;
#define _OJ_ 

priority_queue<int,vector<int>,less<int>> L;// 大根左堆
priority_queue<int,vector<int>,greater<int>> R;// 小根右堆

int main(){
    int n; scanf("%d", &n);
    int mid; scanf("%d", &mid);; printf("%d\n", mid);
    for(int i = 2; i <= 2*n-1; i++){
        int tmp; scanf("%d", &tmp);;
        if(tmp < mid) L.push(tmp);
        else R.push(tmp);
        if(i % 2){
        	while(L.size() != R.size()){
        		if(L.size() > R.size()){
        			R.push(mid);
        			mid = L.top(); L.pop();
        		} else{
        			L.push(mid);
        			mid = R.top(); R.pop();
        		}
        	}
        	printf("%d\n", mid);
        }
    }

    return 0;
}

搭积木(toy)

题目描述

小Z有n块一模一样的正方体积木，他要把这些积木放到m×m的网格中。每块积木要么放到恰好一个格子上，要么叠到另一块积木上。好奇的他想知道，有多少种把这n块积木都放进网格的摆法？

输入格式

一行两个整数n,m

，分别表示积木的数量和网格的边长。

输出格式

一行一个整数，表示答案对109+7取模的结果。

数据范围

1≤n≤1000,1≤m≤30

时间限制：1s；空间限制：512MiB。

样例1

Input

1
2 2

Output

1
10

样例1解释

有两块积木，要放到2×2的网格中。将两块积木叠在一起有C14=4种方法，两个积木分开放有C24=6种方法，共10种。

样例2

Input

1
1000 30

Output

1
443860595

样例2解释

虽然答案很大，但是对109+7取了模，输出就很小了。

Code $O(n*m)$ DP

迷之数据范围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
#define _OJ_ 
#define MOD 1000000007

int CMem[10005][10005] = {0};

int C(int a, int b){
	if(a < b) return 0;
	if(b == 0) return 1;
	return CMem[a][b] ? CMem[a][b] : CMem[a][b] = (C(a-1,b) + C(a-1,b-1)) % MOD;
}

int main(){
	int n; scanf("%d", &n);
	int m; scanf("%d", &m);
	printf("%d", C(n + m*m - 1, n));

	return 0;
}

凑零钱(money)

题目描述

小Z有n枚硬币，面值分别为w1,w2,⋯,wn。请问他总共有多少种办法凑出v块钱？

请注意，相同面值的硬币我们也认为是不同的。

输入格式

第一行两个整数n,v，含义如题所述；

第二行n个整数，第i个整数为wi，表示第i个硬币的面值。

输出格式

一行一个整数，表示答案。特别地，如果没有合法方案，输出0。

数据范围

1≤n≤30,1≤v≤900,∀i,1≤wi≤30。

时间限制：1s；空间限制：512MiB。

样例1

Input

1
2
4 6
1 2 4 4

Output

1
2

样例1解释

有两种选法：

  1. 选1号、2号、3号硬币；
  2. 选1号、2号、4号硬币。

样例2

Input

1
2
21 315
28 26 26 24 10 26 30 4 26 5 21 17 18 7 11 12 16 8 6 30 8

Output

1
123

Code DP

可以构造母函数：

答案就是$x^v$的系数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;

int n,v,w[35];
int dp[1005] = {1}; // dp[0]=1，其它=0. dp[k]表示凑出k元的方法数

int main(){
	scanf("%d %d", &n, &v);
	for(int i = 0; i < n; ++i){
		scanf("%d", &w[i]);
		for(int j = v; j >= w[i]; --j){  // 反向DP
			dp[j] += dp[j - w[i]];
		}
	}
	printf("%d\n", dp[v]);

	return 0;
}

观察(observe)

题目描述

在一个二维平面上，每个满足1≤x≤n,1≤y≤m的整点(x,y)上都种有一棵树，共n×m棵。现在，小Z站在(0,0)处欣赏这些树。因为一棵树可能会挡住一些树，小Z能看到一棵树当且仅当他和树的连线上没有其他树。请问小Z总共能看见多少棵树？

输入格式

第一行两个整数n,m，含义如题所述。

输出格式

一行一个整数，表示小Z能看见的树的数量。

数据范围

存在10%的数据，有1≤n,m≤10；

存在30%的数据，有1≤n,m≤1000；

存在80%的数据，有1≤n,m≤10000；

对于所有数据，有1≤n,m≤105。

时间限制：1s；空间限制：512MiB。

样例1

Input

1
3 3

Output

1
7

样例1解释

(2,2)和(3,3)均被(1,1)挡住，共7棵能看见。

样例2

Input

1
100000 100000

Output

1
6079301507

提示

点击查看

Code

无非就是求形如$\cfrac{x}{y}$的最简分式数量。

1

Code

1

Code

1

Code

1

Code

1

Code

1

Code

1

Code

1