Day1 - 2023/08/13
B - Base K (atcoder.jp)
题意：给你两个 $ K $ 进制数 $ A $ 和 $ B $，将其转化为十进制，并输出二者的乘积。
思路：低位往高位的权重依次为 $ K^0, K^1, \cdot\cdot\cdot K^n $，若这一位是 $ 1 $，就把权重累加起来，最后计算乘积即可。
代码：
#include <bits/stdc++.h> #define L(i, j, k) for (int i = (j); i <= (k); i++) #define R(i, j, k) for (int i = (j); i >= (k); i--) #define i64 long long inline i64 read() { bool sym = false; i64 res = 0; char ch = getchar(); while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar(); while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar(); return sym ? -res : res; } int main() { int k = read(); std::string s, t; std::cin >> s >> t; i64 x = 0, y = 0, base1 = 1, base2 = 1; R (i, s.size() - 1, 0) { x += (s[i] - '0') * base1; base1 *= k; } R (i, t.size() - 1, 0) { y += (t[i] - '0') * base2; base2 *= k; } printf("%lld\n", x * y); return 0; }
B - Star or Not (atcoder.jp)
题意：给定一棵树，问这棵树是不是一个星星，星星的含义是：树中有一个结点，连接其他 $ N - 1 $ 个结点。
思路：记录一下每个结点的度数，若存在度数为 $ N - 1 $ 的结点，那么说明这个一个星星图。
代码：
#include <bits/stdc++.h> #define L(i, j, k) for (int i = (j); i <= (k); i++) #define R(i, j, k) for (int i = (j); i >= (k); i--) #define i64 long long inline i64 read() { bool sym = false; i64 res = 0; char ch = getchar(); while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar(); while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar(); return sym ? -res : res; } int main() { int n = read(); std::vector<int> deg(n + 1); L (i, 1, n - 1) { int u = read(), v = read(); deg[u]++; deg[v]++; } if (*std::max_element(deg.begin() + 1, deg.end()) == n - 1) { printf("Yes\n"); } else { printf("No\n"); } return 0; }
B - Pasta (atcoder.jp)
题意：有 $ N $ 份面条，每份面条的长度为 $A_i $，接下来 $ M $天，每天 Takahashi 会吃一份长度为 $ B_i $ 的面条，问能否满足他的需求。
思路：开一个桶记录每种长度的面条剩余多少份然后逐天判断即可。
代码：
#include <bits/stdc++.h> #define L(i, j, k) for (int i = (j); i <= (k); i++) #define R(i, j, k) for (int i = (j); i >= (k); i--) #define i64 long long inline i64 read() { bool sym = false; i64 res = 0; char ch = getchar(); while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar(); while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar(); return sym ? -res : res; } int main() { int N = read(), M = read(); std::vector<int> A(N), B(M); std::map<int, int> cnt; L (i, 0, N - 1) { A[i] = read(); cnt[A[i]]++; } L (i, 0, M - 1) { B[i] = read(); if (cnt[B[i]] == 0) { printf("No\n"); return 0; } cnt[B[i]]--; } printf("Yes\n"); return 0; }
B - Integer Division (atcoder.jp)
题意：给定一个整数 $ x $，输出其除以 $ 10 $ 向下取整的结果。
#include <bits/stdc++.h> #define L(i, j, k) for (int i = (j); i <= (k); i++) #define R(i, j, k) for (int i = (j); i >= (k); i--) #define i64 long long inline i64 read() { bool sym = false; i64 res = 0; char ch = getchar(); while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar(); while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar(); return sym ? -res : res; } int main() { i64 x = read(); printf("%lld\n", x / 10 - (std::abs(x) % 10 != 0 && x < 0)); return 0; }
B - ABC-DEF (atcoder.jp)
题意：给定 $ 6 $ 个整数 $ A、B、C、D、E、F $，它们都是 long long 范围内的数字，输出 $ (A \times B \times C) - (D \times E \times F) $ 对 $998244353$ 取模后的结果。
思路：因为这 $ 6 $ 个数可能很大，因此，我们需要保证每次参与计算的两个数都小于 $ 998244353 $，注意结果可能是负数。
参考代码：
#include <bits/stdc++.h> #define L(i, j, k) for (int i = (j); i <= (k); i++) #define R(i, j, k) for (int i = (j); i >= (k); i--) #define i64 long long inline i64 read() { bool sym = false; i64 res = 0; char ch = getchar(); while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar(); while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar(); return sym ? -res : res; } const int mod = 998244353; int main() { i64 A = read(), B = read(), C = read(), D = read(), E = read(), F = read(); i64 x = ((((A % mod) * (B % mod)) % mod) * (C % mod)) % mod; i64 y = ((((D % mod) * (E % mod)) % mod) * (F % mod)) % mod; printf("%lld\n", (x - y + mod) % mod); return 0; }