A. Subsegment Reverse
模拟
代码实现
n, l, r = map(int, input().split())
l -= 1
a = list(range(1, n+1))
a[l:r] = a[l:r][::-1]
print(*a)
B. Nutrients
模拟
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> a(m);
rep(i, m) cin >> a[i];
vector x(n, vector<int>(m));
rep(i, n)rep(j, m) cin >> x[i][j];
vector<int> s(m);
rep(i, n)rep(j, m) {
s[j] += x[i][j];
}
rep(i, m) {
if (s[i] < a[i]) {
puts("No");
return 0;
}
}
puts("Yes");
return 0;
}
C.Keys
二进制枚举
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n, m, k;
cin >> n >> m >> k;
vector<int> as(m);
vector<char> r(m);
rep(i, m) {
int c;
cin >> c;
rep(j, c) {
int a;
cin >> a;
--a;
as[i] |= 1<<a;
}
cin >> r[i];
}
int ans = 0;
rep(s, 1<<n) {
bool ok = true;
rep(i, m) {
int num = __builtin_popcount(as[i]&s);
if ((num >= k) != (r[i] == 'o')) ok = false;
}
if (ok) ans++;
}
cout << ans << '\n';
return 0;
}
D. Masked Popcount
\( \sum\limits_{k=0}^n \operatorname{popcount}(k\&m) = \sum\limits_{k=0}^n\sum\limits_{i = 0}^{59} [\frac{k\& m}{2^i} = 1] = \sum\limits_{i = 0}^{59}\sum\limits_{k=0}^n [\frac{k\& m}{2^i} = 1] \)
其中，\(\sum\limits_{k=0}^n [\frac{k\& m}{2^i} = 1]\) 表示使得 \(k\& m\) 的第 \(i\) 位是 \(1\) 的 \(k\) 的个数
容易发现只有 \(m\) 中的 1 所在的位置才会产生贡献
考虑第 \(i\) 位，可以发现 \(2^i\) 个 \(0\) 和 \(2^i\) 个 \(1\) 交替出现
那么周期就是 \(2^{i+1}\)，那么一个完整周期的贡献就是 \(2^i\)，而剩下不足一个周期的部分(假设为 \(r\))的贡献就是 \(\max(0, r-2^i)\)
代码实现
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using mint = modint998244353;
int main() {
ll n, m;
cin >> n >> m;
n++;
mint ans;
rep(i, 60) {
if (m>>i&1) {
ll p = 2ll<<i;
ll r = n%p;
ans += (n-r)/2;
if (r >= (1ll<<i)) {
ans += r-(1ll<<i);
}
}
}
cout << ans.val() << '\n';
return 0;
}