当前位置: 首页 > news >正文

2025 代码源 CSP-S 模拟赛复盘

Day 16

T1 双重心

分类讨论一下:

  1. 是原树的双重心之一,考虑把这条边割掉,接到另一个连通块的任意一个点上都是可行的。
  2. 不割掉原树上的双重心的边,两侧的连通块内的的任意一条边可以断开,连通块内相互连边就行。
  3. 考虑一条边成为新的双中心之间的边,设这条边为 \((u,v)\)\(u\) 为深度较深的点,如果 \(siz_u > n / 2\),那么就是要在 \(u\) 的子树内割下一块大小等于 \(siz_u - n / 2\) 的子树,可以直接开一个桶来计算,在进入子树 \(u\) 时记录一下大小,离开子树时再记录一下当前的大小,做差就可以得出。如果 \(siz_u < n / 2\),那么就是要在子树外选大小为 \(n/2-siz_u\) 大小的部分割掉,这个部分就是全局大小等于 \(n/2-siz_u\) 的子树减去 \(u\) 子树内大小等于 \(n/2-siz_u\) 的子树个数,这两个部分非常好算,此时我们发现在 \(v\) 到根的这条链上子树大小满足要求的点是不能取的,需要减掉,然而有一些点和子树 \(u\) 以外的点可以组成大小可以满足条件,要将这一部分减去,其实可以开一个桶记录一个点到根的路径上的点的子树大小,在 dfs 离开一个点时回溯,将他减去就可以了。此时的答案就是 全局的-子树内的-链上不符合条件的+链上新增的。

分别计算这些部分即可,1、2 可以一起算,第三个另外算。

CODE

