2021 天梯赛选拔 / 蓝桥杯热身赛
你好天梯（5分）
Prepared by : Pony
题意：
给出不超过 3 个字符串，排序输出。
解题思路：
简单签到题，排序或手动比较均可。
简单提一下有同学出现的问题，就是字符数组开的不够大，对于长度为 n 的字符串来说，字符数组至少要开到 char[n+1] ，只开 char[n] 的数字的话会爆掉。
有同学没用排序，仅用 if-else 语句来做这道题的话，要注意能否包含到所有情况。
对于 strcmp 这个函数， C 语言只规定了参数 1 大于参数 2 返回正数，参数 1 小于参数 2 返回负数。所以对于不同的编译器，当参数 1 大于参数 2 只保证返回正数，并不保证一定返回 1 ，同样的，参数1小于参数 2 时也不一定返回 -1 。
代码如下：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
string s[10];
for(int i=0;i<n;i++)cin>>s[i];//输入
sort(s,s+n);//排序
for(int i=0;i<n;i++)cout<<s[i]<<endl;//输出
return 0;
}
乖乖站好（10分）
Prepared by : Pony
题意：
给定若干个数字 1,2,12,21 ，可以将部分或全部连接起来，要求相邻两个数字不能相同，求能连成数字段的最长长度。
解题思路：
为了解释方便，设组合 1,2,12,21 的数量分别为 a,b,c,d 。
首先如果 a,b 都为 0 的话，组合 12,21 就不能连在一起，那答案就是 max(2\times c,2\times d) 。
否则如果 a,b 数量相等的话，所有人都可以排上队，那答案就是 a+b+2\times c+2\times d 。
发现由于要求同性不能站在一起，所以排成的队伍之间的男女数量最多相差1，所以其他情况，即 a 和 b 相差大于等于 1 时，答案就是 2\times min(a,b)+1+2\times c+2\times d 。
注意事项：
未考虑到所有情况，或者全 0 ，部分 0 之类的特例。
代码如下：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a,b,c,d;
cin>>a>>b>>c>>d;
//情况一
if(a==0&&b==0)
{
cout<<max(2*c,2*d);
}
//情况二
else if(a==b)
{
cout<<a+b+2*c+2*d;
}
//否则
else
{
cout<<2*min(a,b)+1+2*c+2*d;
}
return 0;
}
伟大的新概念（10分）
Prepared by : Daniel
题意：
给定两个整数 l, r ，找出 [l,r] 之间的回文质数
解题思路：
数据范围比较小，直接枚举 [l,r] 即可所有数，判断其是否为质数，是否为回文即可。
思考：
如果数据范围开到 10^8 应该怎么做呢？
代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
int l, r;
// 判断是否为质数
bool is_prime(int x)
{
if (x < 2) return false;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
return false;
return true;
}
// 判断是否为回文
bool is_palindrome(int x)
{
string s;
while (x)
{
s += (char)(x % 10 + '0');
x /= 10;
}
string t = s;
reverse(t.begin(), t.end());
return s == t;
}
int main()
{
cin >> l >> r;
while (l <= r)
{
if (is_prime(l) && is_palindrome(l)) cout << l << '\n';
l ++ ;
}
return 0;
}
调整缩进（15分）
Prepared by : Pony
题意：
给定若干行字符，每次遇到一对 begin 和 end ，就将它们以及它们中间的所有行缩进两个空格。
解题思路：
首先要说声抱歉，因为数据出锅了，现场改数据，不过幸好是 IOI 赛制，不是 ACM 赛制，影响没这么大。
首先对于一行来说，除了前面的空格多少，是不需要改其他东西，原样输出就行，所以对于以下一行字符（字符中间有空格）：
a a a a
应该输出：
a a a a
而不是：
>a
>a
>a
>a
因此为了处理方便，读入字符串的时候推荐整行读入。
此外，没有仔细理解样例，每行开始的空格应该直接忽略掉，只输出当前需要缩进的空格。
代码如下：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int suojin=0;
string str;
while(getline(cin,str))//输入
{
int len=str.length();
bool firb=1;
for(int i=0;i<len;i++)
{
if(firb)//消前置空格，为缩进添加空格和判断begin和end
{
while(str[i]==' ')i++;
if(i+5==len&&str.substr(i,5)=="begin")
{
suojin+=2;
}
for(int j=0;j<suojin;j++)cout<<' ';
if(i+3==len&&str.substr(i,3)=="end")
{
suojin-=2;
}
firb=0;
}
cout<<str[i];
}
cout<<endl;
// }
}
}
破解序列锁（15分）
Prepared by : Daniel
题意：
给定一个序列，最多只有三种数，每次操作可以调换任意两个数的位置，问最少操作多少次，可以使得序列变为非降序。
解题思路：
首先统计最小值的个数 cnt1 ，次小值个数 cnt2 ，最大值个数 cnt3 。
枚举 [1,cnt1] 位置，若当前数 a_i 不为最小值，那么这个数一定要进行交换，且这个位置应该得到最小值，分两种情况：
- 如果 a_i 为最大值，它最后应该放在 [n-cnt3+1,n] 的某个位置上，若这些位置现在存在一个最小值，那么可以直接换过来，因此应该从后往前找。
- 如果 a_i 为次小值，它最后应该放在 [cnt1+1,cnt1+cnt2] 的某个位置上，若这些位置现在存在一个最小值，那么可以直接换过来，因此应该从前往后找。
做完以上步骤之后， [1,cnt1] 上全是最小值，因此只需检查 [cnt1+1,cnt1+cnt2] 上的数是否全都是次小值，如果发现某个位置上是最大值，那就需要进行一次交换。
代码如下：
#include <iostream>
using namespace std;
const int N = 1010;
int n;
int a[N];
int main()
{
cin >> n;
// 统计出现次数
int cnt1 = 0, cnt2 = 0, cnt3 = 0;
for (int i = 1; i <= n; i ++ )
{
cin >> a[i];
if (a[i] < 0) cnt1 ++ ;
else if (a[i] == 0) cnt2 ++ ;
else cnt3 ++ ;
}
// 将 [1,cnt1] 的位置整理成全为最小值
int res = 0;
for (int i = 1; i <= cnt1; i ++ )
if (a[i] == 0)
{
for (int j = cnt1 + 1; j <= n; j ++ )
if (a[j] < 0)
{
res ++ ;
swap(a[i], a[j]);
break;
}
}
else if (a[i] > 0)
{
for (int j = n; j > cnt1; j -- )
if (a[j] < 0)
{
res ++ ;
swap(a[i], a[j]);
break;
}
}
// 检查 [cnt1+1,cnt1+cnt2] 位置是否全为次小值
for (int i = cnt1 + 1; i <= cnt1 + cnt2; i ++ )
res += (int)(a[i] != 0);
cout << res << '\n';
return 0;
}
植树造林（20分）
Prepared by : Pony
题意：
给定二叉树的前序遍历和后序遍历，求符合条件的二叉树的数量。
解题思路：
对于二叉树来说，前序遍历的顺序是根左右，后序遍历的顺序是左右根。
为了解释方便，我们不妨后序遍历的输出倒过来，那这样对应字符串的遍历顺序就是根右左了。那么对于一个代表根的结点，如果在前序遍历和后序遍历中其后的一个结点是相同的，就代表在输出根结点后，之后无论是先遍历左子树还是右子数，下一个结点是相同的。
而这就表示这个根结点只有一个子树，而这个子树可以作为左子树存在，也可以作为右子树存在，所以遇到这种情况，符合题意的二叉树的数量就要乘 2 。
可以用递归的思路对每个子树用如上的方式计算，也可以不考虑是否为根结点，直接判断相同结点后是否有相同结点，因为如果相同的是叶子结点，之后是不可能有相同结点的。
方法一：
#include<bits/stdc++.h>
using namespace std;
int qian[100005];
int hou[100005];
int qtip[100005];
int htip[100005];
long long ans=1;
void fen(int qb,int hb,int len)
{
while(len>0)
{
if(qian[qb]==hou[hb])//发现前序遍历和后序遍历对应位置相同时
{
ans*=2;
ans%=1000000007;
}
else
{
//分治
fen(qb+1,qtip[qian[qb]]+1,htip[hou[hb]]-qb-1);
fen(htip[hou[hb]]+1,hb+1,qtip[qian[qb]]-hb-1);
return;
}
qb++;
hb++;
len--;
}
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>qian[i];
htip[qian[i]]=i;//预处理某个结点在前序遍历的对应哪个位置
}
for(int i=n-1;i>=0;i--)
{
cin>>hou[i];
qtip[hou[i]]=i;
}
fen(1,1,n-1);
cout<<ans;
}
}
方法二：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
const long long M = 1000000007;
int a[N], b[N], pos[N];
int main()
{
int n;
cin >> n;
long long ans = 1;
for(int i = 0; i < n; i++)
cin >> a[i];
for(int i = 0; i < n; i++) {
cin >> b[i];
pos[b[i]] = i;//预处理结点在后序遍历的哪个位置
}
for(int i = 0; i < n-1; i++) {
if(a[i+1] == b[pos[a[i]]-1])
ans = ans * 2 % M;
}
cout << ans << endl;
return 0;
}
破解矩阵锁（20分）
Prepared by : Daniel
题意：
给定两个 n\times n 的矩阵，以及 7 种转换方式：
- 将矩阵顺时针旋转 90 度；
- 将矩阵顺时针旋转 180 度；
- 将矩阵顺时针旋转 270 度；
- 将矩阵沿着图片的中间垂直线翻转，使其变为自身的镜像；
- 先进行 4 操作，再进行 1\sim 3 的一种操作；
- 不作任何改变；
- 以上所有方式都无效。
问第一个矩阵通过哪种方式转换到第二个矩阵，如果有多种方式，则输出编号较小的序号。
解题思路：
纯模拟，只要会旋转矩阵以及镜像翻转就行，然后按照序号从小到大顺序转换矩阵，每次转换完检查是否与目标矩阵相同即可。
String数组：
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 15;
int n;
// 将矩阵翻转 90 度
void turn90(vector<string> &g)
{
vector<string> t = g;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
t[j][n - i - 1] = g[i][j];
g = t;
}
// 将矩阵镜像翻转
void mirror(vector<string> &g)
{
vector<string> t = g;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
t[i][j] = g[i][n - j - 1];
g = t;
}
int main()
{
cin >> n;
vector<string> a(n), b(n);
for (int i = 0; i < n; i ++ ) cin >> a[i];
for (int i = 0; i < n; i ++ ) cin >> b[i];
vector<string> g = a;
turn90(g);
if (g == b)
{
cout << "1\n";
return 0;
}
turn90(g);
if (g == b)
{
cout << "2\n";
return 0;
}
turn90(g);
if (g == b)
{
cout << "3\n";
return 0;
}
turn90(g);
mirror(g);
if (g == b)
{
cout << "4\n";
return 0;
}
for (int i = 0; i < 3; i ++ )
{
turn90(g);
if (g == b)
{
cout << "5\n";
return 0;
}
}
if (a == b)
{
cout << "6\n";
return 0;
}
cout << "7\n";
return 0;
}
字符数组：
#include <cstring>
#include <iostream>
using namespace std;
const int N = 15;
int n;
char pre[N][N], now[N][N], temp[N][N], g[N][N];
// 将矩阵翻转 90 度
void turn90(char g[][N])
{
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
temp[j][n - i - 1] = g[i][j];
memcpy(g, temp, sizeof temp);
}
// 将矩阵镜像翻转
void mirror(char g[][N])
{
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
temp[i][j] = g[i][n - j - 1];
memcpy(g, temp, sizeof temp);
}
bool check(char a[][N], char b[][N])
{
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
if (a[i][j] != b[i][j])
return false;
return true;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> pre[i];
for (int i = 0; i < n; i ++ ) cin >> now[i];
memcpy(g, pre, sizeof pre);
turn90(g);
if (check(g, now))
{
cout << "1\n";
return 0;
}
turn90(g);
if (check(g, now))
{
cout << "2\n";
return 0;
}
turn90(g);
if (check(g, now))
{
cout << "3\n";
return 0;
}
turn90(g);
mirror(g);
if (check(g, now))
{
cout << "4\n";
return 0;
}
for (int i = 0; i < 3; i ++ )
{
turn90(g);
if (check(g, now))
{
cout << "5\n";
return 0;
}
}
if (check(pre, now))
{
cout << "6\n";
return 0;
}
cout << "7\n";
return 0;
}
周游山区（25分）
Prepared by : Daniel
题意：
n 个加油站形成一个环形，第 i 个油站有 p_i 升油，每升油可以使汽车行驶一公里，第 i 个油站和它顺时针下一个油站距离为 d_i 。
一辆汽车（初始时没有油）从其中一个点出发，每经过一个油站就将油站中所有油都取走（包括起点），问是否能沿着顺时针 或 逆时针环行一周。
解题思路：
如果暴力枚举每个加油站判断的话可以拿到 10 分的部分分，而正解也有多种方法，以下标程使用的是单调队列优化 DP 。
单调队列是一个常用的数据结构，它的作用主要是求长度为 k 的区间最值。
对于环形问题，为了降低思考难度，可以将其“破环成链”，即将序列转化为两倍，如下图：
以顺时针为例，从 i 点能走到 i+1 点，意味着 p_i\geq d_i ，转换一下就是 (p_i-d_i)\geq 0 。从 i 点能走到 i+2 点，意味着 $(p_i-di)+(p{i+1}-d_{i+1})\geq 0$ 且 (p_i-d_i)\geq 0 。
以此类推，从 i 点能顺时针走完一圈，就意味着以下条件同时满足：
- (p_i-d_i) \geq 0
- $(p_i-di)+(p{i+1}-d_{i+1}) \geq 0$
- \dots
- $(p_i-di)+(p{i+1}-d{i+1}) \dots + (p{i+n-2}-d_{i+n-2}) \geq 0$
- $(p_i-di)+(p{i+1}-d{i+1}) \dots + (p{i+n-1}-d_{i+n-1}) \geq 0$
因此就可以求一个 s_i=p_i-d_i 的前缀和来快速判断某段是否大于等于 0 。
我们可以从上图的最后一个数开始枚举，利用单调队列维护 [i,i+n-1] 的前缀和 最小值 ，如果这个最小值都是大于等于 s_{i-1} 的话，那么 i(1\leq i\leq n) 就满足能走完一圈的条件了。
逆时针也是同样的思路，但是细节要改变一下。
比如从 i 点能走到 i-1 意味着 $pi\geq d{i-1} ，因此从 i-n 点（也相当于是从 i$ 点）逆时针走一圈意味着满足以下条件：
- $(pi-d{i-1})\geq 0$
- $(pi-d{i-1})+(p{i-1}-d{i-2})\geq 0$
- \dots
- $(pi-d{i-1})+(p{i-1}-d{i-2})+\dots +(p{i-n+1}-d{i-n})\geq 0$
因此这时前缀和应该是 $s_i=pi-d{i-1} ，且因为以上公式的下标计算是减法，从前往后枚举序列会更方便。因此从 i-n 点能够逆时针走一圈的条件就是 s_i 大于等于 [i-n+1,i-1]$ 的前缀和 最大值 。
代码如下：
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 2000010;
int n;
int p[N], d[N];
int q[N];
LL s[N];
bool st[N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> p[i] >> d[i];
for (int i = 1; i <= n; i ++ ) s[i] = s[i + n] = p[i] - d[i];
for (int i = 1; i <= 2 * n; i ++ ) s[i] += s[i - 1];
int hh = 0, tt = -1;
for (int i = 2 * n; i; i -- )
{
while (hh <= tt && q[hh] - i >= n) hh ++ ;
while (hh <= tt && s[q[tt]] >= s[i]) tt -- ;
q[ ++ tt] = i;
if (i <= n && s[q[hh]] >= s[i - 1]) st[i] = true;
}
// 因为会用到 d[1-1] ，为了方便直接将 d[0]=d[n]
d[0] = d[n];
for (int i = 1; i <= n; i ++ ) s[i] = s[i + n] = p[i] - d[i - 1];
for (int i = 1; i <= 2 * n; i ++ ) s[i] += s[i - 1];
hh = 0, tt = -1;
for (int i = 1; i <= 2 * n; i ++ )
{
while (hh <= tt && i - q[hh] >= n) hh ++ ;
if (i > n && s[q[hh]] <= s[i]) st[i - n] = true;
while (hh <= tt && s[q[tt]] <= s[i]) tt -- ;
q[ ++ tt] = i;
}
for (int i = 1; i <= n; i ++ ) cout << (st[i] ? "YES\n" : "NO\n");
return 0;
}
房屋面积（25分）
Prepared by : Daniel
题意：
给定 n 个矩形，求它们的并集形成的多边形周长。
解题思路：
扫描线裸题，而且数据范围并不大，直接暴力做就行。将和平行于 X 轴与平行与 Y 轴的边分开考虑，先求平行于 X 轴的所有边的长度之和，然后将每个矩形的横纵坐标调换，同样的方法就可以求出平行于 Y 轴的所有边的长度之和，二者之和即为所求。
扫描线算法的思路如下（以求平行于 X 轴的所有边的长度之和为例）：
如下图，将所有出现过的 X 轴坐标存下来，在这些坐标上画一条垂线，将矩形分割，横坐标上被分割的每一段的长度为 x_{i+1}-x_i ，红色为分割线，黄色为所求。
分别处理被分割出来的区间，在 Y 轴上看，将出现在这个区间上的每个矩形的上下纵坐标构成一段线段，然后进行一个区间合并的处理，求出有多少段没有任何重叠的线段，再乘以 X 轴上分割出来的区间长度，因为有上下两条边，因此再乘以 2 。下图以上图的中间部分的区间合并为例，黑色为矩形纵坐标形成的线段。
代码如下：
#include <vector>
#include <iostream>
#include <algorithm>
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 5010, INF = 0x3f3f3f3f;
int n;
struct Rec
{
PII a, b;
} rec[N];
LL get()
{
// 找出所有 x 坐标
vector<int> xs;
for (int i = 0; i < n; i ++ )
{
xs.emplace_back(rec[i].a.F);
xs.emplace_back(rec[i].b.F);
}
sort(xs.begin(), xs.end());
LL res = 0;
for (int i = 0; i < xs.size() - 1; i ++ )
{
// [l, r] 为 x 轴分割出来的区间
int l = xs[i], r = xs[i + 1];
// 在 y 轴上找出所有出现的矩形的竖边
vector<PII> seg;
for (int j = 0; j < n; j ++ )
{
if (rec[j].a.F <= l && rec[j].b.F >= r)
seg.emplace_back(rec[j].a.S, rec[j].b.S);
}
// 区间合并问题，求区间数
sort(seg.begin(), seg.end());
int cnt = 0, L = -INF, R = -INF;
for (auto [x, y] : seg)
if (x > R)
{
cnt ++ ;
L = x, R = y;
}
else R = max(R, y);
res += 2LL * cnt * (r - l);
}
return res;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ )
{
PII a, b;
cin >> a.F >> a.S >> b.F >> b.S;
rec[i] = {a, b};
}
LL res = get();
// 将横纵坐标交换
for (int i = 0; i < n; i ++ )
{
swap(rec[i].a.F, rec[i].a.S);
swap(rec[i].b.F, rec[i].b.S);
}
res += get();
cout << res << '\n';
return 0;
}
U 型锁（30分）
Prepared by : Pony
题意：
请直接浏览 原题 。
解题思路：
可以直接用 O(n^3) 的方法暴力算出 b,c ，并且检验是否符合题意，不过要考虑是否爆 long long 或者精度问题。
此外，可以将U型锁对应公式变个形式： y-x^2=bx+c ，然后将点坐标的y坐标统一变为 y-x^2 。这样原来的二次函数就变成了直线形式的一次函数，原来的问题就变成了典型的求上凸包问题了。求上凸包用 O(nlgn) 的方法就可以解决。
代码如下：
#include<bits/stdc++.h>
using namespace std;
struct Po
{
long long x,y;
Po()
{
}
Po(long long xx,long long yy)
{
x=xx;
y=yy;
}
bool operator <(const Po& po)
{
if(x==po.x)
{
return y>po.y;
}
else return x<po.x;
}
Po operator -(const Po& a)
{
return Po(x-a.x,y-a.y);
}
long long operator *(const Po& a)
{
return x*a.y-y*a.x;
}
};
int main()
{
int n;
cin>>n;
long long x,y;
Po po[1005];
Po sta[1005];
for(int i=0;i<n;i++)
{
cin>>x>>y;
po[i]=Po(x,y-x*x);//对y坐标进行处理
}
//以下就是求上凸包的方法
sort(po,po+n);
int tot=0;
for(int i=0;i<n;i++)
{
if(i>0&&po[i].x!=po[i-1].x||i==0)//避免x坐标相同的情况
{
while(tot>1&&Po(sta[tot-1]-sta[tot-2])*Po(po[i]-sta[tot-2])>=0)
{
tot--;
}
sta[tot++]=po[i];
}
}
cout<<tot-1;
return 0;
}