由于没讲课所以就把写的两篇题解发上
开营测试 B 题小贝的饭量题解
题目描述
小贝现在上六年级，正是长身体的时候，小贝的妈妈给小贝规定了每天要吃的饭量。
小贝要连续吃 \(n\) 天的饭，有 \(n + 1\) 个碗，第 \(i\) 个碗的容量为 \(a_i\)，所有的碗每天都会重新盛满饭。小贝妈妈规定小贝在第 \(i\) 天要吃第 \(i\)、\(i + 1\) 两碗饭。而小贝的饭量有限，每天最多只能吃 k 的饭量。但是小贝妈妈永远都觉得小贝吃的不够多，以至于可能会有小贝吃不下的剩饭。
浪费粮食可耻！现在小贝请你帮他调整序列 \(a\) 变为 \(a′\)，也就是减少一些碗的容量（可以不减），使得小贝每天吃饭的总量不会超过 k。但是减去的容量总和不能太大，否则小贝妈妈会觉得小贝是故意不想吃饭。
请你回答满足条件的序列 \(a′\)，表示调整之后每个碗的容量，并且减去的容量总和要最小。
不同的碗减去的容量可以不一样，最后每个碗的容量不可以是负数！
如果有多个满足条件的序列 \(a′\) ，则输出 字典序最大 的那一个。
假设序列 \(x\) 和序列 \(y\) 都符合要求，则序列 \(x\) 的字典序比序列 \(y\) 的字典序大，当且仅当存在一个 \(i\) 满足
- \(1≤i≤n+1\)
- \(x_i>y_i\)
- 对于所有的 j(1≤j<i) 均有 \(x_j=y_j\)
输入格式
第 \(1\) 行 \(2\) 个正整数 \(n,k\)。
第 \(2\) 行 \(n+1\) 个正整数表示序列 \(a\)。
输出格式
输出一行 \(n+1\) 个整数，表示调整后的序列 \(a′\)。
样例
Input 1
5 6 3 4 2 7 3 1
Output 1
3 3 2 4 2 1
Input 2
5 6 7 4 3 7 2 8
Output 2
6 0 3 3 2 4
数据范围
前 50% : \(1≤n≤2×10^3\) , \(1≤a_i,k≤10^4\)
后 50% : \(1≤n≤2×10^5\), \(1≤a_i,k≤10^4\)
样例解释
第 \(1\) 个样例中
第 \(2\) 个碗容量减少了 \(1\)，第 \(4\) 个碗容量减少了 \(3\)，第 \(5\) 个碗容量减少了 \(1\)。
总共减少了 \(5\) 的容量，这是最少的减少容量之和。
思路
此题重点就是输出字典序最大的。
编译结果
compiled successfully
time: 158ms, memory: 1136kb, score: 100, status: Accepted
> test 01: time: 1ms, memory: 1136kb, points: 10, status: Accepted
> test 02: time: 1ms, memory: 1136kb, points: 10, status: Accepted
> test 03: time: 1ms, memory: 1136kb, points: 10, status: Accepted
> test 04: time: 1ms, memory: 1136kb, points: 10, status: Accepted
> test 05: time: 1ms, memory: 1136kb, points: 10, status: Accepted
> test 06: time: 24ms, memory: 1136kb, points: 10, status: Accepted
> test 07: time: 35ms, memory: 1136kb, points: 10, status: Accepted
> test 08: time: 53ms, memory: 1136kb, points: 10, status: Accepted
> test 09: time: 18ms, memory: 1136kb, points: 10, status: Accepted
> test 10: time: 23ms, memory: 1136kb, points: 10, status: Accepted
#include<iostream>
using namespace std;
#define MAXN 200005
int n, a[MAXN], k;
int main() {
cin >> n >> k;
for(int i = 1; i <= n + 1; i ++) cin >> a[i];
for(int i = 1; i <= n; i ++) {
if(a[i] + a[i + 1] > k)
if(a[i] > k) a[i] = k, a[i + 1] = 0;
else a[i + 1] -= a[i] + a[i + 1] - k;
else continue;
}
for(int i = 1; i <= n + 1; i ++) cout << a[i] << " ";
return 0;
}
开营测评 D 题小贝的影分身题解
题目描述
小贝是一名忍者，他所在的仓前村出现了一名叛忍，叛忍藏匿在仓前村的某一个位置，现在组织要求你去追捕这名叛忍。小贝刚学会了影分身，所以他不用亲自出手，只需要派遣分身去执行任务即可。小贝可以在某些位置召唤分身，召唤的分身会赶往叛忍所在的位置实行抓捕。每个分身需要相对应的查克拉能量。此叛忍实力十分强大，所以小贝会召唤尽可能多的能够到达叛忍位置的分身，在满足这一前提下，希望消耗的查克拉能量最少。
整个仓前村可以看作一个 \(n×m\) 的地图，’#‘ 表示障碍物，'.' 表示空地，’O‘ 表示叛忍，'X' 表示小贝可以召唤分身的位置。相邻位置（四连通）之间的距离为 \(1\)，每个分身所需要的查克拉能量值为该分身赶路的路程长度。如果有的分身位置无法到达叛忍所在地，则这些位置不必召唤分身。
请你帮小贝计算，需要放置几个分身，并且最少一共需要多少查克拉能量值。
输入格式
第 \(1\) 行 \(2\) 个正整数 \(n 和 m\)。
接下来 \(n\) 行表示仓前村 \(n×m\) 的地图。
输出格式
一行两个整数，分别表示 需要派遣的分身数量 和 最少的一共需要的查克拉能量值。
样例
Input 1
4 3
O#X
X..
.X#
.#X
Output 1
3 8
数据范围
前 50%： \(1≤n,m≤50\)
后 50%： \(1≤n,m≤2000\)
思路
首先很容易看出此题是个搜索， 但他是深搜还是广搜？第一问要求分身数量， 很显然深搜和广搜都可以轻易完成此问题， 而第二问最少能量值就需要求最短路的路径长， 所以需用广搜完成搜索， 并在搜索过程中进行标记每个点到终点的最短路径长。
有了这个思路， 就很容易可以写出广搜代码了。
编译结果
compiled successfully
time: 500ms, memory: 23908kb, score: 100, status: Accepted
> test 01: time: 1ms, memory: 7524kb, points: 10, status: Accepted
> test 02: time: 1ms, memory: 3740kb, points: 10, status: Accepted
> test 03: time: 1ms, memory: 9672kb, points: 10, status: Accepted
> test 04: time: 1ms, memory: 9616kb, points: 10, status: Accepted
> test 05: time: 1ms, memory: 7420kb, points: 10, status: Accepted
> test 06: time: 110ms, memory: 23908kb, points: 10, status: Accepted
> test 07: time: 69ms, memory: 16928kb, points: 10, status: Accepted
> test 08: time: 188ms, memory: 23808kb, points: 10, status: Accepted
> test 09: time: 91ms, memory: 19680kb, points: 10, status: Accepted
> test 10: time: 37ms, memory: 19484kb, points: 10, status: Accepted
#include<iostream>
#include<queue>
using namespace std;
#define MAXN 2005
int n, m, x, y, ans1 = 0, ans2 = 0, num = 0;
int a[MAXN][MAXN];
char mp[MAXN][MAXN];
bool vis[MAXN][MAXN];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
struct node {
int qx, qy, num;
};
void bfs(int x, int y) {
queue<node> q;
q.push({x, y, 0});
a[x][y] = 0;
vis[x][y] = true;
while(!q.empty()) {
for(int i = 0; i < 4; i ++) {
node p = q.front();
int xx = p.qx + dx[i], yy = p.qy + dy[i];
if(xx > n || xx < 1 || yy > m || yy < 1 || vis[xx][yy] || mp[xx][yy] == '#') continue;
a[xx][yy] = p.num + 1;
if(mp[xx][yy] == 'X') ans1 ++, ans2 += a[xx][yy];
q.push({xx, yy, p.num + 1});
vis[xx][yy] = true;
}
q.pop();
}
}
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++) {
cin >> mp[i][j];
if(mp[i][j] == 'O') x = i, y = j;
}
bfs(x, y);
cout << ans1 << " " << ans2;
return 0;
}