2017年上海金马五校程序设计竞赛网上资格赛部分题题解

Problem A : Corn’s new language

原题

Description

Corn is going to promote programming in the campus, so he wants to add a lot of interesting ideas to make programming more attractive. One task he is working on is to develop a new programming language because he thinks all existing ones are too simple to him. The syntax rules of the language are:

  1. $()$ is a valid program
  2. $( P )$ is a valid program, if $P$ is a valid program
  3. $PQ$ is a valid program, if both $P$ and $Q$ are valid programs

Corn wants a compiler for the language. For a program, if it is valid, the compiler should print the max depth in the program. For example “$(())$” has a depth of $2$, while “$((())())$” has a depth of $3$. Formally, the max depth is the max number of unmatched open brackets in any prefix.

Input

Each case is a non-empty string in a single line, the string will only contain ‘$($’ or ‘$)$’, its length will be no more than $100$.

Output

For each case, output “YES” and the integer required above if the program is valid, separated with a space. Or “NO” if the program is invalid.

Sample Input

1
2
3
4
5
6
7
(
)
()
(())
((())())
())
((

Sample Output

1
2
3
4
5
6
7
NO
NO
YES 1
YES 2
YES 3
NO
NO

思路

  • 简单模拟一下匹配括号的过程,当读到左括号的时候,增加深度,读到右括号时减少深度,正确匹配的话,最后的深度应该是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
#include <bits/stdc++.h>
using namespace std;

int main()
{
char a[102];
while (cin >> a)
{
bool flag = 0;
int ans = 0;
int cnt = 0;
for (int i = 0; i < strlen(a); i++)
{
if (a[i] == '(')
cnt++;
ans = max(cnt, ans);
if (a[i] == ')')
cnt--;
if (cnt < 0)
{
flag = 1;
break;
}
}
if (cnt == 0 && !flag)
cout << "YES " << ans << endl;
else
cout << "NO" << endl;
}
return 0;
}

Problem B : Coach

原题

Description

In the ACM training team, the coach wants to split all students into many groups and each group consists of three students. Let’s assume that all students are numbered from $1$ to $n$. The teacher wants the groups to achieve good results, so he wants to hold the following condition: In a group of three students, they are friends. Also it is obvious that each student must be in exactly one team. If $A$ and $B$ are friends, $B$ and $C$ are friends, then $A$ and $C$ are friends.

Input

There are multiple test cases.

For each test case, the first line contains integers $n$ and $m$ $(1≤n≤5000,0≤m≤5000)$. Then follows $m$ lines, each contains a pair of integers $a_i,b_i$ $(1≤a_i,b_i≤n)$. The pair $a_i,b_i$ means that the students $a_i$ and $b_i$ are friend. It is guaranteed that each pair of $a_i$ and $b_i$ occurs in the input at most once.

Output

If the required group division plan doesn’t exist, print “No”. Otherwise, print “Yes”.

Sample Input

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

Sample Output

1
2
No
Yes

思路

  • 非常标准的并查集,数据输入即为合并操作,最后判断只需查询每个树元素的总数是否为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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5010;
int par[maxn], num[maxn];

void init(int n)
{
for (int i = 1; i <= n; i++)
{
par[i] = i;
num[i] = 1;
}
}

int search(int x)
{
if (par[x] == x)
return x;
return par[x] = search(par[x]);
}

void unite(int x, int y)
{
x = search(x);
y = search(y);
par[x] = y;
if (x == y)
return;
num[y] += num[x];
}

bool same(int x, int y)
{
return search(x) == search(y);
}

bool judge(int n)
{
for (int i = 1; i <= n; i++)
if (par[i] == i && num[i] % 3)
return false;
return true;
}

int main()
{
int n, m;
while (cin >> n >> m)
{
init(n);
while (m--)
{
int a, b;
cin >> a >> b;
if (!same(a, b))
unite(a, b);
}
bool ans = judge(n);
if (ans)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}

Problem C : Frog

原题

Description

There is a little frog called Matt. One day he comes to a river. The river could be considered as an axis. Matt is standing on the left bank now (at position $0$). He wants to cross the river and reach the right bank (at position $N$). But Matt could only jump at most $L$ units, for example from $0$ to $L$. There are $N−1$ rocks lying on the river equably (at position $1,2,⋯,N−1$). The size of the rocks can be ignored, so each rock can be thought as a point on the axis. Matt can jump to a rock from the left bank or other rocks, and he can jump to the right bank from a rock or the left bank.

Now, Matt wants to know how many ways are there to cross the river. Of course, Matt could only jump forward.

Input

There are no more than $100$ cases. Each case contains two integers $N$ $(2≤N≤100000)$ and $L$ $(1≤L≤N)$, denoting the position of the right bank and the distance Matt could jump most.

Output

For each test case, print the number of way to cross the river module $10^9+7$.

Sample Input

1
2
3 1
4 3

Sample Output

1
2
1
7

思路

  • 状态转移方程$$dp[i]=\sum_{j=i-l}^{i-1} {dp[j]}=2dp[i-1]-dp[i-l-1],i>l$$
  • 当$i≤l$时,$dp[i]=2^{i-1}$
  • 于是只需维护一段区间的和即可将$dp[n]$解出。
  • 注意取模运算时溢出的问题。

代码

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

long long fastpow(long long b)
{
long long r = 1, base = 2;
while (b)
{
if (b & 1)
r = r * base % MOD;
base = base * base % MOD;
b >>= 1;
}
return r;
}

int main()
{
long long dp[100010];
int n, l;
while (cin >> n >> l)
{
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= l; i++)
dp[i] = fastpow(i - 1);
long long sum = fastpow(l) - 1;
for (int i = 1; l + i <= n; i++)
{
dp[l + i] = sum;
sum = (sum + MOD - dp[i] + dp[l + i]) % MOD;
}
cout << dp[n] << endl;
}
return 0;
}

Problem H : DHU Club Festival

原题

Description

During the past DHU Club Festival, XiaoTang got many bottles of drinks, but each was of a different taste. And they were not of the same concentration.

Sometimes it’s just that confusing with too many choices. XiaoTang decided to mix all of them up to create an extreme unique taste. Please help him. Following is the rule of mixing.

Given the concentrations of each drink: $\lbrace c_1,c_2,⋯,c_n\rbrace$, each time you can take $x$ $(x≥2)$ bottles of drinks and mix them up. It is guaranteed that after your mixing, the concentration become the average number. For example, if you choose three drinks with concentrations of $3$, $4$ and $8$, you will get a mixture with a concentration of $5$. Repeat mixing until there is only one bottle drink left and your aim is to make the final concentration maximal.

Hint: In this problem, we use integer division, eg: $\frac{3+2}2=2$

Input

There are several test cases, each contains two lines.
The first line is $n$ $(1≤n≤100)$, the number of the drinks.
The second line contains nn positive integers $c_i$ $(1≤c_i≤100)$, the concentration of each drink.

Output

For each test case, output the final concentration in a line.

Sample Input

1
2
3
4
2
2 3
1
1

Sample Output

1
2
2
1

思路

  • 贪心策略:每次都取最小的两个进行合并,直到最后一个。

代码

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

int main()
{
int c[102];
int n;
while (cin >> n)
{
for (int i = 0; i < n; i++)
cin >> c[i];
sort(c, c + n);
for (int i = 0; i < n - 1; i++)
c[i + 1] = (c[i] + c[i + 1]) / 2;
cout << c[n - 1] << endl;
}
}

Problem J : Raising Bacteria

原题

Description

You are a lover of bacteria so you want to raise some bacteria in a box. Initially, the box is empty. Every morning, you can put any number of bacteria into the box. Every night every bacterium in the box will split into two bacteria. You hope to see exactly xx bacteria in the box at some moment. What is the minimum number of bacteria you need to put into the box across those days?

Input

There are several test cases. Each case contains only one integer $x$ $(1≤x≤10^9)$ a line.

Output

For each case, output the only line containing one integer: the answer.

Sample Input

1
2
5
8

Sample Output

1
2
2
1

思路

  • 求二进制中1的个数

代码

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

int main()
{
int n;
while (cin >> n)
{
int cnt = 0;
do
cnt += n % 2;
while (n >>= 1);
cout << cnt << endl;
}
return 0;
}
捐助作者