题目链接：ACM International Collegiate Programming Contest, Arabella Collegiate Programming Contest (2018)
A – Multiplication Dilemma
分解成$\sum_{i = 1}^{n}10^i \cdot w_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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; LL T, a, b; LL sgn; LL cost[10] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000}; vector <LL> va, vb; void work(LL x, LL y) { va.clear(); vb.clear(); while (x) { va.push_back(x % 10); x /= 10; } while (y) { vb.push_back(y % 10); y /= 10; } LL cnt = 0; for (auto i = 0; i < va.size(); ++i) { for (auto j = 0; j < vb.size(); ++j) { if (va[i] == 0 || vb[j] == 0) continue; ++cnt; if (sgn == 1) { if (cnt != 1) printf(" + "); printf("%lld x %lld", va[i] * cost[i], vb[j] * cost[j]); } else { if (cnt == 1) printf("-%lld x %lld", va[i] * cost[i], vb[j] * cost[j]); else printf(" - %lld x %lld", va[i] * cost[i], vb[j] * cost[j]); } } } printf("\n"); } int main() { scanf("%lld", &T); for (LL cs = 1; cs <= T; ++cs) { scanf("%lld%lld", &a, &b); // 1 => positive, 0 => negative if (a > 0 && b > 0) sgn = 1; if (a < 0 && b > 0) sgn = 0; if (a > 0 && b < 0) sgn = 0; if (a < 0 && b < 0) sgn = 1; a = (a > 0 ? a : -a); b = (b > 0 ? b : -b); work(a, b); } return 0; } |
D – Wooden Fence
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; LL T, n, x, y; int main() { ios::sync_with_stdio(false); cin >> T; for (LL i = 1; i <= T; ++i) { cin >> n >> x >> y; if (n / 2 <= y && n / 2 + 1 <= x) cout << "YES" << endl; else cout << "NO" << endl; } return 0; } |
H – Beautiful Substrings
二分。
|
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 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL maxn = 100000 + 5; char a[maxn], b[maxn]; LL T, n, m, k, ans; set <char> nex[26]; vector <LL> pos[26]; void init() { for (LL i = 0; i < 26; ++i) { nex[i].clear(); pos[i].clear(); } } int main() { scanf("%d", &T); for (LL cs = 0; cs < T; ++cs) { init(); ans = 0; scanf("%lld%lld%lld", &n, &m, &k); scanf("%s%s", a, b); for (LL i = 0; i + k - 1 < n; ++i) nex[a[i] - 'a'].insert(a[i + k - 1]); for (LL i = 0; i < m; ++i) pos[b[i] - 'a'].push_back(i); for (LL i = 0; i < m; ++i) { char u = b[i]; for (auto v: nex[u - 'a']) { auto it = lower_bound(pos[v - 'a'].begin(), pos[v - 'a'].end(), i); if (it == pos[v - 'a'].end()) continue; LL fir = it - pos[v - 'a'].begin(); ans += (pos[v - 'a'].size() - fir); } } printf("%lld\n", ans); } return 0; } close |
J – Even Numbers
结论：$C_{n}^{k} \& k = k$ 时候k为奇数。
统计n的二进制中1的个数，共n+1个数，其中$2^t$（t为1的个数）个是奇数，剩下的是偶数。
|
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 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; LL T, n; LL f[64]; void work() { LL tot = n + 1; LL one = 0; LL x = n; do { if ((x & 1)) ++one; x >>= 1; } while (x); cout << tot - f[one] << endl; } int main() { f[0] = 1; for (LL i = 1; i < 63; ++i) f[i] = f[i - 1] * 2; ios::sync_with_stdio(false); cin >> T; for (LL cs = 1; cs <= T; ++cs) { cin >> n; work(); } return 0; } |
K – Cyclic Shift
模拟。
|
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 |
#include <bits/stdc++.h> using namespace std; int T, n; string a, b; bool check(const string &x, const string &y) { for (unsigned i = 0; i < x.size(); ++i) { if (y[i] != x[(i + 1) % x.size()]) return false; } return true; } int main() { ios::sync_with_stdio(false); cin >> T; for (int cs = 1; cs <= T; ++cs) { cin >> n >> a >> b; string ta, tb; for (unsigned i = 0; i < n; ++i) { if (a[i] != b[i]) { ta.push_back(a[i]); tb.push_back(b[i]); } } cout << (check(ta, tb) ? "YES" : "NO") << endl; } return 0; } |
说点什么