十二省联考 2019 题解

mac2024-09-30 52

[十二省联考2019]异或粽子首先异或转前缀和，类似超级钢琴，将三元组 $(l, r, p)$ 插入堆，表示 $s u m [p]$ 可以跟 $[l, r]$ 之间的拼接每次取出最大值后，将 $(l, p o s - 1, p), (p o s + 1, r, p)$ 插入，查询最大用可持久化 $0 / 1 t r i e$

#include<bits/stdc++.h> #define N 500050 #define LL long long using namespace std; LL read(){ LL cnt = 0, f = 1; char ch = 0; while(!isdigit(ch)){ ch = getchar(); if(ch=='-') f = -1; } while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar(); return cnt * f; } int n, k, rt[N], ch[N*40][2], siz[N*40], id[N*40], tot; LL a[N], s[N], ans; void Modify(int &x, int last, int i, LL val,int now){ x = ++tot; siz[x] = siz[last] + 1; if(i < 0){ id[x] = now; return;} int k = (val >> i) & 1; ch[x][k^1] = ch[last][k^1]; Modify(ch[x][k], ch[last][k], i-1, val, now); } int Quary(int a, int b, int i, LL val){ if(i < 0) return id[a]; int k = (val >> i) & 1; if(siz[ch[a][k^1]] - siz[ch[b][k^1]] > 0) return Quary(ch[a][k^1], ch[b][k^1], i-1, val); else return Quary(ch[a][k], ch[b][k], i-1, val); } struct Node{ int x, l, r, id; LL val; Node(int xx=0, int ll=0, int rr=0){ x = xx, l = ll, r = rr; id = Quary(rt[r], rt[l-1], 31, s[x]); val = s[x] ^ s[id-1]; } friend bool operator < (const Node &a, const Node &b){ return a.val < b.val; } }; priority_queue<Node> q; int main(){ n = read(), k = read(); for(int i=1; i<=n; i++){ a[i] = read(); s[i] = s[i-1] ^ a[i]; Modify(rt[i], rt[i-1], 31, s[i-1], i); } for(int i=1; i<=n; i++) q.push(Node(i, 1, i)); for(int i=1; i<=k; i++){ Node tmp = q.top(); q.pop(); ans += tmp.val; if(tmp.l <= tmp.id-1) q.push(Node(tmp.x, tmp.l, tmp.id - 1)); if(tmp.id+1 <= tmp.r) q.push(Node(tmp.x, tmp.id + 1, tmp.r)); } cout << ans; return 0; }

[十二省联考2019]字符串问题发现就是 $A$ 中的每个串向所有 $A$ 中的能跟它拼接的合法的串连边合法指的是存在一个 $A_x$ 支配的串 $B$ 满足 $B$ 是 $A_y$ 的前缀两种做法： $S A M$ ：发现可以 $A_x$ 向 $B_y$ 连边，然后 $B_y$ 向它作为前缀的 $A_z$ 连边倒着减 $S A M$ ， $B_y$ 在它自己的结点只能向长度比它大的连边，然后可以向 $p a r e n t$ 子树中所有结点连边直接用 $p a r e n t$ 树优化建图，父结点向子节点连边对于这一个结点，对 $l e n$ 排序， $l e n$ 小的向 $l e n$ 大的连边然后 $l e n$ 相同的把 $B$ 放在前面但是有一个问题，就是这样串连的话一个 $B$ 会向它后面一段 $A$ 连边，是不合法的一个 $B$ 只能向后面一段 $A$ 的一个转移，所以 $B$ 向后面一段 $A$ 每个连边 $A$ 之间不能连边， $B$ 还要向下一个 $B$ 连边建好图后 $D A G$ 上 $d p$ 即可 $S A$ ：考虑 $B_x$ 可以向哪些 $A_y$ 连边，就是 $h e i g h t$ 数组上面的一段区间中的 $A_y$ 满足区间任何一个 $A_y$ ， $lcp(A_y,B_x)=len(B_x)$ 我们考虑的是一个完整的后缀的情况，但实际上不是一个完整后缀，还需要满足 $|A_y|\ge |B_x|$ 于是就变成了向区间 $[l,r],|A_y|\ge|B_x|$ 的点连边按长度建主席树，主席树优化建图即可

