上海市计算机学会竞赛月赛2025年1月份丙组
T1水瓶灌水
【题目链接】
上海计算机学会举办的竞赛平台 / YACS
【考点】
循环、判断
【题目大意】
Alice拥有三个水瓶，在至少有两个瓶子为空的情况下她会将它们装满水；但如果仅最多只有一个瓶子为空，则不会采取任何行动。
【解析】
设置三个变量用于记录水瓶状态，并对这些变量进行求和运算；若求和结果超过1，则返回值设为'Not now'；否则返回值设为'Water filling time'"
【难度】
GESP二级
【代码参考】
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, a, b, c;
cin >> n;
for(int i = 0; i < n; i++){
cin >> a >> b >> c;
if(a + b + c > 1)cout << "Not now" << endl;
else cout << "Water filling time" << endl;
}
return 0;
}T2 音乐播放
【题目链接】
原题链接：上海市计算机学会竞赛网站 | YACS
【考点】
排序、贪心
【题目大意】
某天早晨，Bob 意图聆听语言为 L 的歌曲，并希望从备选曲目中精确挑选正好 k 张专辑（其中每张专辑上的全部曲目均为语言 L）。若无法满足条件，则应返回 -1。
【解析】
根据输入条件选择语言参数设为 L 的歌曲；然后按照 descending 顺序排列；随后计算出前 k 张专辑的累计值；若 k 超过所选歌曲的数量，则返回 -1。
【难度】
GESP四级
【代码参考】
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, k, L, T, l, m;
cin >> T;
while(T--){
long long sum = 0;
cin >> n >> k >> L;
vector<int> a;
for(int i = 0; i < n; i++){
cin >> m >> l;
if(L == l){
a.push_back(m);
}
}
if(k > a.size()){
cout << -1 << endl;
continue;
}
sort(a.rbegin(), a.rend());
for(int i = 0; i < k; i++){
sum += a[i];
}
cout << sum << endl;
}
return 0;
}T3 小球涂色
【题目链接】
请参赛者在限定时间内完成以下任务：首先完成比赛，并随后提交代码
原题链接：上海市计算机学会竞赛平台 | YACS
【考点】
排列组合
【题目大意】
有 n 个小球排成一列，并按顺序编号为1到n，并需要使用 k 种不同的颜色来涂色它们。对于任意的起点i，在包含这些位置的小球范围内的区间内（即从位置i到位置i+k），其颜色必须各不相同。
【解析】
在k范围内的小球中第一个小球有k种颜色第二个也有k-1种以此类推直到第k个小仅剩一种颜色这些情况均满足乘法原理因此总的排列数目为A(k,k)总共存在两种不同的情况若n\geqslant k则k之外的小球颜色安排将受到k范围内的色彩限制其总的排列数目仍然是A(k,k)而当n
【难度】
GESP四级
【代码参考】
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int main(){
int n, k, T;
cin >> T;
while(T--){
cin >> n >> k;
long long sum = 1;
if(n >= k)n = 1;
else n = k - n;
for(int i = k; i > n; i--){//求k！
sum *= i;
sum %= mod;
}
cout << sum << endl;
}
return 0;
}T4 草莓分组
【题目链接】
题目出处：上海交通大学信息技术学院组织的竞赛平台；该平台上的问题编号为1015的是关于YACS项目的具体描述
题目出处：上海交通大学信息技术学院组织的竞赛平台；该平台上的问题编号为1015的是关于YACS项目的具体描述
【考点】
二分、贪心
【题目大意】
每一种草莓都有 ai 个，并且在任意一盒中都必须包含 k种不同种类的草莓，请问最多能制作多少盒。
【解析】
按草莓进行分类后, 依次进行操作: 首先将数量最少的草莓分配到最小的那一组中. 关于具体方法有两种选择: 一种是采用二分法(Divide and Conquer), 另一种则是应用贪心算法(Greedy Algorithm).
二分法的应用旨在确定能够制作的最大盒数。为此步骤首先计算所有草莓的总数量sum，并将草莓按照数量从高到低进行排序。设定一个左边界l=0（表示可制作的最小盒数），右边界r=sum/k+1（表示不可制作的最大盒数）。在二分判断过程中：若当前分组的最后一组总数量sumk满足大于等于假设盒数x，则调整右边界至当前区间；否则调整左边界至当前区间。其中，在计算最后一组总数量sumk时需遍历前k-1个品种：如果某一品种a[i]的数量超过假设值x，则从总数sum中减去该品种的数量；否则减去假设值x本身。特别地，在逐步缩减每一分组时若出现无法满足条件的情况（即剩余总数不足以支持下一层次分组），则直接判定不符合条件并终止当前判断路径。
贪心算法采用降序排序的方式进行处理，并计算各类别水果的平均分后进行排序。随后确定目标水果中第一项达到或超过平均分数的部分作为补充对象，并针对当前需求量不足的部分进行具体调整：对于超过需求量的类别，则无需额外补充；而对于刚好满足需求的部分，则需扣除现有库存。
【难度】
GESP五级
【代码参考】
//二分
#include <bits/stdc++.h>
using namespace std;
int n, k, T;
int a[200005];
bool check(long long x, long long sum){
for(int i = 0; i < k-1; i++){
if(a[i] > x)sum -= a[i];//不需要补充，减去该种类
else sum -= x;//将草莓补到x
if(sum / (k - i - 1) < x)return 0;//不足以继续分
}
return sum >= x;
}
int main(){
cin >> T;
while(T--){
cin >> n >> k;
long long sum = 0;
memset(a, 0, sizeof(a));
for(int i = 0; i < n; i++){
cin >> a[i];
sum += a[i];
}
if(k > n){//n种不满于分k盒
cout << 0 << endl;
continue;
}
sort(a, a + n, greater<int>());//降序
long long l = 0, r = sum / k + 1;
while(l < r){
long long mid = (l + r + 1) >> 1;
if(check(mid, sum))l = mid;
else r = mid - 1;
}
cout << l << endl;
}
return 0;
} //贪心
#include <bits/stdc++.h>
using namespace std;
int a[200005];
int main(){
int n, k, T;
cin >> T;
while(T--){
cin >> n >> k;
long long sum = 0;
memset(a, 0, sizeof(a));
for(int i = 0; i < n; i++){
cin >> a[i];
sum += a[i];
}
if(k > n){
cout << 0 << endl;
continue;
}
sort(a, a + n, greater<int>());//降序
for(int i = 0; i < k; i++){//遍历不需要补充的草莓
if(sum / (k - i) >= a[i]){//剩余的草莓都需要补充
cout << sum / (k - i) << endl;
break;
}
else sum -= a[i];//该草莓不需要补充
}
}
return 0;
}T5 分块序列
【题目链接】
上海
【考点】
动态规划dp
【题目大意】
一个长度为n的序列a进行分段处理其中每个块由起始位置ai和后续ai个元素组成例如[3 1 2 3 2 1 2]是一种合理方案即并非所有序列都能自然地分成这样的结构则需考虑移除若干元素找出最少需去除的数量
【解析】
创建一个动态规划数组dp用于记录从i开始的序列中至少需要删除多少个元素。并维护两个属性：a数组中的每个元素及其后续连续段长度。逆序遍历整个数组，在处理到第i个位置时：若当前元素及其后续段长度满足条件（即后续段足够长），则有两种操作可选；否则仅能进行另一种操作。具体而言，在满足条件的情况下可以选择取当前数或删掉它，并根据哪种选择会导致更短的结果而进行相应的更新；而不满足条件时则只能继续往下处理并递增计数器。最终结果即为dp[1]
【难度】
GESP六级
【代码参考】
#include <bits/stdc++.h>
using namespace std;
struct node{
int len, num;
}a[200005];
int n, k, T, dp[200005];
int main(){
cin >> T;
while(T--){
cin >> n;
k = 0, minn = 1e9;
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; i++){
cin >> a[i].num;
a[i].len = n - i;
}
for(int i = n; i >= 1; i--){
if(a[i].len >= a[i].num){//后继有足够多的元素
dp[i] = min(dp[a[i].num + i + 1], dp[i+1] + 1);//取后a[i]个值或删数
}
else{//后继没有足够的元素
dp[i] = dp[i+1] + 1;//删数
}
}
cout << dp[1] << endl;
}
return 0;
} 有其他解法欢迎私信！！！