抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

前言

这场没来打,但看上去很不好打的样子。

D1T1 格雷码

Description

Solution

直接按照题意递归模拟即可,注意 2^{64} 超出了 long long 的范围,需要特判。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <cstdio>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define DEC(i, a, b) for (int i = a; i >= b; --i)

typedef unsigned long long ull;

ull tmp[65];

void work(ull n, ull k)
{
if (n == 1) return (void)printf("%d", k);
if (k >= (1llu << (n - 1)))
printf("1"), work(n - 1, tmp[n] - k);
else printf("0"), work(n - 1, k);
return;
}

int main()
{
FOR(i, 1, 63) tmp[i] = (1llu << i) - 1;
tmp[64] = (ull)(-1);
ull n, k;
scanf("%llu %llu", &n, &k);
work(n, k);
return 0;
}

D1T2 括号树

Description

给定一棵树,每个节点上有一个括号 (),定义 s_i 为根到 i 节点的简单路径上的括号组成的字符串,求出其连续子段中括号序列的数量 k_i ,输出

\operatorname{xor}_{i = 1}^n (i\times k_i)

Solution

经典的括号匹配模型上了树。

让我们从根往下一步步走,并按照之前常用的括号匹配问题的套路把沿途的左括号压进栈里面。现在考虑一个点 u 是怎么贡献出合法的括号序列的,分 u 上为 () 两种情况讨论:

u 括号为 ( 的时候,不难发现 u 的答案肯定是从 fa_u 继承下来的,因为 ( 不可能再贡献出多的合法的序列,同时使这个括号入栈。

u 括号为 ) 的时候,让我们思考一下这个右括号加进来之后会有什么影响。首先如果栈里面还有括号,说明它可以匹配到一个合法的左括号,记为 x ,先退栈。然后这个 [x,u] 很明显会对之前的括号序列产生贡献。假设 x 之前有连续的 k 段括号序列,那么不难发现 u 的这个 ) 就会产生 k + 1 的贡献。把这个 k 在代码里面用 lst[u] 体现,就大致可以写出一个框架了。

但是要注意的是回溯问题。这个栈我们是进行动态调整的,所以如果在 u 的时候一开始退了栈那么回溯的时候就要把这个元素补回去,如果一开始有元素入了栈那么回溯的时候就要把这个元素退掉,否则就会对 u 的姐妹节点产生错误的贡献。

那么这题就做完了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <cstdio>
#include <cstring>

typedef long long ll;
const int maxn = 5e5 + 5;
char str[maxn];
int n, fa[maxn];
int head[maxn], to[maxn], nxt[maxn], cnt;
int s[maxn], top;
ll ans, lst[maxn], sum[maxn];

void add(int u, int v)
{
to[++cnt] = v;
nxt[cnt] = head[u];
head[u] = cnt;
return;
}

void dfs(int u)
{
int tmp = 0;
if (str[u] == ')' && top) lst[u] = lst[fa[tmp = s[top--]]] + 1;
else if (str[u] == '(') s[++top] = u;
sum[u] = sum[fa[u]] + lst[u];
for (int i = head[u]; i; i = nxt[i]) dfs(to[i]);
if (tmp) s[++top] = tmp;
else if (top) --top;
return;
}

int main()
{
scanf("%d", &n);
scanf("%s", str + 1);
for (int i = 2; i <= n; i++)
{
scanf("%d", fa + i);
add(fa[i], i);
}
dfs(1);
for (ll i = 1; i <= n; i++)
ans ^= (sum[i] * i);
printf("%lld\n", ans);
return 0;
}


D1T3 树上的数

Description

给定一棵大小为 n 的树,节点从 1 n 编号,每个节点上有一个数字,这些数字构成一个 1 n 的排列。

进行 n - 1 次删边操作,每次删边都交换两个节点上的数字。最后所有边都被删掉,按照数字从小到大得到一个节点编号的排列 P ,最小化 P 的字典序。

Solution

10pts Brute Force

O(n!) 枚举删边的顺序,然后暴力判断。

代码就不写了。

25pts Chain

首先不难发现这肯定是一个字典序贪心。我们可以依次从小到大依次考虑每个数字最后的点最小可以到哪里。然后就是想这个数字的移动有什么性质了。

假设我们要把数字 x 从点 a 移到点 b ,那么不难发现以下的条件需要得到满足:

  • 首先 a b 要联通
  • 对于出发点 a ,我们必须保证 x 最先走的边最先被删去。因为如果其他边先被删的话 x 就跑到其他地方去了。
  • 对于中间的任意点 u ,设入边为 i x 要走的出边为 j ,那么 j 必须紧挨着 i 之后被删,原因同理。
  • 对于结束点 b ,我们必须保证 x 进来的入边最后被删去,原因同理。

