蓝桥杯：模拟、枚举

爱丽丝要完成一项修剪灌木的工作。

有 N 棵灌木整齐的从左到右排成一排。

爱丽丝在每天傍晚会修剪一棵灌木，让灌木的高度变为 0 厘米。

爱丽丝修剪灌木的顺序是从最左侧的灌木开始，每天向右修剪一棵灌木。

当修剪了最右侧的灌木后，她会调转方向，下一天开始向左修剪灌木。

直到修剪了最左的灌木后再次调转方向。

然后如此循环往复。

灌木每天从早上到傍晚会长高 1 厘米，而其余时间不会长高。

在第一天的早晨，所有灌木的高度都是 0 厘米。爱丽丝想知道每棵灌木最高长到多高。

输入格式
一个正整数 N，含义如题面所述。

输出格式
输出 N 行，每行一个整数，第行表示从左到右第 i 棵树最高能长到多高。

数据范围
对于 30% 的数据，N≤10，
对于 100% 的数据，1

• 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

示例代码：

#include 

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second

const int N = 1e4+10;

int n;

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> n;
	
	for(int i = 1; i <= n; ++i)
	{
	    int res = max(2*(n-i), 2*(i-1));
	    cout << res << endl;
	}
	
	return 0;
}
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

二、特殊年份

标签： 第十二届蓝桥杯省赛第二场C++ B组、模拟、枚举

思路：就是输入五个数，每个数取出每一位判断即可。

题目描述：

今年是 2021 年，2021 这个数字非常特殊，它的千位和十位相等，个位比百位大 1，我们称满足这样条件的年份为特殊年份。

输入 5 个年份，请计算这里面有多少个特殊年份。

输入格式
输入 5 行，每行一个 4 位十进制数（数值范围为 1000 至 9999），表示一个年份。

输出格式
输出一个整数，表示输入的 5 个年份中有多少个特殊年份。

输入样例：
2019
2021
1920
2120
9899
输出样例：
2
样例解释
2021 和 9899 是特殊年份，其它不是特殊年份。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

示例代码：

#include 

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second

const int N = 1e5+10;

int res, year;
int n, m;


int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	for(int i = 0; i < 5; ++i)
	{
		cin >> year;
		int t1 = year / 1000;
		int t2 = year / 100 % 10;
		int t3 = year % 100 / 10;
		int t4 = year % 10;
		if(t1 == t3 && t4 == t2 + 1) res++;
	}
	
	cout << res << endl;
	
	return 0;
}
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

三、刷题统计

标签： 第十三届蓝桥杯省赛C++ B组、模拟、枚举

思路：就是先计算有多少周，然后再枚举七天就行了。另外这题刚开始 $n$ 拿 $ULL$ 存了，所以不可能小于 $0$ ，还是得注意些。

题目描述：

小明决定从下周一开始努力刷题准备蓝桥杯竞赛。

他计划周一至周五每天做 a 道题目，周六和周日每天做 b 道题目。

请你帮小明计算，按照计划他将在第几天实现做题数大于等于 n 题？

输入格式
输入一行包含三个整数 a,b 和 n。

输出格式
输出一个整数代表天数。

数据范围
对于 50% 的评测用例，1≤a,b,n≤106，
对于 100% 的评测用例，1≤a,b,n≤1018。

输入样例：
10 20 99
输出样例：
8
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

示例代码：

#include 

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
#define x first
#define y second

const int N = 1e5+10;

LL a = 0, b = 0, n = 0;
ULL res = 0;

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> a >> b >> n;
	
	LL week = n / ((ULL)5*a+(ULL)2*b);
	n -= week * ((ULL)5*a+(ULL)2*b); 
	res += week * 7;
	if(n) 
	{
		for(int i = 1; i <= 7; ++i)
		{
			res++;
			if(i < 6)
			{
				n -= a;
			}
			else
			{
				n -= b;
			}
			if(n <= 0) break;
		}
	}
	
	cout << res << endl;
	
	
	return 0;
}
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

四、日期问题

标签：第八届蓝桥杯省赛C++ B组、第八届蓝桥杯省赛Java B组/C组、模拟、日期问题、枚举

