The 15ph Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple题解

发表于 | 分类于 ， | 热度 ℃
字数统计: 2,984 | 阅读时长 ≈ 15

4月29日，13:30-18:30，浙江大学程序设计校赛

A-Peak

题意：

有一串数字，问这串数字是否符合以下情况：

存在一个数在这串数的第k位置，即ak，以k为基准，k之前的数呈递增趋势，即ai-1 < ai。k之后的数呈递减趋势，即ai-1 > ai。ak不能为首元素和尾元素，且ak为最大的那个数。

题解：

水题，每输入一个数直接和前一个数进行比较，先递增判断直到比前一个数小，则递减判断。如果期间存在不符合情况的，则输出No,否则输出Yes。

B - King of Karaoke

题意：

两个数组a，b，对a中的每个元素加k使得ai[i]=b[i]的个数最多。求k

题解：

只需用b中的每个元素减去a中的每个元素，即b[i]-a[i]，得到数组c，从中出现元素最多的那个数值的个数即为k。

D - Sequence Swapping

Time Limit: 1 Second Memory Limit: 65536 KB

BaoBao has just found a strange sequence {<, >, <, >, , <, >} of length in his pocket. As you can see, each element <, > in the sequence is an ordered pair, where the first element in the pair is the left parenthesis ‘(‘ or the right parenthesis ‘)’, and the second element in the pair is an integer.

As BaoBao is bored, he decides to play with the sequence. At the beginning, BaoBao’s score is set to 0. Each time BaoBao can select an integer , swap the -th element and the -th element in the sequence, and increase his score by , if and only if , ‘(‘ and ‘)’.

BaoBao is allowed to perform the swapping any number of times (including zero times). What’s the maximum possible score BaoBao can get?

Input

There are multiple test cases. The first line of the input contains an integer , indicating the number of test cases. For each test case:

The first line contains an integer (), indicating the length of the sequence.

The second line contains a string () consisting of ‘(‘ and ‘)’. The -th character in the string indicates , of which the meaning is described above.

The third line contains integers (). Their meanings are described above.

It’s guaranteed that the sum of of all test cases will not exceed .

Output

For each test case output one line containing one integer, indicating the maximum possible score BaoBao can get.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
4
6
)())()
1 3 5 -1 3 2
6
)())()
1 3 5 -100 3 2
3
())
1 -1 -1
3
())
-1 -1 -1

Sample Output

1
2
3
4
24
21
0
2

Hint

For the first sample test case, the optimal strategy is to select in order.

For the second sample test case, the optimal strategy is to select in order.

题意：一串由‘(’与‘)’组成的字符串，其中每一个字符都有一个权值，如果两个相邻的字符a,b为‘（’‘）’，则这两个字符可以进行交换，交换后可获得a和b权值之积的权值sum。求如何操作可以获得最大权值sum。

题解：由于权值存在负数，因此如果相邻两个可以交换的字符如果异号则需谨慎考虑。先从第一个字符进行判断，如果为‘（’，则cur为该字符权值，然后继续判断，如果出现”)”，如果权值相乘为正，则cur不变，权值sum加上cur乘当前权值即curweight[i]。否则将cur和curweight[i]压栈，然后cur变为0，继续下一次判断。如果之后以此方法得到的权值为负，则看和栈顶元素相加后是否为正，若为正则取栈顶元素合成新元素，栈顶pop，再继续取栈判断。

代码：

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
#include<cstdio>
#include<cmath>
#include<stack>
using namespace std;
struct node {
	int cur;
	int cnt;
};
char str[1010];
int wei[1010];
int main() {
	int t, n;
	scanf("%d", &t);
	while (t--) {
		scanf("%d%s", &n, str);
		for (int i = 0; i < n; i++) {
			scanf("%d", &wei[i]);
		}
		stack<node>st;
		int sum = 0;
		int cur = 0;
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			if (str[i] == '(') {
				if (cur == 0) {
					cur = wei[i];
				}
				else if (abs(cur) < abs(cur + wei[i])) {
					cur = cur + wei[i];
				}
				else {
					cur = wei[i];
				}
			}
			else if (str[i] == ')') {
				if (!st.empty() && (cur + st.top().cur)*wei[i] + st.top().cnt > 0 && (cur + st.top().cur)*wei[i] + st.top().cnt>cur*wei[i]) {
					cnt = 0;
					do {
						cur += st.top().cur;
						cnt += st.top().cnt;
						st.pop();
					} while (!st.empty() && (cur + st.top().cur)*wei[i] + st.top().cnt > 0 && (cur + st.top().cur)*wei[i] + st.top().cnt > cur*wei[i]);
					sum += cur*wei[i] + cnt;
				}
				else if (cur*wei[i] > 0) {
					sum += wei[i] * cur;
				}
				else {
					if (!st.empty() && (cur + st.top().cur)*wei[i] + st.top().cnt > 0) {
						cur += st.top().cur;
						sum += cur*wei[i] + st.top().cnt;
						st.pop();
					}
					else {
						if (!cur&&!st.empty()) {
							st.top().cnt += st.top().cur*wei[i];
						}
						else {
							node tmp;
							tmp.cnt = cur*wei[i];
							tmp.cur = cur;
							st.push(tmp);
							cur = 0;
						}
					}
				}
			}
		}
		printf("%d\n", sum);
	}
	return 0;
}

