CSP-S 模拟 191101

$n,m\le 7e5$ 求出全局 $gcd,min$ 后按题意模拟即可，注意 $a$ 可以和 $1e9$ 取 $min$ 避免 暴$longlong$ 的问题

#include<bits/stdc++.h> #define cs const using namespace std; typedef long long ll; 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; } cs ll Mx = 1e9 + 7; int n, q; ll mi = 1e18, g; ll gcd(ll a, ll b){ return !b ? a : gcd(b, a % b);} int main(){ n = read(); for(int i = 1; i <= n; i++){ ll x = read(); g = gcd(x, g); mi = min(mi, x); } q = read(); while(q--){ ll a = read(); int b = read(); if(b == 1){ if(gcd(a, g) == a) puts("Yes"); else puts("No");} if(b == 2){ ll x = min(a, Mx); if(mi <= x * x) puts("No"); else puts("Yes"); } } return 0; }

---

T2：给一个序列和 $m$次询问，$n,m\le 2e3,T\le 15$，每次询问与一段区间 $[l,r]$ 相同的区间个数 相同定义为将元素按你喜欢的方式映射后每种元素的出现次数相同 发现就是维护一些桶，把桶按出现次数排序后完全相同 将一个桶的出现次数查入一个桶，最后就是让维护桶的个数的桶是完全一样的 考虑维护一个差值 $\Delta$，表示维护桶的出现次数的桶的不同的地方 如果 $\Delta =0$ 那么是可以作为答案 然后就可以模拟了，桶套桶

#include<bits/stdc++.h> #define cs const using namespace std; typedef long long ll; int read(){ char c; int num = 0; while(!isdigit(c=getchar())); num=c^48; while(isdigit(c=getchar())) num=(num+(num<<2)<<1)+(c^48); return num; } cs int N = 2e3 + 5, M = 26; int T, n, m; char s[N]; int a[N], gl[N], bin[N], goal[N], c[N]; // goal, c 维护 bin 的出现次数 int delta; // 差值 void del(int x){ if(c[bin[a[x]]] <= goal[bin[a[x]]]) ++delta; else --delta; c[bin[a[x]]]--; bin[a[x]]--; if(c[bin[a[x]]] >= goal[bin[a[x]]]) ++delta; else --delta; c[bin[a[x]]]++; } void ins(int x){ if(c[bin[a[x]]] <= goal[bin[a[x]]]) ++delta; else --delta; c[bin[a[x]]]--; bin[a[x]]++; if(c[bin[a[x]]] >= goal[bin[a[x]]]) ++delta; else --delta; c[bin[a[x]]]++; } void Solve(){ n = read(), m = read(); scanf("%s", s + 1); for(int i = 1; i <= n; i++) a[i] = s[i] - 'a'; while(m--){ int l = read(), r = read(), ans = 0, len = r - l + 1; delta = 0; for(int i = l; i <= r; i++) gl[a[i]]++; for(int i = 1; i <= len; i++) bin[a[i]]++; for(int i = 0; i < M; i++) goal[gl[i]]++; for(int i = 0; i < M; i++) c[bin[i]]++; for(int i = 0; i <= len; i++) delta += abs(c[i] - goal[i]); if(delta == 0) ans ++; for(int l = 1; l + len <= n; l++){ del(l); ins(l + len); if(delta == 0) ans++; } cout << ans << '\n'; for(int i = 0; i < M; i++) gl[i] = bin[i] = 0; memset(c, 0, sizeof(int)*(len+1)); memset(goal, 0, sizeof(int)*(len+1)); } } int main(){ T = read(); while(T--) Solve(); return 0; }

T3：一个点的权值为子树的权值和，对每一个点求一个答案，表示它为起点可以到达的终点的权值的或，能到达终点当且仅当路径上的最大最小不是它本身 开始很…地写了一个点分治，贼难写 然后我发现，出题人吃饱了撑着让我们求一个子树和吗？显然不是，出题人是很良心的 显然一个点不能往下走，因为下面一定比它小，所以只能往上走再往下走 走到的所有点就是 $dfs$ 序在 $[1,l-1],[r+1,n]$ 的点 于是问题转换为求这两个区间的中 $val<$ 一个数的个数 离线，前缀做一次，后缀做一次，树状数组即可 另一个方法是按位处理，因为按位处理后是答案是可减的，可能会方便一些

