10.14 4道题目
2026-10-14 20:31:33
发布于：上海
3阅读
0回复
0点赞
分糖果
暴力做法（90 pts）
枚举 [L, R] 中的每个糖果总数，将糖果总数依次 % n，则为奖励的糖果数，在奖励中取最大的数字就是答案。
for(int i = l; i <= r; i++){
ans = max(ans, i % n);
}
数学规律（100pts）
直到篮子里的糖数量少于 n 块。此时篮子里剩余的糖果均归你所有。
观察样例，发现，在某些情况下，最多的奖励就是 n - 1 块糖果。
关键分类：区间 [L, R] 够不够覆盖一整轮余数？
情况1：R−L≥n−1（区间横跨了一整个周期）
答案 = n - 1
情况2：R−L<n−1
答案 = r % n
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n, L, R;
cin >> n >> L >> R;
if (R - L >= n - 1) {
cout << n - 1 << endl;
} else {
cout << R % n << endl;
}
return 0;
}
小熊的果篮
暴力做法（70 - 80 pts）
维护一个数组存“还活着，没被挑走”的水果。每轮扫一遍，块首取走，其余保留。
每轮都要扫描整个数组，最坏情况下需要跑 n 轮，每轮遍历 n 个水果。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
scanf("%d", &n);
vector<int> a(n), id(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
id[i] = i + 1;
}
while (!a.empty()) {
vector<int> na, nid;
bool first = true;
for (int i = 0; i < (int)a.size(); i++) {
if (i == 0 || a[i] != a[i - 1]) {//块首判断
if (!first) printf(" ");
printf("%d", id[i]);
first = false;
} else {
na.push_back(a[i]);
nid.push_back(id[i]);
}
}
printf("\n");
a = na;
id = nid;
}
return 0;
}
正解1（结构体链表）
由于朴素做法每次扫描数组都需要O(n)的时间开销，所以考虑用结构体链表存储每个块的存活情况。
#include <bits/stdc++.h>
using namespace std;
struct Block {
int type;
list<int> q;//一个块的数据
};
int main() {
int n;
cin >> n;
list<Block> blk; // 块列表本身也用 list，方便 O(1) 删除和合并
int pre = -1;
for (int i = 1; i <= n; i++) {
int a;
cin >> a;
if (a != pre) {
blk.push_back({a, {}});
pre = a;
}
blk.back().q.push_back(i);
}
while (!blk.empty()) {
// 弹出每个块的队首，输出果篮
bool first = true;
for (list<Block>::iterator it = blk.begin(); it != blk.end(); it++) {
if (!first) cout << " ";
cout << it->q.front();
it->q.pop_front();
first = false;
}
cout << "\n";
// 删除空块
list<Block>::iterator it = blk.begin();
while (it != blk.end()) {
if (it->q.empty()) {
it = blk.erase(it); // O(1) 删除
} else {
it++;
}
}
// 合并相邻同类型块
it = blk.begin();
while (it != blk.end()) {
list<Block>::iterator nxt = next(it);
if (nxt != blk.end() && nxt->type == it->type) {
it->q.splice(it->q.end(), nxt->q); // O(1) 拼接
blk.erase(nxt); // 删掉被合并的空壳，不前进 it
} else {
it++;
}
}
}
return 0;
}
正解2（set + 数学规律）
由于水果只有两个类型，把苹果和橘子放进两个 set 中。
取不同的水果的块首 = 交替从 s1 和 s2 中取数字，且从 s1 取完后，下一次从 s2 中取时，一定要取比 s1 水果编号更大的数字。
#include <bits/stdc++.h>
using namespace std;
const int INF = 200010;
int main() {
int n;
cin >> n;
set<int> s1, s2;
for (int i = 1; i <= n; i++) {
int a;
cin >> a;
if (a == 1) s1.insert(i);
else s2.insert(i);
}
s1.insert(INF);
s2.insert(INF);
int nw = 0;
int p;
if (*s1.begin() < *s2.begin()) p = 0;
else p = 1;
while ((!p && (int)s1.size() > 1) || (p && (int)s2.size() > 1)) {
if (p == 0) {
nw = *s1.upper_bound(nw);
if (nw == INF) {
nw = 0;
if (*s1.begin() < *s2.begin()) p = 0;
else p = 1;
cout << "\n";
continue;
}
cout << nw << " ";
s1.erase(nw);
p = 1;
} else {
nw = *s2.upper_bound(nw);
if (nw == INF) {
nw = 0;
if (*s1.begin() < *s2.begin()) p = 0;
else p = 1;
cout << "\n";
continue;
}
cout << nw << " ";
s2.erase(nw);
p = 0;
}
}
cout << "\n";
while ((int)s1.size() > 1) {
cout << *s1.begin() << "\n";
s1.erase(s1.begin());
}
while ((int)s2.size() > 1) {
cout << *s2.begin() << "\n";
s2.erase(s2.begin());
}
return 0;
}
纪念品
观察到：题目主要是围绕每天用金币购买纪念品，然后卖出，获取最大金币的问题。本质是一个资源交换的问题，所以考虑：背包DP。
状态：dp[v]：金币为 v 时的最大纪念品个数。
状态转移方程：每天考虑怎么购买能获得最大利润。
#include <bits/stdc++.h>
using namespace std;
int price[105][105];
int dp[10005];
int main() {
int T, N, M;
cin >> T >> N >> M;
for (int i = 1; i <= T; i++)
for (int j = 1; j <= N; j++)
cin >> price[i][j];
for (int i = 1; i < T; i++) {
memset(dp, 0, sizeof(dp));
for (int j = 1; j <= N; j++) {
int c = price[i][j];
int w = price[i + 1][j] - price[i][j];//第i天买进来时，第i+1天卖出去会不会更便宜
if (w <= 0) continue;
for (int v = c; v <= M; v++) {//枚举金币，才能拿到上一天当倒狗，赚到的钱
dp[v] = max(dp[v], dp[v - c] + w);
}
}
M += dp[M];//每天获得利润要累计到金币中去
}
cout << M << endl;
return 0;
}
这里空空如也
有帮助，赞一个