不难发现,这是一系列关于选边顺序的条件。

而对于链这种点度至多为 2 的树,每个点无非就是两种选择:左边的边先删还是右边的边先删,对于这个性质打个标记,然后 O(n) 从小到大枚举数字,然后就让这个数字往左/往右一直走,找到合法的最优解然后打上标记就可以了。加上之前的暴力可以获得 35 分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <cstdio>
#include <cctype>
#include <cstring>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define DEC(i, a, b) for (int i = a; i >= b; --i)
#define GO(u) for (int i = head[u], v = to[i]; i; i = nxt[i], v = to[i])
#define clr(__x) memset(__x, 0, sizeof __x)

const int maxn = 2e3 + 5;

int read()
{
int s = 0, x = 0;
char c = getchar();
while (!isdigit(c))
x |= (c == '-'), c = getchar();
while (isdigit(c))
s = s * 10 + c - '0', c = getchar();
return x ? -s : s;
}

inline int min(int a, int b) {return a < b ? a : b;}

int n, head[maxn], to[maxn << 1], nxt[maxn << 1], cnte, deg[maxn];
int p[maxn], tag[maxn];

void add(int u, int v)
{
++deg[v];
to[++cnte] = v;
nxt[cnte] = head[u];
head[u] = cnte;
return;
}

void init()
{
n = read(), cnte = 0;
FOR(i, 1, n) p[i] = read(), head[i] = deg[i] = tag[i] = 0;
FOR(i, 1, n - 1)
{
int u = read(), v = read();
add(u, v), add(v, u);
}
return;
}

int pos[maxn], id[maxn], cnt;

void dfs(int u, int fa)
{
id[++cnt] = u, pos[u] = cnt;
GO(u) if (v != fa) dfs(v, u);
return;
}

int main()
{
int T = read();
while (T--)
{
init();
if (n == 1)
{
printf("1\n");
continue;
}
int root = 0;
FOR(i, 1, n) if (deg[i] == 1) root = i;
cnt = 0;
dfs(root, 0);
FOR(i, 1, n)
{
int x = p[i], b = pos[x];
int to = n + 1;
if (tag[b] != 1)
{
FOR(j, b + 1, n)
{
if (tag[j] != 1) to = min(to, id[j]);
if (tag[j] == 2) break;
}
}
if (tag[b] != 2)
{
DEC(j, b - 1, 1)
{
if (tag[j] != 2) to = min(to, id[j]);
if (tag[j] == 1) break;
}
}
if (pos[to] > b)
{
FOR(j, b + 1, pos[to] - 1) tag[j] = 1;
tag[b] = tag[pos[to]] = 2;
}
else
{
FOR(j, pos[to] + 1, b - 1) tag[j] = 2;
tag[b] = tag[pos[to]] = 1;
}
tag[1] = tag[n] = 0;
printf("%d ", to);
}
puts("");
}
return 0;
}

25pts Star

然后考虑菊花图的部分分。我们还是考虑一个数字 x a b 的情况。

  • 如果 a b 均不为根,那么 x 经过的点即为 a\to r\to b ,其中 r 为根。假设这两条边分别为 i j ,那么有一个很显然的结论就是 j 必须紧接着 i 后面删掉。
  • 如果 a 为根,那么这条边必须是第一个被删掉的。
  • 如果 b 为根,那么这条边必须是最后一个被删掉的。

这样子一列出来就可以看得出,这些删边顺序是可以用一个双向链表来进行维护的。而且为了这个链表中途不接出环来,我们需要一个并查集来维护连通性。时间复杂度 O(n^2\alpha(n))

细节比较繁冗,注意实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <cstdio>
#include <cctype>
#include <cstring>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define DEC(i, a, b) for (int i = a; i >= b; --i)
#define GO(u) for (int i = head[u], v = to[i]; i; i = nxt[i], v = to[i])
#define clr(__x) memset(__x, 0, sizeof __x)

const int maxn = 2e3 + 5;

int read()
{
int s = 0, x = 0;
char c = getchar();
while (!isdigit(c))
x |= (c == '-'), c = getchar();
while (isdigit(c))
s = s * 10 + c - '0', c = getchar();
return x ? -s : s;
}

inline int min(int a, int b) {return a < b ? a : b;}

int n, head[maxn], to[maxn << 1], nxt[maxn << 1], cnte, deg[maxn];
int p[maxn], pre[maxn], suf[maxn];