#include<bits/stdc++.h> #define cs const using namespace std; cs int N = 4e5 + 5, M = 1e6 + 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; } int first[N], nxt[N << 1], to[N << 1], tot; void add(int x, int y){ nxt[++tot] = first[x], first[x] = tot, to[tot] = y; } int n, Cap, Mx; int a[N], ans[N]; int in[N], out[N], ps[N], sign; void dfs(int u, int fa){ in[u] = ++sign; ps[sign] = u; for(int i = first[u]; i; i = nxt[i]){ int t = to[i]; if(t == fa) continue; dfs(t, u); a[u] += a[t]; } out[u] = sign; Mx = max(Mx, a[u]); } struct BIT{ int c[M]; void clear(){ memset(c, 0, sizeof(c)); } void add(int x, int v){ for(;x<=Mx; x+=x&-x) c[x] |= v; } int ask(int x){ int ans = 0; for(;x;x-=x&-x) ans |= c[x]; return ans; } }bit; vector<int> pre[N], suf[N]; // 前缀后缀分别做一遍 int calc(int x){ if(in[x] > 1) pre[in[x] - 1].push_back(x); if(out[x] < n) suf[out[x] + 1].push_back(x); } int main(){ n = read(), Cap = read(); for(int i = 1; i < n; i++){ int x = read(), y = read(); add(x, y); add(y, x); } for(int i = 1; i <= n; i++) a[i] = read(); dfs(Cap, 0); for(int i = 1; i <= n; i++) calc(i); // 询问离线 for(int i = 1; i <= n; i++){ bit.add(a[ps[i]], a[ps[i]]); for(int j = 0; j < pre[i].size(); j++){ int nx = pre[i][j]; ans[nx] |= bit.ask(a[nx] - 1); } } bit.clear(); for(int i = n; i >= 1; i--){ bit.add(a[ps[i]], a[ps[i]]); for(int j = 0; j < suf[i].size(); j++){ int nx = suf[i][j]; ans[nx] |= bit.ask(a[nx] - 1); } } for(int i = 1; i <= n; i++) cout << ans[i] << " "; return 0; }

---

T4：给定 $n,k,l$ 问长度为 $n$，可以选出一个子序列的和为 $k$，值域在 $[0,l]$ 的序列个数 $n,k\le 20,l\le 1e9$ 考虑直接把能表示哪些数压到一个状态里，转移时状态的变化就类似背包的转移 复杂度 $O(nk{2}^k)$，严重不满

#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 = 21, M = 1 << 21; typedef long long ll; 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){ ll r = 1ll * a * b; if(r >= Mod) return r % Mod; return r; } void Add(int &a, int b){ a = add(a, b); } int n, k, L, f[2][M]; int main(){ int now = 0, nxt = 1; n = read(), k = read(), L = read(); f[now][1] = 1; int S = (1 << k + 1) - 1, lim = min(L, k); for(int i = 1; i <= n; i++){ memset(f[nxt], 0, sizeof(f[nxt])); for(int j = 1; j <= S; j += 2){ if(f[now][j]){ for(int l = 1; l <= lim; l++){ int nS = j | (((ll)j << l) & S); Add(f[nxt][nS], f[now][j]); } Add(f[nxt][j], f[now][j]); if(L > k) Add(f[nxt][j], mul(f[now][j], L - k)); } } swap(nxt, now); } int ans = 0; for(int j = 1; j < (1 << k); j++) Add(ans, f[now][j | (1 << k)]); cout << ans; return 0; }

---

T5：BZOJ 4261 乐园建设 考场一直在想 $dp$，有一个想法不知道可不可行： 按行转移，维护上一行可以接下来的状态，发现需要知道一个半圆环的左右端点 用 $()0$ 三进制来压，贼难写

