省选模拟 19/10/15

本文主要是介绍省选模拟 19/10/15，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

T1
开始是这么写的，修改父亲的时候，改 $E[A[i]]$，然后改 $A[i]$ 一圈的 $C[i]$
然后这样最坏是 $O(n)$ 的
令 $G[i]=B[i]-E[i]\ast D[i]+E[i]$
则 $C[i]=G[i]+E[A[i]]+{\sum }_{son}E[son]$
考虑维护 $sum(E[son])$
令 $F[i]=G[i]+sum(E[son])$
显然一个点的 $C[i]$ 就是 $F[i]+E[A[i]]$
如何维护全局最值，考虑将每一个 $E[A[i]]$ 的贡献加上最大最小的$F[i]$丢到全局 $set$ 里面
一个点需要维护所有儿子的 $F$ 构成的 $set$
考虑修改的影响
$D[A[i]],E[A[i]],F[A[i]],F[A[A[i]]$ 要改，然后 $A[A[A[i]]]$ 的 $set$ 也要改
每次修改时先删完在全部扔回去
然后就可以大常数模拟

#include<bits/stdc++.h>
#define cs const
using namespace std;
cs int N = 1e5 + 50;
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 inf = 1e18;
int n, m;
ll A[N], B[N], C[N], D[N], E[N], F[N], G[N];
multiset<ll> S, s[N];
typedef multiset<ll>::iterator Int;
ll mi(int x){ return *s[x].begin();}
ll mx(int x){ return *(--s[x].end());}
void add(int x){if(s[x].empty()) return;S.insert(mi(x) + E[x]);S.insert(mx(x) + E[x]);
}
void del(int x){if(s[x].empty()) return;S.erase(S.find(mi(x) + E[x]));S.erase(S.find(mx(x) + E[x]));
}
void ins(int x){ s[A[x]].insert(F[x] + G[x]);}
void era(int x){ s[A[x]].erase(s[A[x]].find(F[x] + G[x]));}
int main(){n = read(), m = read();for(int i = 1; i <= n; i++) B[i] = read();for(int i = 1; i <= n; i++){A[i] = read(), D[i] += 2, ++D[A[i]];}for(int i = 1; i <= n; i++){E[i] = B[i] / D[i];G[i] = B[i] - D[i] * E[i] + E[i];F[A[i]] += E[i]; } for(int i = 1; i <= n; i++) ins(i);for(int i = 1; i <= n; i++) add(i);while(m--){int op = read();if(op == 1){ int i = read(), j = read();if(A[i] == j) continue;del(A[i]); del(A[A[i]]); del(A[A[A[i]]]);era(i); era(A[i]); era(A[A[i]]);F[A[i]] -= E[i]; --D[A[i]];F[A[A[i]]] -= E[A[i]];E[A[i]] = B[A[i]] / D[A[i]];G[A[i]] = B[A[i]] - D[A[i]] * E[A[i]] + E[A[i]];F[A[A[i]]] += E[A[i]];ins(A[i]); ins(A[A[i]]);add(A[i]); add(A[A[i]]); add(A[A[A[i]]]);A[i] = j;del(A[i]); del(A[A[i]]); del(A[A[A[i]]]);era(A[i]); era(A[A[i]]);F[A[i]] += E[i]; ++D[A[i]];F[A[A[i]]] -= E[A[i]];E[A[i]] = B[A[i]] / D[A[i]];G[A[i]] = B[A[i]] - D[A[i]] * E[A[i]] + E[A[i]];F[A[A[i]]] += E[A[i]];ins(i); ins(A[i]); ins(A[A[i]]);add(A[i]); add(A[A[i]]); add(A[A[A[i]]]);}if(op == 2){ int x = read(); cout << F[x] + G[x] + E[A[x]] << '\n';}if(op == 3){ cout << *S.begin() << " " << *(--S.end()) << '\n'; }}return 0;
}

T2
第一次写轮廓线…
朴素的状压 $2^{2m}\ast n$ 有 $40pts$
朴素的轮廓线 $2^m\ast n\ast m$ 有 $60pts$
显然都不够优秀，需要压成 $2^n$ 级别
考虑按列转移，发现出了问题

需要考虑 1 能不能被 2 压，考虑 2 的时候要考虑 3 有没有被压，考虑 3 有没有被压要考虑 4 有没有压 3，然后就没完没了了，发现正好是一条对角线的状态需要被考虑到，考虑压对角线
类似计数 $dp$的套路，$g$ 表示方案，$f$ 表示推倒的总个数
0 表示被压了，1 表示没有被压

与红色的决策点有关的只有它左边，它上面，和它右上
讨论：
如果 2 被压：
---- 如果 1 被压：这个格子自由了，状态为 1
---- 如果 1 没有被压：
---- ---- 如果 1 选了右，决策点会被压，当前是 $E,S$ 不影响，对 $f^{\prime }$ 的贡献为 $2(f+g)$
---- ---- 如果 1 选了下，决策点会被压，当且仅当是在最后一排，贡献同样是 $2(f+g)$，否则它就自由了
如果 2 没有被压：
---- 如果 3 被压，2 是 $E,S$ 无所谓，决策点是 $E,S$ 无所谓，贡献为 $4(f+g)$
---- 如果 3 没有被压，2 只能向下，贡献为 $2(f+g)$
然后每条对角线的最后一个需要单独转移

---

第一次学轮廓线，开始还有些不理解怎么压，其实就是对我们需要的格子标号，轮廓线是黄色部分，红色是决策点，然后每次完了更新一下轮廓线就可以了，类似状压

然后转移到最低下需要把最下面的挪上去，发现上面两个一定为 0，不需要记录，于是直接平移一下
---- 标号 0 变到 1,1 变到 2…

#include<bits/stdc++.h>
#define cs const
using namespace std;
cs int M = 1 << 15;
typedef long long ll;
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 n, m, p;
int add(int a, int b){ return a + b >= p ? a + b - p : a + b;}
int mul(int a, int b){ return 1ll * a * b % p;}
void Add(int &a, int b){ a = add(a, b);}
int f[2][M], g[2][M], *pf, *nf, *pg, *ng;
int get(int s, int t){ if(t < 0) return 0; return s >> t & 1;}
int Set(int s, int t, int p){ if(t < 0) return s; return (s >> t & 1) == p ? s : (s ^ (1 << t));}
int u[55], d[55], S;
int main(){n = read(), m = read(), p = read();pf = f[0]; nf = f[1]; pg = g[0]; ng = g[1];S = 1 << (n + 1);for(int i = 0; i < m; i++) u[i] = 0;for(int i = m; i < n + m - 1; i++) u[i] = i - m + 1;for(int i = n + m - 2; i >= n - 1; i--) d[i] = n - 1;for(int i = 0; i < n - 1; i++) d[i] = i;ng[0] = 1; nf[0] = 0;for(int i = 0; i < n + m - 1; i++){// 0 禁用，1 自由 swap(nf, pf); swap(ng, pg);for(int l = 0; l < S; l++) nf[l] = ng[l] = 0;// 对角线最后一个格子单独转移 for(int s = 0; s < S; s++){if(pg[s] || pf[s]){int t = get(s, n);Add(ng[Set(s, n, 0)<<1], pg[s]);Add(nf[Set(s, n, 0)<<1], pf[s]);if(t){Add(ng[Set(s, n, 0)<<1], pg[s]);Add(nf[Set(s, n, 0)<<1], pf[s]);		}}}for(int j = 0; j < n; j++){swap(nf, pf); swap(ng, pg);for(int l = 0; l < S; l++) nf[l] = ng[l] = 0;for(int s = 0; s < S; s++){if(pg[s] || pf[s]){int f = pf[s], g = pg[s];if(j < u[i] || d[i] < j){ // 对角线越界强制禁用  Add(nf[Set(s, j, 0)], f);Add(ng[Set(s, j, 0)], g);continue;}int t1 = get(s, j-1), t2 = get(s, j), t3 = get(s, j+1);if(!t2){if(t3){// 当前被禁用，决策 * 2 // t3 的决策为右 int t = Set(s, j, 0); t = Set(t, j+1, 0);Add(nf[t], add(add(f, f), add(g, g)));Add(ng[t], add(g, g));// t3 的决策为下 if(j == n - 1){	int t = Set(s, j, 0); t = Set(s, j+1, 0);Add(nf[t], add(add(f, f), add(g, g)));Add(ng[t], add(g, g));}else{int t = Set(s, j, 1);Add(nf[t], f);Add(ng[t], g);}} else{int t = Set(s, j, 1);Add(nf[t], f);Add(ng[t], g);} }else{int t = Set(s, j, 0); Add(f, f); Add(g, g);if(!t1){Add(nf[t], add(add(f,f), add(g,g))); Add(ng[t], add(g,g));} else{Add(nf[t], add(f, g));Add(ng[t], g);}}}}}} int ans = 0;Add(ans, nf[0]);Add(ans, mul(2, nf[1 << n-1]));Add(ans, mul(2, nf[1 << n])); cout << ans; return 0;
}

T3
结论题：
首先假设有$x$个桶，全部乘上 $x$，然后每个桶的容量为 $tot$，即总和
1.任意 n 个果汁，如果 $(n-1)\ast tot=sum$，那么可以被放到 $n-1$ 个桶中
证明：2 的时候显然成立，$n>2$ 时，考虑到 $min+max\ge average$，于是将 $max$ 的一部分和 $min$ 放在一起，就变成了 $n-1$ 的情况
2.如果 n 个果汁放进 m 个桶，则可以拆成 $n-m$ 个集合，每个集合都形如 1
证明：如果将放进一个桶看做两两连边，那么这种情况可以抽象为 $n$ 个点 $m$ 条边的图
至少有 $n-m$ 个联通块
然后直接枚举最后桶的个数，判断时暴力子集拆分，看合不合法
$O(3^n\ast n)$

#include<bits/stdc++.h>
#define N 20
using namespace std;
typedef long long ll;
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 bin[1 << N]; ll sum[1 << N], tot;
int n, c[N + 5], lim, num[1 << N];
bool ok[1 << N];
bool dfs(int s){if(ok[s]) return true;for(int t = s&(s-1); t; t = s & (t-1)){if(ok[t]) return dfs(s^t);} return false;
}
bool ck(int x){for(int s = 1; s < lim; s++) ok[s] = (sum[s] * x == (bin[s] - (bin[s]>1)) * tot);return dfs(lim - 1);
}
int main(){n = read();for(int i = 0; i < n; i++) c[i] = read(), num[1 << i] = c[i], tot += (ll)c[i];lim = 1 << n;for(int i = 1; i < lim; i++){bin[i] = bin[i >> 1] + (i&1);sum[i] = sum[i^i&(-i)] + (ll)num[i&(-i)];}	for(int i = (n + 1) / 2; i < n; i++){if(ck(i)){ cout << i; break; }} return 0;
}

这篇关于省选模拟 19/10/15的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---