思路：遇到日期问题就先把模板写好，然后一般都是直接拿数来枚举日期，如果数的范围太大，一般要按要求构造数，比如说回文日期，直接枚举年份就行了。然后就按条件判断即可。

题目描述：

小明正在整理一批历史文献。这些历史文献中出现了很多日期。

小明知道这些日期都在1960年1月1日至2059年12月31日。

令小明头疼的是，这些日期采用的格式非常不统一，有采用年/月/日的，有采用月/日/年的，还有采用日/月/年的。

更加麻烦的是，年份也都省略了前两位，使得文献上的一个日期，存在很多可能的日期与其对应。

比如02/03/04，可能是2002年03月04日、2004年02月03日或2004年03月02日。

给出一个文献上的日期，你能帮助小明判断有哪些可能的日期对其对应吗？

输入格式
一个日期，格式是”AA/BB/CC”。

即每个’/’隔开的部分由两个 0-9 之间的数字（不一定相同）组成。

输出格式
输出若干个不相同的日期，每个日期一行，格式是”yyyy-MM-dd”。

多个日期按从早到晚排列。

数据范围
0≤A,B,C≤9
输入样例：
02/03/04
输出样例：
2002-03-04
2004-02-03
2004-03-02
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 

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second

const int N = 1e5+10;

int a, b, c;