int anc[maxn];

inline int find(int u) {return u == anc[u] ? u : anc[u] = find(anc[u]);}

void add(int u, int v)
{
++deg[v];
to[++cnte] = v;
nxt[cnte] = head[u];
head[u] = cnte;
return;
}

void init()
{
n = read(), cnte = 0;
FOR(i, 1, n) p[i] = read(), head[i] = deg[i] = 0;
FOR(i, 1, n + 1) anc[i] = i, pre[i] = suf[i] = 0;
FOR(i, 1, n - 1)
{
int u = read(), v = read();
add(u, v), add(v, u);
}
return;
}

int main()
{
int T = read();
while (T--)
{
init();
if (n == 1)
{
printf("1\n");
continue;
}
int root;
FOR(i, 1, n) if (deg[i] == n - 1) root = i;
FOR(i, 1, n)
{
int from = p[i];
FOR(to, 1, n)
{
bool ok = 1;
if (from != root && to != root)
{
if (pre[to] || suf[from]) ok = 0;
if (find(from) == find(to) && i < n) ok = 0;
if (ok) pre[to] = from, suf[from] = to, anc[find(from)] = find(to);
}
else if (from == root && to != root)
{
if (pre[to] || suf[n + 1]) ok = 0;
if (find(to) == find(n + 1)) ok = 0;
if (ok) pre[to] = n + 1, suf[n + 1] = to, anc[find(to)] = find(n + 1);
}
else if (from != root && to == root)
{
if (suf[from] || pre[n + 1]) ok = 0;
if (find(from) == find(n + 1)) ok = 0;
if (ok) suf[from] = n + 1, pre[n + 1] = from, anc[find(from)] = find(n + 1);
}
else if (from == to && from == root) ok = 0;
if (ok)
{
printf("%d ", to);
break;
}
}
}
puts("");
}
return 0;
}

40pts Normal Tree

最后拔刀抽向正解。通过上面的分析我们已经知道我们需要解决的无非是对于一个点而言:

  • 某边最先被删
  • 某边挨着某边被删
  • 某边最后被删

依次枚举,问这个约束是否有解。

我们可以依旧像之前那样,但现在我们需要对每个节点开一个链表+并查集,然后就考虑这个点的约束能否满足。实现就变得复杂了起来。

具体地,每次考虑一个数字能到达的最小编号的点。就在从这个数字开始 dfs 的过程中依次判断。判断的过程跟之前的其实也类似:

  • 对于出发点,其出发边必须是第一个被删掉的
  • 对于中间的点, j 必须紧挨着 i 被删掉
  • 对于结束点,入边必须是最后一个被删掉的

但是还有需要补充的点:就是删边的这个链表的长度必须等于点度,不能出现“提前自闭”的情况,否则有一些边就不会被删了。所以

  • 在处理出发点时,出发边的后面如果接有结束边,注意其不能提前自闭(体现在代码里面就是只能有一条边没有删去)
  • 在处理结束点时,结束边的前面如果接有出发边,注意其不能提前自闭
  • 在中间点时,如果要把 i j 连接,且 i 与出发边相连, j 与结束边相连,则同样注意不能自闭(体现在代码里面就是只能有两条边没有删去)

我们来总结一下这个比较复杂的算法流程:

  • 1 n 枚举每个数字
    • 从该数字一开始的位置开始 dfs
      • 结束点显然不可能在起始点
      • 对于已经到达的 u ,判断能否成为结束点,能的话存进临时答案
      • u 枚举出边,判断这条出边是否合法
        • 作为出发边
          • 首先出发边前面不能接其他边
          • 出发边后面接结束边的话不能提前自闭
        • 作为中间边
          • 首先初始边不能接在结束边之后
          • i j 不能已经连起来
          • i 后面不能连边, j 前面不能连边
          • i j 不能提前自闭
    • 找到结束点之后,再次 dfs,更新每个节点对应的链表和并查集,同时删边
    • 输出结束点编号

然后就是写代码了。这个算法的复杂度是 O(n^2\alpha(n)) ,虽然比较慢但是写着还算方便,代码内有详细注释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <cstdio>
#include <cctype>
#include <cstring>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define DEC(i, a, b) for (int i = a; i >= b; --i)
#define GO(u) for (int i = head[u], v = to[i]; i; i = nxt[i], v = to[i])

const int maxn = 2e3 + 5;

int read()
{
int s = 0, x = 0;
char c = getchar();
while (!isdigit(c))
x |= (c == '-'), c = getchar();
while (isdigit(c))
s = s * 10 + c - '0', c = getchar();
return x ? -s : s;
}