J - CONTINUE…?

Time Limit: 1 Second Memory Limit: 65536 KB Special Judge

DreamGrid has classmates numbered from to . Some of them are boys and the others are girls. Each classmate has some gems, and more specifically, the -th classmate has gems.

DreamGrid would like to divide the classmates into four groups , , and such that:

  • Each classmate belongs to exactly one group.
  • Both and consist only of girls. Both and consist only of boys.
  • The total number of gems in and is equal to the total number of gems in and .

Your task is to help DreamGrid group his classmates so that the above conditions are satisfied. Note that you are allowed to leave some groups empty.

Input

There are multiple test cases. The first line of input is an integer indicating the number of test cases. For each test case:

The first line contains an integer () – the number of classmates.

The second line contains a string () consisting of 0 and 1. Let be the -th character in the string . If , the -th classmate is a boy; If , the -th classmate is a girl.

It is guaranteed that the sum of all does not exceed .

Output

For each test case, output a string consists only of {1, 2, 3, 4}. The -th character in the string denotes the group which the -th classmate belongs to. If there are multiple valid answers, you can print any of them; If there is no valid answer, output “-1” (without quotes) instead.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
5
1
1
2
10
3
101
4
0000
7
1101001

Sample Output

1
2
3
4
5
-1
-1
314
1221
3413214

题意：

有一串由0和1组成的数字，该串数字的长度是n，即n个数。这n个数1代表男生，0代表女生，每个人有一个权值。这n个数按次序权值依次为1到n，即第i个人权值为i。现将女生分两队，即1队2队，男生分两队，即3队4队，问如何分配队员使1队+3队的权值总和等于2队＋4队的权值总和。（每队人数可以为0，如果有多种符合情况的组队方法，只需选择其中一种即可）

题解：

看似复杂，其实仔细想想，只需将所有数的权值相加除以2得到half，以half这个数为基准，看哪些数相加为half，如果没有输出-1。思路大致是这样。将所有数的性别情况用a[i]存储。然后从1加到n，得到的数除以2，如果不能整除则表示1队+3队永远不会等于2队+4队，直接输出-1。如果能整除，则以half为基准，sum为每次加的数，初始值为0。把1队和3队归为一队，把2队4队归为一队。先从最大的即n开始进行比较，如果n < half，sum加上n。然后进行判断half - sum=tmp是否小于n，如果小于n则证明tmp这个数一定在n之前，那直接将n以及tmp分为1个队，其他人则自然分为另一个队。如果 >= n，则再从n-1开始比较，如果sum+n-1这个数大于half，则表示n-1和之前标记的数不是一个队，则从n-2继续比较。一直循环下去，直到加完之后刚好等于half，则标记过的是一队，未标记的是另一对，再分别对这两队进行性别判断，再细分即可。这样直接用贪心就解决了

代码：

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
#include<cstdio>
#include<cstring>
#include<iostream>
int a[100010], vis[100010];
using namespace std;
int main() {
	int t;
	scanf("%d", &t);
	long long int sum = 0, half = 0;
	while (t--) {
		int n;
		sum = 0;
		scanf("%d", &n);
		memset(vis, 0, sizeof(vis));
		for (int i = 0; i < n; i++) {
			scanf("%1d", &a[i]);
			sum += i + 1;
		}
		if (sum % 2 != 0) {
			printf("-1\n");
			continue;
		}
		else
			half = sum / 2;
		sum = 0;
		for (int i = n; i > 0; i--) {
			if (sum + i <= half) {
				sum += i;
				vis[i - 1] = 1;
				if (sum == half)
					break;
				else if (half - sum < i) {
					vis[half - sum - 1] = 1;
					break;
				}
			}
		}
		for (int i = 0; i < n; i++) {
			if (a[i]) {
				if (vis[i])
					printf("3");
				else
					printf("4");
			}
			else if (!a[i]) {
				if (vis[i])
					printf("1");
				else
					printf("2");
			}
		}
		printf("\n");
	}
	return 0;
}