const int days[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

bool is_leap(int y)
{
	if(y % 400 == 0 || y % 4 == 0 && y % 100 != 0) return true;
	return false;
}

int get_month_day(int y, int m)
{
	if(m == 2) return days[m] + is_leap(y);
	return days[m];
}

bool is_vaild(int y, int m, int d)
{
	if(m < 1 || m > 12 || d < 1 || d > 31) return false;
	return d <= get_month_day(y,m);
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	scanf("%d/%d/%d", &a, &b, &c);
	
	for(int date = 19600101; date <= 20591231; ++date)
	{
		int y = date / 10000, m = date % 10000 / 100, d = date % 100;
		int t = y % 100;
		if( !((a == t && b == m && c == d) || (a == m && b == d && c == t) || (a == d && b == m && c == t)) ) continue;
		if(!is_vaild(y,m,d)) continue;
		printf("%d-%02d-%02d\n", y, m, d);
	}
	
	
	return 0;
}
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

五、航班时间

标签： 第九届蓝桥杯省赛C++ A组、第九届蓝桥杯省赛Java A组、模拟、枚举

思路：这道题首先要明白一个公式，如下：$$t_1+时差+飞行时间=t_2$$$$t_3-时差+飞行时间=t_4$$$$飞行时间=(t_2+t_4-t_1-t_3)÷2$$ 然后就是我们可以把时间都化成秒来计算，然后就套公式就行了，再一个就是输入的问题了，详情见代码。
注意： 无论是拿 $cin,scanf$ 读入都不会把空格或者换行符抵消掉，所以在 $getline$ 前，一定要再拿 $getline$ 把其吃掉。

题目描述：

小 h 前往美国参加了蓝桥杯国际赛。

小 h 的女朋友发现小 h 上午十点出发，上午十二点到达美国，于是感叹到“现在飞机飞得真快，两小时就能到美国了”。

小 h 对超音速飞行感到十分恐惧。

仔细观察后发现飞机的起降时间都是当地时间。

由于北京和美国东部有 12 小时时差，故飞机总共需要 14 小时的飞行时间。

不久后小 h 的女朋友去中东交换。

小 h 并不知道中东与北京的时差。

但是小 h 得到了女朋友来回航班的起降时间。

小 h 想知道女朋友的航班飞行时间是多少。

对于一个可能跨时区的航班，给定来回程的起降时间。

假设飞机来回飞行时间相同，求飞机的飞行时间。

输入格式
一个输入包含多组数据。

输入第一行为一个正整数 T，表示输入数据组数。

每组数据包含两行，第一行为去程的起降时间，第二行为回程的起降时间。

起降时间的格式如下:

h1:m1:s1 h2:m2:s2
h1:m1:s1 h3:m3:s3 (+1)
h1:m1:s1 h4:m4:s4 (+2)
第一种格式表示该航班在当地时间h1时m1分s1秒起飞，在当地时间当日h2时m2分s2秒降落。

第二种格式表示该航班在当地时间h1时m1分s1秒起飞，在当地时间次日h2时m2分s2秒降落。

第三种格式表示该航班在当地时间h1时m1分s1秒起飞，在当地时间第三日h2时m2分s2秒降落。

输出格式
对于每一组数据输出一行一个时间hh:mm:ss，表示飞行时间为hh小时mm分ss秒。

注意，当时间为一位数时，要补齐前导零，如三小时四分五秒应写为03:04:05。

数据范围
保证输入时间合法（0≤h≤23,0≤m,s≤59），飞行时间不超过24小时。

输入样例：
3
17:48:19 21:57:24
11:05:18 15:14:23
17:21:07 00:31:46 (+1)
23:02:41 16:13:20 (+1)
10:19:19 20:41:24
22:19:04 16:41:09 (+1)
输出样例：
04:09:05
12:10:39
14:22:05
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

示例代码：

#include 

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second

const int N = 1e5+10;

int T;
string line;

void get_time(LL& t1, LL& t2)
{
	getline(cin, line);
	if(line.back() == ')')
	{
		int h1,m1,s1,h2,m2,s2,k;
		sscanf(line.c_str(), "%d:%d:%d %d:%d:%d (+%d)", &h1,&m1,&s1, &h2,&m2,&s2, &k);
		t1 = h1 * 3600 + m1 * 60 + s1;
		t2 = (h2 + k * 24) * 3600 + m2 * 60 + s2;
	}
	else
	{
		int h1,m1,s1,h2,m2,s2;
		sscanf(line.c_str(), "%d:%d:%d %d:%d:%d", &h1,&m1,&s1, &h2,&m2,&s2);
		t1 = h1 * 3600 + m1 * 60 + s1;
		t2 = h2 * 3600 + m2 * 60 + s2;
	}
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> T;
	getline(cin, line);
	while(T--)
	{
		LL t1 = 0,t2 = 0,t3 = 0,t4 = 0;
		get_time(t1,t2); get_time(t3,t4);
		LL res = (t2 + t4 - t1 - t3) / 2;
		//cout << res << endl;
		int h = res / 3600, m = res % 3600 / 60, s = res % 60;
		printf("%02d:%02d:%02d\n", h, m, s);
	}
	
	return 0;
}
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

六、纸张尺寸

标签：第十三届蓝桥杯省赛C++ C组、第十三届蓝桥杯省赛Java C组、第十三届蓝桥杯省赛Python B组/C组、模拟、枚举

思路：整体思路就是 $a$ 是最长的边，然后将其除以二，然后再交换长短边，然后 $a$ 又成了长边，然后重复操作 $n$ 次，这个 $n$ 可以通过格式化输入得到。

题目描述：

在 ISO 国际标准中定义了 A0 纸张的大小为 1189mm×841mm，将 A0 纸沿长边对折后为 A1 纸，大小为841mm×594mm，在对折的
过程中长度直接取下整（实际裁剪时可能有损耗）。

将 A1 纸沿长边对折后为 A2 纸，依此类推。

输入纸张的名称，请输出纸张的大小。

输入格式
输入一行包含一个字符串表示纸张的名称，该名称一定是 A0、A1、A2、A3、A4、A5、A6、A7、A8、A9 之一。

输出格式
输出两行，每行包含一个整数，依次表示长边和短边的长度。

输入样例1：
A0
输出样例1：
1189
841
输入样例2：
A1
输出样例2：
841
594
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

示例代码：

#include 

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second

const int N = 1e5+10;

int n, m;

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	scanf("A%d", &n);
	int a = 1189, b = 841;
	while(n--)
	{
		a /= 2;
		swap(a,b);
	}
	
	cout << a << endl;
	cout << b << endl;
	
	return 0;
}
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

七、特别数的和

标签： 第十届蓝桥杯省赛C++ B组、第十届蓝桥杯省赛Java B组、模拟、枚举

思路：就是从 $1\sim n$ 中遍历一遍，然后依次判断每一个数中是否有一位为 $2、0、1、9$ 当中的一个，满足就加起来即可。

题目描述：

小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0），在 1 到 40 中这样的数包括 1、2、9、10 至 32、39
 和 40，
 共 28 个，他们的和是 574。

