2018 Autumn 清北学堂普及刷题班 Day3 题解

十月 03, 2018 8024

不同寻常的题面

T1. H因子

问题描述

h因子是一种评价学术成就的新方法。一名科研人员的h因子是指他至少有h篇论文分别被引用了不少于h次。Alice已经发表了很多论文了，现给出一个序列a0，a1，a2，…，an，其中 a_i 表示有 a_i 篇文章分别被引用了i次。

请你求出Alice的h因子。

输入格式

第一行包含一个正整数T（1≤T≤10），表示有多少组数据。

每组数据的第一行包含一个正整数n（1≤n≤200,000） 。

每组数据的第二行包含n个正整数a0，a1，a2，……，an（1≤ai≤1000,000,000），表示序列中的每个数。

输出格式

对于每组数据，输出一行，包含一个整数，表示该组数据的h因子 。

样例输入

1
2
3
4
5
6
7
3
1
1 2
2
1 2 3
3
0 0 0 0

样例输出

1
2
3
1
2
0

解析

首先要把题看懂！！！

首先要把题看懂！！！

首先要把题看懂！！！

（我就因为题意理解错误而完美爆零）

我们从n开始，从大到小枚举h因子

一个有效的h因子为i当且仅当有大于等于i篇文章被引用了大于等于i次

所以我们可以用一个sum来存当前有多少篇文章被引用了大于等于当前i次

第一个满足sum >= i的i即为最大的h因子

代码实现

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
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

/* -- STL Iterator -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>
using namespace std;

/*  Constants Start  */

const int MAXN = 200000 + 10;

/*  Constants End  */

/*  Variants Start  */

int seq[MAXN];

/*  Variants End  */

namespace FastIO {
	void DEBUG(char comment[], int x) {
		cerr << comment << x << endl;
	}

	inline int getint() {
		int s = 0, x = 1;
		char ch = getchar();
		while (!isdigit(ch)) {
			if (ch == '-') x = -1;
			ch = getchar();
		}
		while (isdigit(ch)) {
			s = s * 10 + ch - '0';
			ch = getchar();
		}
		return s * x;
	}
	inline void __basic_putint(int x) {
		if (x < 0) {
			x = -x;
			putchar('-');
		}
		if (x >= 10) __basic_putint(x / 10);
		putchar(x % 10 + '0');
	}

	inline void putint(int x, char external) {
		__basic_putint(x);
		putchar(external);
	}
}

int main(int argc, char *const argv[]) {
	#ifndef HANDWER_FILE
	freopen("testdata.in", "r", stdin);
	freopen("testdata.out", "w", stdout);
	#endif
	using namespace FastIO;
	int t = getint();
	while (t --> 0) {
		int n = getint();
		for (int i = 0; i <= n; ++i) {
			seq[i] = getint();
		}
		int sum = 0;
		for (int i = n; i >= 0; --i) {
			sum += seq[i];
			if (sum >= i) {
				putint(i, '\n');
				break;
			}
		}
	} 
	return 0;
}


T2. 超回文字符串

问题描述

给出一个只由小写字母的字符串，要求在最少的操作数下将它转成一个超回文字符串。每次操作仅可以改变字符串中的一个字符。

一个字符串被称为超回文字符串，当且仅当它的所有奇数长度的子串都是回文串（回文串是指一个字符串从前往后与从后往前读是一样的）。

输入格式

第一行包含一个正整数T（1≤T≤100），表示有多少组数据。

对于每组数据，只有单独一行，包含一个仅由小写字母组成的字符串。保证字符串的长度不超过100。

输出格式

对于每组数据，输出一行，包含一个整数，表示最少的操作数。

样例输入

1
2
3
4
3
ncncn
aaaaba
aaaabb

样例输出

1
2
3
0
1
2

解析

简单分析之后，我们发现满足题目要求的字符串存在当且仅当这个字符串的奇数位、偶数位分别相同

那么直接暴力就好

我们枚举每一个奇数位上的字母，计算有多少个奇数位上的字母与它不同（即要修改多少次）

取个min即为答案

偶数位同理

将两个min相加即为答案

代码实现

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
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

/* -- STL Iterator -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>
using namespace std;

/*  Constants Start  */

/*  Constants End  */

/*  Variants Start  */

/*  Variants End  */

namespace FastIO {
	void DEBUG(char comment[], int x) {
		cerr << comment << x << endl;
	}

	inline int getint() {
		int s = 0, x = 1;
		char ch = getchar();
		while (!isdigit(ch)) {
			if (ch == '-') x = -1;
			ch = getchar();
		}
		while (isdigit(ch)) {
			s = s * 10 + ch - '0';
			ch = getchar();
		}
		return s * x;
	}
	inline void __basic_putint(int x) {
		if (x < 0) {
			x = -x;
			putchar('-');
		}
		if (x >= 10) __basic_putint(x / 10);
		putchar(x % 10 + '0');
	}

	inline void putint(int x, char external) {
		__basic_putint(x);
		putchar(external);
	}
}

