CCF GESP 2026年9月认证 C++ 6级
所有 GESP 真题，手机上也能刷 · 自动判分 · 错题自动进错题本 扫码去刷题目描述
给定 $n$ 个整数构成的数组 $A=[a_{1},a_{2},…,a_{n}]$。
你需要将数组 $A$ 划分为若干非空连续子段。对于划分得到的某个子段，它的偏差值定义为子段内整数和的平方。划分方案的偏差值定义为所有子段偏差值之和。
你需要最小化划分方案的偏差值。
形式化地，你可以将 $A$ 划分为若干非空连续子段 $A_{1},A_{2},…,A_{k}$，使得 $A=A_{1}+A_{2}+…+A_{k}$，这里的 $+$ 代表数组的连接。对于 $1≤i≤k$，设数组 $A_{i}=[a_{1}^{(i)},…,a_{m_i}^{(i)}]$ 包含 $m_{i}$ 个整数。你需要最小化 $\sum_{i=1}^k(\sum_{j=1}^{m_i}a_{j}^{(i)})^2$。
输入格式
第一行，一个正整数 $n$，表示数组 $A$ 的长度。
第二行，$n$ 个整数 $a_{1},a_{2},…,a_{n}$，表示数组 $A$。
输出格式
一行，一个整数，表示划分方案偏差值的最小值。
样例说明
样例 1
4
1 2 -3 46样例 2
6
-1 -1 4 -5 -1 40数据范围
对于 40% 的测试点，保证 $0≤a_{i}≤50$。
对于所有测试点，保证 $1≤n≤2000$，$−100≤a_{i}≤100$。
题目描述
老师有一棵有 $n$ 个结点的树，结点依次以 $1,2,…,n$ 编号。
老师想将这棵树作为奖品分给两位同学。具体而言，老师会选择一条边并从树上删去它，从而将这棵树分为两个连通块。两位同学分别可以得到其中一个连通块。
如果有同学拿到的连通块结点数明显小于另一位同学，那么这位同学会不太高兴。为了避免这种情况出现，老师想知道两个连通块结点数之差的绝对值最小是多少。
输入格式
第一行，一个正整数 $n$，表示结点数量。
接下来 $n−1$ 行，每行两个正整数 $u_{i},v_{i}$，表示一条连接结点 $u_{i}$ 和结点 $v_{i}$ 的边。
输出格式
输出一行，一个整数，表示答案。
样例说明
样例 1
4
1 2
2 3
3 40样例 2
6
1 2
1 3
1 4
1 5
5 62数据范围
对于 40% 的测试点，保证 $2≤n≤500$。
对于所有测试点，保证 $2≤n≤2×10^{4}$。
小程序开心码未来
微信扫码，随时随地练 GESP 真题
- 手机刷题 · 自动判分，错题自动归档到错题本
- 绑定网站账号后，查看答案解析等权限自动同步
微信扫一扫