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;
}
- 2019 Programming Provincial Contest Shaanxiprogramming provincial contest shaanxi 2019 programming provincial contest programming collegiate provincial contest programming contest nikkei 2019 programming contest yahoo 2019 programming diverta contest 2019 programming keyence contest 2019 programming collegiate provincial shandong programming provincial collegiate sichuan programming collegiate provincial guangdong