The 2019 ICPC China Shaanxi Provincial Programming Contest(2019陕西省赛)
B. Grid with Arrows
并查集一下。
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
struct UnionFind {
int n;
vector<int> f;
UnionFind(const int &n) : n(n), f(n) {
iota(f.begin(), f.end(), 0);
}
int get(int x) {
while (x != f[x]) {
x = f[x] = f[f[x]];
}
return x;
}
bool unite(int x, int y) {
x = get(x), y = get(y);
if (x != y) {
f[y] = x;
return 1;
}
return 0;
}
bool united(int x, int y) {
return get(x) == get(y);
}
};
void solve() {
int n, m;
cin >> n >> m;
vector<string> d(n);
for (int i = 0; i < n; i++) {
cin >> d[i];
}
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
}
}
vector<vector<int>> vis(n, vector<int>(m));
UnionFind f(n * m);
int cnt1 = n * m, cnt2 = cnt1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int x = i, y = j;
int u = x * m + y;
if (d[i][j] == 'u') {
x -= a[i][j];
} else if (d[i][j] == 'd') {
x += a[i][j];
} else if (d[i][j] == 'l') {
y -= a[i][j];
} else {
y += a[i][j];
}
if (x < 0 || x >= n || y < 0 || y >= m) {
continue;
}
if (!vis[x][y]) {
cnt2--;
}
vis[x][y] = 1;
int v = x * m + y;
if (f.unite(u, v)) {
cnt1--;
}
}
}
cout << (cnt1 == 1 && cnt2 <= 1 ? "Yes" : "No") << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
C. 0689
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
string s;
cin >> s;
int a = 0, b = 0, c = 0, d = 0;
int n = s.size();
for (int i = 0; i < n; i++) {
if (s[i] == '0') {
a++;
} else if (s[i] == '6') {
b++;
} else if (s[i] == '8') {
c++;
} else {
d++;
}
}
i64 ans = (1LL + n) * n / 2;
ans += (b != n && d != n);
ans -= (1LL + a) * a / 2;
ans -= (1LL + c) * c / 2;
ans -= 1LL * b * d;
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
E. Turn It Off
二分。
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
int n, k;
cin >> n >> k;
string s;
cin >> s;
int ans = 0;
int l = 0, r = n;
auto check = [&](int x) {
int cnt = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '1') {
i += x;
cnt++;
}
}
return cnt <= k;
};
while (l <= r) {
int m = (l + r) >> 1;
if (check(m)) {
r = m - 1;
ans = m;
} else {
l = m + 1;
}
}
cout << ans + 1 << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
F. K-hour Clock
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
constexpr int P = 1000000007;
void solve() {
int x, y, z;
cin >> x >> y >> z;
int n = x + y;
if (n == z) {
cout << z + 1 << '\n';
return;
}
if (n > z && n - z > x && n - z > z) {
cout << n - z << '\n';
} else {
cout << -1 << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
I. Unrooted Trie
先判断 \(0\) 的情况，\(\text{dfs}\) 序，前缀和。
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
int n;
cin >> n;
vector<vector<pair<int, int>>> g(n);
for (int i = 1; i < n; i++) {
int u, v;
char c;
cin >> u >> v >> c;
u--, v--;
g[u].push_back({v, c - 'a'});
g[v].push_back({u, c - 'a'});
}
int cnt[26] {};
for (int i = 0; i < n; i++) {
bool flag = 0;
for (auto &[nex, w] : g[i]) {
cnt[w]++;
}
for (auto &[nex, w] : g[i]) {
if (cnt[w] > 2) {
cout << "0\n";
return;
}
if (cnt[w] == 2) {
if (flag) {
cout << "0\n";
return;
}
flag = 1;
}
cnt[w] = 0;
}
}
vector<int> dfn(n), sz(n);
int tot = 0;
function<void(int, int)> dfs = [&](int cur, int pre) {
dfn[cur] = tot++;
sz[cur] = 1;
for (auto &[nex, w] : g[cur]) {
if (nex != pre) {
dfs(nex, cur);
sz[cur] += sz[nex];
}
}
};
dfs(0, -1);
vector<int> sum(n);
int f[26];
for (int i = 0; i < 26; i++) {
f[i] = -1;
}
auto cover = [&](const int &l, const int &r) {
sum[l]++;
if (r < n) {
sum[r]--;
}
};
for (int x = 0; x < n; x++) {
for (auto [y, w] : g[x]) {
if (f[w] == -1){
f[w] = y;
} else {
int z = f[w];
int i = dfn[x], j = dfn[y], k = dfn[z];
if (j > k) {
swap(j, k);
swap(y, z);
}
if (k > i && j > i) {
cover(0, j);
if (j + sz[y] < n) {
cover(j + sz[y], k);
}
if (k + sz[z] < n) {
cover(k + sz[z], n);
}
} else if (j < i && i < k) {
cover(i, k);
if (k + sz[z] < n) {
cover(k + sz[z], i + sz[x]);
}
}
break;
}
}
for (auto &[y, w] : g[x]) {
f[w] = -1;
}
}
for (int i = 0; i < n - 1; i++) {
sum[i + 1] += sum[i];
}
int ans = n;
for (int i = 0; i < n; i++) {
ans -= (sum[i] != 0);
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
L. Digit Product
会发现出现 \(0\) 答案就会始终为 \(0\)。
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
constexpr int P = 1000000007;
void solve() {
int l, r;
cin >> l >> r;
i64 ans = 1;
for (int i = l; i <= r; i++) {
string s = to_string(i);
for (auto &si : s) {
if (si == '0') {
cout << 0 << '\n';
return;
}
ans *= (si - '0');
ans %= P;
}
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}