---

考虑先求一下可行的情况 发现一个点连出去的边的个数一定是 $2$ 于是网格图黑白染色，显然黑色只会连到白色，然后必须连出两条边，于是源点向黑色连边流量为2，黑色向白色连边，白色向汇点连边流量为 $2$ 考虑如何将权值表示出来 发现一个点的两根轨道独立，如果两个竖或是两个横就没有贡献，否则有贡献 拆点，表示横和竖，一个点向两个点连两条边，一条权值为 0，一条权值为 $val$ 显然如果两个都选横或竖只有 $val$ 的贡献，否则有 $2\ast val$ 的贡献，减去 $sum$ 即可

#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 = 155, M = 35; cs int E = 5e5 + 5; int first[E], nxt[E], to[E], w[E], c[E], tot = 1; void add(int x, int y, int z, int v){ nxt[++tot] = first[x], first[x] = tot, to[tot] = y, w[tot] = z, c[tot] = v; nxt[++tot] = first[y], first[y] = tot, to[tot] = x, w[tot] = 0, c[tot] = -v; } int mp[N][M], val[N][M], id[N][M][3], node, st, ed; int fx[4] = {1, -1, 0, 0}; int fy[4] = {0, 0, 1, -1}; int n, m, sum, Cost, cnt; int dis[E]; bool vis[E]; int from[E], froms[E]; bool spfa(){ queue<int> q; memset(dis, 0x3f, sizeof(dis)); memset(vis, 0, sizeof(vis)); dis[st] = 0; q.push(st); int INF = dis[ed]; while(!q.empty()){ int x = q.front(); q.pop(); vis[x] = false; for(int i = first[x]; i; i = nxt[i]){ int t = to[i]; if(dis[t] > dis[x] + c[i] && w[i]){ dis[t] = dis[x] + c[i]; from[t] = x; froms[t] = i; if(!vis[t]) q.push(t), vis[t] = true; } } } return dis[ed] != INF; } int calc(){ int flow = 1e9, u = ed; while(u^st) flow = min(flow, w[froms[u]]), u = from[u]; u = ed; while(u^st) w[froms[u]] -= flow, w[froms[u]^1] += flow, u = from[u]; return flow; } int dinic(){ int ans = 0; while(spfa()){ int flow = calc(); ans += flow; Cost += flow * dis[ed];} return ans; } int main(){ n = read(), m = read(); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) mp[i][j] = read(); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) val[i][j] = read(), sum += mp[i][j] ? 0 : val[i][j]; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) for(int k = 0; k <= 2; k++) id[i][j][k] = ++node; st = 0; ed = node + 1; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ if(!mp[i][j]){ if((i+j) & 1){ add(st, id[i][j][0], 2, 0); add(id[i][j][0], id[i][j][1], 1, - val[i][j]); add(id[i][j][0], id[i][j][1], 1, 0); add(id[i][j][0], id[i][j][2], 1, - val[i][j]); add(id[i][j][0], id[i][j][2], 1, 0); } else{ add(id[i][j][0], ed, 2, 0); cnt += 2; add(id[i][j][1], id[i][j][0], 1, - val[i][j]); add(id[i][j][1], id[i][j][0], 1, 0); add(id[i][j][2], id[i][j][0], 1, - val[i][j]); add(id[i][j][2], id[i][j][0], 1, 0); } } } } for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ if(!mp[i][j] && ((i+j) & 1)){ for(int l = 0; l < 4; l++){ int nx = i + fx[l], ny = j + fy[l]; if(nx < 1 || nx > n || ny < 1 || ny > m || mp[nx][ny]) continue; if(l <= 1) add(id[i][j][1], id[nx][ny][1], 1, 0); else add(id[i][j][2], id[nx][ny][2], 1, 0); } } } } int flow = dinic(); if(flow < cnt){ puts("-1"); return 0; } cout << - Cost - sum; return 0; }