0%

Codeforces Round 826 (Div. 3)

Codeforces Round #826 (Div. 3) A-E

Codeforces Round #826 (Div. 3) A-E

https://codeforces.com/contest/1741

今天vp了一下最近一场div3,感觉难度在上升啊(悲
vp出了abd,c是我sb了有个地方初始化错了。
然后预期的话应该是要能出E的(“简单dp”)
FG还没补,感觉小难
F是一个动态开点线段树,周末学学再补。
G是一个复杂dp呜

A. Compare T-Shirt Sizes

嗯模拟

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
#include <bits/stdc++.h>

using namespace std;
map <char, int> mp;

void solve () {
string a, b;
cin >> a >> b;
if (a == b) {
puts ("=");
return;
}
int n = a.size (), m = b.size ();
for (int i = n - 1, j = m - 1; i >= 0 && j >= 0; i--, j--) {
if (a[i] == b[j]) continue;
else {
if (mp[a[i]] > mp[b[j]]) puts (">");
else puts ("<");
return ;
}
}
if (a[n-1] == 'S') {
if (n < m) puts (">");
else puts ("<");
}
else {
if (n > m) puts (">");
else puts ("<");
}

}

int main () {
mp['S'] = 0, mp['M'] = 1, mp['L'] = 2;
int t;
cin >> t;
while (t --) solve ();
}

//S, M, L

B. Funny Permutation

简单构造

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
#include <bits/stdc++.h>

using namespace std;

void solve () {
int n;
cin >> n;
if (n == 3) puts ("-1");
else {
if (n & 1) {
for (int i = (n + 1) / 2 + 1; i <= n; i++) cout << i << ' ';
for (int i = 1; i <= (n + 1) / 2; i++) cout << i << ' ';
cout << endl;
}
else {
for (int i = n; i >= 1; i--) cout << i << ' ';
cout << endl;
}
}
}

int main () {
int t;
cin >> t;
while (t --) solve ();
}

//S, M, L

C. Minimize the Thickness

枚举第一段的长度然后贪心构造

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 <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 2005;
int a[N], n, ans, sum;

void solve () {
cin >> n;
ans = n, sum = 0;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int len = 1; len < n; len++) {
//后面贪心构造
sum += a[len];
//cout << "sum=" << sum << endl;
int cur_sum = 0, cur_len = 0, maxn = len; //当前连续段的和, 当前连续段的长度,最大连续段的长度
bool suc = true; //能否这样划分
for (int i = len + 1; i <= n; i++) {
cur_sum += a[i], cur_len ++;
// cout << "cur sum=" << cur_sum << endl;
// cout << "cur len=" << cur_len << endl;
if (cur_sum > sum) {
suc = false;
break;
}
if (cur_sum == sum) {
maxn = max (cur_len, maxn);
cur_len = cur_sum = 0;
}
//cout << "maxn=" << maxn << endl;
}
if (cur_sum && cur_sum < sum) suc = false;
//cout << "suc=" << suc << endl;
if (suc) ans = min (ans, maxn);
}
cout << ans << endl;
}

signed main () {
int t;
cin >> t;
while (t --) solve ();
}

//划分成若干段,每一段的和都相等
//第一段是固定的,枚举第一段的长度,记录最大长度

D. Masha and a Beautiful Tree

每两个交换,然后每四个交换…依次按照两倍扩大

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
#include <bits/stdc++.h>

using namespace std;
const int N = 262144 + 5;
int a[N];

void solve () {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
if (is_sorted (a + 1, a + n + 1)) puts ("0");
else {
//逐层check
long long ans = 0;
for (int len = 1; len < n; len *= 2) {
for (int i = 1; i <= n; i += len * 2) {
int j = i + len;
//cout << i << ' ' << j << endl;
if (abs (a[j] - a[i]) != len) {
puts ("-1");
return ;
}
if (a[j] < a[i]) ans ++, swap (a[j], a[i]);
}
//for (int i = 1; i <= n; i++) cout << a[i] << ' ';cout << endl;
}
cout << ans << endl;
}
}

int main () {
int t;
cin >> t;
while (t --) solve ();
}

E. Sending a Sequence Over the Network

f[i]表示能转移到的状态,然后往左右跳a[i],记录合法转移即可

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
#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
int a[N], f[N];

void solve () {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i], f[i] = 0;
if (n == 1) {
puts ("NO");
return ;
}
f[0] = 1;
for (int i = 1; i <= n; i++) {
if (i + a[i] <= n) f[i + a[i]] |= f[i - 1];
if (i - a[i] >= 1) f[i] |= f[i - 1 - a[i]];
}
if (f[n]) puts ("YES");
else puts ("NO");
}

signed main () {
int t;
cin >> t;
while (t --) solve ();
}

FG待补