const int mod = 998244353, inf = 0x3f3f3f3f;
const int MAXN = 5e6 + 10;
int n, type, siz[MAXN], sz[MAXN], f[MAXN];
vector<int> g[MAXN], v;
vector<pair<int, int>> p;
ll buc[MAXN], cnt[MAXN], ins[MAXN], ous[MAXN];
ll ans[MAXN];inline int grnd(int &s) {s ^= s << 13;s ^= s >> 17;s ^= s << 5;if (s < 0) s = -s;return s;
}void dfs0(int x, int fa) 
{siz[x] = 1, f[x] = fa;int wt = 0;for (auto y : g[x]){if (y != fa) {dfs0(y, x);siz[x] += siz[y];wt = max(wt, siz[y]);}}wt = max(wt, n - siz[x]);if (wt <= n / 2) v.push_back(x);
}void dfs1(int x, int fa) 
{int tmp = 0;if (siz[x] > n / 2) tmp = cnt[siz[x] - n / 2];else if (n / 2 > siz[x]) tmp = cnt[n / 2 - siz[x]];cnt[siz[x]]++;for (auto y : g[x]){if (y != fa)dfs1(y, x);}if (siz[x] > n / 2) {ll num = cnt[siz[x] - n / 2] - tmp;ans[x] += num * (siz[x] - n / 2) * (n - siz[x]);ans[f[x]] += num * (siz[x] - n / 2) * (n - siz[x]);}else if (siz[x] < n / 2) ins[x] = cnt[n / 2 - siz[x]] - tmp;
}void dfs2(int x, int fa)
{if (siz[x] < n / 2){ll num = cnt[n / 2 - siz[x]] - ins[x] - buc[n / 2 - siz[x]] + ous[n / 2 - siz[x]];ans[x] += num * (n / 2 - siz[x]) * siz[x];ans[f[x]] += num * (n / 2 - siz[x]) * siz[x];}buc[siz[x]]++;for (auto y : g[x]){if (y != fa){ous[n - siz[y]]++;dfs2(y, x);ous[n - siz[y]]--;}}buc[siz[x]]--;
}void dfs3(int u, int fa) {sz[u] = 1;for (auto v : g[u]) {if (v != fa) {dfs3(v, u);sz[u] += sz[v];}}
}int main()
{n = read(), type = read();if (n & 1){cout << 0 << '\n';return 0;}if (type == 1) {for (int i = 1, x, y; i < n; i++) {x = read(), y = read();g[x].push_back(y); g[y].push_back(x);p.push_back(mp(x, y));}}else {int a = read(), b = read(); for (int i = 1; i < n; i++) {p.push_back(make_pair(max(1, i - grnd(b) % a), i + 1));}for (auto edge : p) {int x = edge.first, y = edge.second;g[x].push_back(y); g[y].push_back(x);}}dfs0(1, 0);if (v.size() == 2){for (int i = 1; i <= n; i++) ans[i] += n / 2;memset(sz, 0, (n + 1) << 2); dfs3(v[0], v[1]);for (int i = 1; i <= n; i++) {if (sz[i] < n / 2 && sz[i] > 0) {	ans[v[0]] += (ll)sz[i] * (n / 2 - sz[i]);ans[v[1]] += (ll)sz[i] * (n / 2 - sz[i]);}}memset(sz, 0, (n + 1) << 2); dfs3(v[1], v[0]);for (int i = 1; i <= n; i++) {if (sz[i] < n / 2 && sz[i] > 0) {ans[v[0]] += (ll)sz[i] * (n / 2 - sz[i]);ans[v[1]] += (ll)sz[i] * (n / 2 - sz[i]);}}}dfs1(1, 0);dfs2(1, 0);ll res = 0, P = 1;for (int i = 1; i <= n; i++) {// cout << i << " " << ans[i] << '\n';res = (res + (ans[i] % mod) * P % mod) % mod;P = (P * 2333) % mod;}cout << res << '\n';return 0;
}

T2 线段树

弱化版:E - Segment-Tree Optimization 的做法:

首先可以发现一个性质:如果所有询问至多扫到某一层,那么这一层中的区间对于每个询问要么包含,要么相离。所以,对于询问 \([l,r]\),这一层必然存在一个 \(l−1→l\) 的断点和一个 \(r→r+1\) 的断点。区间 \([1,n]\) 被所有断点切割后形成的区间个数就是这一层的结点个数。既然我们知道了结点个数,由于第 \(x\) 层至多有 \(2x\) 个结点,那么我们也能够知道它在哪一层。接下来考虑最小化 \(c\)。对于这一层的所有区间,有两种决策:

  1. 把这个区间拉到上一层,那么就不会造成贡献。
  2. 把这个区间和一个相邻区间合并,然后放到上一层。

对于决策 2 的贡献,我们这样考虑:如果这两个区间是 \([l,mid)\)\([mid,r]\),合并后的区间就是 \([l,r]\)。根据题意,所有包含 \([l,r]\) 或者跟 \([l,r]\) 相离的区间都不会造成贡献。那么造成贡献的就是与 \([l,r]\) 相交或者被 \([l,r]\) 包含的区间,这些区间会造成 2 的贡献。根据之前的断点可以发现一个小性质:这些造成贡献的区间要么右端点是 \(mid−1\),要么左端点是 \(mid\),且满足条件的区间必然会造成贡献。可以维护以某个下标为左端点或者右端点的区间个数来快速求出贡献。唯一的限制是上一层的区间个数不能超过 \(2d−1\)。设 \(fi,j\) 表示考虑到这一层从左往右第 \(i\) 个区间,且上一层当前有 \(j\) 个区间的贡献最小值。按照决策 DP 即可。时间复杂度 \({O(n2+q)}\)

Day 17

A. 优势种类

我们不难发现性质:只要在任意一个长度为 3 的区间存在绝对众数,那么一定可以传播到整个区间,那么只需要将

http://www.hskmm.com/?act=detail&tid=35477

相关文章:

  • 2025.10.21——1绿
  • 【JavaScript-基础】map、forEach、for、for in、for of等的区别
  • dotnet 利用 Windows 注册表实现开机自动启动
  • 使用uWSGI和Nginx部署深度学习模型指南
  • 帮我回答这些问题
  • Python 类属性的应用场景
  • 为什么很多人分不清关联和聚合?
  • 机器学习商业应用实战指南
  • 在线签名工具,手写签名保存为png图片,用于生成电子签名用于word文档等
  • 什么情况下,有必要将属性设为类属性而非实例属性?
  • 在线签名工具,保存为png图片,用于生成电子签名用于word文档等
  • 玄机——第五章 Windows 实战-evtx 文件分析
  • CityRefer:城市规模点云数据上的地理感知 3D 视觉接地数据集 - MKT
  • SensatUrban语义分割数据集SensatUrban - MKT
  • 推荐算法参考资料
  • LLM学习笔记DAY8
  • 软件工程第二次团队作业——构建一个智能体
  • VoxelNeXt 用于 3D 对象检测和跟踪的完全稀疏 VoxelNet(CVPR 2023) - MKT
  • CityNav:包含地理信息的语言目标空中导航数据集 - MKT
  • Grounded-SAM 使用文本提示检测和分割所有内容 - MKT
  • Linux权限维持-后门
  • 视觉和语言 国防科大清华城市空间无人机导航推理!GeoNav:赋予多模态大模型地理空间推理能力,实现语言指令导向的空中目标导航 - MKT
  • mysql数据库查询参考
  • Python理论题目集
  • 基于yakit的dvwa靶场暴力破解和代码执行漏洞
  • 视觉和语言-港科大 NMPC 控制下的高效自主导航!SkyVLN:城市环境无人机视觉语言导航与非线性模型预测控制 - MKT
  • 北航高低无人机协同导航方案:高空掌全局+低空查细节 - MKT
  • sourcetree 克隆项目仓库地址,输入账号密码后提示:这是一个无效的源路径/URL
  • 软工第三次作业-结对作业
  • 20251020 之所思 - 人生如梦