inline int min(int a, int b) {return a < b ? a : b;}

int n, head[maxn], to[maxn << 1], nxt[maxn << 1], cnte, deg[maxn];
int p[maxn];

void add(int u, int v)
{
++deg[v];
to[++cnte] = v;
nxt[cnte] = head[u];
head[u] = cnte;
return;
}

struct node
{
int fi, la;
int pre[maxn], suf[maxn], anc[maxn];
void clear()
{
fi = la = 0;
FOR(i, 1, n) pre[i] = suf[i] = anc[i] = 0, anc[i] = i;
}
int find(int u) {return anc[u] == u ? u : anc[u] = find(anc[u]);}
bool ask(int u, int v) {return find(u) == find(v);}
void uni(int u, int v) {if (!ask(u, v)) anc[find(v)] = find(u);}
} t[maxn];

void init()
{
n = read();
FOR(i, 1, n) p[i] = read(), head[i] = deg[i] = 0, t[i].clear();
cnte = 1;
FOR(i, 1, n - 1)
{
int u = read(), v = read();
add(u, v), add(v, u);
}
}

int dfs(int u, int fa)
{
int res = n + 1;
if (fa != n + 1 && !t[u].la && !t[u].suf[fa] && !(t[u].fi && deg[u] > 1 && t[u].ask(fa, t[u].fi))) res = u;
//判断作为结束点。首先结束边不能确定过,而且 fa 不能有后继边
//后面一句是判断提前自闭的情况,因为如果确定它为结束边,且它与起始边相连,则可能中间会有没有考虑到的边
GO(u)
{
if (v == fa) continue;
if (fa == n + 1)//u 为起始点
{
if (!t[u].fi)//首先初始边不能已经指定过
{
if (t[u].pre[v]) continue;//v边也不能有前驱
if (t[u].la && deg[u] > 1 && t[u].ask(v, t[u].la)) continue;//提前自闭的情况
res = min(res, dfs(v, u));
}
else continue;
}
else
{
if (t[u].fi == v || t[u].la == fa || t[u].ask(v, fa)) continue;//初始边肯定不能接在结束边后,而且这两条边不能已经连起来
if (t[u].pre[v] || t[u].suf[fa]) continue;//如果不能接起来
if (t[u].fi && t[u].la && deg[u] > 2 && t[u].ask(t[u].fi, fa) && t[u].ask(t[u].la, v)) continue;//两者接起来之后不能提前自闭
res = min(res, dfs(v, u));
}
}
return res;
}

bool update(int u, int fa, int dest)
{
if (u == dest)
{
t[u].la = fa;
return true;
}
GO(u)
{
if (v == fa) continue;
if (update(v, u, dest))
{
if (fa == n + 1)
t[u].fi = v;
else
t[u].uni(fa, v), t[u].suf[fa] = v, t[u].pre[v] = fa, --deg[u];
return true;
}
}
return false;
}

int main()
{
int T = read();
while (T--)
{
init();
if (n == 1)
{
printf("1\n");
continue;
}
FOR(i, 1, n)
{
int ans = dfs(p[i], n + 1);
update(p[i], n + 1, ans);
printf("%d ", ans);
}
puts("");
}
return 0;
}

D2T1 Emiya 家的饭

Description

Emiya 会 n 种烹饪方法和处理 m 种主要食材。Emiya 做菜一定会用一种烹饪方法和一种主要食材,具体地,用第 i 种方法处理 j 号主要食材可以做出 a_{i,j} 种菜。现在他要做 k 道菜,需要满足:

  • k\ge1
  • 每道菜的烹饪方法互不相同
  • 每种主要食材最多使用 \lfloor k/2\rfloor

求所有满足要求的做菜方案数。

Solution

Analysis

注意到 k 至少为 2,然后第二个要求非常好处理,而第三个要求比较困难。 正难则反,先求出一共能做出多少种搭配,然后减去不合法的方案即可。由加法原理和乘法原理知一共能做出来的即为 \displaystyle\prod_{i=1}^n(\sum_{j=1}^ma_{i,j}+1)-1 。(减去的 1 为什么都不做) 接下来就可以考虑怎么处理第三个要求了。

84pts O(n^3m)

然后,我们可以发现不满足要求的食材有且仅有一样(显然),所以可以枚举这个不满足要求的食材,然后进行 dp 求解。 设 f_{i,j,k} 为正在处理第 p 样食材,考虑前 i 个方法,使用其余食材做了 j 道菜,用第 p 样食材做了 k 道菜的方案数。 则由乘法原理和加法原理得到