#include<bits/stdc++.h> #define cs const using namespace std; cs int N = 4e5 + 5, M = 2e6 + 5; typedef long long ll; int T; char s[N]; int na, nb; int n, m; int a[N], b[N]; int ed[N]; bool isA[N << 1]; int le[N << 1]; vector<int> v[N]; int ret; // 给每个串分配编号 bool cmp(int a, int b){ return le[a] > le[b] || (le[a] == le[b] && isA[a] > isA[b]);} #define pb push_back void clear(){ for(int i = 1; i <= ret; i++) isA[i] = le[i] = 0; ret = 0; } namespace SAM{ int ch[N][26], lk[N], len[N], node, las; int fa[N][20], pos[N]; int c[N], a[N]; void clear(){ for(int i = 0; i <= node; i++){ memset(ch[i], 0, sizeof(ch[i])); lk[i] = len[i] = pos[i] = a[i] = c[i] = 0; memset(fa[i], 0, sizeof(fa[i])); v[i].clear(); } las = node = 1; } void extend(int c){ int p = las, now = ++node; len[now] = len[p] + 1; for(;p && !ch[p][c]; p = lk[p]) ch[p][c] = now; if(!p) lk[now] = 1; else{ int q = ch[p][c]; if(len[q] == len[p] + 1) lk[now] = q; else{ int cl = ++node; len[cl] = len[p] + 1; lk[cl] = lk[q]; for(int i = 0; i < 26; i++) ch[cl][i] = ch[q][i]; lk[now] = lk[q] = cl; for(;p && ch[p][c] == q; p = lk[p]) ch[p][c] = cl; } } las = now; } void build(){ for(int i = 1; i <= node; i++) c[len[i]]++; for(int i = 1; i <= n; i++) c[i] += c[i-1]; for(int i = node; i >= 1; i--) a[c[len[i]]--] = i; for(int i = 1; i <= node; i++) fa[i][0] = lk[i]; for(int j = 1; j <= 19; j++) for(int i = 1; i <= node; i++) fa[a[i]][j] = fa[fa[a[i]][j-1]][j-1]; } void jump(int l, int r, int typ){ int Len = r - l + 1; int x = pos[l]; for(int i = 19; i >= 0; i--) if(fa[x][i] && len[fa[x][i]] >= Len) x = fa[x][i]; ++ret; isA[ret] = typ; le[ret] = Len; v[x].pb(ret); } } namespace G{ int first[N << 1], nxt[M], to[M], tot, du[M]; void add(int x, int y){ nxt[++tot] = first[x], first[x] = tot, to[tot] = y; ++du[y];} ll dis[M]; void clear(){ for(int i = 1; i <= ret; i++) first[i] = du[i] = dis[i] = 0; tot = 0; } ll dp(){ queue<int> q; for(int i = 1; i <= ret; i++) if(!du[i]) q.push(i); ll ans = 0; int flg = 0; while(!q.empty()){ int x = q.front(); q.pop(); ++flg; ans = max(ans, dis[x] + (ll)le[x]); for(int i = first[x]; i; i = nxt[i]){ int t = to[i]; dis[t] = max(dis[t], dis[x] + (ll)le[x]); if(--du[t] == 0) q.push(t); } } if(flg ^ ret) return -1; return ans; } } void Solve(){ scanf("%s", s + 1); n = strlen(s + 1); for(int i = n; i >= 1; i--) SAM::extend(s[i] - 'a'), SAM::pos[i] = SAM::las; SAM::build(); ret = SAM::node; scanf("%d", &na); for(int i = 1; i <= na; i++){ int l, r; scanf("%d%d", &l, &r); SAM::jump(l, r, 1); a[i] = ret; } scanf("%d", &nb); for(int i = 1; i <= nb; i++){ int l, r; scanf("%d%d", &l, &r); SAM::jump(l, r, 0); b[i] = ret; } for(int i = 1; i <= SAM::node; i++) sort(v[i].begin(), v[i].end(), cmp); for(int i = 1; i <= SAM::node; i++){ int las = i; for(int j = v[i].size() - 1; ~j; j--){ int now = v[i][j]; G::add(las, now); if(!isA[now]) las = now; } ed[i] = las; // 该 endpos 集合的最后一个点，需要向下一个集合连边 } for(int i = 2; i <= SAM::node; i++) G::add(ed[SAM::lk[i]], i); for(int i = 1; i <= ret; i++) if(!isA[i]) le[i] = 0; scanf("%d", &m); for(int i = 1; i <= m; i++){ int x, y; scanf("%d%d", &x, &y); G::add(a[x], b[y]); } cout << G::dp() << '\n'; } int main(){ scanf("%d", &T); while(T--) SAM::clear(), G::clear(), clear(), Solve(); return 0; } #include<bits/stdc++.h> #define cs const using namespace std; cs int N = 4e5 + 5, E = 1.2e7 + 5; int read(){ int cnt = 0, f = 1; char ch = 0; while(!isdigit(ch)){ ch = getchar(); if(ch=='-') f = -1; } while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar(); return cnt * f; } typedef long long ll; char s[N]; int T, n, m, q, na, nb, la[N], ra[N], lb[N], rb[N]; int sa[N], rk[N], tp[N], hi[N], st[N][20], y[N], c[N]; void Sort(){ for(int i = 0; i <= m; i++) c[i] = 0; for(int i = 1; i <= n; i++) c[rk[i]]++; for(int i = 1; i <= m; i++) c[i] += c[i-1]; for(int i = n; i >= 1; i--) sa[c[rk[y[i]]]--] = y[i]; } void SA(){ for(int i = 1; i <= n; i++) rk[i] = s[i], y[i] = i; Sort(); for(int k = 1; k <= n; k <<= 1){ int ret = 0; for(int i = n - k + 1; i <= n; i++) y[++ret] = i; for(int i = 1; i <= n; i++) if(sa[i] > k) y[++ret] = sa[i] - k; Sort(); swap(rk, tp); rk[sa[1]] = 1; int cnt = 1; for(int i = 2; i <= n; i++){ if(tp[sa[i]] == tp[sa[i-1]] && tp[sa[i] + k] == tp[sa[i-1] + k]) rk[sa[i]] = cnt; else rk[sa[i]] = ++cnt; } m = cnt; } } void HI(){ int k = 0; for(int i = 1; i <= n; i++){ if(rk[i] == 1) continue; int j = sa[rk[i] - 1]; if(k) k--; while(i <= n && j <= n && s[i + k] == s[j + k]) ++k; hi[rk[i]] = k; } for(int i = 1; i <= n; i++) st[i][0] = hi[i]; for(int j = 1; (1 << j) <= n; j++) for(int i = 1; i + (1<<j) - 1 <= n; i++) st[i][j] = min(st[i][j - 1], st[i + (1<<j-1)][j - 1]); } int node, rt[N], pa[N], pb[N], le[E]; vector<int> v[N]; namespace G{ int first[E], nxt[E], to[E], tot, du[E]; void add(int x, int y){ //cout << x << " " << y << endl; nxt[++tot] = first[x], first[x] = tot, to[tot] = y; ++du[y];} ll dis[E]; void clear(){ for(int i = 1; i <= node; i++) first[i] = du[i] = dis[i] = 0; tot = 0; } ll dp(){ queue<int> q; for(int i = 1; i <= node; i++) if(!du[i]) q.push(i); ll ans = 0; int flg = 0; while(!q.empty()){ int x = q.front(); q.pop(); ++flg; ans = max(ans, dis[x] + (ll)le[x]); for(int i = first[x]; i; i = nxt[i]){ int t = to[i]; dis[t] = max(dis[t], dis[x] + (ll)le[x]); if(--du[t] == 0) q.push(t); } } if(flg ^ node) return -1; return ans; } } namespace seg{ int ls[E], rs[E]; void clear(){ for(int i = 1; i <= node; i++) ls[i] = rs[i] = 0; } #define mid ((l+r)>>1) void ins(int &x, int las, int l, int r, int p, int pos){ x = ++node; if(las) G::add(x, las); ls[x] = ls[las]; rs[x] = rs[las]; if(l == r){ G::add(x, pos); return; } if(p <= mid) ins(ls[x], ls[las], l, mid, p, pos), G::add(x, ls[x]); else ins(rs[x], rs[las], mid + 1, r, p, pos), G::add(x, rs[x]); } void modify(int x, int l, int r, int L, int R, int p){ if(!x) return; if(L<=l && r<=R){ G::add(p, x); return; } if(L<=mid) modify(ls[x], l, mid, L, R, p); if(R>mid) modify(rs[x], mid+1, r, L, R, p); } }; void Clear(){ seg::clear(); G::clear(); for(int i = 1; i <= n; i++){ sa[i] = rk[i] = tp[i] = hi[i] = y[i] = c[i] = 0; v[i].clear(); rt[i] = 0; } for(int i = 1; i <= node; i++) le[i] = 0; node = 0; } void Solve(){ scanf("%s", s + 1); n = strlen(s + 1); m = 127; SA(); HI(); na = read(); for(int i = 1; i <= na; i++){ la[i] = read(); ra[i] = read(); pa[i] = ++node; le[pa[i]] = ra[i] - la[i] + 1; v[ra[i] - la[i] + 1].push_back(i); // 按长度建主席树 } nb = read(); for(int i = 1; i <= nb; i++){ lb[i] = read(); rb[i] = read(); pb[i] = ++node; } for(int i = n; i >= 1; i--){ rt[i] = rt[i + 1]; for(int j = 0; j < v[i].size(); j++){ int k = v[i][j]; seg::ins(rt[i], rt[i], 1, n, rk[la[k]], pa[k]); } } q = read(); while(q--){ int x = read(), y = read(); G::add(pa[x], pb[y]); } for(int i = 1; i <= nb; i++){ int len = rb[i] - lb[i] + 1; int lp = rk[lb[i]], rp = rk[lb[i]] + 1; for(int j = 18; j >= 0; j--){ if(lp - (1 << j) > 1 && st[lp - (1 << j) + 1][j] >= len) lp -= 1 << j; } for(int j = 18; j >= 0; j--){ if(rp + (1 << j) <= n && st[rp][j] >= len) rp += 1 << j; } if(hi[rp] < len) rp--; if(hi[lp] < len) lp++; seg::modify(rt[len], 1, n, lp - 1, rp, pb[i]); } cout << G::dp() << '\n'; } int main(){ T = read(); while(T--) Solve(), Clear(); return 0; }