请问，在 1 到 n 中，所有这样的数的和是多少？

输入格式
共一行，包含一个整数 n。

输出格式
共一行，包含一个整数，表示满足条件的数的和。

数据范围
1≤n≤10000
输入样例：
40
输出样例：
574
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

示例代码：

#include 

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second

const int N = 1e5+10;

int n;
LL res;

bool check(int x)
{
	while(x)
	{
		int t = x % 10; x /= 10;
		if(t == 2 || t == 0 || t == 1 || t == 9) return true; 
	}
	return false;
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> n;
	for(int i = 1; i <= n; ++i)
	{
		if(check(i)) res += i;
	}
	
	cout << res << endl;
	
	return 0;
}
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

八、旋转

标签： 第十届蓝桥杯省赛C++ C组、第十届蓝桥杯省赛Java C组、模拟

思路：其实就是从左向右，从下到上的依次遍历即可。

题目描述：

图片旋转是对图片最简单的处理方式之一，在本题中，你需要对图片顺时针旋转 90 度。

我们用一个 n×m 的二维数组来表示一个图片，例如下面给出一个 3×4 的图片的例子：

1 3 5 7
9 8 7 6
3 5 9 7
这个图片顺时针旋转 90 度后的图片如下：

3 9 1
5 8 3
9 7 5
7 6 7
给定初始图片，请计算旋转后的图片。

输入格式
输入的第一行包含两个整数 n 和 m，分别表示行数和列数。

接下来 n 行，每行 m 个整数，表示给定的图片。图片中的每个元素（像素）为一个值为 0 至 255 之间的整数（包含 0
 和 255）。

输出格式
输出 m 行 n 列，表示旋转后的图片。

数据范围
1≤n,m≤100
输入样例：
3 4
1 3 5 7
9 8 7 6
3 5 9 7
输出样例：
3 9 1
5 8 3
9 7 5
7 6 7
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

示例代码：

#include 

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second

const int N = 110;

int n, m;
int a[N][N];

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	for(int i = 0; i < n; ++i)
	{
		for(int j = 0; j < m; ++j)
		{
			cin >> a[i][j];
		}
	}
	
	for(int j = 0; j < m; ++j)
	{
		for(int i = n - 1; i >= 0; --i)
		{
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
	
	
	return 0;
}
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

九、移动距离

标签： 第六届蓝桥杯省赛C++ B组、第六届蓝桥杯省赛Java A组/C组、模拟

思路：我的思路就是按行和列的顺序去枚举每一个数，具体的思路可以看我之前的博客
二维数组填充问题 ，然后这道题其实就是模拟每一个数的位置，并不需要输出矩阵，因为就会出现内存超限的问题。然后记录这两个数的行和列，然后分别相减再相加即可。

题目描述：

X星球居民小区的楼房全是一样的，并且按矩阵样式排列。

其楼房的编号为 1,2,3…当排满一行时，从下一行相邻的楼往反方向排号。

比如：当小区排号宽度为 6 时，开始情形如下：

1  2  3  4  5  6
12 11 10 9  8  7
13 14 15 .....
我们的问题是：已知了两个楼号 m 和 n，需要求出它们之间的最短移动距离（不能斜线方向移动）。

输入格式
输入共一行，包含三个整数 w,m,n，w 为排号宽度，m,n 为待计算的楼号。

输出格式
输出一个整数，表示 m,n 两楼间最短移动距离。

数据范围
1≤w,m,n≤10000,

输入样例：
6 8 2
输出样例：
4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

示例代码：

#include 

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second

const int N = 1e4+10;

int w, n, m;
int idx = 1;
int dir[4][2] = {0,1, 1,0, 0,-1, 1,0};



int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> w >> n >> m;
	
	int r = 0, c = -1;
	int r1 = -1, r2 = -1, c1 = -1, c2 = -1;
	
	while(true)
	{
		if(r1 != -1 && r2 != -1 && c1 != -1 && c2 != -1) break;
		
		for(int i = 0; i < 4; ++i)
		{
			if(i % 2) 
			{
				int x = r + dir[i][0];
				int y = c + dir[i][1];
				r = x, c = y;
				if(idx == n) r1 = r, c1 = c;
				if(idx == m) r2 = r, c2 = c;
				idx++;
			}
			else
			{
				while(true)
				{
					int x = r + dir[i][0];
					int y = c + dir[i][1];
					if(x < 0 || y < 0 || y >= w) break;
					r = x, c = y;
					if(idx == n) r1 = r, c1 = c;
					if(idx == m) r2 = r, c2 = c; 
					idx++;
				}
			}
		}
	}
	
	cout << abs(r1-r2) + abs(c1-c2) << endl;
	
	return 0;
}
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

