Solved:3
Rank:331
B xor
题意:5e4个集合 每个集合最多32个数
5e4个询问 询问l到r个集合是不是都有一个子集的xor和等于x
题解:在牛客多校第一场学了线性基 然后这个题就是求线性基的交 如果一个区间都能表示x 那么就表示这个区间内所有线性基的交能表示x
用线段树维护这个东西 然后线性基交是抄的板子
#include <bits/stdc++.h> using namespace std; typedef long long ll; int n, m; ll a[50005][35]; struct node { ll val[35]; }; node lb[200005], t1, t2; node merge(node A, node B) { node res; for(int i = 0; i <= 31; i++) t1.val[i] = t2.val[i] = A.val[i], res.val[i] = 0; for(int i = 0; i <= 31; i++) { ll x = B.val[i], t = 0; if(!x) continue; int j = i; for(; j >= 0; j--) { if(x & (1LL << j)) { if(t1.val[j]) x ^= t1.val[j], t ^= t2.val[j]; else break; } } if(!x) res.val[i] = t; else t1.val[j] = x, t2.val[j] = t; } return res; } void build(int l, int r, int rt) { for(int i = 0; i <= 31; i++) lb[rt].val[i] = 0; if(l == r) { for(int i = 1; i <= a[l][0]; i++) { ll tmp = a[l][i]; for(int j = 31; j >= 0; j--) { if(tmp & (1LL << j)) { if(!lb[rt].val[j]) { lb[rt].val[j] = tmp; break; } tmp ^= lb[rt].val[j]; } } } return; } int mid = l + r >> 1; build(l, mid, rt << 1); build(mid + 1, r, rt << 1 | 1); lb[rt] = merge(lb[rt << 1], lb[rt << 1 | 1]); } bool ask(int rt, ll va) { for(int i = 31; i >= 0; i--) { if(va & (1LL << i)) va ^= lb[rt].val[i]; } return va == 0; } bool query(int ql, int qr, ll val, int l, int r, int rt) { if(ql <= l && qr >= r) return ask(rt, val); bool res = 1; int mid = l + r >> 1; if(ql <= mid) res &= query(ql, qr, val, l, mid, rt << 1); if(qr > mid) res &= query(ql, qr, val, mid + 1, r, rt << 1 | 1); return res; } int main() { scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) { scanf("%lld", &a[i][0]); for(int j = 1; j <= a[i][0]; j++) scanf("%lld", &a[i][j]); } build(1, n, 1); for(int i = 1; i <= m; i++) { int a, b; ll c; scanf("%d%d%lld", &a, &b, &c); if(query(a, b, c, 1, n, 1)) puts("YES"); else puts("NO"); } return 0; }
C sequence
题意:给定a,b两个数组 求所有l,r中 最大的 a的最小值*b的区间和
题解:存一下每个点作为最小值 左右两边的最大最小连续子序列
比如每个点左边的最大连续子序列可以由在他左边的点转移过来 这个转移是具有单调性的
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 3e6 + 5; int n; int a[MAXN]; int b[MAXN]; ll sum[MAXN]; ll lz[MAXN], rz[MAXN], lf[MAXN], rf[MAXN]; int lpos[MAXN], rpos[MAXN]; int main() { scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); for(int i = 1; i <= n; i++) scanf("%d", &b[i]), sum[i] = sum[i - 1] + 1LL * b[i]; ll ans = 1LL * a[1] * b[1]; lpos[1] = 0; lz[1] = lf[1] = 0; for(int i = 2; i <= n; i++) { int pos = i - 1; lz[i] = lf[i] = 0; while(pos >= 1 && a[i] <= a[pos]) { lz[i] = max(lz[i], lz[pos] + sum[i - 1] - sum[pos - 1]); lf[i] = min(lf[i], lf[pos] + sum[i - 1] - sum[pos - 1]); pos = lpos[pos]; } lpos[i] = pos; } rpos[n] = n + 1; rz[n] = rf[n] = 0; for(int i = n - 1; i >= 1; i--) { int pos = i + 1; rz[i] = rf[i] = 0; while(pos <= n && a[i] <= a[pos]) { rz[i] = max(rz[i], rz[pos] + sum[pos] - sum[i]); rf[i] = min(rf[i], rf[pos] + sum[pos] - sum[i]); pos = rpos[pos]; } rpos[i] = pos; } for(int i = 1; i <= n; i++) { if(a[i] > 0) { ans = max(ans, (lz[i] + rz[i] + 1LL * b[i]) * a[i]); } else ans = max(ans, (lf[i] + rf[i] + 1LL * b[i]) * a[i]); } printf("%lld ", ans); return 0; }
D triples I
题意:把一个数最少表示成几个数的 or和
题解:如果这个数不是三的倍数的话 那么最多用两个数也可以构造出来了 题目保证有解
然后二进制下瞎逼搞搞 在算第i位大小时1没开LL wa死
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll val1[70]; ll val2[70]; int main() { int T; scanf("%d", &T); while(T--) { ll n; scanf("%lld", &n); int cnt1 = 0, cnt2 = 0; for(ll i = 0; i <= 60; i++) { if((n & (1LL << i)) == (1LL << i)) { if((1LL << i) % 3 == 1LL) val1[++cnt1] = (1LL << i); else val2[++cnt2] = (1LL << i); } } if(n % 3 == 0) printf("1 %lld ", n); else if(n % 3 == 1) { if(cnt1 && cnt2) printf("2 %lld %lld ", n - val1[1], val1[1] + val2[1]); else if(cnt1) printf("2 %lld %lld ", n - val1[1], n - val1[2]); else if(cnt2) printf("2 %lld %lld ", n - val2[1] - val2[2], val2[1] + val2[2] + val2[3]); } else { if(cnt1 && cnt2) printf("2 %lld %lld ", n - val2[1], val1[1] + val2[1]); else if(cnt2) printf("2 %lld %lld ", n - val2[1], n - val2[2]); else if(cnt1) printf("2 %lld %lld ", n - val1[1] - val1[2], val1[1] + val1[2] + val1[3]); } } return 0; }
E triples II (DP)
题意:给一个数a 求用n个是三的倍数的数把它与出来的方案数
题解:根本想不出来是DP.... 一个数的二进制有的位(单看这一位)是%3=1的 有的是%3=2的
这里引用一个题解子集的定义:如果a中为1的二进制位在b中也都为1，我们称a是b的'子集'
dp[i][j]表示有i个%3=1 j个%3=2的数的 且是三的倍数的子集数量 这个东西是可以预处理来的
然后统计答案的时候 因为算的是子集 所以里面有不合法的子集.. 要把不合法的容斥搞出去
以后多复习几遍....
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 998244353; ll pow_mod(ll x, ll y) { ll res = 1; while(y) { if(y & 1) res = res * x % mod; x = x * x % mod; y >>= 1; } return res; } ll dp[40][40]; ll c[40][40]; int main() { c[0][0] = 1; for(int i = 1; i <= 35; i++) { c[i][0] = 1; for(int j = 1; j <= i; j++) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod; } for(int i = 0; i <= 35; i++) { for(int j = 0; j <= 35; j++) { for(int x = 0; x <= i; x++) { for(int y = 0; y <= j; y++) { if((x + y * 2) % 3 == 0) dp[i][j] = (dp[i][j] + c[i][x] * c[j][y] % mod) % mod; } } } } int T; scanf("%d", &T); while(T--) { int cnt1 = 0, cnt2 = 0; ll n, a; scanf("%lld %lld", &n, &a); for(int i = 0; i <= 61; i++) { if(a & (1LL << i)) { if(i & 1) cnt2++; else cnt1++; } } ll ans = 0; for(int i = cnt1 + cnt2; i >= 0; i--) { ll tmp = 0; for(int j = 0; j <= cnt1; j++) { if(i - j > cnt2 || i < j) continue; tmp += c[cnt1][j] * c[cnt2][i - j] % mod * pow_mod(dp[j][i - j], n) % mod; tmp %= mod; } if((cnt1 + cnt2 - i) & 1) tmp = -tmp; ans = (ans + tmp + mod) % mod; } printf("%lld ", ans); } return 0; }