[十二省联考2019]骗分过样例一道打表思维好题存在几个难点： $1 ?$ ：发现结果大概是 $1 e 6$ 左右的，枚举模数暴力判断即可 $1 ? +$ ：好题显然不能直接枚举，只能解方程考虑到如果有两个差很小的数 $x, y$ ，那么 $ans_x=ans_y*19^{y-x}$ 也就是说，我们算出 $ans_y*19^{y-x}-ans_x$ ，那么模数是这个数的约数打表出来发现 $ans_y*19^{y-x}-ans_x=719200885258981741674$ 而观察发现模数在 $1 e 18$ 左右，也就是说要除一个几百的数暴力枚举发现 $m o d = 5211600617818708273$ $1_{WA}$ :盲猜自然溢出，没法快速幂，第二个点没法搞猜想它会不会有循环，用 $m a p$ 求一下即可 $2 p$ ， $m i l l e r - r a b i n$ ，考虑到把样例过了就行了，手玩一波，能少用几个模数判断就少用几个 $2 u$ ：第一个直接线性筛，又有一个很 $n i c e$ 的 $i d e a$ 先将每个数把 $1 e 6$ 的质数除去，除的时候顺便算一下它们对 $\mu$ 的贡献然后现在存在几种数： 1.完全平方数 2.质数 3.合数且最多只有两个 $> 1 e 6$ 的质因子如果有两个，显然对 $\mu$ 没有贡献，不用考虑，算一下质数和平方数的贡献即可这种思维是很妙的，通过预处理，减小规模，将问题化简 $2 g$ ：判断原根，当且仅当 $g^{\frac{\phi(p)}{q}} \% p!=1$ ， $q$ 为 $\phi(p)$ 的质因子然后第二个点凉了考虑到如果一个数 $g$ 是原根，然后 $g^k(gcd(k,\phi(p))$ 也是原根一个比较好理解的方式是，原根的任意次方正好把模 $p$ 意义下的数取遍，然后它的 $k$ 次方如果满足 $gcd(k,\phi(p))=1$ ，也可以取遍然后就是一个数 $x$ ，它的指标 $I (x)$ 如果与 $\phi(p)$ 互质，那么 $x$ 就是原根预处理指标，暴力分解 $\phi(p)$ 然后覆盖不互质的点第三个点又是猜质数，考虑到出题人要卡我们，一定把模数放到中间我们就从中间开始枚举然后不用把所有原根判断完，大概判 50 个就够了

#include<bits/stdc++.h> #define cs const using namespace std; cs int Mod = 998244353; typedef long long ll; ll add(ll a, ll b, ll p){ return a + b >= p ? a + b - p : a + b;} ll mul(ll a, ll b, ll p){ if(p <= 1e9) return 1ll * a * b % p; return (a*b-p*(ll)((long double)a/p*b + 0.5)+p)%p; } ll ksm(ll a, ll b, ll p){ ll ans = 1; for(;b;b>>=1, a = mul(a,a,p)) if(b&1) ans=mul(ans,a,p); return ans; } ll read(){ ll cnt = 0, f = 1; char ch = 0; while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1; if(ch == '?') return 1515343657;} while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar(); return cnt * f; } ll gi(ll p){ ll cnt = 0, f = 1; char ch = 0; while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1;} while(isdigit(ch)) cnt = add(mul(cnt, 10, p-1), ch-'0', p-1), ch = getchar(); return cnt * f; } cs int K = 1e6 + 5; int ans[K]; void WApre(){ ans[0] = 1; for(int i = 1; i <= K - 5; i++) ans[i] = ans[i - 1] * 19 % Mod; } int WA(ll k){ return k >= 55245 ? ans[(k - 55245) % 45699 + 55245] : ans[k]; } char s[20]; int n; cs int N = 1e7; int prim[N + 5]; bool isp[N + 5]; int tot; void prework(){ for(int i = 2; i <= N; i++){ if(!isp[i]) prim[++tot] = i; for(int j = 1; j <= tot; j++){ if(prim[j] * i > N) break; isp[prim[j] * i] = 1; if(i % prim[j] == 0) break; } } } namespace PRIM{ int c[23] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 24251}; bool Miller(ll p, int op = 0){ if(p == 1) return false; if(p == 2) return true; if(p % 2 == 0) return false; if(p == 3) return true; if(p % 3 == 0) return false; if(p <= N) return !isp[p]; bool flg = 1; for(int i = op; i < 10; i++){ if(p == c[i]) return true; ll x = p-1, y = 0; while(x%2 == 0) x/=2, ++y; ll cur = ksm(c[i], x, p); if(cur == 1) continue; for(int j = 1; j <= y; j++){ ll nxt = mul(cur, cur, p); if(nxt == 1 && (cur != 1 && cur != p-1)){ flg = 0; break; } cur = nxt; if(cur == 1) break; } if(cur != 1) flg = 0; if(!flg) break; } return flg; } void calc(ll l, ll r){ for(ll i = l; i <= r; i++){ if(Miller(i)) cout << "p"; else cout << "."; } puts(""); } } namespace MU{ cs int M = 1e6 + 5; int mu[M]; ll p[M]; void calc(ll l, ll r){ for(int j = 0; j <= r - l; ++j) mu[j] = 1, p[j] = 1; for(int j = 1; j <= tot; j++){ for(ll k = l / prim[j]; k <= r / prim[j]; k++){ if(k * prim[j] - l < 0) continue; if(k % prim[j]) mu[k * prim[j] - l] *= -1, p[k * prim[j] - l] *= prim[j]; else mu[k * prim[j] - l] = 0; } } for(ll j = l; j <= r; j++){ if(mu[j - l]){ ll x = j / p[j - l]; if(x > 1){ ll sq = sqrt(x); if(sq * sq == x) mu[j - l] = 0; else if(PRIM::Miller(x, 8)) mu[j - l] *= -1; } } if(mu[j - l] == 0) putchar('0'); else putchar(mu[j - l] == 1 ? '+' : '-'); } puts(""); } } namespace G{ cs int len = 13123111 + 5; int f[len]; bool yes[len]; void calc(ll l, ll r, ll mod){ if(mod == 998244353){ for(int i = l; i <= r; i++){ if(ksm(i, mod/2, mod) == 1 || ksm(i, mod/7, mod) == 1 || ksm(i, mod/17, mod) == 1) putchar('.'); else putchar('g'); } puts(""); } if(mod == 13123111){ static int p[] = {2, 3, 5, 7, 11, 13, 19, 23}; for(int o = 0; o < 8; o++) for(int i = p[o]; i <= mod; i += p[o]) yes[i] = 1; for(int i = 1, g = 6; i < mod; i++, g = mul(g, 6, mod)) f[g] = i; for(int i = l; i <= r; i++) if(yes[f[i]]) putchar('.'); else putchar('g'); puts(""); } if(mod == 1515343657){ for(int i = l; i <= r; i++){ if(ksm(i, mod/2, mod) == 1 || ksm(i, mod/3, mod) == 1 || ksm(i, mod/4003, mod) == 1 || ksm(i, mod/15773, mod) == 1) putchar('.'); else putchar('g'); } puts(""); } } } int main(){ scanf("%s", s); if(s[0] == '1'){ if(s[1] == '?'){ if(s[2] != '+'){ int n = read(); while(n--){ ll k = gi(1145141); cout << ksm(19, k, 1145141) << '\n';} } else{ int n = read(); while(n--){ll k = gi(5211600617818708273); cout << ksm(19, k, 5211600617818708273) << '\n';}} } if(s[1] == 'w'){ WApre(); int n = read(); while(n--){ll k = read(); cout << WA(k) << '\n';}} if(s[1] == '_'){ n = read(); while(n--){ int k = gi(Mod); cout << ksm(19, k, Mod) << '\n'; } } } if(s[0] == '2'){ if(s[1] == 'p'){ prework(); int n = read(); while(n--){ ll l = read(), r = read(); PRIM::calc(l, r); } } if(s[1] == 'u'){ prework(); int n = read(); while(n--){ ll l = read(), r = read(); MU::calc(l, r); } } if(s[1] == 'g'){ int n = read(); while(n--){ll l = read(), r = read(), mod = read(); G::calc(l, r, mod);} } } return 0; }

[十二省联考2019]皮配首先考虑暴力按城市排序，对于同城考虑，再跨成考虑有 $O(nM^2)$ 的背包， $f_{i,j,k,0/1}$ 表示当前到了 $i$ ，红阵营有 $j$ 个，鸭派有 $k$ 个，当前是什么阵营的方案数然后发现 $k = 0$ ，选红阵营蓝阵营，选鸭派还是 $R$ 派是独立的，对城市确定阵营，对学校确定派系就相当于对每一个学校确定了阵营与派系，复杂度 $O (n M)$ 考虑对于没有限制的单独转移，有限制的用上述背包暴力转移找到问题的两维相对独立的思想比较巧妙复杂度 $O(nM+k*s_i*M^2)$

#include<bits/stdc++.h> #define cs const using namespace std; int read(){ int cnt = 0, f = 1; char ch = 0; while(!isdigit(ch)){ ch = getchar(); if(ch=='-') f = -1; } while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar(); return cnt * f; } cs int N = 1e3 + 5, M = 3e3; cs int Mod = 998244353; int add(int a, int b){ return a + b >= Mod ? a + b - Mod : a + b; } int mul(int a, int b){ return 1ll * a * b % Mod;} void Add(int &a, int b){ a = add(a, b); } int T, n, c; int C0, C1, D0, D1; int b[N], s[N]; int f[M]; int g[M]; int k; int hate[N]; bool city[N]; int sum[N]; int F[M][M], G[M][M]; // 该学校选的是红还是蓝 int ALL; void Clear(){ memset(hate, -1, sizeof(hate)); memset(city, 0, sizeof(city)); memset(sum, 0, sizeof(sum)); ALL = 0; } void Solve(){ n = read(); c = read(); C0 = read(); C1 = read(); D0 = read(); D1 = read(); for(int i = 1; i <= n; i++) b[i] = read(), s[i] = read(), sum[b[i]] += s[i], ALL += s[i]; k = read(); for(int i = 1; i <= k; i++){ int x = read(); hate[x] = read(); city[b[x]] = true; } // 对于没有限制的点，2 维独立，分别转移 memset(f, 0, sizeof(f)); f[0] = 1; memset(g, 0, sizeof(g)); g[0] = 1; for(int i = 1; i <= c; i++){ if(!city[i] && sum[i]){ for(int j = C0; j >= sum[i]; j--) Add(f[j], f[j - sum[i]]); } } for(int i = 1; i <= C0; i++) Add(f[i], f[i - 1]); for(int i = 1; i <= n; i++){ if(hate[i] == -1){ for(int j = D0; j >= s[i]; j--) Add(g[j], g[j - s[i]]); } } for(int i = 1; i <= D0; i++) Add(g[i], g[i - 1]); memset(F, 0, sizeof(F)); F[0][0] = 1; memset(G, 0, sizeof(G)); int Cs = 0, Ss = 0; for(int t = 1; t <= c; t++){ if(city[t]){ // 该城市有限制 Cs += sum[t]; Cs = min(Cs, C0); for(int i = 0; i <= Cs; i++) for(int j = 0; j <= Ss; j++) G[i][j] = F[i][j]; for(int a = 1; a <= n; a++){ if(b[a] == t && ~hate[a]){ Ss += s[a]; Ss = min(Ss, D0); if(hate[a] == 1){ // 选 0 for(int i = 0; i <= Cs; i++){ for(int j = Ss; j >= s[a]; j--) F[i][j] = F[i][j - s[a]]; for(int j = s[a] - 1; ~j; j--) F[i][j] = 0; } } if(hate[a] >= 2){ // 红色阵营可以任意转移 for(int i = 0; i <= Cs; i++) for(int j = Ss; j >= s[a]; j--) Add(F[i][j], F[i][j - s[a]]); } if(hate[a] == 3){ // 选 2 for(int i = 0; i <= Cs; i++){ for(int j = Ss; j >= s[a]; j--) G[i][j] = G[i][j - s[a]]; for(int j = s[a] - 1; ~j; j--) G[i][j] = 0; } } if(hate[a] <= 1){ // 蓝色阵营可以任意转移 for(int i = 0; i <= Cs; i++) for(int j = Ss; j >= s[a]; j--) Add(G[i][j], G[i][j - s[a]]); } } } for(int j = 0; j <= Ss; j++){ // 看一下这一座城市选的是红还是蓝 for(int i = Cs; i >= sum[t]; i--) F[i][j] = F[i - sum[t]][j]; for(int i = 0; i < sum[t]; i++) F[i][j] = 0; } for(int i = 0; i <= Cs; i++) for(int j = 0; j <= Ss; j++) Add(F[i][j], G[i][j]); } } int ans = 0; for(int i = 0; i <= Cs; i++){ for(int j = 0; j <= Ss; j++){ if(!F[i][j]) continue; int l1 = max(0, ALL - C1 - i), r1 = C0 - i; if(l1 > r1) continue; int l2 = max(0, ALL - D1 - j), r2 = D0 - j; if(l2 > r2) continue; int vf = f[r1]; if(l1) Add(vf, Mod - f[l1 - 1]); int vg = g[r2]; if(l2) Add(vg, Mod - g[l2 - 1]); Add(ans, mul(F[i][j], mul(vf, vg))); } } cout << ans << '\n'; } int main(){ T = read(); while(T--) Clear(), Solve(); return 0; }

[十二省联考2019]春节十二响首先暴力是先选最大的点，然后看有哪些点能扒着它选树状数组+ $d f s$ 序就可以判断祖先关系考虑链的情况，显然就是这边的最大扒走那边的最大发现这个过程就是子树合并的过程，每次将两个子树的最大合并，保留更大的那个去扒走更多的点小的那个直接扔掉，用一个堆 + 启发式合并就可以了，合并到根的时候剩下的堆中的所有点就是必须删的

#include<bits/stdc++.h> #define N 200050 #define LL long long using namespace std; int read(){ int cnt = 0; char ch = 0; while(!isdigit(ch)) ch = getchar(); while(isdigit(ch)) cnt = (cnt<<1) + (cnt<<3) + (ch-'0'), ch = getchar(); return cnt; } int first[N], nxt[N], to[N], tot; void add(int x,int y){ nxt[++tot] = first[x], first[x] = tot, to[tot] = y;} int n, a[N], id[N], sign, tmp[N]; priority_queue<int> q[N]; void dfs(int u){ id[u] = ++sign; for(int i=first[u];i;i=nxt[i]){ int t = to[i]; dfs(t); if(q[id[t]].size() > q[id[u]].size()) swap(id[t], id[u]); int Siz = q[id[t]].size(); for(int i=1; i<=Siz; i++){ tmp[i] = max(q[id[t]].top(), q[id[u]].top()); q[id[u]].pop(); q[id[t]].pop(); } for(int i=1; i<=Siz; i++) q[id[u]].push(tmp[i]); } q[id[u]].push(a[u]); } int main(){ n = read(); for(int i=1; i<=n; i++) a[i] = read(); for(int i=2; i<=n; i++){ int fa = read(); add(fa, i); } dfs(1); LL ans = 0; while(!q[id[1]].empty()) ans += (LL)q[id[1]].top(), q[id[1]].pop(); printf("%lld", ans); return 0; }

[十二省联考2019]希望只会 $48 p t s$ … 首先选出来的 $k$ 个集合的交集是一个连通块，考虑对这个联通块统计答案显然就是包涵它的连通块个数 ^ k 考虑到一个树上连通块计数的 $t r i c k$ 就是点数 = 边数 + 1 对每个点统计一遍答案，对每条边统计一遍答案，相减，显然一个连通块只被统计了一次树形 $d p$ $f_{i,j}$ 表示 $i$ 向下，距离不超过 $j$ 的连通块个数，单独一个点 $i$ 不算 $f_{i,j}=\prod (f_{son,j-1}+1)$ $g_{i,j}$ 表示向上的，单独一个点算上 $g_{i,j}=1+g_{fa,j-1}\prod g_{son_{fa}!=x,j-2}$ 然后对于 $n = L$ 的点没有距离限制，可以过 $48$ 分

#include<bits/stdc++.h> #define cs const using namespace std; int read(){ int cnt = 0, f = 1; char ch = 0; while(!isdigit(ch)){ ch = getchar(); if(ch=='-') f = -1; } while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar(); return cnt * f; } cs int Mod = 998244353; cs int N = 1e6 + 5, M = N << 1; int add(int a, int b){ return a + b >= Mod ? a + b - Mod : a + b;} int mul(int a, int b){ return 1ll * a * b % Mod;} int ksm(int a, int b){ int ans = 1; for(;b;b>>=1,a=mul(a,a)) if(b&1) ans=mul(ans, a); return ans; } int n, L, k; int first[N], nxt[M], to[M], tot; void adde(int x, int y){ nxt[++tot] = first[x], first[x] = tot, to[tot] = y; } namespace Subtask1{ vector<int> f[N], g[N]; int ans; void dfs1(int u, int fa){ for(int i = first[u]; i; i = nxt[i]){ int t = to[i]; if(t == fa) continue; dfs1(t, u); for(int j = 1; j <= L; j++){ f[u][j] = mul(f[u][j], f[t][j - 1] + 1); } } } int pre[N], suf[N], son[N]; void dfs2(int u, int fa){ int ct = 0; for(int i = first[u]; i; i = nxt[i]){ int t = to[i]; if(t == fa) continue; son[++ct] = t; } pre[0] = suf[ct + 1] = 1; for(int i = 1; i <= L; i++){ if(i >= 2){ for(int j = 1; j <= ct; j++) pre[j] = mul(pre[j - 1], f[son[j]][i - 2] + 1); for(int j = ct; j >= 1; j--) suf[j] = mul(suf[j + 1], f[son[j]][i - 2] + 1); } else{ for(int j = 1; j <= ct; j++) pre[j] = suf[j] = 1; } for(int j = 1; j <= ct; j++){ g[son[j]][i] = add(1, mul(g[u][i - 1], mul(pre[j - 1], suf[j + 1]))); } } for(int i = first[u]; i; i = nxt[i]){ int t = to[i]; if(t == fa) continue; ans = add(ans, ksm(mul(g[t][L] - 1, f[t][L - 1]), k)); dfs2(t, u); } } void Solve(){ for(int i = 1; i <= n; i++) f[i].resize(L + 1, 1), g[i].resize(L + 1, 1); dfs1(1, 0); dfs2(1, 0); ans = Mod - ans; for(int i = 1; i <= n; i++) ans = add(ans, ksm(mul(g[i][L], f[i][L]), k)); cout << ans; } } namespace Subtask2{ int f[N], g[N]; int ans; void dfs1(int u, int fa){ f[u] = 1; for(int i = first[u]; i; i = nxt[i]){ int t = to[i]; if(t == fa) continue; dfs1(t, u); f[u] = mul(f[u], f[t] + 1); } } int pre[N], suf[N], son[N]; void dfs2(int u, int fa){ int ct = 0; for(int i = first[u]; i; i = nxt[i]){ int t = to[i]; if(t == fa) continue; son[++ct] = t; } pre[0] = suf[ct + 1] = 1; for(int j = 1; j <= ct; j++) pre[j] = mul(pre[j - 1], f[son[j]] + 1); for(int j = ct; j >= 1; j--) suf[j] = mul(suf[j + 1], f[son[j]] + 1); for(int j = 1; j <= ct; j++){ g[son[j]] = add(1, mul(g[u], mul(pre[j - 1], suf[j + 1]))); } for(int i = first[u]; i; i = nxt[i]){ int t = to[i]; if(t == fa) continue; ans = add(ans, ksm(mul(g[t] - 1, f[t]), k)); dfs2(t, u); } } void Solve(){ for(int i = 0; i <= n; i++) f[i] = g[i] = 1; dfs1(1, 0); dfs2(1, 0); ans = Mod - ans; for(int i = 1; i <= n; i++) ans = add(ans, ksm(mul(g[i], f[i]), k)); cout << ans; } } int main(){ n = read(); L = read(); k = read(); for(int i = 1; i < n; i++){ int x = read(), y = read(); adde(x, y); adde(y, x); } if(n * L <= 1e7){ Subtask1::Solve(); return 0; } if(n == L){ Subtask2::Solve(); return 0; } }

最新回复(0)