十、外卖店优先级

标签：第十届蓝桥杯省赛C++ A组/C组、第十届蓝桥杯省赛Java A组/B组/C组、模拟

思路：枚举每一家店，如果这家店的订单数至少有 $3$ 个，对每一家店的每一个订单进行枚举，先计算出优先级减少了多少，再判断是否取出优先级队列，然后再加上 $2$ ，这里要注意，优先级最大为 $0$ ， 并且减少的数量也最大为 $0$ ，最后再对最后的时刻 $T$ 进行判断即可，详情见代码。

题目描述：

“饱了么”外卖系统中维护着 N 家外卖店，编号 1∼N。

每家外卖店都有一个优先级，初始时 (0 时刻) 优先级都为 0。

每经过 1 个时间单位，如果外卖店没有订单，则优先级会减少 1，最低减到 0；
而如果外卖店有订单，则优先级不减反加，每有一单优先级加 2。

如果某家外卖店某时刻优先级大于 5，则会被系统加入优先缓存中；
如果优先级小于等于 3，则会被清除出优先缓存。

给定 T 时刻以内的 M 条订单信息，请你计算 T 时刻时有多少外卖店在优先缓存中。

输入格式
第一行包含 3 个整数 N,M,T。

以下 M 行每行包含两个整数 ts 和 id，表示 ts 时刻编号 id 的外卖店收到一个订单。

输出格式
输出一个整数代表答案。

数据范围
1≤N,M,T≤105,1≤ts≤T,1≤id≤N
输入样例：
2 6 6
1 1
5 2
3 1
6 2
2 1
6 2
输出样例：
1
样例解释
6 时刻时，1 号店优先级降到 3，被移除出优先缓存；2 号店优先级升到 6，加入优先缓存。

所以是有 1 家店 (2 号) 在优先缓存中。
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

示例代码：

#include 

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second

const int N = 1e5+10;

int n, m, T;
vector<int> order[N];
bool st[N];

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> n >> m >> T;
	while(m--)
	{
		int ts, id; cin >> ts >> id;
		order[id].push_back(ts);
	}
	
	for(int i = 1; i <= n; ++i)
	{
		if(order[i].size() >= 3)
		{
			sort(order[i].begin(), order[i].end());
			int last = 0, sum = 0;
			for(int j = 0; j < order[i].size(); ++j)
			{
				int t = order[i][j];
				sum = max(0, sum - max(0,t - last - 1));
				if(sum <= 3) st[i] = false;
				sum += 2, last = t;
				if(sum > 5) st[i] = true;
			}

			sum = max(0, sum - max(0, T - last));
			if(sum <= 3) st[i] = false;
			if(sum > 5) st[i] = true;
// 			cout << sum << endl;
		}
	}
	
	int res = 0;
	for(int i = 1; i <= n; ++i)
	{
		if(st[i]) res++;
	}
	
	cout << res << endl;
	
	return 0;
}
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

十一、日志统计

标签：第九届蓝桥杯省赛C++ B组、第九届蓝桥杯省赛Java B组、模拟、枚举

思路：这道题和上一道题的思路差不多，都是遍历每一家店，如果该店的点赞数至少为 $K$ 时，再对该店的所有订单进行枚举，每 $K$ 个进行遍历，如果首末的时间差在 $D$ 以内，那就说明该帖子是热帖。

题目描述：

小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 N 行。

其中每一行的格式是：

ts id  表示在 ts 时刻编号 id 的帖子收到一个”赞”。

现在小明想统计有哪些帖子曾经是”热帖”。

如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞，小明就认为这个帖子曾是”热帖”。

