题面：http://codeforces.com/contest/1092/problems
最近的div3打得好像都很顺利的样子。
A了4题，当时排名前100。赛后D2 fst了555。
不过前三题(好像都是水题)出的比较快，排名还是挺靠前的。涨了131分，差一点就上蓝了。
（怕不是以后只能掉分了）
A. Uniform String
题意：给定$n$和$k$，要求构造出一个出现26个字母中的前$k$个字符的长度为$n$的字符串。且每个字母出现的频率要可能低。
解法：按’a’ - char(a+k)的字符顺序依次输出即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
using namespace std;
pii a[2000];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--)
{
int n, k;
cin >> n >> k;
int len = 0;
for(int i = 0; len < n; i = (i + 1) % k, len++)
putchar('a' + i);
putchar('\n');
}
return 0;
}
B. Teams Forming
题意：有$n$个学生，需要分为$\frac{n}{2}$组。每个组由2名成员组成。两个组员的能力值必须一样。能力值低的那一方必须提高自己的能力值。可以任意组队。问总共最少需要提高的能力值为多少。
解法：随便排个序，然后第2个减第1个就好了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i];
sort(a , a + n);
ll ans = 0;
for(int i = 0; i < n - 1; i += 2)
ans += a[i + 1] - a[i];
cout << ans << endl;
return 0;
}
C. Prefixes and Suffixes
题意：一个长度为$n$的字符串，必然有$n-1$个前缀和$n-1$个后缀。给定这$2n-2$个字符串，但不告诉你是前缀还是后缀。要求你判断这所有的字符串哪些为前缀输出P，后缀输出S
解法：先找到两个长度为n-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
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
using namespace std;
const int maxn = 1e3 + 10;
char ans[maxn];
struct node{
string s;
int idx;
};
node a[maxn];
int n;
bool cmp(node a, node b)
{
return a.s.length() < b.s.length();
}
void test(string s)
{
sort(a, a + 2 * n - 2, cmp);
for(int i = 0; i < 2 * n - 3; i += 2)
{
if(a[i].s == s.substr(0, i / 2 + 1) && a[i + 1].s == s.substr(n - (i / 2 + 1)))
{
ans[a[i].idx] = 'P';
ans[a[i + 1].idx] = 'S';
}
else if(a[i].s == s.substr(n - (i / 2 + 1)) && a[i + 1].s == s.substr(0, i / 2 + 1))
{
ans[a[i].idx] = 'S';
ans[a[i + 1].idx] = 'P';
}
else
return;
}
for(int i = 0; i < 2 * n - 2; i++)
cout << ans[i];
cout << endl;
exit(0);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
vector<string> p;
for(int i = 0; i < 2 * n - 2; i++)
{
cin >> a[i].s;
a[i].idx = i;
if(a[i].s.length() == n - 1)
p.push_back(a[i].s);
}
string pl = p[1][0] + p[0];
string pr = p[0][0] + p[1];
test(pl);
test(pr);
// cout << pl << endl;
// cout << pr << endl;
return 0;
}
D1. Great Vova Wall (Version 1)
题意：D1和D2题意比较接近。给你$n$列砖，第$i$列砖有$a_i$块砖。每块砖的规格为$1\cdot1$。现在给你一系列$1\cdot2$的砖，你可以横着放或者竖着放。使得最终所有的$n$列砖到达一样的高度且均被填满。
解法：栈的运用。
像这类题目，用什么方法去解是最重要的。或者说是用什么思想去解。
用一个栈，如果栈顶元素和当前个数差为2的整数倍，则这两列必然可以被达到一样的高度。栈顶出栈。
否则的话入栈。最后判断栈内元素个数是否小于等于1即可。
对于像1 2 2 1 这样的情况也可以处理 只需要在第2列和第3列横着放一块，1和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
25
26
27
28
29
using namespace std;
const int maxn = 3e5 + 10;
int a[maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i];
vector<int> sta;
for(int i = 0; i < n; i++)
{
if(sta.size() && ((sta.back() - a[i]) % 2 == 0))
sta.pop_back();
else
sta.push_back(a[i]);
}
if(sta.size() <= 1)
cout << "YES" << endl;
else
cout << "NO" << endl;
return 0;
}
D2. Great Vova Wall (Version 2)
题意：和D1类似，只是这一题不能竖着放。
解法：由于 不能竖着放，所以必须两者高度一致才能保证最终到达相同高度。
显然 1 2 2 1这样的数据不能通过测试。
所以我们还需要保证能被消的一定要比之前消的要高才行。
即2 1 1 2这样的样例可行。因为2入栈 1 入栈 1被消 2比1高。
所以设一个值pre记录前一次被消的值。当然如果有值入栈了则可以随便消pre置-1
比如7 7 4 4在4入栈以后需要把pre置为-11
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
38x
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, pre = -1, maxh = -1;
cin >> n;
for(int i = 0; i < n; i++)
{
cin >> a[i];
maxh = max(maxh, a[i]);
}
vector<int> sta;
for(int i = 0; i < n; i++)
{
if(sta.size() && sta.back() == a[i] && a[i] >= pre)
{
sta.pop_back();
pre = a[i];
}
else
{
sta.push_back(a[i]);
pre = -1;
}
}
if(sta.empty() ||(sta.size() == 1 && sta.back() == maxh))
cout << "YES" << endl;
else
cout << "NO" << endl;
return 0;
}
E. Minimal Diameter Forest
待补
F. Tree with Maximum Cost
题意：待补
解法：树形dp
待补
1 |
|