int main(int argc, char *const argv[]) {
	#ifndef HANDWER_FILE
	freopen("testdata.in", "r", stdin);
	freopen("testdata.out", "w", stdout);
	#endif
	int t;
	cin >> t;
	string s;
	while (t --> 0) {
		cin >> s;
		int len = s.length();
		int min1 = len, min2 = len;
		for (int i = 0; i < len; i += 2) {
			int now = 0;
			for (int j = 0; j < len; j += 2) { 
				if (s[i] != s[j]) ++now; 
			} 
			min1 = std::min(min1, now);
		}
		if (len == 1) min2 = 0;
		for (int i = 1; i < len; i += 2) {
			int now = 0;
			for (int j = 1; j < len; j += 2) { 
				if (s[i] != s[j]) ++now; 
			} 
			min2 = std::min(min2, now);
		}
		cout << min1 + min2 << endl;
	}
	return 0;
}


T3. 移动桌子

问题描述

题面略（表格太多）

输入格式

第一行包含一个正整数T（1≤T≤10），表示有多少组数据。

每组数据的第一行包含一个正整数n（1≤n≤200,000），表示要移动n张桌子 。

每组数据的接下来n行，每行包含2个正整数a和b，表示该张桌子原本在房间a，需要移动到房间b。

输出格式

对于每组数据，输出一行，包含一个整数，表示移动完n张桌子所需要的最少时间 。

输入样例

1
2
3
4
5
6
7
8
9
10
11
12
13
3
4
10 20
30 40
50 60
70 80
2
1 3
2 200
3
10 100
20 80
30 50

输出样例

1
2
3
10
20
30

解析

我们对于每一个桌子的区间头和区间尾都加一再除以二（将房间化为走廊）

接着开一个长度为250的桶，把走廊长度累计到这个桶里面（暴力区间加1）

最后取最大值，乘以10（一次移动桌子10十分钟）就是最终答案

代码实现

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
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

/* -- STL Iterator -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>
using namespace std;

/*  Constants Start  */

/*  Constants End  */

/*  Variants Start  */

int way[250 + 10];

/*  Variants End  */

namespace FastIO {
	void DEBUG(char comment[], int x) {
		cerr << comment << x << endl;
	}

	inline int getint() {
		int s = 0, x = 1;
		char ch = getchar();
		while (!isdigit(ch)) {
			if (ch == '-') x = -1;
			ch = getchar();
		}
		while (isdigit(ch)) {
			s = s * 10 + ch - '0';
			ch = getchar();
		}
		return s * x;
	}
	inline void __basic_putint(int x) {
		if (x < 0) {
			x = -x;
			putchar('-');
		}
		if (x >= 10) __basic_putint(x / 10);
		putchar(x % 10 + '0');
	}

	inline void putint(int x, char external) {
		__basic_putint(x);
		putchar(external);
	}
}

int main(int argc, char *const argv[]) {
	#ifndef HANDWER_FILE
	freopen("testdata.in", "r", stdin);
	freopen("testdata.out", "w", stdout);
	#endif
	using namespace FastIO;
	int t = getint();
	while (t --> 0) {
		memset(way, 0, sizeof(way));
		int n = getint();
		for (int i = 1; i <= n; ++i) {
			int s = getint();
			int t = getint();
			s = (s + 1) >> 1;
			t = (t + 1) >> 1;
			for (int j = s; j <= t; ++j) ++way[j];
		}
		int ans = 0;
		for (int i = 1; i <= 250; ++i) ans = std::max(ans, way[i]);
		putint(ans * 10, '\n');
	}
	return 0;
}


T4. 口算

问题描述

Alice口算能力非常强。Bob为了考考Alice，给了她一个长度为n的正整数序列a1，a2，……，an，同时抛出了m个问题。
​
每个问题给出三个正整数。
​
Alice需要快速判断出 a_l\times a_{l+1}\times \dots \times a_{r-1} \times a_r 是不是d的倍数。
​
Alice凭借她强大的口算能力快速给出了答案。然而Bob很菜，他并不知道正确答案是什么。请写一个程序帮助Bob计算这些问题的答案。

输入格式

第一行包含一个正整数T（1≤T≤10），表示有多少组数据。
​
每组数据的第一行包含两个正整数n，m（1≤n,m≤100,000），分别表示序列长度以及问题个数。
​
第二行包含n个正整数a1，a2，……，an（1≤ai≤100,000），表示序列中的每个数。
​
接下来的m行，每行包含3个正整数l,r,d（1≤l≤r≤n，1≤d≤100,000），表示每个问题。

输出格式

对于每个问题，输出一行，若是倍数，输出Yes，否则输出No。

输入样例

1
2
3
4
5
6
7
8
1
5 5
6 4 7 2 5
1 2 24
1 3 18
2 5 17
3 5 35
1 3 21

输出样例

1
2
3
4
5
Yes
No
No
Yes
Yes

数据规模

【数据规模】

对于30%数据，1≤T≤5，1≤n,m≤50，且保证对于每一个问题， a_l\times a_{l+1}\times \dots \times a_{r-1} \times a_r 不超过long long的数据范围。

对于60%数据，1≤T≤10，1≤n,m≤1000，1≤ai≤1000

对于100%数据，1≤T≤10，1≤n,m≤100,000，1≤ai≤100,000

解析

暴力做法

30pts 的模拟

（伪）正解

进行质因数分解，暴力判断

正解

在（伪）正解的基础上进行优化

预处理：将所有的数进行质因数分解，按照顺序把所有质数的出现的下标push_back进每个质数专门的vector里

将读入的d进行质因数分解，同上push_back进一个专门的vector里

然后在给定的区间里进行寻找质因数（使用lower_bound和upper_bound）

如果该有的质因数都有，显然可以整除

否则不可以整除

代码实现

不提供。