具体来说，如果存在某个时刻 T 满足该帖在 [T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 K 个赞，该帖就曾是”热帖”。

给定日志，请你帮助小明统计出所有曾是”热帖”的帖子编号。

输入格式
第一行包含三个整数 N,D,K。

以下 N 行每行一条日志，包含两个整数 ts 和 id。

输出格式
按从小到大的顺序输出热帖 id。

每个 id 占一行。

数据范围
1≤K≤N≤105,0≤ts,id≤105,1≤D≤10000
输入样例：
7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3
输出样例：
1
3
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 

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second

const int N = 1e5+10;

int n, D, K;
vector<int> logs[N];
bool st[N];

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> n >> D >> K;
	while(n--)
	{
		int ts, id; cin >> ts >> id;
		logs[id].push_back(ts);
	}
	
	for(int i = 0; i < N; ++i)
	{
		if(logs[i].size() >= K)
		{
			sort(logs[i].begin(), logs[i].end());
			for(int j = 0; j + K - 1 < logs[i].size(); ++j)
			{
				if(logs[i][j+K-1] - logs[i][j] + 1 <= D) 
				{
					st[i] = true;
					break;
				}
			}
		}
	}
	
	int res = 0;
	for(int i = 0; i < N; ++i)
	{
		if(st[i]) cout << i << endl;
	}
	
	
	return 0;
}
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

十二、消除游戏

标签：模拟

思路：我们可以每次记录一下当前的字符串的长度，然后处理之后如果长度没有变的话那就直接退出即可。详细的操作细节见代码。虽然只有一个数据没过，其实还算可以了。
注意： 这里有一个注意的地方，这个 $string.size()$ 的返回类型为 $unsignedint$ ，所以为 $0$ 时再减一就成很大的数了，所以要强转为 $int$ 。

还有就是关于 $string$ 其实，关于C++ string类的运算符=的速度，string类的设计是为了提供便利性和安全性。string类中的+=运算符被用于字符串的追加，并且其实现是高效的。尽管涉及到内存的分配与复制，但是这些操作已经被高度优化，尤其是在现代编译器中。
string类的拷贝构造函数也是快速且高效的。默认的拷贝构造函数简单地对成员变量进行一一赋值，没有显著的性能负担。实际上，由于内部优化和管理，使用string类可以避免许多手动管理内存的复杂性和潜在错误。
将C++ string类和字符数组在算法竞赛中进行速度比较时，通常会发现string类更快、更方便。尽管对于某些底层操作，字符数组可能具有微小的性能优势，但这种差异通常可以忽略不计。在大多数情况下，string类的接口设计使得它的操作不仅速度快，而且代码的可读性和可维护性都更好。

题目描述：

在一个字符串 S 中，如果 Si=Si−1 且 Si≠Si+1，则称 Si 和 Si+1 为边缘字符。

如果 Si≠Si−1 且 Si=Si+1，则 Si−1 和 Si 也称为边缘字符。

其它的字符都不是边缘字符。

对于一个给定的串 S，一次操作可以一次性删除该串中的所有边缘字符（操作后可能产生新的边缘字符）。

请问经过 2^64 次操作后，字符串 S 变成了怎样的字符串，如果结果为空则输出 EMPTY。

输入格式
输入一行包含一个字符串 S。

输出格式
输出一行包含一个字符串表示答案，如果结果为空则输出 EMPTY。

数据范围
对于 25% 的评测用例，|S|≤103，其中 |S| 表示 S 的长度；
对于 50% 的评测用例，|S|≤104；
对于 75% 的评测用例，|S|≤105；
对于所有评测用例，|S|≤106，S 中仅含小写字母。

输入样例1：
edda
输出样例1：
EMPTY
输入样例2：
sdfhhhhcvhhxcxnnnnshh
输出样例2：
s
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

示例代码：10/11

#include 

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second

const int N = 1e6+10;

