蓝桥杯|第十二届蓝桥杯 2021年省赛真题 (C/C++ 大学A组) 第一场蓝桥杯|c

蓝桥杯 2021年省赛真题 (C/C++ 大学A组）

#A 卡片
#B 直线
#C 货物摆放
#D 路径
#E 回路计数
#F 砝码称重
- 背包 DP
#G 异或数列
#H 左孩子右兄弟
#I 括号序列
#J 分果果

解析移步对应 Java组的题解。
#A 卡片本题总分： 5 5 5 分
【蓝桥杯|第十二届蓝桥杯 2021年省赛真题 (C/C++ 大学A组) 第一场】问题描述
??小蓝有很多数字卡片，每张卡片上都是数字0 0 0 到9 9 9。
??小蓝准备用这些卡片来拼一些数，他想从1 1 1 开始拼出正整数，每拼一个，就保存起来，卡片就不能用来拼其它数了。
??小蓝想知道自己能从1 1 1 拼到多少。
??例如，当小蓝有30 30 30 张卡片，其中0 0 0 到9 9 9 各3 3 3 张，则小蓝可以拼出1 1 1 到10 10 10，但是拼11 11 11 时卡片1 1 1 已经只有一张了，不够拼出11 11 11。
??现在小蓝手里有0 0 0 到9 9 9 的卡片各2021 2021 2021 张，共20210 20210 20210 张，请问小蓝可以从1 1 1 拼到多少？
??提示：建议使用计算机编程解决问题。
答案提交
??这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

3181

calcCode：

#include int n, ans, cnt; int main() { while (1) { n = ans; while (n) { if (n % 10 == 1) cnt++; n /= 10; } if (cnt < 2021) ans++; else break; } printf("%d", ans); }

#B 直线本题总分： 5 5 5 分
问题描述
??在平面直角坐标系中，两点可以确定一条直线。如果有多点在一条直线上，那么这些点中任意两点确定的直线是同一条。
??给定平面上2 × 3 2 × 3 2×3 个整点{ ( x , y ) ∣ 0 ≤ x < 2 , 0 ≤ y < 3 , x ∈ Z , y ∈ Z } \{(x, y)|0 ≤ x < 2, 0 ≤ y < 3, x ∈ Z, y ∈ Z\} {(x,y)∣0≤x<2,0≤y<3,x∈Z,y∈Z}，即横坐标是0 0 0 到1 1 1 (包含0 0 0 和1 1 1) 之间的整数、纵坐标是0 0 0 到2 2 2 (包含0 0 0 和2 2 2) 之间的整数的点。这些点一共确定了11 11 11 条不同的直线。
??给定平面上20 × 21 20 × 21 20×21 个整点{ ( x , y ) ∣ 0 ≤ x < 20 , 0 ≤ y < 21 , x ∈ Z , y ∈ Z } \{(x, y)|0 ≤ x < 20, 0 ≤ y < 21, x ∈ Z, y ∈ Z\} {(x,y)∣0≤x<20,0≤y<21,x∈Z,y∈Z}，即横坐标是0 0 0 到19 19 19 (包含0 0 0 和19 19 19) 之间的整数、纵坐标是0 0 0 到20 20 20 (包含0 0 0 和20 20 20) 之间的整数的点。请问这些点一共确定了多少条不同的直线。
答案提交
??这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

40257

calcCode：

#include const int X = 20, Y = 21; int linked[X][Y][X][Y], ans; int main() { for (int x1 = 0; x1 < X; x1++) for (int y1 = 0; y1 < Y; ++y1) { linked[x1][y1][x1][y1] = 1; for (int x2 = 0; x2 < X; ++x2) for (int y2 = 0; y2 < Y; ++y2) if (!linked[x1][y1][x2][y2]) { int x = x1, x_offset = x1 - x2; int y = y1, y_offset = y1 - y2; while (x >= 0 && x < X && y >= 0 && y < Y) x -= x_offset, y -= y_offset; for (x += x_offset, y += y_offset; x >= 0 && x < X && y >= 0 && y < Y; x += x_offset, y += y_offset) for (int xx = x, yy = y; xx >= 0 && xx < X && yy >= 0 && yy < Y; xx += x_offset, yy += y_offset) linked[x][y][xx][yy] = linked[xx][yy][x][y] = 1; ans++; } } printf("%d", ans); }

#C 货物摆放本题总分： 10 10 10 分
问题描述
??小蓝有一个超大的仓库，可以摆放很多货物。
??现在，小蓝有n n n 箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、宽、高。
??小蓝希望所有的货物最终摆成一个大的立方体。即在长、宽、高的方向上分别堆L 、 W 、 H L、W、H L、W、H 的货物，满足n = L × W × H n = L × W × H n=L×W×H。
??给定n n n，请问有多少种堆放货物的方案满足要求。
??例如，当n = 4 n = 4 n=4 时，有以下6 6 6 种方案： 1 × 1 × 4 1×1×4 1×1×4、 1 × 2 × 2 1×2×2 1×2×2、 1 × 4 × 1 1×4×1 1×4×1、 2 × 1 × 2 2×1×2 2×1×2、 2 × 2 × 1 2 × 2 × 1 2×2×1、 4 × 1 × 1 4 × 1 × 1 4×1×1。
??请问，当n = 2021041820210418 n = 2021041820210418 n=2021041820210418 （注意有16 16 16 位数字）时，总共有多少种方案？
??提示：建议使用计算机编程解决问题。
答案提交
??这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

2430

calcCode：

#include typedef long long ll; using namespace std; ll N = 2021041820210418, n = 1, ans; int main() { priority_queue exps; for (int i = 2; i <= sqrt(N); i++) if (N % i == 0) { int exp = 0; while (N % i == 0) N /= i, exp++; exps.push(exp); } if (N != 1) exps.push(1); for (int i = 2; exps.size(); i++) { bool flag = 1; for (int a = 2; a < i; ++a) if (i % a == 0) flag = 0; if (flag) n *= pow(i, exps.top()), exps.pop(); } for (ll i = 1; i <= n; i++) for (ll j = 1; j <= n; j++) if (n % (i * j) == 0) ans++; cout << ans << endl; }

#D 路径本题总分： 10 10 10 分
问题描述
??小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。
??小蓝的图由2021 2021 2021 个结点组成，依次编号1 1 1 至2021 2021 2021。对于两个不同的结点a , b a, b a,b，如果a a a 和b b b 的差的绝对值大于21 21 21，则两个结点之间没有边相连；如果a a a 和b b b 的差的绝对值小于等于21 21 21，则两个点之间有一条长度为a a a 和b b b 的最小公倍数的无向边相连。
??例如：结点1 1 1 和结点23 23 23 之间没有边相连；结点3 3 3 和结点24 24 24 之间有一条无向边，长度为24 24 24；结点15 15 15 和结点25 25 25 之间有一条无向边，长度为75 75 75。
??请计算，结点1 1 1 和结点2021 2021 2021 之间的最短路径长度是多少。
??提示：建议使用计算机编程解决问题。
答案提交
??这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

10266837

calcCode：

#include #include const int N = 2021; int map[N + 1][N + 1]; int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }int lcm(int a, int b) { return a * b / gcd(a, b); }int min(int a, int b) { return a < b ? a : b; }int main() { memset(&map, 0x3F, sizeof map); for (int u = 1; u <= N; u++) for (int v = min(N, u + 21); v > u; --v) map[u][v] = map[v][u] = lcm(u, v); for (int k = 1; k <= N; k++) for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) map[i][j] = min(map[i][j], map[i][k] + map[k][j]); printf("%d", map[1][N]); }

#E 回路计数本题总分： 15 15 15 分
问题描述
??蓝桥学院由21 21 21 栋教学楼组成，教学楼编号1 1 1 到21 21 21。对于两栋教学楼a a a 和b b b，当a a a 和b b b 互质时， a a a 和b b b 之间有一条走廊直接相连，两个方向皆可通行，否则没有直接连接的走廊。
??小蓝现在在第一栋教学楼，他想要访问每栋教学楼正好一次，最终回到第一栋教学楼（即走一条哈密尔顿回路），请问他有多少种不同的访问方案？两个访问方案不同是指存在某个i i i，小蓝在两个访问方法中访问完教学楼i i i 后访问了不同的教学楼。
??提示：建议使用计算机编程解决问题。
答案提交
??这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

881012367360

calcCode：

#include typedef long long ll; using namespace std; const int N = 21; ll cnt[N - 1][1 << N - 1]; vector graph[N]; ll dfs(int start, int status) { if (status == 0) return 1; if (cnt[start][status] >= 0) return cnt[start][status]; ll sum = 0; for (int v : graph[start]) if (status & (1 << v)) sum += dfs(v, status - (1 << v)); return cnt[start][status] = sum; }int gcd(int a, int b) { return b? gcd(b, a % b) : a; }int main() { for (int i = 2; i <= N; i++) for (int j = 2; j < i; j++) if (gcd(i, j) == 1) graph[i - 2].push_back(j - 2), graph[j - 2].push_back(i - 2); memset(cnt, 0xC3, sizeof cnt); ll sum = 0; for (int i = 0; i < N - 1; i++) sum += dfs(i, (1 << N - 1) - (1 << i) - 1); cout << sum << endl; }

#F 砝码称重时间限制:1.0 s 1.0\mathrm s 1.0s 内存限制:256.0 M B 256.0\mathrm{MB} 256.0MB 本题总分： 15 15 15 分
问题描述
??你有一架天平和N N N 个砝码，这N N N 个砝码重量依次是W 1 , W 2 , ? ? ? , W N W_1, W_2, · · · , W_N W1?,W2?,???,WN?。
??请你计算一共可以称出多少种不同的重量？
??注意砝码可以放在天平两边。
输入格式
??输入的第一行包含一个整数N N N。
??第二行包含N N N 个整数： W 1 , W 2 , W 3 , ? ? , W N W_1, W_2, W_3, \cdots , W_N W1?,W2?,W3?,?,WN?。
输出格式
??输出一个整数代表答案。
测试样例1

Input： 3 1 4 6Output： 10Explanation：能称出的 10 种重量是：1、2、3、4、5、6、7、9、10、11。 1 = 1； 2 = 6 ? 4 (天平一边放 6，另一边放 4)； 3 = 4 ? 1； 4 = 4； 5 = 6 ? 1； 6 = 6； 7 = 1 + 6； 9 = 4 + 6 ? 1； 10 = 4 + 6； 11 = 1 + 4 + 6。

评测用例规模与约定
??对于50 50 50% 的评测用例， 1 ≤ N ≤ 15 1 ≤ N ≤ 15 1≤N≤15。
??对于所有评测用例， 1 ≤ N ≤ 100 1 ≤ N ≤ 100 1≤N≤100， N N N 个砝码总重不超过100000 100000 100000。
背包 DP ??终于逮到一个J a v a \mathrm{Java} Java 组没有的题，可惜是F \mathrm F F 题，还是个简单背包。
??不过依题意若干砝码做加减运算，得到的绝对值可以视为一个可以称出的重量，
??如果我们将若干砝码可能加减出的结果放在数轴上，显然可以发现，它是以原点对称的，于是我们可以只对正整数部分做背包，然后将上一轮背包( 1 , w i ) (1,w_i) (1,wi?) 部分的结果视为( ? w i , ? 1 ) (-w_i, -1) (?wi?,?1)，可以减少算法的常数。

#include using namespace std; const int N = 100000; bool dp[N + 1 << 1] = {1}, bf[N + 1 << 1] = {1}; int n, w, ans; int main() { cin >> n; while (n--) { cin >> w; swap(dp, bf); for (int i = N; i >= w; i--) dp[i] = bf[i] | bf[i - w] | bf[i + w]; for (int i = 1; i < w; i++) dp[i] |= bf[w - i]; } for (int i = 1; i <= N; i++) if (dp[i]) ans++; cout << ans << endl; }

#G 异或数列时间限制:1.0 s 1.0\mathrm s 1.0s 内存限制:256.0 M B 256.0\mathrm{MB} 256.0MB 本题总分： 20 20 20 分
?? A l i c e \mathrm{Alice} Alice 和B o b \mathrm{Bob} Bob 正在玩一个异或数列的游戏。初始时， A l i c e \mathrm{Alice} Alice 和B o b \mathrm{Bob} Bob 分别有一个整数a a a 和b b b，有一个给定的长度为n n n 的公共数列X 1 , X 2 , ? ? , X n X_1, X_2, \cdots , X_n X1?,X2?,?,Xn?。
?? A l i c e \mathrm{Alice} Alice 和B o b \mathrm{Bob} Bob 轮流操作， A l i c e \mathrm{Alice} Alice 先手，每步可以在以下两种选项中选一种：
??选项1 1 1：从数列中选一个X i X_i Xi? 给A l i c e \mathrm{Alice} Alice 的数异或上，或者说令a a a 变为a ⊕ X i a ⊕ X_i a⊕Xi?。（其中⊕ ⊕ ⊕ 表示按位异或）
??选项2 2 2：从数列中选一个X i X_i Xi? 给B o b \mathrm{Bob} Bob 的数异或上，或者说令b b b 变为b ⊕ X i b ⊕ X_i b⊕Xi?。
??每个数X i X_i Xi? 都只能用一次，当所有X i X_i Xi? 均被使用后（ n n n 轮后）游戏结束。游戏结束时，拥有的数比较大的一方获胜，如果双方数值相同，即为平手。
??现在双方都足够聪明，都采用最优策略，请问谁能获胜？
输入格式
??每个评测用例包含多组询问。询问之间彼此独立。
??输入的第一行包含一个整数T T T，表示询问数。
??接下来T T T 行每行包含一组询问。其中第i i i 行的第一个整数n i n_i ni? 表示数列长度，随后n i n_i ni? 个整数X 1 , X 2 , ? ? , X n i X_1, X_2, \cdots , X_{ni} X1?,X2?,?,Xni? 表示数列中的每个数。
输出格式
??输出T T T 行，依次对应每组询问的答案。
??每行包含一个整数1 1 1、 0 0 0 或? 1 ?1 ?1 分别表示A l i c e \mathrm{Alice} Alice 胜、平局或败。
测试样例1

Input： 4 1 1 1 0 2 2 1 7 992438 1006399 781139 985280 4729 872779 563580Output： 1 0 1 1

评测用例规模与约定
??对于所有评测用例， 1 ≤ T ≤ 200000 1 \leq T \leq 200000 1≤T≤200000， 1 ≤ ∑ i = 1 T n i ≤ 200000 1 \leq \sum_{i=1}^T n_i \leq 200000 1≤∑i=1T?ni?≤200000， 0 ≤ X i < 2 20 0 \leq X_i < 2^{20} 0≤Xi?<220。

#include #include int T, S, n, A[200010]; int main() { scanf("%d", &T); while (T--) { S = 0; scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d", &A[i]), S ^= A[i]; if (S) { int k = log2(S), a = 0; for (int i = 0; i < n; ++i) if (A[i] >> k & 1) ++a; if (n & 1 || a == 1) printf("1\n"); else printf("-1\n"); } else printf("0\n"); } }

#H 左孩子右兄弟时间限制:1.0 s 1.0\mathrm s 1.0s 内存限制:256.0 M B 256.0\mathrm{MB} 256.0MB 本题总分： 20 20 20 分
问题描述
??对于一棵多叉树，我们可以通过 “左孩子右兄弟” 表示法，将其转化成一棵二叉树。
??如果我们认为每个结点的子结点是无序的，那么得到的二叉树可能不唯一。换句话说，每个结点可以选任意子结点作为左孩子，并按任意顺序连接右兄弟。
??给定一棵包含N N N 个结点的多叉树，结点从1 1 1 至N N N 编号，其中1 1 1 号结点是根，每个结点的父结点的编号比自己的编号小。请你计算其通过 “左孩子右兄弟” 表示法转化成的二叉树，高度最高是多少。注：只有根结点这一个结点的树高度为0 0 0 。
??例如如下的多叉树：

文章图片

??可能有以下3 3 3 种 (这里只列出3 3 3 种，并不是全部) 不同的 “左孩子右兄弟”表示：

文章图片

??其中最后一种高度最高，为4 4 4。
输入格式
??输入的第一行包含一个整数N N N。
??以下N ? 1 N ?1 N?1 行，每行包含一个整数，依次表示2 2 2 至N N N 号结点的父结点编号。
输出格式
??输出一个整数表示答案。
测试样例1

Input： 5 1 1 1 2Output： 4

评测用例规模与约定
??对于30 30 30% 的评测用例， 1 ≤ N ≤ 20 1 ≤ N ≤ 20 1≤N≤20；
??对于所有评测用例， 1 ≤ N ≤ 100000 1 ≤ N ≤ 100000 1≤N≤100000。

#include using namespace std; #define N 100005vector tree[N]; int dp(int root) { if (!tree[root].size()) return 0; int res = 0; for (int son : tree[root]) res = max(res, dp(son)); return res + tree[root].size(); }int main() { int n, t; cin >> n; for (int i = 2; i <= n; ++i) cin >> t, tree[t].push_back(i); cout << dp(1) << endl; }

#I 括号序列时间限制:1.0 s 1.0\mathrm s 1.0s 内存限制:256.0 M B 256.0\mathrm{MB} 256.0MB 本题总分： 25 25 25 分
问题描述
??给定一个括号序列，要求尽可能少地添加若干括号使得括号序列变得合法，当添加完成后，会产生不同的添加结果，请问有多少种本质不同的添加结果。
??两个结果是本质不同的是指存在某个位置一个结果是左括号，而另一个是右括号。
??例如，对于括号序列 ((()，只需要添加两个括号就能让其合法，有以下几种不同的添加结果：()()()、()(())、(())()、(()()) 和 ((()))。
输入格式
??输入一行包含一个字符串s s s，表示给定的括号序列，序列中只有左括号和右括号。
输出格式
??输出一个整数表示答案，答案可能很大，请输出答案除以1000000007 1000000007 1000000007 (即 1 0 9 + 7 10^{9} + 7 109+7) 的余数。
测试样例1

Input： ((()Output： 5

评测用例规模与约定
??对于40 40 40% 的评测用例， ∣ s ∣ ≤ 200 |s| ≤ 200 ∣s∣≤200。
??对于所有评测用例， 1 ≤ ∣ s ∣ ≤ 5000 1 ≤ |s| ≤ 5000 1≤∣s∣≤5000。

#include #include typedef long long ll; #define N 5555int dp[N][N], p = 1000000007; char str[N] = {'$'}; int calc(char *str) { memset(dp, 0, sizeof dp); dp[0][0] = 1; int opening = 0, n = strlen(str) - 1; for (int i = 1; i <= n; i++) { if (str[i] == '(') { for (int j = 1; j <= n; j++) dp[i][j] = dp[i - 1][j - 1]; opening++; } else { dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % p; for (int j = 1; j <= n; j++) dp[i][j] = (dp[i][j - 1] + dp[i - 1][j + 1]) % p; if (opening) opening--; } } return dp[n][opening]; }int reverse(char *str) { for (int i = 1, j = strlen(str) - 1; i <= j; i++, j--) { char temp = str[i] ^ 1; str[i] = str[j] ^ 1; str[j] = temp; } }int main() { scanf("%s", str + 1); ll ans = calc(str); reverse(str); printf("%d\n", ans * calc(str) % p); }

#J 分果果时间限制:1.0 s 1.0\mathrm s 1.0s 内存限制:256.0 M B 256.0\mathrm{MB} 256.0MB 本题总分： 25 25 25 分
问题描述
??小蓝要在自己的生日宴会上将n n n 包糖果分给m m m 个小朋友。每包糖果都要分出去，每个小朋友至少要分一包，也可以分多包。
??小蓝已经提前将糖果准备好了，为了在宴会当天能把糖果分得更平均一些，小蓝要先计算好分配方案。
??小蓝将糖果从1 1 1 到n n n 编号，第i i i 包糖果重w i w_i wi?。小朋友从1 1 1 到m m m 编号。每个小朋友只能分到编号连续的糖果。小蓝想了很久没想出合适的分配方案使得每个小朋友分到的糖果差不多重。因此需要你帮他一起想办法。为了更好的分配糖果，他可以再买一些糖果，让某一些编号的糖果有两份。当某个编号的糖果有两份时，一个小朋友最多只能分其中的一份。
??请找一个方案，使得小朋友分到的糖果的最大重量和最小重量的差最小，请输出这个差。
??例如，小蓝现在有5 5 5 包糖果，重量分别为6 , 1 , 2 , 7 , 9 6, 1, 2, 7, 9 6,1,2,7,9，如果小蓝要分给两个小朋友，则他可以将所有糖果再买一份，两个小朋友都分到1 1 1 至5 5 5 包糖果，重量都是25 25 25，差为0 0 0。
??再如，小蓝现在有5 5 5 包糖果，重量分别为6 , 1 , 2 , 7 , 9 6, 1, 2, 7, 9 6,1,2,7,9，如果小蓝要分给三个小朋友，则他可以将第3 3 3 包糖果再买一份，第一个小朋友分1 1 1 至3 3 3 包，第二个小朋友分3 3 3 至4 4 4 包，第三个小朋友分第5 5 5 包，每个小朋友分到的重量都是9 9 9，差为0 0 0。
??再如，小蓝现在有5 5 5 包糖果，重量分别为6 , 1 , 2 , 7 , 9 6, 1, 2, 7, 9 6,1,2,7,9，如果小蓝要分给四个小朋友，则他可以将第3 3 3 包和第5 5 5 包糖果再买一份，仍然可以每个小朋友分到的重量都是9 9 9，差为0 0 0。
??再如，小蓝现在有5 5 5 包糖果，重量分别为6 , 1 , 2 , 7 , 9 6, 1, 2, 7, 9 6,1,2,7,9，如果小蓝要分给五个小朋友，则他可以将第4 4 4 包和第5 5 5 包糖果再买一份，第一个小朋友分第1 1 1 至2 2 2 包重量为7 7 7，第二个小朋友分第3 3 3 至4 4 4 包重量为9 9 9，第三个小朋友分第4 4 4 包重量为7 7 7，第四个和第五个小朋友都分第5 5 5 包重量为9 9 9。差为2 2 2。
输入格式
??输入第一行包含两个整数n n n 和m m m，分别表示糖果包数和小朋友数量。
??第二行包含n n n 个整数w 1 , w 2 , ? ? ? , w n w_1, w_2, · · · , w_n w1?,w2?,???,wn?，表示每包糖果的重量。
输出格式
??输出一个整数，表示在最优情况下小朋友分到的糖果的最大重量和最小重量的差。
测试样例1

Input： 5 2 6 1 2 7 9Output： 0

测试样例2

Input： 5 5 6 1 2 7 9Output： 2

评测用例规模与约定
??对于30 30 30% 的评测用例， 1 ≤ n ≤ 10 1 \leq n \leq 10 1≤n≤10， 1 ≤ m ≤ 10 1 \leq m \leq 10 1≤m≤10， 1 ≤ w i ≤ 10 1 \leq w_i \leq 10 1≤wi?≤10；
??对于60 60 60% 的评测用例， 1 ≤ n ≤ 30 1 \leq n \leq 30 1≤n≤30， 1 ≤ m ≤ 20 1 \leq m \leq 20 1≤m≤20， 1 ≤ w i ≤ 30 1 \leq w_i \leq 30 1≤wi?≤30；
??对于所有评测用例， 1 ≤ n ≤ 100 1 \leq n \leq 100 1≤n≤100， 1 ≤ m ≤ 50 1 \leq m \leq 50 1≤m≤50， 1 ≤ w i ≤ 100 1 \leq w_i \leq 100 1≤wi?≤100。在评测数据中， w i w_i wi? 随机生成，在某个区间均匀分布。

#include #include int dp[51][101][101], W[101], n, m, ans = 0x3F3F3F3F; int max(int arg1, int arg2) { return arg1 > arg2 ? arg1 : arg2; }int min(int arg1, int arg2) { return arg1 < arg2 ? arg1 : arg2; }int main() { memset(dp, 0x3F, sizeof dp); scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &W[i]), W[i] += W[i - 1]; dp[0][0][0] = 0; for (int minW = W[n] * 2 / m; minW > 0; minW--) { for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) { int trans2 = 0, trans3 = 0; for (int k = 1; k <= j; k++) { dp[i][j][k] = dp[i][j][k - 1]; while (trans2 < k && W[j] - W[trans2 + 1] >= minW && max(dp[i - 1][trans2 + 1][trans2 + 1], W[j] - W[trans2 + 1]) <= max(dp[i - 1][trans2][trans2], W[j] - W[trans2])) trans2++; if (W[j] - W[trans2] >= minW) dp[i][j][k] = min(dp[i][j][k], max(dp[i - 1][trans2][trans2], W[j] - W[trans2])); while (trans3 < k && W[j] - W[trans3 + 1] >= minW && max(dp[i - 1][k][trans3 + 1], W[j] - W[trans3 + 1]) <= max(dp[i - 1][k][trans3 + 1], W[j] - W[trans3])) trans3++; if (W[j] - W[trans3] >= minW) dp[i][j][k] = min(dp[i][j][k], max(dp[i - 1][k][trans3], W[j] - W[trans3])); } } ans = min(ans, dp[m][n][n] - minW); } printf("%d\n", ans); }