L - Doki Doki Literature Club

Time Limit: 1 Second Memory Limit: 65536 KB

Doki Doki Literature Club! is a visual novel developed by Team Salvato. The protagonist is invited by his childhood friend, Sayori, to join their high school’s literature club. The protagonist then meets the other members of the club: Natsuki, Yuri, and the club president Monika. The protagonist starts to participate in the club’s activities such as writing and sharing poetry, and grows close to the four girls. What a lovely story!

A very important feature of the game is its poetry writing mechanism. The player is given a list of various words to select from that will make up his poem. Each girl in the Literature Club has different word preferences, and will be very happy if the player’s poem is full of her favorite words.

imgThe poem writing mini-game (from wikipedia)

BaoBao is a big fan of the game and likes Sayori the most, so he decides to write a poem to please Sayori. A poem of words is nothing more than a sequence of strings, and the happiness of Sayori after reading the poem is calculated by the formula

Given a list of words and Sayori’s preference to each word, please help BaoBao select words from the list and finish the poem with these words to maximize the happiness of Sayori.

Please note that each word can be used at most once!

Input

There are multiple test cases. The first line of input contains an integer (about 100), indicating the number of test cases. For each test case:

The first line contains two integers and (), indicating the number of words and the length of the poem.

For the following lines, the -th line contains a string consisting of lowercased English letters () and an integer (), indicating the -th word and Sayori’s preference to this word. It’s guaranteed that for all .

Output

For each test case output one line containing an integer and strings separated by one space, indicating the maximum possible happiness and the corresponding poem. If there are multiple poems which can achieve the maximum happiness, print the lexicographically smallest one.

Please, DO NOT output extra spaces at the end of each line, or your answer may be considered incorrect!

A sequence of strings is lexicographically smaller than another sequence of strings , if there exists a () such that for all and is lexicographically smaller than .

A string is lexicographically smaller than another string , if there exists a () such that for all and , or for all and .

Sample Input

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
4
10 8
hello 0
world 0
behind 0
far 1
be 2
spring 10
can 15
comes 20
winter 25
if 200
5 5
collegiate 0
programming -5
zhejiang 10
provincial 5
contest -45
3 2
bcda 1
bcd 1
bbbbb 1
3 2
a 1
aa 1
aaa 1

Sample Output

1
2
3
4
2018 if winter comes can spring be far behind
15 zhejiang provincial collegiate programming contest
3 bbbbb bcd
3 a aa

题意：

有n个字符串，每个字符串都有一个权值。现从n个字符串中选择m个字符串，其中m个字符串选取的第i个字符串的权值乘i。问如何选择使权值之和最大，并输出这些字符串。如果权值相同则输出字符串优先级高的。

题解：按权值从大到小进行排序，如果权值相同则按字符串的首字符优先级从大到小排序。排完序后选择前m个字符串，第i字符串的权值乘i之后相加，输出相加值之后，再输出前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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
struct node{
	string str;
	long long int weight;
};
node level[110];
bool cmp(node a,node b) {
	if (a.weight != b.weight)
		return a.weight > b.weight;
	else {
		return a.str < b.str;
	}
}
int main() {
	int t, n, m;
	scanf("%d", &t);
	while (t--) {
		long long int h = 0;
		scanf("%d%d", &n, &m);
		for (int i = 0; i < n; i++) {
			cin >> level[i].str >> level[i].weight;
		}
		sort(level, level + n, cmp);
		for (int i = m; i > 0; i--)
			h += level[m - i].weight*i;
		printf("%lld ", h);
		for (int i = 0; i < m - 1; i++)
			cout << level[i].str << " ";
		cout << level[m - 1].str << endl;
	}
	return 0;
}

K - Lucky 7

给一个数n和m，接下来n个数，问这n个数中是否存在一个数加m是7的倍数。

题解：

每输入一个数直接进行判断即可。

文章结束了，但我们的故事还在继续
坚持原创技术分享，您的支持将鼓励我继续创作！