A - Lucky 7
大水题，模拟即可。
#include <iostream> #include <cstdio> using namespace std; int main() { string s; cin >> s; if (s[0] == '7' || s[1] == '7' || s[2] == '7') { puts("Yes"); } else { puts("No"); } return 0; }
B - FizzBuzz Sum
还是大水题，模拟。
#include <iostream> #include <cstdio> using namespace std; int main() { int n; long long ans = 0; cin >> n; for (int i = 1; i <= n; i++) { if (i % 3 != 0 && i % 5 != 0) { ans += i; } } cout << ans; return 0; }
C - Sum of gcd of Tuples (Easy)
这次的前几题怎么都那么水鸭。
数据范围那么小，暴力枚举即可。
#include <iostream> #include <cstdio> using namespace std; int k; long long ans; int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } int main() { cin >> k; for (int a = 1; a <= k; a++) { for (int b = 1; b <= k; b++) { int d = gcd(a, b), e; for (int c = 1; c <= k; c++) { e = gcd(d, c); ans += e; } } } cout << ans; return 0; }
D - RGB Triplets
枚举前两个数的位置，假设是i，j（$i < j$）
处理一个后缀颜色数量cnt[x][c]代表从x-n有多少颜色c。
枚举的时候先加上cnt[j+1][除了i,j的另外一种颜色]
然后再判断和i到j等距的那个点有没有被算上，如果被算上了直接减一即可。
#include <iostream> #include <cstdio> using namespace std; long long n; char s[4010]; long long cnt[4010][3];//0:R 1:G 2:B long long ans; long long f(char c) { if (c == 'R') return 0; if (c == 'G') return 1; return 2; } long long g(char a, char b) { return (3 - f(a) - f(b)) % 3; } int main() { scanf("%lld%s", &n, s + 1); for (long long i = n; i >= 1; i--) { cnt[i][0] = cnt[i + 1][0]; cnt[i][1] = cnt[i + 1][1]; cnt[i][2] = cnt[i + 1][2]; cnt[i][f(s[i])]++; } for (long long i = 1; i < n - 1; i++) { for (long long j = i + 1; j < n; j++) { if (s[i] == s[j]) continue; ans += cnt[j + 1][g(s[i], s[j])]; if (j + j - i <= n && f(s[j + j - i]) == g(s[i], s[j])) ans--; } } cout << ans; return 0; }
E - Sum of gcd of Tuples (Hard)
简单容斥。
设dp[d]=gcd(a1,a2...an)=d的数列的数量，显然ai得是d的倍数，有$frac{k}{d}$种选择，所以有${frac{k}{d}}^n$个数列。
但是这样会包含gcd=d*2,gcd=d*3...的答案，所以要减去。
实现的时候倒着循环即可。
#include <iostream> #include <cstdio> using namespace std; const long long mod = 1e9 + 7; long long n, k; long long dp[100010], ans; long long ksm(long long a, long long b) { long long ret = 1; while (b) { if (b & 1) { ret = (ret * a) % mod; } a = (a * a) % mod; b >>= 1; } return ret; } int main() { cin >> n >> k; for (long long i = k; i >= 1; i--) { long long num = k / i; dp[i] = ksm(num, n); for (long long j = i + i; j <= k; j += i) { dp[i] = (dp[i] - dp[j] + mod) % mod; } ans = (ans + dp[i] * i) % mod; } cout << ans; return 0; }
F - Select Half
动态规划。
设计子状态dp[i]代表前i个数取$frac{i}{2}$个数的最大值，显然dp[1]=0。
考虑转移方程。
若i为奇数
则若不选i，答案是dp[i-1]，若选i，答案是dp[i-2]+a[i]，在两者之间取max即可
若i为偶数，若选i同上，若不选i只有取i-1以内左右编号为奇数的数这一种情况，两者取max即可。
#include <iostream> #include <cstdio> using namespace std; long long n; long long a[200010]; long long dp[200010]; long long sum[200010]; int main() { scanf("%lld", &n); for (long long i = 1; i <= n; i++) scanf("%lld", &a[i]); sum[1] = a[1]; for (long long i = 3; i <= n; i += 2) { sum[i] = sum[i - 2] + a[i]; } for (long long i = 2; i <= n; i++) { if (i & 1) { dp[i] = max(dp[i - 1], dp[i - 2] + a[i]); } else { dp[i] = max(sum[i - 1], dp[i - 2] + a[i]); } } printf("%lld", dp[n]); return 0; }