Codeforces Round #729 (Div. 2)
A - Odd Set
int main() {
ios::sync_with_stdio(0); cout.tie(0); cin.tie(0);
for (cin >> _; _; --_) {
cin >> n;
int x = 0;
for (int i = 0; i < n * 2; ++i) {
cin >> m;
if (m & 1) ++x;
}
cout << (x == n ? "YES
" : "NO
");
}
return 0;
}
B - Plus and Multiply
不管怎么算, 最终都可以写成
(k = a^x + b imes y = b imes n + m, m < b and m > 0)
不断让(m) 加上 (b) 直到 (m + b imes t equiv 0 mod b)
复杂度为(log)级别
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
for (cin >> _; _; --_) {
long long a, b, c;
cin >> c >> a >> b;
bool f = c % b == 1 % b;
for (long long sum = a; sum <= c && a != 1 && !f; sum *= a)
f = sum % b == c % b;
cout << (f ? "Yes" : "No") << '
';
}
return 0;
}
C - Strange Function
打表找规律, 手推也行
第一个不整除的数, 那可肯定是(2, 3) 交替取
然而当(n mod lcm(2,3) = 0), (2, 3)都去不了, 就取(4)
同理什么时候取(5)呢?
(n mod lcm(2, 3, 4) = 0)
相当于每个数贡献都是2, 然后每(lcm(2))出现一个(3), 相当于从(2)变到(3), 加了个(1)
每(lcm(2, 3)) 出现个(4), 且一定是在(3)的基础上便过来的, 还是加了个(1),
就是不断除(lcm), 加(1) 即可
前(43)个数的(lcm)已经超了(1e16)
long long lcm[44];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
lcm[1] = 1;
for (int i = 2; i < 44; ++i)
lcm[i] = lcm[i - 1] * i / __gcd(lcm[i - 1], (long long)i);
for (cin >> _; _; --_) {
long long n, ans = 0;
cin >> n;
for (int i = 1; i < 44; ++i)
ans = (ans + n / lcm[i]) % mod;
cout << (ans + n) % mod << '
';
}
return 0;
}
D - Priority Queue
复杂度(O(n^3))的dp
考虑每个数的贡献, 即位于位置(k)的数字(a_i)能被选几次
设(f(i, j))表示前(i)个数有(j)个遇到(-)时可以删除的数, 则
当(i + 1 eq k, f(i, j) ightarrow f(i + 1, j)), 即不选第(i + 1)步操作
当第(i + 1)个操作为(-),
- (i + 1 < k), 无论当前(j) 为多少, 都可以把 (-) 选上, (f(i, j) ightarrow f(i + 1, max(j - 1, 0)))
- (i + 1 > k and j > 1), 不能把第(k)个数扔了, (f(i, j) ightarrow f(i + 1, j - 1))
当(a_{i + 1} > a_k, f(i, j)
ightarrow f(i + 1, j)) 选上第(i + 1)个数, (j) 不变
当(a_{i + 1} < a_k, f(i, j)
ightarrow f(i + 1, j + 1)) 选上第(i + 1)个数, (j) 加 (1)
当(a_{i + 1} = a_k and i + 1 < k) 选上第(i + 1)个数, (j) 加 (1)
每次算上贡献 (f(n, i) imes a_k) 即可
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, ans = 0;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; ++i) {
char c; cin >> c;
if (c == '+') cin >> a[i];
}
for (int k = 1; k <= n; ++k) if (a[k]) {
vector<vector<int>> f(n + 1, vector<int>(n + 1, 0));
f[0][0] = 1;
for (int i = 0; i < n; ++i)
for (int j = 0; j <= i; ++j) {
if (i + 1 ^ k)
f[i + 1][j] = (f[i + 1][j] + f[i][j]) % mod;
if (!a[i + 1]) {
if (i + 1 < k || j)
f[i + 1][max(j - 1, 0)] = (f[i + 1][max(j - 1, 0)] + f[i][j]) % mod;
} else {
if (a[i + 1] < a[k] || (a[i + 1] == a[k] && i + 1 < k))
f[i + 1][j + 1] = (f[i + 1][j + 1] + f[i][j]) % mod;
else
f[i + 1][j] = (f[i + 1][j] + f[i][j]) % mod;
}
}
for (int j = 0; j <= n; ++j)
ans = (ans + (long long)f[n][j] * a[k] % mod) % mod;
}
cout << ans;
return 0;
}