SDKD 2023 Summer Team Contest B 训练赛总结
2023-08-05 13:00 - 18:00
比赛过程
这次比赛还是延续上次的题目分配, 甲看前4题, 乙看中间3题, 丙看后4题; 丙很快就发现H题较为简单于是做了标记, 甲发现C题是签到题也做了标记; 甲接下来发现D题像是二分但是其并不擅长于是来和乙交流, 并确定了一个模糊的思路后交给了乙; 然后乙的中间三题里面认为F的题意较为简单, 于是和丙花了一些时间来想F, 但其实F题难以优化复杂度, 之后的比赛中也没有队伍能ac; 在搁置F后, 乙发现G题可以做, 和甲交流后感觉像是一个dp问题, 然后甲想到了思路并做好标记; 此时丙继续看后四题中有没有可以做的; 而甲则就A题和乙进行了讨论并想到了思路, 甲同样也揽下了A题; 至此用了一个半小时分配了5道题; 在之后的一个半小时里乙和丙在思考I题, 甲因为揽了3道题所以在完善思路; 在开题后甲先去ac了C题找个签到题, 然后我们发现D题已经被绝大部分的队伍在3分钟内就ac了, 但是当时没有多想就让丙去写H题, 结果wa了一发后一时间没有发现问题, 于是甲接力去写G题, 在成功ac后便想趁热打铁去写A题, 结果也wa了一发; 这时候便让乙去接力写D题, 结果写到一半发现二分的上限难以确定也卡住了, 但是好在这是甲想到了A的漏洞并成功ac了A题; 至此5道题只ac了3道, 丙改动后又交了一次H题结果仍是wa; 大概在卡了15分钟后, 乙突然想到了D的做法, 其实并不是二分而是找规律并且成功ac了D题, 这时候时间差不多正好一个小时; 之后丙又想了一段时间H题但是仍没有找到漏洞, 于是乙决定他来做H题, 花了20分钟写完后因为此时H已经wa了2次, 三人都比较谨慎, 但是检查了几分钟后决定交一发, 好在成功ac; 此时大概1小时40分钟做完了之前标记的5道题, 但是因为D题的判断错误, 比其他队晚交了差不多一个小时, 再加上H题wa了两发, 导致最终罚时较高;
【NCPC 2022】题目解析
A - Ace Arbiter（Gym - 104030A）
难度 ⭐
【题目描述】
爱丽丝和鲍勃正在打一场友好的乒乓球比赛。游戏由几轮组成。每轮结束时，只有一名玩家获得一分。第一个获得 11 分的玩家获胜。当这种情况发生时，游戏立即结束。 Alice 开始第一轮发球，然后 Bob 在接下来的两轮发球，然后 Alice 发球两次，然后 Bob 发球两次，以此类推。
在比赛中的任何时刻，当前得分都写为 X - Y ，其中 X 是当前发球的球员的得分，并且 Y 是其他玩家的点数。这种不断地来回切换分数可能有点容易出错。伊芙是裁判，她在比赛过程中的几个不同时间写下了当前得分的日志。但由于伊芙有点不可靠，你担心她记错了分数。编写一个程序，根据夏娃写下的分数列表，检查该分数列表是否可以出现在实际游戏中。
【题目模型】
给定n组分数记录, 记录中第一个数是当前发球人的分数, 可以在同一时间记录多次; 某人分数到11后立刻停止, 问这n组中是否有出错的分数记录; n为100
【解题思路】
一道普通的判断题, 先想出错误情况都有哪些, 然后在循环中一一排查即可; 错误情况无非2种: 一是某人的分数减少, 二是有人分数到11后比赛还在继续, 对于第二种情况还需要特判一下11-11的情况, 这种记录是不可能存在的; 可以根据当前两人的分数和来判断当前的回合数, 再根据题目给出的发球顺序判断当前发球的是谁; 复杂度为O(n);
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6 + 10;
int n, A, B;
int f = 0;
signed main(){
scanf("%lld", &n);
for(int i = 1; i <= n; i++){
int a, b;
scanf("%lld-%lld", &a, &b);
if (f) continue;
if (a == 11 && b == 11) {
f = i;
continue;
}
int c = (a + b + 1) / 2;
if (c % 2) {
if ((B == 11 && b != A) || (A == 11 && a != B)) {
f = i;
continue;
}
if (a < B|| b < A) f = i;
else B = a, A = b;
}
else {
if ((A == 11 && b != B) || (B == 11 && a != A)) {
f = i;
continue;
}
if (a < A || b < B) f = i;
else A = a, B = b;
}
}
if(f) printf("error %lld", f);
else printf("ok");
return 0;
}
B - Berry Battle（Gym - 104030B）
难度 ⭐⭐⭐
【题目描述】
采摘浆果是辛苦的工作，但也是一种平静、放松的体验。经过一整天的采摘，闭上眼睛睡觉时，通常除了浆果什么也看不见。当你的思绪进入无意识状态时，浆果就会开始过自己的生活，并创造出各种荒谬的场景。 您将获得一棵具有 n 顶点的树，编号从 1 到 n 。最初，每个顶点都有一个浆果。每个顶点还有一只蚂蚁，守护着浆果。当采摘顶点 v 处的浆果时，位于不同顶点的所有蚂蚁都会向 v 迈出一步。已经在 v 的蚂蚁将留在原地。请注意，由于该图是一棵树，因此蚂蚁总是会选择一条唯一的路径。
【题目模型】
给定一颗无向树, 每个节点都有一个蚂蚁, 每选择一个节点, 所有蚂蚁都会朝这个节点走一步, 问如何遍历所有节点可以使得任何时刻都不会出现所有蚂蚁汇聚在同一个点; 边数和节点数最大为3e5;
【解题思路】
想让蚂蚁不汇聚到一个点上, 如果树的最大深度小于等于3那么是一定不可能的, 所以我们可以先求一下树的直径来看看最大深度; 如果最大深度大于3, 我们可以想到让两只相邻的蚂蚁始终都朝同一个方向前进, 使得这两只蚂蚁始终相邻而不汇聚; 为了满足上述条件, 我们不能选择这两只蚂蚁所在位置的浆果, 因此我们要先营造一个环境, 让这两个蚂蚁移动到没有浆果的节点; 设1-2-3-4这样一个分支, 1和3与2相连, 4与3相连, 如果我们以2, 1, 3的顺序遍历, 我们会发现此时我们位于3, 4只蚂蚁都汇聚在1和2, 并且1和2上没有浆果, 然后我们需要从3开始往后遍历即可, 1和2上的蚂蚁一定都是始终朝同一个方向前进;
当时比较卡我的一个点是: 假设我们走到了点3, 4和5都与3相连, 5后面还有节点, 而4就自己; 如果我们此时先走4, 后面蚂蚁则移动到2和3; 然后我们再走5, 后面蚂蚁则移动到3和5, 此时相当于我和蚂蚁之间的距离缩短了一格; 所以当时我以为行不通, 其实不然, 我们继续模拟, 如果又遇到了相同的情况, 我们先走4, 后面蚂蚁则移动到3和4; 然后我们再走5, 后面蚂蚁则移动到3和5, 此时发现我们和蚂蚁之间的距离没有再缩小, 而是两个节点的蚂蚁交换了前后关系, 所以这个方法是可行的;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 10;
int n, m;
vector<int> v[N];
vector<int> dep(N);
void dfs(int u, int fa) {
for (int x : v[u]) {
if (x == fa) continue;
dep[x] = dep[u] + 1;
dfs(x, u);
}
}
void dfs2(int u, int fa) {
for (int x : v[u]) {
if (x == fa) continue;
cout << ' ' << x;
dfs2(x, u);
}
}
signed main(){
cin >> n;
for (int i = 1; i < n; i++) {
int a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
int st = 0, ed = 0;
dfs(1, 0);
for (int i = 1; i <= n; i++) {
if (dep[i] > dep[st]) st = i;
}
dep = vector<int>(N);
dfs(st, 0);
for (int i = 1; i <= n; i++) {
if (dep[i] > dep[ed]) ed = i;
}
int maxn = dep[ed] + 1;
if (maxn <= 3) cout << "NO" << endl;
else {
cout << "YES" << endl;
cout << v[st][0] << ' ' << st;
dfs2(v[st][0], st);
}
return 0;
}
C - Coffee Cup Combo（Gym - 104030C）
难度 ⭐
【题目描述】
Jonna 是一名大学生，每天参加 n 讲座。由于大多数讲座对于像乔娜这样的算法专家来说都太简单了，所以她只有在喝咖啡的情况下才能在讲座期间保持清醒。在一次讲座中，她需要喝一杯咖啡才能保持清醒。有些报告厅配有咖啡机，因此乔娜总能确保在那里喝到咖啡。此外，当乔娜离开演讲厅时，她最多可以携带两个咖啡杯参加接下来的讲座（每只手一杯）。但请注意，她在任何特定时间都不能携带超过两个咖啡杯。给定乔娜的哪些讲座有咖啡机，计算乔娜可以保持清醒的最大讲座次数。
【题目模型】
给定一个序列, 从前往后遍历, 当前数字为1, 则保持清醒并且把次数补充到2; 当前数字为0, 如果还有次数就次数减一以保持清醒, 否则就睡觉, 问有多少次是清醒的; 序列长度为1e6;
【解题思路】
签到题, 如果当前为1, 把次数改为2, 天数+1; 如果当前为0且次数大于0, 则次数-1, 天数+1; 遍历一遍O(n)的复杂度
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 10;
int n, m, res, idx;
signed main(){
string s;
cin >> n >> s;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '1') idx = 2, res++;
else if (idx > 0) idx--, res++;
}
cout << res;
return 0;
}
D - Disc District（Gym - 104030D）
难度 ⭐
【题目描述】
您住在 Flatland 的 Disc 区，为最近的便利绘图公司 (NCPC) 工作。你的工作是在光盘区之外找到最近方便的土地进行建设。圆盘区可以描述为平面上的一个圆盘，其中心为 (0,0) ，半径为 r 。因此，如果一个点到原点的（欧几里德）距离严格大于 r ，则该点位于圆盘区之外。如果 x 和 y 是整数，则平面上的点 (x,y) 是一个方便的绘图。
【题目模型】
给定一个距离r, 要求找到一个坐标(x, y), 要求该坐标到原点的距离在大于r的基础上尽可能小;
【解题思路】
签到题, 要求找x2+y2 > r2的最小值; 最小肯定就是r2+1, 那么就直接让x=1, y=r就好了;
神秘代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> PII;
const int N=110;
int n,m;
signed main(){
cin>>n;
cout<<1<<' '<<n<<endl;
return 0;
}
E - Enigmatic Enumeration（Gym - 104030E）
难度 ⭐⭐⭐⭐
【题目描述】
您的朋友 Cajsa 有一个带有 n 个顶点的图，她需要找到其最短周期。为此，她只需采用随机的顶点序列，幸运的是，这恰好是最短的循环。 “几率有多大？”她问自己，并编写了另一个程序来计算这个概率。为此，Cajsa 需要一种算法来计算图中最短循环的数量。她使用在 O(1) 中运行的自制随机算法。但您怀疑这个算法是不正确的，因为它肯定必须考虑图的每个顶点（对吗？）。您认为 Cajsa 的算法只是打印一些小图上恰好正确的随机数。为了回应这些疑问，Cajsa 生成了一堆图表，并要求您检查她的答案是否正确。给你一个带有 n 个顶点和 m 个边的无向图，你的任务是计算其中最短循环的数量。图中的循环是由不同顶点组成的路径，此外，该路径的第一个顶点和最后一个顶点之间存在一条边。如果两个循环不由同一组边组成，则认为它们是不同的。因此，循环 3,1,2 和 3,2,1 是相同的，并且循环 1,2,3 和 2,3,1 被认为是相同的。
【题目模型】
给定一个不含重边和自环但是一定存在环的图, 注意该图可能不连通; 找出该图中最小的环的数量; n个点, m条边, n为3e3, m为6e3;
【解题思路】
找出最小的环可以用bfs, 但是因为图可能不连通, 所以我们需要对所有节点作为根节点进行bfs; 我们用数组d表示以当前节点u为根节点时所有节点的深度, 如果当前节点a的子节点b的深度小于等于当前节点, 说明一定存在一个环经过u, a, b; 由于a和b相邻, 所有这个环的大小就是d[a]+d[b]+1;
在找出最小环的大小min后我们计算个数, 也是对每个点进行bfs找出经过该点的最小环的数量, 重复上述操作确立所有点当前的深度;
当min为奇数时, 如果存在经过u的最小环, 说明我们可以找到相邻的两个点a, b, 两点的深度都是(min-1)/2; 所以我们可以先找到点a, 然后遍历a的子节点, 有多少个深度为(min-1)/2的子节点, 经过u的最小环就有多少个, 但是我们之后还会找到b, 然后遍历b的子节点; 这样相当于每个节点都被算了2次, 所以最后再除以2即可;
当min为偶数时, 如果存在经过u的最小环, 说明我们可以找到相邻的两个点a, b, 两点的深度为min/2和min/2 - 1; 和奇数情况不同, 在同一个环里a其实会有两个相邻的点深度为min/2 - 1, 你可以想象一个倒置的三角形, a就是下面的尖, 左右存在深度相同的两个点; 我们也是先找到点a, 然后遍历a的子节点, 记录深度为min/2 - 1的子节点个数cnt, 从刚才的解释中我们可以知道在cnt个节点里中任取两个就是一个不同的最小环, C(cnt, 2)也就是cnt * (cnt - 1) / 2;
遍历完所有点后, 其实对于每个最小环, 我们都用它的所有节点把这个最小环记录了一次, 也就是说每个最小环都被重复记录了min次, 所以最后答案再除以min即可; 复杂度在于对每个节点都进行bfs, 也就是O(n*(n+m))
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int n, m, res, minn = 1e9;
int d[N], fa[N];
vector<int> v[N];
void bfs(int u) {
for (int i = 1; i <= n; i++) d[i] = 1e9;
for (int i = 1; i <= n; i++) fa[i] = 0;
d[u] = 0, fa[u] = 0;
queue<int> q;
q.push(u);
while (q.size()) {
int t = q.front();
q.pop();
for (int x : v[t]) {
if (x == fa[t]) continue;
if (d[x] == 1e9) {
d[x] = d[t] + 1;
fa[x] = t;
q.push(x);
}
else if (d[x] <= d[t]) minn = min(minn, d[t] + d[x] + 1);
}
}
}
void bfs2(int u) {
for (int i = 1; i <= n; i++) d[i] = 1e9;
for (int i = 1; i <= n; i++) fa[i] = 0;
d[u] = 0, fa[u] = 0;
queue<int> q;
q.push(u);
while (q.size()) {
int t = q.front();
q.pop();
for (int x : v[t]) {
if (x == fa[t]) continue;
if (d[x] == 1e9) {
d[x] = d[t] + 1;
fa[x] = t;
q.push(x);
}
}
}
int cnt = 0;
if (minn % 2) {
for (int i = 1; i <= n; i++) {
if (d[i] == minn / 2) {
for (int x : v[i]) {
if (d[x] == minn / 2) cnt++;
}
}
}
res +=cnt/2;
}
else {
for (int i = 1; i <= n; i++) {
if (d[i] == minn / 2) {
cnt = 0;
for (int x : v[i]) {
if (d[x] == d[i] - 1) cnt++;
}
res += cnt * (cnt - 1) / 2;
}
}
}
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
for (int i = 1; i <= n; i++) bfs(i);
for (int i = 1; i <= n; i++) bfs2(i);
cout << res / minn;
return 0;
}
F - Foreign Football（Gym - 104030F）
难度 ⭐⭐⭐⭐
【题目描述】
您正在国外度假。这个国家有一个地方足球联赛，但你不知道任何球队的名字。然而，您已经找到了本赛季所有结果的表格，每场比赛旁边都是两支球队的串联名称。总共有 n 个团队，名为 s1,s2,⋯ ,sn 。为每个有序对 i≠j 提供串联 si+sj 。找到团队名称 s1,s2,⋯,sn 。团队名称必须非空，但不需要不同。
【题目模型】
给定n个字符串两两组合后(自己和自己的除外)的(n-1)*(n-1)个字符串; 问是否能找出这n个字符串; 我们可以用s[i][j]表示第i个字符串在前, 第j个字符串在后的组合串; 字符串个数n为500, 组合后的字符串长度m最大为1e6;
【解题思路】
一道掺杂很多细节的找规律; 为了方便我们设第i个字符串长度为li, 1~n的字符串长度和为sum; 我们可以通过把所有组合串长度加起来除以(2 *(n-1))就得到了sum; 然后我们发现第一列的所有组合串就是由2~n的所有字符串和(n-1)个字符串1组成的, 所有我们可以把第一列的所有组合串长度加起来减去sum后再除以(n-2)就得到了l1, (注意, 如果求出来长度为0则说明无解, 下面也一样); 然后让第一列第i行的组合串长度减去l1就可以得到li了, 并且得到长度的同时我们可以用substr函数得到所有的字符串; 至此我们就得到了目前所有字符串的长度和第一列中1~n的所有字符串, 接下来我们就要去判断这第一列中1~n的所有字符串是否也适用于全部, 对此我们遍历所有组合串看s[i][j]是否等于res[i]+res[j]即可;
此时我们应该注意到一个点, 当我们求l1时做了一个除以(n-2)的操作, 而n的取值是可以为2的, 因此我们要对n=2的情况做一个特殊处理; 并且我们一直没有说多解情况, 这是因为当n大于2时, l1一定可以求出一个确切的值, 也使得所有字符串都有一个确定的值, 因此这样是不存在多解的情况吗, 也就是说多解的情况只会在n=2时存在; 当n=2时只有两个组合串, 设a = s[1][2]和b = s[2][1]; 对此我们可以做b+b的处理; 然后用kmp算法找出a作为子串在b+b中出现了几次; 如果只有一次则是唯一解, 多次就是多解, 0从为无解; 注意这里有一个坑点, 如果a作为子串出现在了b+b的开头或者结尾是不能算作一次, 因为这种处理方法不算是一种解; 具体代码如下, 如果n=2, 则复杂度为O(m);
如果n>2, 复杂度为O(n2);
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int n, m, sum, num;
string s[550][550];
string res[N];
int len[N];
int ne[N];
int check(string a,string b) {
int x;
int len1 = a.size() - 1, len2 = b.size() - 1;
for (int i = 2, j = 0; i <= len2; i++) {
while (j && b[j + 1] != b[i]) j = ne[j];
if (b[j + 1] == b[i]) j++;
ne[i] = j;
}
for (int i = 1, j = 0; i <=len1; i++) {
while (j && b[j + 1] != a[i]) j = ne[j];
if (b[j + 1] == a[i]) j++;
if (j ==len2) {
if (i - len2 != 0&&i!=len1) {
num++;
if (num == 1) x = i - len2 + 1;
}
j = ne[j];
}
}
if(num) return x;
}
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> s[i][j];
if (s[i][j] != "*") sum += s[i][j].size();
}
}
if (n == 2) {
string a = " " + s[1][2] + s[1][2];
string b = " " + s[2][1];
int l1 = check(a, b) - 1;
int l2 = b.size() - 1 - l1;
if (num == 1) {
cout << "UNIQUE" << endl;
cout << a.substr(1, l1) << endl << b.substr(1, l2) << endl;
}
else if (num > 1)cout << "MANY";
else if(num==0)cout << "NONE";
return 0;
}
sum = sum / (2 * (n - 1));
for (int i = 2; i <= n; i++) len[1] += s[i][1].size();
len[1] = (len[1] - sum) / (n - 2);
res[1]= s[1][2].substr(0, len[1]);
if (len[1] == 0) {
cout << "NONE" << endl;
return 0;
}
for (int i = 2; i <= n; i++) {
len[i] = s[i][1].size() - len[1];
res[i] = s[i][1].substr(0, len[i]);
if (len[i] == 0) {
cout << "NONE" << endl;
return 0;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) continue;
if (res[i]+res[j]!=s[i][j]) {
cout << "NONE" << endl;
return 0;
}
}
}
cout << "UNIQUE" << endl;
for (int i = 1; i <= n; i++) {
cout << res[i] << endl;
}
return 0;
}
G - Graduation Guarantee（Gym - 104030G）
难度 ⭐⭐
【题目描述】
古斯塔夫正在学习成为一名口译员。在这一行，掌握多种语言是必须的，古斯塔夫已经精通法语、普通话、纳瓦特尔语，甚至芬兰语。但古斯塔夫有一种语言很困难：挪威语。在古斯塔夫毕业之前，他必须完成臭名昭著的挪威结论性能力检查。该考试由 n 是/否问题组成。回答正确给予 +1 分，回答错误给予 −1 分，不回答给予 0 分。要通过考试，至少需要 k 分。对于每个问题，古斯塔夫都有一个猜测，他知道正确的概率为 pi ( 0.5≤ pi ≤1 )。请注意 pi≥0.5 ，因为否则猜测相反的结果会更好。假设我们仔细选择要回答哪些问题以及不回答哪些问题，通过考试的最大可能概率是多少？请注意，与编程竞赛不同，考试没有即时反馈。因此古斯塔夫将回答问题，提交答案，然后才得知结果。
【题目模型】
给定n个题以及每个题答对的概率, 每个问题答对得一分, 打错扣一分, 也可以不回答; 问最后该怎么处理这些题使得最后获得分数大于等于m的概率最大; n和m都为5e3;
【解题思路】
一道比较明显的线性dp, 因为对于每个题都要选择回答或不回答, 为了提高通过的概率, 我们肯定要优先选择答对概率高的问题回答, 所以我们先将所有问题按照概率从大到小排序; 状态表示dp[i][j]: 表示做了前i道题得到j的概率, 这里的前i道题是排好序后的; 状态计算就是分为加分和减分, 加分: dp[i][j] += dp[i - 1][j - 1] * f[i]; 减分: dp[i][j] += dp[i - 1][j + 1] * (1 - f[i]); 对于不回答的情况, 因为状态表示是做前i道, 那么也就默认后面的题都是选择不回答; 注意分数可能会出现负数, 所以我们让所有分数都加上n以保证不越界即可, 注意数组也要开2倍; 处理完后把做前i道题且分数大于等于m的概率加起来就是回答前i道题通过的概率, 对于每个i取最大值即可; 复杂度为O(n2);
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e3 + 10;
int n, m;
double maxn;
double f[N];
double dp[N][N + N];
bool cmp(double a, double b) {
return a > b;
}
signed main(){
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> f[i];
sort(f + 1, f + 1 + n, cmp);
dp[0][n] = 1;
for (int i = 1; i <= n; i++) {
for (int j = n - i; j <= n + i; j++) {
if (j - 1 >= 0)dp[i][j] += dp[i - 1][j - 1] * f[i];
dp[i][j] += dp[i - 1][j + 1] * (1 - f[i]);
}
}
for (int i = 1; i <= n; i++) {
double res = 0;
for (int j = n + m; j <= 2 * n; j++) {
res += dp[i][j];
maxn = max(maxn, res);
}
}
cout << maxn;
return 0;
}
H - Highest Hill（Gym - 104030H）
难度 ⭐⭐
【题目描述】
与挪威和冰岛等其他 NCPC 国家相比，瑞典可能没有特别令人印象深刻的山脉，但至少比丹麦的平原更胜一筹。但与其他成员国相比，情况并不那么明显。例如，爱沙尼亚的山地比立陶宛多吗（是的，但不是很多！立陶宛的最高点是 Aukštojas 山，海拔 293.84 米，而爱沙尼亚拥有波罗的海的最高峰：Suur Munamägi海拔 318 米。）？为了解决这个问题，您需要确定这两个国家中哪一个拥有最令人印象深刻的山峰。山脉是通过对 n 等距点的高度 hihi 进行采样来定义的。在山脉内，如果 hi≤⋯≤hj≥⋯≥hk ，我们将三重索引 1≤i<j<k≤n称为峰。峰的高度定义为 hj−hi 和 hj−hk 中较小的一个。给定一座山脉，你能找到其最高峰的高度吗？
【题目模型】
先从左端点开始找单调不下降的连续序列确定一个最高点, 然后再往后找单调不上升的连续序列确定右端点; 最高点和左右端点的差值中较小的那个定义为该山峰的高度, 找出所有山峰中的最大值; 序列长度n为2e5;
【解题思路】
先把开头定义为左端点之后往后找, 如果h[i] > h[i - 1]就更新山顶的坐标为i, 如果h[i] < h[i - 1]就更新右端点的坐标为i; 如果h[i] = h[i - 1], 假设现在已经有右端点, 那么接下来更新的就是右端点, 否则就是更新山顶; 对于什么时候确定找到了一个完整的区间, 就是在h[i] > h[i - 1]时, 如果i - 1是当前右端点的坐标, 那说明当前这个单调不上升的连续序列就结束了, 更新最大值, 把i-1这个坐标设为新区间的左端点, i设为新区间的山顶, 右端点初始化即可; 遍历一遍所有高度复杂度为O(n);
题解的方法是开两个数组l[i]和r[i], 分别表示距离i点最远的左端点和右端点, 先正着遍历得到l数组:预处理l[1]=1; 如果h[i] >= h[i - 1], 那么l[i] = l[i - 1]; 否则l[i] = i; 然后反着遍历得到r数组; 最后只需要用maxn = max(maxn, min(h[i] - h[l[i]], h[i] - h[r[i]]))更新最大值即可; 复杂度也是O(n);
神秘代码
//比赛解
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
int h[N];
int n, l, r, maxn;
int res = 0;
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> h[i];
l = 1;
for (int i = 2; i <= n; i++) {
if (h[i] > h[i - 1]) {
if (r == i - 1) {
res = max(res, min(h[maxn] - h[l], h[maxn] - h[r]));
r = 0, l = i - 1;
}
maxn = i;
}
else if (h[i] < h[i - 1]) r = i;
else {
if (r) r = i;
else if (maxn) maxn = i;
}
}
if (r) res = max(res, min(h[maxn] - h[l], h[maxn] - h[r]));
cout << res;
return 0;
}
//题解
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 200000 + 10;
int n, maxn;
int res = 0;
int h[N], l[N], r[N];
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> h[i];
l[1] = 1, r[n] = n;
for (int i = 2; i <= n; i++) {
if (h[i] >= h[i - 1]) l[i] = l[i - 1];
else l[i] = i;
}
for (int i = n-1; i >=1; i--) {
if (h[i] >= h[i + 1]) r[i] = r[i + 1];
else r[i] = i;
}
for (int i = 1; i <= n; i++) {
maxn = max(maxn, min(h[i] - h[l[i]], h[i] - h[r[i]]));
}
cout << maxn;
return 0;
}
I - Icy Itinerary（Gym - 104030I）
难度 ⭐⭐⭐⭐
【题目描述】
这是一个严酷而寒冷的冬天，在一个由 n 房屋组成的小镇里。凌晨时分，大家都在睡觉。除了连接一些房屋的 m 道路外，地面上的积雪很深。只有托马斯醒着。邮递员托马斯需要将邮件递送到镇上的每栋 n 房屋。房屋编号从 1 到 n 。托马斯将从他自己的房子（房子 1 ）开始，然后按某种顺序访问所有其他房子。他可以骑自行车往返于有道路相连的两栋房屋之间，如果房屋之间没有道路，他可以使用滑雪板。但不能在道路上使用滑雪板，也不能在道路外使用自行车。在自行车和滑雪板之间切换是很乏味的，所以托马斯最多只做一次。你的任务是找到 n 房屋的排序 a1,a2,⋯ ,an ，使得 a1=1 ，并且最多有一个索引 i ( 2≤i≤n−1 ) 使得ai−1 和 ai 有道路连接，但 ai 和 ai+1 没有道路连接，或者ai−1 和ai 没有通过道路连接，但 ai 和 ai+1 有道路连接换句话说，序列从 1 开始，最多在使用道路和非道路之间切换一次。
【题目模型】
给定一个无向图, 图不一定是连通的; 现在需要从1号点出发去遍历所有点, 我们可以选择沿着给定边走, 也可以直接从一个点到另一个点; 但这两只状态之间只能转换一次; 即如果我们从走边改为不走边后, 不能再调整为走边, 反过来也一样; 问到达每个点的顺序; n个点, m条边数据范围都是3e5;
J - Junk Journey（Gym - 104030J）
难度 ⭐⭐⭐⭐
【题目描述】
你是 MALL-E，商场滑板车机器人。你的工作是在一天结束时取回所有放错地方的商场踏板车并将它们返回踏板车仓库。商场是一个无限网格，包含 n 需要归还的踏板车。您可以沿四个方向之一移动：上、下、左或右，每个移动需要一秒钟。如果您移动到包含踏板车的位置，该踏板车将按照您移动的方向移动到下一个位置。如果一辆踏板车移动到包含另一辆踏板车的位置，也会发生同样的情况，因此每个位置永远不会有超过一辆踏板车，并且您永远不会占据与踏板车相同的位置。如果踏板车移至踏板车仓库，它就会消失。然而，机器人可以在滑板车车库上自由移动。商场即将开业。您需要找到一种方法，在最多 105 秒内将所有踏板车运送到停车场。
【题目模型】
在一个二维平面上有n个物品和1个仓库, 给定它们的坐标; 现在也给出我们当前的坐标, 我们需要把所有物品都推到仓库里, 推的意思是说让我们以某个方向到达物品的坐标时, 该物品也会沿着这个方向移动一格, 如果我们推的物品也到达某个物品的位置, 那么那个物品也会被推出去, 也就是说我们和物品或者物品和物品都无法处于同一坐标, 但是我们可以一次推多个物品; 每移动一次需要1妙, 给出每一步的方向, 使得最终可以在105秒内把所有箱子推到仓库里; n最多为50, 坐标最大为30;
K - Keyboard Queries（Gym - 104030k）
难度 ⭐⭐⭐⭐⭐
【题目描述】
卡特琳和她的朋友都是大学生，他们每周都会去参加一个研讨会。每次研讨会开始时，教授都会将学生随机分组。 Katrín 和她的朋友们不喜欢随机分组，他们想组成一个小组，这样他们就可以互相聊天，而不是认识其他学生。教授的计算机上有一个由 n 字符组成的秘密字符串 S 。该字符串充当随机组生成的种子。生成组时，程序管理器以 S 子字符串作为输入运行。但有时，教授会打错字，写成“manacher”。这将表明该子字符串是回文。也许卡特琳可以利用这些信息来预测小组划分会是什么样子？1 l r：这意味着 SS 索引 l 到 r 处的子串是回文。2 a b x y：这意味着您应该确定索引 a 到 b 处的子字符串是否等于索引 x 到 y ，给出之前查询中的信息。
【题目模型】
有一个未知的字符串s。给出两种类型的查询：1 l r 表示字符串是回文。2 x y a b 表示如果两个子字符串必须相等则应该回答 n和q为1e5