2025年CUGBACM2022校新生选拔赛总结

大家好，我是讯享网，很高兴认识大家。

2023/1/8 19：00~22：00 PTA AC 7/15 排名5

新生选拔赛相对比较简单，好多都是板子题，包括dp、dijsktra、Kruskal、并查集、完全背包等，实在不应该做不出，长时间没练习，我竟然给忘了，这也意味着训练迫在眉睫。当然也有些需要思维的题，如总结第一题的逆向思维，第二题的思维方式，第三题的函数等。第四题第一次接触到了巨大数据范围的爬楼梯问题（对于还没学矩阵的大一不太友好），学到了一种新的方法。随着寒假的到来，队内系统训练的开展，自校赛结束就开始摆烂的我也必须正式开始认真学习和训练了，不然真不行了。。

一、carry的糖果

题面描述

万圣节那天，Carry买了一堆糖果准备给妹妹，但是他刚把糖果带到机房，一堆人围了上来要糖果

作为队长，Carry自然要出题考考这些“白嫖党”，于是Carry掏出一堆糖果，把它们摆成一列，说：“这些糖果都有一个甜蜜值Vi，谁要是能在这里面找到连续的一串糖果（不可以不选），使得它们甜蜜值之和最高，我就让他从我的糖罐子里面抓一把糖果。”

大家都很想吃糖果，于是都回去开始计算。Wolfycz看了一眼，觉得这样太简单了，于是把那一列糖首尾相连摆成一个圆环，并说：“修改一下，现在不是一列，是一个环。”

由于你也很想吃糖，所以赶紧算出来去拿糖果吧

PS：算出来了可以找Carry要糖果哦（划掉）

输入格式

第一行一个整数n(1≤ n≤10^5)，代表糖果的总数

第二行n个整数V1,V2,...,Vn，Vi(|Vi|≤10^4)代表第i颗糖果的甜蜜值

输出格式

一行一个整数，表示答案

tag

动态规划

解题思路

首先考虑Carry原本的题意，一列数组求最大连续子串和

设F[i]表示以i结尾的最大连续子串和，那么答案显然就是： $\text{[math]}$

至于F[i]的转移方程，显然是F[i]=max(F[i-1]+Vi,Vi)

考虑环形，环形的答案无非就是两种，一种是上述这种情况，另一种则是跨越了首尾

反向思考，跨越首尾选取了最大连续子串和，那么剩下的部分肯定是最小连续子串和

所以做两遍dp即可

代码

#include<limits.h> #include<iostream> using namespace std; const int N = 1e5; int V[N + 10], n; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &V[i]); int Max = numeric_limits<int>::min(), MaxSum = 0; int Min = numeric_limits<int>::max(), MinSum = 0; int Sum = 0; for (int i = 1; i <= n; i++) { Sum += V[i]; Max = max(Max, MaxSum = max(MaxSum, 0) + V[i]); Min = min(Min, MinSum = min(MinSum, 0) + V[i]); } int Ans = Max; if (Sum != Min) Ans = max(Ans, Sum - Min); printf("%d\n", Ans); return 0; }

讯享网

二、lemonGJacky的排水工程

题面描述

众所周知，Peking夏季容易下暴雨，而一旦下暴雨CUGB就会被水淹没，不知所措。作为地大学子，lemonGJacky非常痛心，他想发挥自己的专业水平，给CUGB重新规划一遍排水系统

要想规划排水系统，首先得统计一下CUGB哪些地方容易积水，总共会积多少水。而想要研究二维平面，首先得研究一维直线

lemonGJacky找来两块巨大玻璃板，将它们间隔1cm平行摆放，之后在里面放入若干高为Hi(cm)的柱子（柱子为1cm见方）

然后lemonGJacky开始模拟下雨，lemonGJacky想知道，在经历一次极为漫长的降雨之后，两片玻璃之间会攒多少cm^3的水？

PS：这个水是遵循物理原则的，可不是MC

输入格式

一行一个整数n(1≤ n≤10^4)，表示柱子的数目

之后一行n个整数Hi(1≤ Hi≤10^4)，代表每根柱子的高度

输出格式

一行一个整数，表示答案

2025年CUGBACM2022校新生选拔赛总结

一、carry的糖果

题面描述

输入格式

输出格式

tag

解题思路

代码

二、lemonGJacky的排水工程

题面描述

输入格式

输出格式

相关推荐