Codeforces Round #598 (Div. 3)
A. Payment Without Change
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
ll a, b, n, s;
// ------- 函数 ------- //
void Init() {
scanf("%lld%lld%lld%lld", &a, &b, &n, &s);
}
int Solve() {
ll t = s / n;
a = min(a, t);
if (s - a * n > b) return puts("NO");
return puts("YES");
}
B. Minimize the 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
const int N = (int)1e2+7;
// ------- 变量 ------- //
int n, a[N], vis[N];
// ------- 函数 ------- //
void Init() {
memset(vis, 0, sizeof(vis));
scanf("%d", &n);
rep(i, 1, n+1) scanf("%d", a+i);
}
int Solve() {
int cnt = 0;
rep(i, 1, n+1) {
if (cnt == n - 1) break;
int pos = find(a + 1, a + n + 1, i) - a - 1;
while (pos && !vis[pos] && a[pos+1] < a[pos]) {
swap(a[pos], a[pos+1]);
vis[pos] = 1;
pos--;
}
}
rep(i, 1, n+1) printf("%d%c", a[i], " \n"[i==n]);
return 0;
}
C. Platforms Jumping
贪心
代码
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
const int N = (int)3e3+7;
// ------- 变量 ------- //
int n, m, d;
int c[N], vis[N];
// ------- 函数 ------- //
void Init() {
scanf("%d%d%d", &n, &m, &d);
memset(vis, 0, sizeof(vis));
rep(i, 1, m+1) scanf("%d", c+i);
}
int Solve() {
int pos = n;
per(i, 1, m+1) rep(j, 0, c[i]) vis[pos--] = i;
int cur = 0, id = 0;
while (1) {
cur += d;
if (cur > n) break;
if (!vis[cur]) {
++id;
if (id > m) return puts("NO");
rep(i, 0, c[id]) {
vis[++pos] = 0;
vis[cur+i] = id;
}
cur += c[id] - 1;
}
}
puts("YES");
rep(i, 1, n+1) printf("%d%c", vis[i], " \n"[i==n]);
return 0;
}
D. Binary String Minimizing
贪心
代码
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
const int N = (int)1e6+7;
// ------- 变量 ------- //
int n;
ll k;
char s[N];
// ------- 函数 ------- //
void Init() {
scanf("%d%lld", &n, &k);
scanf("%s", s + 1);
}
int Solve() {
ll cnt = 0, pos0 = 1;
rep(i, 1, n+1) {
if (cnt == k) break;
pos0 = max((ll)i, pos0);
while (pos0 <= n && s[pos0] == '1') pos0++;
if (pos0 == n + 1) return puts(s + 1);
if (pos0 - i + cnt >= k) {
ll pos = pos0;
while (pos > i) {
pos--;
swap(s[pos], s[pos+1]);
cnt++;
if (cnt == k) return puts(s + 1);
}
} else {
cnt += pos0 - i;
swap(s[i], s[pos0]);
}
}
return puts(s + 1);
}
E. Yet Another Division Into Teams
dp
题意
$n$ 个数，分若干组，每组至少 $3$ 个数。
每组代价为最大值减最小值。
总代价为各组代价之和。
求最小总代价。
$3 \le n \le 2 \cdot 10^5$
$1 \le a_i \le 10^9$
代码
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
const int N = 2e5+7;
// ------- 变量 ------- //
int n;
ll dp[N], pre[N];
struct node { int val, id, grp; } a[N];
// ------- 函数 ------- //
void Init() {
scanf("%d", &n);
rep(i, 1, n+1) { scanf("%d", &a[i].val); a[i].id = i; }
}
int Solve() {
sort(a + 1, a + n + 1, [](node &a, node &b){ return a.val < b.val; });
dp[0] = 0; dp[1] = dp[2] = LINF;
rep(i, 3, n+1) {
ll t1 = dp[i-3] + a[i].val - a[i-2].val;
ll t2 = dp[i-1] + a[i].val - a[i-1].val;
if (t1 < t2) {
dp[i] = t1;
pre[i] = 1;
} else {
dp[i] = t2;
pre[i] = 0;
}
}
ll ans1 = dp[n];
a[n].grp = 0;
int poi = n;
while (poi) {
if (pre[poi]) {
a[poi-1].grp = a[poi-2].grp = a[poi].grp;
poi -= 3;
a[poi].grp = a[poi+1].grp - 1;
} else {
a[poi-1].grp = a[poi].grp;
poi--;
}
}
per(i, 1, n+1) a[i].grp -= a[1].grp - 1;
int ans2 = a[n].grp;
sort(a + 1, a + n + 1, [](node &a, node &b){ return a.id < b.id; });
printf("%lld %d\n", ans1, ans2);
rep(i, 1, n+1) printf("%d%c", a[i].grp, " \n"[i==n]);
return 0;
}
F. Equalizing Two Strings
题意
两个字符串 $s$ 和 $t$ ，
每次操作可以选择一个任意长度 $len$ ，
分别翻转 $s$ 和 $t$ 中一个长度为 $len$ 的子串，子串位置可以不同，
问最终是否能使 $s$ 和 $t$ 相同。
题解
- 字符种类和个数相同。
- 若某种字符超过一个，则可使其中一个字符串不动，必为 $YES$ 。
- 否则，即为两个排列，考虑逆序对奇偶性。
代码
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
const int N = 2e5+7;
// ------- 变量 ------- //
int n;
char s[N], t[N];
// ------- 函数 ------- //
char b[N];
void msort(char a[], int l, int r, int &ans) {
if (l >= r) return;
int m = (r + l) >> 1;
msort(a, l, m, ans);
msort(a, m+1, r, ans);
int i = l, j = m+1;
rep(k, l, r+1) {
if (j > r || i <= m && a[i] <= a[j]) b[k] = a[i++];
else b[k] = a[j++], ans += m - i + 1; // ans 为逆序对数
}
rep(k, l, r+1) a[k] = b[k];
}
void Init() {
scanf("%d", &n);
scanf("%s%s", s, t);
}
int Solve() {
int cnt1 = 0, cnt2 = 0;
msort(s, 0, n-1, cnt1);
msort(t, 0, n-1, cnt2);
rep(i, 0, n) if (s[i] != t[i]) return puts("NO");
rep(i, 1, n) if (s[i] == s[i-1]) return puts("YES");
if (abs(cnt1 - cnt2) & 1) return puts("NO");
return puts("YES");
}
