ZJOI 2022
2022/5/4 6:23:19
本文主要是介绍ZJOI 2022,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Day 1
A. 树
考虑假设现在确定了哪个叶子集合是第一棵的,剩下是第二棵。那就是要算恰好第棵叶子集合是这个的方案数,钦定一个集合是叶子好做的,第一棵树就是每个点前面非叶子个数乘起来(第二颗树类似),所以可以选一个不能是叶子集合的容斥。
所以大概就是类似这样的形式:
\[(\sum_{}(-1)^{|s|} \times w(s))(\sum_{}(-1)^{|t|} \times w(t)) \]然后你展开发现同样是行的,就意味着可以一起容斥,其实很显然。。
所以就 dp,决定每个点是哪个叶子的同时,另一颗树可以选择也视为叶子容斥。
考虑按编号从小到大决定,\(f_{x, y}\) 表示目前位置(包括现在这个)之前第一棵树前面有 \(x\) 非叶子,目前位置之后(不包括这个)第二棵树有 \(y\) 个非叶子。
初始 \(f_{1, i} = i\),终止 \(ans = \sum_{i} f_{i, 1} \times i\)
每次迭代加一个,设之前的是 \(f'\),考虑对当前 \(f\) 的贡献:
- 考虑当前叶子给第一棵树
- 钦定第二棵树是叶子容斥: \(-f'_{x,y} \times x \times y \rightarrow f_{x,y}\)
- 不钦定第二棵树是叶子: \(f'_{x,y} \times x \times (y-1) \rightarrow f_{x,y-1}\)
- 考虑第二棵树叶子集合是这个
- 钦定第一棵树是叶子容斥: \(-f'_{x,y} \times x \times y \rightarrow f_{x,y}\) (哈哈,和刚才是一样的,神奇哦
- 不钦定:\(f'_{x,y} \times x \times y \rightarrow f_{x+1,y}\)
复杂度 \(O(n^3)\)。
代码应该是对的吧,,计数题诶。
// SKyqwq #include <bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back using namespace std; typedef pair<int, int> PII; typedef long long LL; template <typename T> bool inline chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; } template <typename T> bool inline chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; } template <typename T> void inline read(T &x) { x = 0; int f = 1; char s = getchar(); while (s > '9' || s < '0') { if (s == '-') f = -1; s = getchar(); } while (s <= '9' && s >= '0') x = x * 10 + s - '0', s = getchar(); x *= f; } const int N = 505; int P, n, f[N][N], g[N][N], ans; void inline add(int &x, int y) { x += y; if (x >= P) x -= P; } void inline del(int &x, int y) { x -= y; if (x < 0) x += P; } int main() { read(n), read(P); for (int i = 1; i <= n; i++) f[1][i] = i; for (int i = 2; i <= n; i++) { ans = 0; for (int j = 1; j <= n; j++) add(ans, 1ll * f[j][1] * j % P); printf("%d\n", ans); memcpy(g, f, sizeof f); memset(f, 0, sizeof f); for (int x = 1; x <= n; x++) { for (int y = 1; y <= n; y++) { if (!g[x][y]) continue; int w = g[x][y]; add(f[x][y - 1], 1ll * w * x % P * (y - 1) % P); del(f[x][y], 1ll * w * x % P * y % P); add(f[x + 1][y], 1ll * w * x % P * y % P); del(f[x][y], 1ll * w * x % P * y % P); } } } return 0; }
D2T2 众数
都有众数了,,,感觉就不能 polylog!
就是选一段区间,算出他里面的众数 + 外面的众数最大值,然后这个贡献是外面众数颜色的。
考虑对每种颜色大小根号分治,暂且以 \(\sqrt{n}\) 为界。
对于 \(> \sqrt{n}\) 的颜色,可以 \(O(n)\) 暴力做,先预处理关于这个颜色的前缀和,可以快速求出一段区间有多少这个颜色,可以枚举每种另外一个颜色,然后用 \(O(这个颜色大小)\) 的复杂度算出他在两边或者在中间的贡献。复杂度 \(O(n \sqrt{n})\)
于是我们只剩下了两两都是 \(\le \sqrt{n}\) 的。
考虑我们可以暴力枚举选的区间左右端点了,因为如果两边都有数,两边外面都是这个颜色一定不劣。考虑扫描线,枚举选的右端点,然后暴力枚举这个颜色前面所有出现的位置当左端点。
然后我们要快速算这之间的众数,似乎不太能做,但其实我们只用考虑出现次数 \(\le \sqrt{n}\) 的颜色就行,答案也肯定不超过根号。
于是我们可以开个数组 \(S_i\) 表示现以 \(i\) 为左端点的众数(只管次数小于根号的),考虑更新的时候也是暴力枚举他的之前所有颜色的位置 \(j\),考虑之间有 \(k\) 个这个颜色的,需要做的就是对 \(S_{1 \sim j}\) 对 \(k\) 进行 \(\text{chkMax}\),我们发现 \(S\) 数组是不增的,并且值域不超过根号,那其实能 \(\text{chkMax}\) 就往前跳,不能就停就好了,考虑每次 chkMax 至少使 \(S\) 总和 \(+1\),而最终 \(S\) 总和不会超过 \(n \sqrt {n}\),那么复杂度就是对的。
综上,因为两侧都达到了上届,所以分块界是合适的(这范围也不太可能有 \(\log\) 了。。
还要注意一些细节,例如两边可能只有一边有这个颜色,还得正反扫一遍?
总复杂度 \(O(n \sqrt {n})\)
// Skyqwq #include <bits/stdc++.h> #define pb push_back #define fi first #define se second #define mp make_pair using namespace std; typedef pair<int, int> PII; typedef long long LL; template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; } template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; } template <typename T> void inline read(T &x) { int f = 1; x = 0; char s = getchar(); while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); } while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar(); x *= f; } const int N = 2e5 + 5; int n, a[N], b[N], len, d[N], t, ans, w[N], B, s[N], pos[N], L[N], R[N], loc[N], cnt[N]; int S[N]; int inline get(int x) { return lower_bound(b + 1, b + 1 + len, x) - b; } vector<int> c[N]; void inline pr() { for (int i = 1; i <= n; i++) b[i] = a[i]; len = n; sort(b + 1, b + 1 + len); len = unique(b + 1, b + 1 + len) - b - 1; for (int i = 1; i <= len; i++) w[i] = 0; for (int i = 1; i <= n; i++) a[i] = get(a[i]); for (int i = 1; i <= n; i++) loc[i] = c[a[i]].size(), c[a[i]].pb(i); B = sqrt(n); // B = 1; for (int i = 1; i <= n; i++) { pos[i] = (i - 1) / B + 1; if (!L[pos[i]]) L[pos[i]] = i; R[pos[i]] = i; } } // x 在两边,x 前缀和 s,y 在中间 void inline wk1(int x, int y) { int v = -1e9, ret = 0; for (int A = 0; A < (int)c[y].size(); A++) { chkMax(v, -A + s[c[y][A] - 1]); chkMax(ret, v + A + 1 + s[n] - s[c[y][A]]); } chkMax(w[x], ret); } // y 在两边,x 在中间,x 前缀和 s void inline wk2(int x, int y) { int v = -1e9, ret = 0; for (int A = 0; A < (int)c[y].size(); A++) { chkMax(ret, v + s[c[y][A] - 1] + (int)c[y].size() - A + 1); chkMax(v, A + -s[c[y][A]]); chkMax(ret, s[c[y][A] - 1] + (int)c[y].size() - A); chkMax(ret, A + 1 + s[n] - s[c[y][A]]); } chkMax(w[y], ret); } void inline big() { for (int i = 1; i <= len; i++) { if ((int)c[i].size() > B) { for (int j = 1; j <= n; j++) s[j] = 0; for (int v: c[i]) s[v] = 1; for (int j = 1; j <= n; j++) s[j] += s[j - 1]; for (int j = 1; j <= len; j++) if (i != j) wk1(i, j); for (int j = 1; j <= len; j++) if ((int)c[j].size() <= B) wk2(i, j); } } } void inline upd(int x, int y) { while (x && S[x] < y) { S[x] = y; --x; } } void inline small() { for (int i = 1; i <= n; i++) { if ((int)c[a[i]].size() <= B) { // do calc int val = (int)c[a[i]].size() - loc[i] + S[1]; for (int j = loc[i] - 1; j >= 0; j--) { int p = c[a[i]][j]; chkMax(val, j + 1 + (int)c[a[i]].size() - loc[i] + S[p + 1]); } chkMax(w[a[i]], val); // do upd for (int j = loc[i]; j >= 0; j--) upd(c[a[i]][j], loc[i] - j + 1); } } int mx = 0; for (int i = n; i; i--) { chkMax(w[a[i]], mx + loc[i] + 1); cnt[a[i]]++; chkMax(mx, cnt[a[i]]); } } void inline out() { ans = 0; for (int i = 1; i <= len; i++) chkMax(ans, w[i]); for (int i = 1; i <= len; i++) if (w[i] == ans) d[++t] = b[i]; printf("%d\n", ans); sort(d + 1, d + 1 + t); t = unique(d + 1, d + 1 + t) - d - 1; for (int i = 1; i <= t; i++) printf("%d\n", d[i]); } void inline clr() { for (int i = 1; i <= len; i++) c[i].clear(); for (int i = 1; i <= n; i++) cnt[i] = 0, S[i] = 0, pos[i] = L[i] = R[i] = w[i] = 0; ans = 0; t = 0; len = 0; } int main() { //freopen("mode.in", "r", stdin); //freopen("mode.out", "w", stdout); int T; read(T); while (T--) { read(n); for (int i = 1; i <= n; i++) read(a[i]); pr(); big(); small(); out(); clr(); } return 0; }
这篇关于ZJOI 2022的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)