题目
Codeforces Round 617 (Div. 3) - Codeforces
Problem - A
方法一：数学
思路
数组在以下两种情况下是合法的：
- 数组和为奇数：不用替换任何元素就已经符合题意；
- 数组和为偶数但数组内元素有奇有偶：把偶数元素替换为奇数元素数组和就会变为奇数。
代码
#include <cstdio>
using namespace std;
int t, n;
void solve() {
int sum = 0;
bool has_odd = false, has_even = false;
scanf("%d", &n);
while (n--) {
int x; scanf("%d", &x);
sum += x;
if (x & 1) has_odd = true;
else has_even = true;
}
puts((sum & 1) || has_odd && has_even ? "YES" : "NO");
}
int main() {
scanf("%d", &t);
while (t--) solve();
return 0;
}
Problem - B
方法一：模拟
思路
按照题意模拟即可。
代码
#include <cstdio>
using namespace std;
int t, n;
void solve() {
scanf("%d", &n);
int ans = 0;
while (n / 10) {
ans += n / 10 * 10;
n = n / 10 + n % 10;
}
ans += n;
printf("%d\n", ans);
}
int main() {
scanf("%d", &t);
while (t--) solve();
return 0;
}
Problem - C
方法一：暴力 枚举 模拟
思路
如果存在一段移动满足：完成这段移动后回到了这段移动前所在的点。那么这段移动就是可以删掉的。
模拟所有移动找到最短的一段即可（如果有多段长度一样的，输出最前面的）。
代码1
把坐标处理成一个长整数。
#include <cstdio>
#include <unordered_map>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10, MASK = 1e6;
int DIRS[128][2];
int t, n;
char s[N];
unordered_map<LL, int> mp;
void solve() {
scanf("%d%s", &n, s + 1);
mp.clear();
int mn = n + 1, l = 0;
int x = 0, y = 0;
for (int i = 1; i <= n; ++i) {
mp[1LL * x * MASK + y] = i;
const auto& DIR = DIRS[s[i]];
x += DIR[0], y += DIR[1];
int j = mp[1LL * x * MASK + y];
if (j) {
int len = i - j + 1;
if (len < mn) {
mn = len;
l = j;
}
}
}
if (mn <= n) printf("%d %d\n", l, l + mn - 1);
else puts("-1");
}
int main() {
scanf("%d", &t);
DIRS['L'][0] = -1, DIRS['L'][1] = 0;
DIRS['R'][0] = 1, DIRS['R'][1] = 0;
DIRS['U'][0] = 0, DIRS['U'][1] = 1;
DIRS['D'][0] = 0, DIRS['D'][1] = -1;
while (t--) solve();
return 0;
}
代码2
自定义结构哈希。
#include <cstdio>
#include <utility>
#include <functional>
#include <unordered_map>
using namespace std;
struct Info {
int x, y;
bool operator==(const Info& o) const {
return x == o.x && y == o.y;
}
};
struct InfoHash {
size_t operator()(const Info& info) const {
return hash<int>()(info.x) ^ hash<int>()(info.y);
}
};
const int N = 2e5 + 10;
unordered_map<char, Info> DIRS;
int t, n;
char s[N];
unordered_map<Info, int, InfoHash> mp;
void solve() {
scanf("%d%s", &n, s + 1);
mp.clear();
int x = 0, y = 0;
int mn = n + 1, l = -1;
for (int i = 1; i <= n; ++i) {
mp[{x, y}] = i;
const Info& DIR = DIRS[s[i]];
x += DIR.x, y += DIR.y;
int j = mp[{x, y}];
if (j) {
int len = i - j + 1;
if (len < mn) {
mn = len;
l = j;
}
}
}
if (mn <= n) printf("%d %d\n", l, l + mn - 1);
else puts("-1");
}
int main() {
scanf("%d", &t);
DIRS['L'] = {-1, 0};
DIRS['R'] = {1, 0};
DIRS['U'] = {0, 1};
DIRS['D'] = {0, -1};
while (t--) solve();
return 0;
}
Problem - D
方法一：贪心
思路
先让所有怪物把能挨的 hp 全部挨完（也就是保证怪物血量：）再进行讨论。
此时， 的怪物不需要使用秘籍就能让 抢到人头。
由于每只怪物对答案的贡献都固定为 ，所以对于剩下的怪物：优先找血量少的怪物去使用秘籍处理（血量越少，使用秘籍的次数一定会越少），所以直接从小到大排个序依次处理，直到秘籍不够用了为止即可。
代码
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int n, a, b, k;
int h[N];
int main() {
scanf("%d%d%d%d", &n, &a, &b, &k);
for (int i = 0; i < n; ++i) {
scanf("%d", &h[i]);
h[i] %= a + b;
if (h[i] == 0) h[i] += a + b;
}
sort(h, h + n);
int ans = 0;
for (int i = 0; i < n; ++i) {
h[i] -= a;
int cnt = (h[i] + a - 1) / a;
if (cnt <= k) {
++ans;
k -= cnt;
} else break;
}
printf("%d\n", ans);
return 0;
}
Problem - E1
方法一：二分图
冒泡排序把所有逆序对连边建图，然后染色法判二分图即可。合法方案即为染色数组。
（这种方法只有 easy version 能用）
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 210;
int n;
char s[N];
int pos[N];
int h[N], e[N * N], ne[N * N], idx;
int color[N];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
bool dye(int u, int c) {
color[u] = c;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (color[v] == -1 && !dye(v, !c) || color[v] == c) return false;
}
return true;
}
int main() {
scanf("%d%s", &n, s + 1);
memset(h, -1, sizeof(h));
for (int i = 1; i <= n; ++i) pos[i] = i;
for (int i = 1; i <= n - 1; ++i) {
for (int j = 1; j <= n - i; ++j) {
if (s[j] > s[j + 1]) {
swap(s[j], s[j + 1]), swap(pos[j], pos[j + 1]);
add(pos[j], pos[j + 1]), add(pos[j + 1], pos[j]);
}
}
}
memset(color, -1, sizeof(color));
for (int u = 1; u <= n; ++u) {
if (color[u] == -1 && !dye(u, 0)) {
puts("NO");
return 0;
}
}
puts("YES");
for (int i = 1; i <= n; ++i) putchar('0' + color[i]);
return 0;
}
方法二：动态规划 最长严格降序子序列
字符串里的严格降序子序列都是一串需要交换的集合。
所以直接对字符串做动态规划找到最长严格降序子序列，如果其长度不大于 2 就说明可以进行合法染色，否则不能。
合法方案即为 。
代码
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 210;
int n;
int chr_color[128], pos_color[N];
int main() {
scanf("%d", &n);
getchar();
for (int i = 0; i < n; ++i) {
char c = getchar();
for (char j = 'a'; j <= 'z'; ++j) {
if (c < j) pos_color[i] = max(pos_color[i], chr_color[j]);
}
if (pos_color[i] > 1) {
puts("NO");
return 0;
}
chr_color[c] = ++pos_color[i];
}
puts("YES");
for (int i = 0; i < n; ++i) putchar('0' + pos_color[i] - 1);
return 0;
}
Problem - E2
方法一：动态规划 最长严格降序子序列
同上。
数组长度最长有 ，用一般的 LIS 问题的 DP 做法肯定行不通（ 的时间复杂度）。但是发现字符串中之可能出现 26 个小写英文字母，所以内层循环不再枚举下标，直接枚举字母即可（代价是要多维护一个字符的贡献数组）。
代码
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int n;
char s[N];
int f[N], g[128];
int main() {
scanf("%d%s", &n, &s);
getchar();
int mx = 0;
for (int i = 0; i < n; ++i) {
f[i] = 1;
for (int j = 'a'; j <= 'z'; ++j) {
if (j > s[i]) f[i] = max(f[i], g[j] + 1);
}
g[s[i]] = f[i];
mx = max(mx, f[i]);
}
printf("%d\n", mx);
for (int i = 0; i < n; ++i) printf("%d ", f[i]);
return 0;
}
Problem - F
方法一：建图 构造 DFS
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5010, INF = 2e9;
int n, m;
int h[N], w[N * 2], e[N * 2], ne[N * 2], idx;
struct Edge {
int u, v, w;
bool operator<(const Edge& o) const {
return w < o.w;
}
} edges[N], qs[N];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
bool dfs(int u, int p, int dest, int d) {
if (u == dest) return true;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == p) continue;
if (dfs(v, u, dest, d)) {
int j = h[v];
while (~j && e[j] != u) j = ne[j];
w[i] = w[j] = d;
return true;
}
}
return false;
}
int get_mn(int u, int p, int dest) {
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == dest) return w[i];
if (v == p) continue;
int d = get_mn(v, u, dest);
if (d != -1) return min(w[i], d);
}
return -1;
}
int main() {
scanf("%d", &n);
memset(h, -1, sizeof(h));
for (int i = 0; i < n - 1; ++i) {
int x, y;
scanf("%d%d", &x, &y);
add(x, y), add(y, x);
edges[i] = {x, y, -1};
}
scanf("%d", &m);
for (int i = 0; i < m; ++i) scanf("%d%d%d", &qs[i].u, &qs[i].v, &qs[i].w);
sort(qs, qs + m);
for (int i = 0; i < m; ++i) dfs(qs[i].u, -1, qs[i].v, qs[i].w);
for (int i = 0; i < m; ++i) {
int res = get_mn(qs[i].u, -1, qs[i].v);
if (res != qs[i].w) {
puts("-1");
return 0;
}
}
for (int i = 0; i < n - 1; ++i) {
const int& u = edges[i].u, & v = edges[i].v;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == v) {
printf("%d ", w[i] ? w[i] : 0721);
break;
}
}
}
return 0;
}
评论区