int n, last = -1;
string str, backup;
bool st[N];

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> str;
	n = str.size();
	while(str.size() != last)
	{
		memset(st, 0, sizeof st);
		backup.clear();
		last = str.size();
		for(int i = 1; i < (int)str.size() - 1; ++i)
		{
			if(str[i] == str[i-1] && str[i] != str[i+1])
			{
				st[i] = true, st[i+1] = true;
			}
			if(str[i] == str[i+1] && str[i] != str[i-1])
			{
				st[i] = true, st[i-1] = true;
			}
		}
		
		for(int i = 0; i < str.size(); ++i)
		{
			if(!st[i]) backup += str[i];
		}
		
		str = backup;
	}
	
	if(str.size()) cout << str << endl;
	else cout << "EMPTY" << endl;
	
	return 0;
}
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

十三、三国游戏

标签：模拟

思路：这道题可以看成是 $W_i=A_i-B_i-C_i>0$ ，然后构造出 $W$ 数组，然后由大到小排序，找最多能有多少个 $W_i$ ，使得他们之和大于 $0$ ，然后把这个过程重复三遍（三个国家依次赢一遍），找最大值。

题目描述：

小蓝正在玩一款游戏。

游戏中魏蜀吴三个国家各自拥有一定数量的士兵 X,Y,Z（一开始可以认为都为 0）。

游戏有 n 个可能会发生的事件，每个事件之间相互独立且最多只会发生一次，当第 i 个事件发生时会分别让 X,Y,Z 增加 Ai,Bi,Ci。

当游戏结束时 (所有事件的发生与否已经确定)，如果 X,Y,Z 的其中一个大于另外两个之和，我们认为其获胜。

例如，当 X>Y+Z 时，我们认为魏国获胜。

小蓝想知道游戏结束时如果有其中一个国家获胜，最多发生了多少个事件?

如果不存在任何能让某国获胜的情况，请输出 −1。

输入格式
输入的第一行包含一个整数 n。

第二行包含 n 个整数表示 Ai，相邻整数之间使用一个空格分隔。

第三行包含 n 个整数表示 Bi，相邻整数之间使用一个空格分隔。

第四行包含 n 个整数表示 Ci，相邻整数之间使用一个空格分隔。

输出格式
输出一行包含一个整数表示答案。

数据范围
对于 40% 的评测用例，n≤500；
对于 70% 的评测用例，n≤5000；
对于所有评测用例，1≤n≤105，0≤Ai,Bi,Ci≤109。

注意，蓝桥杯官方给出的关于 Ai,Bi,Ci 的数据范围是 1≤Ai,Bi,Ci≤109，但是这与给出的输入样例相矛盾，因此予以纠正。

输入样例：
3
1 2 2
2 3 2
1 0 7
输出样例：
2
样例解释
发生两个事件时，有两种不同的情况会出现获胜方。

发生 1,2 事件时蜀国获胜。

发生 1,3 事件时吴国获胜。
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

示例代码：

#include 

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second

const int N = 1e5+10;

int n;
int a[N], b[N], c[N], w[N];

LL work(int a[], int b[], int c[])
{
	for(int i = 0; i < n; ++i) w[i] = a[i] - b[i] - c[i];
	
	sort(w,w+n,greater<int>());
	
	LL sum = 0, res = -1;
	for(int i = 0; i < n; ++i)
	{
		sum += w[i];
		if(sum > 0) res = i + 1;
		else break;
	}
	
	return res;
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> n;
	for(int i = 0; i < n; ++i) cin >> a[i];
	for(int i = 0; i < n; ++i) cin >> b[i];
	for(int i = 0; i < n; ++i) cin >> c[i];
	
	cout << max({work(a,b,c), work(b,a,c), work(c,a,b)}) << endl;
	
	return 0;
}
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

十四、整数序列

标签：第十一届蓝桥杯省赛第一场C++ B组、模拟

思路：就没啥难度，怪不得之前老说蓝桥杯是水赛，这种题那当然啊。

题目描述：

有一个序列，序列的第一个数是 n，后面的每个数是前一个数整除 2，请输出这个序列中值为正数的项。

输入格式
输入一行包含一个整数 n。

输出格式
输出一行，包含多个整数，相邻的整数之间用一个空格分隔，表示答案。

数据范围
1≤n≤1018
输入样例：
20
输出样例：
20 10 5 2 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14

示例代码：

#include 

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second

const int N = 1e5+10;

LL n;

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> n;
	while(n)
	{
		cout << n << " ";
		n /= 2;
	}
	
	return 0;
}
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