A - x to y
可以把与操作理解为减，把或操作理解为加。先减掉多的，再加上少的。因此至多两次即可。
#include <bits/stdc++.h>using namespace std;using i32 = int32_t;
using i64 = long long;
using ui32 = unsigned int;using pii = pair<int,int>;void solve(){i64 x, y, z;cin >> x >> y;z = x ^ y;int res = 0;if(x & z) res ++;if(y & z) res ++;cout << res << "\n";
}i32 main() {ios::sync_with_stdio(false), cin.tie(nullptr);int t;cin >> t;while(t --) solve();return 0;
}B - 闯关
构造题，我们从 k 往前构造，尽可能多填就好了。
#include <bits/stdc++.h>using namespace std;using i32 = int32_t;
using i64 = long long;
using ui32 = unsigned int;#define int i64using pii = pair<int,int>;i32 main() {ios::sync_with_stdio(false), cin.tie(nullptr);int n, k, h, l, r;cin >> n >> k >> h >> l >> r;if(h + k * l > 0) {cout << "impossible"; return 0;} if(h + (k - 1) * r <= 0) {cout << "impossible"; return 0;}vector<int> a(n + 1, r);a[k] = l, h += (k - 1) * r + l;for(int i = k - 1, x; i >= 1; i --){if(h <= 0) break;x = min(h, r - l);a[i] -= x, h -= x;}for(int i = 1; i <= n; i ++)cout << a[i] << " \n"[i == n];return 0;
}C - f * g
其实就是区间的端点乘积。
除了端点相等的情况外，其他情况都会出现两次。
对于修改来说，我们只要查询出另一个数组的区间和就可以计算出答案。因此这题就是单点修改区间查询的题目。
#include <bits/stdc++.h>using namespace std;using i32 = int32_t;
using i64 = long long;
using ui32 = unsigned int;#define int i64using pii = pair<int,int>;
using vi = vector<int>;const int mod = 998244353;struct mint {int x;mint(int x = 0) : x(x) {}mint &operator=(int o) { return x = o, *this; }mint &operator+=(mint o) { return (x += o.x) >= mod && (x -= mod), *this; }mint &operator-=(mint o) { return (x -= o.x) < 0 && (x += mod), *this; }mint &operator*=(mint o) { return x = (i64) x * o.x % mod, *this; }mint &operator^=(int b) {mint w = *this;mint ret(1);for (; b; b >>= 1, w *= w) if (b & 1) ret *= w;return x = ret.x, *this;}mint &operator/=(mint o) { return *this *= (o ^= (mod - 2)); }friend mint operator+(mint a, mint b) { return a += b; }friend mint operator-(mint a, mint b) { return a -= b; }friend mint operator*(mint a, mint b) { return a *= b; }friend mint operator/(mint a, mint b) { return a /= b; }friend mint operator^(mint a, int b) { return a ^= b; }int val(){return x = (x % mod + mod) % mod;}
};struct BinaryIndexedTree{
#define lowbit(x) ( x & -x )int n;vector<mint> b;BinaryIndexedTree(int n) : n(n) , b(n+1 , 0){};BinaryIndexedTree(vector<mint> &c){ // 注意数组下标必须从 1 开始n = c.size() , b = c;for(int i = 1, fa = i + lowbit(i); i <= n; i ++, fa = i + lowbit(i))if( fa <= n ) b[fa] += b[i];}void modify(int i , mint y){for(; i <= n ; i += lowbit(i)) b[i] += y;return;}mint calc(int i){mint sum = 0;for(; i ; i -= lowbit(i)) sum += b[i];return sum;}mint calc(int l, int r) { if(l > r) return 0;return calc(r) - calc(l - 1);}
};i32 main() {ios::sync_with_stdio(false), cin.tie(nullptr);int n, q;cin >> n >> q;vector<mint> f(n + 1), g(n + 1);for(int i = 1; i <= n; i ++) cin >> f[i].x;for(int i = 1; i <= n; i ++) cin >> g[i].x;BinaryIndexedTree F(f), G(g);mint res = 0;for(int i = 1; i <= n; i ++){res += f[i] * g[i];res += f[i] * G.calc(i + 1, n) * 2;}for(int t, i, x; q; q --) {cin >> t >> i >> x;if(t == 1) {mint delta = x - f[i];f[i] += delta, F.modify(i, delta);res += delta * g[i];res += delta * G.calc(i + 1, n) * 2;}else{mint delta = x - g[i];g[i] += delta, G.modify(i, delta);res += delta * f[i];res += delta * F.calc(1, i - 1) * 2;} cout << res.val() << "\n";}return 0;
}D - 最好的序列（Easy）
因为要保证 MEX 最大，因此基础的序列一定是\(1,2,3,\dots,x\)这样的。打表可以看出\(x\)值不会超过\(32\)。对于剩下的部分，如果我们希望继续提高 LCM，就只能按照质因子提高，我们知道求 LCM有一种方法是，质因子分解，然后对不同质因子的指数求 MAX。因此我们可以枚举质因子，算出答案对于当前质因子的指数，然后再枚举最大可以增加多少。然后就会出现很多个质因子可以增加，我们就可以采用状压 DP的方法来计算能达到的最大值。
#include <bits/stdc++.h>using namespace std;using i32 = int32_t;
using i64 = long long;
using ui32 = unsigned int;#define int i64using pii = pair<int,int>;
using vi = vector<int>;const int mod = 998244353;vi p;void init() {int n = 32;p = vi(n);p[0] = 1;for(int i = 1; i <= n; i ++) p[i] = lcm(p[i - 1], i);return;
}void solve() {int n, X, Y;cin >> n >> X >> Y;int t = -1;for(int i = min({32LL, n, X}); i >= 1 and t == -1; i --)if(p[i] <= Y) t = i;int res = p[t];n -= t;for(int delta = t; delta > 1 and n > 0; delta --) {if(delta * res > Y) continue;vector<pii> b;for(int i = 2, cur = delta; i <= delta and cur >= 1; i ++) {if(cur % i != 0) continue;b.emplace_back(i, 1);while(cur % i == 0) b.back().second *= i, cur /= i;}int M = (1 << b.size()) - 1;vi can;for(int i = 1; i <= M; i ++) {int cnt = 1, cur = res;for(int j = 0; j < b.size(); j ++) {if((i & (1 << j)) == 0) continue;cnt *= b[j].second;while(cur % b[j].first == 0) cnt *= b[j].first, cur /= b[j].first;}if(cnt <= X) can.push_back(i);}vi f(M + 1);f[0] = 1;for(int N = min(n, (int)b.size()); N; N --) {auto g = f;for(int i = 1; i <= M; i ++) {if(g[i]) continue;for(int j : can) {if((i & j) != j) continue;g[i] |= f[i ^ j];}}f = move(g);}if(f[M]){cout << res * delta << "\n";return ;}}cout << res << "\n";return;
}i32 main() {ios::sync_with_stdio(false), cin.tie(nullptr);init();int T;cin >> T;while(T --) solve();return 0;
}