f_{i,j,k}=f_{i-1,j,k}+f_{i-1,j-1,k}\times (s_i-a_{i,p})+f_{i-1,j,k-1}\times a_{i,p}

其中 s_i=\sum_j a_{i,j} 然后只需要枚举 j k 并减掉不合要求的方案数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <cstdio>
#include <cctype>
#include <cstring>

//...

ll a[maxn][maxm], s[maxn]; //n 方法,m食材
ll ans = 1;
ll f[maxn][maxn][maxn]; //考虑到第 a 种食材,前 i 种方法,其余做了 j 道菜,剩下 k 道是用当前食材做的

int main()
{
n = read(), m = read();
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
a[i][j] = read(), s[i] = (s[i] + a[i][j]) % mod;
ans = ans * (s[i] + 1) % mod;
}
ans = (ans - 1ll) % mod; //先减掉全部选的方案
for (int gg = 1; gg <= m; ++gg) //枚举每一种食材
{
memset(f, 0, sizeof f);
f[0][0][0] = 1; //边界
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= n; ++j)
for (int k = 0; k <= n; ++k)
{
if (j + k > i)
break;
ll tmp1 = 0, tmp2 = 0, tmp3 = 0;
tmp1 = f[i - 1][j][k];
if (j > 0) //防止访问负下标而 RE
tmp2 = f[i - 1][j - 1][k] * (s[i] - a[i][gg]) % mod;
if (k > 0) //防止访问负下标而 RE
tmp3 = f[i - 1][j][k - 1] * a[i][gg] % mod;
f[i][j][k] = tmp1 + tmp2 + tmp3;
f[i][j][k] %= mod;
}
ll tmp = 0; //记录不合法方案数
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= n; ++j)
{
ll tot = i + j;
if (tot > n)
break;
if (j <= (tot >> 1))
continue;
tmp += f[n][i][j], tmp %= mod;
}
ans = (ans - tmp + mod) % mod; //取模注意防止负数出现
}
printf("%lld\n", ans);
return 0;
}

100pts O(n^2m)

考虑优化之前 O(n^3m) 的 dp,注意到我们如果想要判断一个方案合不合法,根本就不需要知道 j k 具体的值,只需知道用 p 做出来的菜比其他的多多少,只要这个差量 \Delta>0 ,说明就是不合法的。 定义 f_{i,j} 为考虑前 i 种烹饪方法,用 p 做出来菜的数量比用其他菜做的数量多 j 道的方案数, j 可能为负,需要防止数组越界 转移方程:

f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\times a_{i,p}+f_{i-1,j+1}\times(s_i-a_{i,p})

最后不合法的方案数就是 \sum_{j>0}f_{n,j}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//...
#define f(i, j) f[i][j + maxn]

//...
ll a[maxn][maxm], s[maxn]; //n 方法,m食材
ll ans = 1;
ll f[maxn][maxn << 1];

int main()
{
n = read(), m = read();
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
a[i][j] = read(), s[i] = (s[i] + a[i][j]) % mod;
ans = ans * (s[i] + 1) % mod;
}
ans = (ans - 1ll) % mod;
for (int gg = 1; gg <= m; ++gg)
{
memset(f, 0, sizeof f);
f(0, 0) = 1;
for (int i = 1; i <= n; ++i)
for (int j = -i; j <= i; ++j)
f(i, j) = (f(i - 1, j) + f(i - 1, j - 1) * a[i][gg] + f(i - 1, j + 1) * (s[i] - a[i][gg])) % mod;
for (int j = 1; j <= n; ++j)
ans = (ans - f(n, j) + mod) % mod;
}
printf("%lld\n", ans);
return 0;
}

D2T2 划分

Description

给定 n \{a_i\} 。找到一些分界点 1\le k_1 < k_2 < k_3 < \cdots < k_p < n ,使得

\sum_{i = 1}^{k_1}a_i\le \sum_{i = k_1 + 1}^{k_2}a_i\le \cdots\le \sum_{i = k_p + 1}^n a_i

注意 p 可能为 0 k_0 = 0

请最小化

\left(\sum_{i = 1}^{k_1}a_i\right)^2 + \left(\sum_{i = k_1 + 1}^{k_2}a_i\right)^2 + \cdots + \left(\sum_{i = k_p + 1}^{n}a_i\right)^2

2\le n\le 4\times 10^7 ,答案不一定在 unsigned long long 范围内。

Solution

D2T3 树的重心

Description

评论




Blog content follows the [Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) License](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en)
本站总访问量为 访客数为
Use Volantis as theme