蓝桥省赛模拟
填空题
对于填空题，其实很多时候枚举啊之类的就完事了。但是作为整理，我认为认真的态度是把它当成独立的可以用编程解决的普适的问题来分析，所以下面我会写上每道题的题目改编及思路。
问题描述
将LANQIAO中的字母重新排列，可以得到不同的单词，如LANQIAO、AAILNOQ等，注意这7个字母都要被用上，单词不一定有具体的英文意义。 请问，总共能排列如多少个不同的单词。
答案
$2520$
改编
给定一个字符串，求可以得到的排列数。
戏说
根据组合数学原理，统计不同的字符数$n$，以及不同字符出现的个数$tot[i]$，那么结果即为$\frac{n!}{\prod_{i=1}^n{tot[i]!}}$
问题描述
一个包含有2019个结点的无向连通图，最少包含多少条边？
答案
$2018$
改编一
一个包含有$n$个结点的无向连通图，最少包含多少条边？
戏说
该图应为一条链，边数为$n-1$
改编二
一个包含有$n$个结点的无向连通图，最多包含多少条边？
戏说
该图应为完全图，边数为$\frac{(1+(n-1))(n-1)}{2} = \frac{n(n-1)}{2}$
问题描述
在计算机存储中，12.5MB是多少字节？
答案
$13107200$
戏说
$1\text{MB}=1024\text{KB}=1024*1024\text{B}$
问题描述
由1对括号，可以组成一种合法括号序列：()。 由2对括号，可以组成两种合法括号序列：()()、(())。 由4对括号组成的合法括号序列一共有多少种？
答案
$14$
改编
由$n$对括号组成的合法括号序列一共有多少种？
戏说
这题作为填空题肯定是手动枚举一下就行了。
这里深度为1的序列有一种为：()()()()，深度为2的有7种:(())()()、()(())()、()()(())、(()()())、(()())()、()(()())、(())(())，深度为3的有5种：((()))()、()((()))、((())())、(()(()))、((()()))，深度为4的有1种:(((())))
我知道你一定觉得这中间有什么规律，但是一时半会儿想不出来。注意，规律不是$2^{n-1}$，我一开始枚举漏了，差点写成8。
实际上，这是一个卡特兰$Catalan$数问题。
这里直接给出卡特兰数的定义，即卡特兰数
$Catalan(n+1)=Catalan(0)*Catalan(n)+Catalan(1)*Catalan(n-1)+…+Catalan(n)*Catalan(0)$
其中，$Catalan(0)=1$
带入一下是不是可以算出：
$Catalan(1)=1$
$Catalan(2)=2$
$Catalan(3)=5$
$Catalan(4)=14$
这里便可以用来解决一部分问题了，但这种递推的求法对于$n$较大的情况还是很难处理，即使交给计算机，也容易超时，是否有更好的解法呢？我们可以尝试推一推卡特兰数的通项公式，以这个问题为例：
-
考虑$n$对括号，共有$n$个
(和$n$个)。显然其全排列的个数为$2n\choose n$ -
考虑减法原理，计算非法个数。
-
观察非法排列的特性，我们假设
(为$1$，)为$-1$，那么对于任意一个非法排列$a_1,a_2,…,a_n$ ，一定存在一个$k$,使得$a_1+a_2+…+a_k<0$，即$1\sim k$中，)个数比(个数多 -
考虑一个$n=3$时具体的排列$1,-1,1,-1-1,1$，在$k=5$时，出现了非法情况。我们将$1\sim 5$的每个元素元素翻转，那么该序列就变成了$-1,1,-1,1,1,1$
翻转过后，一共有$n+1$个$1$，$n-1$个$-1$，共有$2n\choose n+1$种。
也就是说，对于一个含$n$个$1$，$n$个$-1$的非法排列，总是存在一个最小的$k$，使得我们对第$1$个到第$k$个元素翻转，就能变成含$n+1$个$1$，$n-1$个$-1$的非法排列。同样，对于含$n+1$个$1$，$n-1$个$-1$的非法排列，也总是存在一个最小的$pos$，使得我们对第$1$个到第$pos$个元素翻转，就能变成含$n$个$1$，$n$个$-1$的非法排列。比如对于非法排列$-1,1,1,1,1,-1$，存在$pos=3$，使得翻转后序列变为$1,-1,-1,1,1,-1$。
-
这意味着所有的含$n+1$个$1$，$n-1$个$-1$的非法排列和含$n$个$1$，$n$个$-1$的非法排列建立了一一对应的关系，所以可以推得，非法排列的个数为$2n\choose n+1$
-
那么对于$n$对括号，合法的排列共有${2n\choose n} - {2n\choose n+1}=\frac{(2n)!}{(n+1)!n!}=\frac{2n\choose n}{n+1}$种
而卡特兰数的通项公式正好对应上述结果，即$Catalan(n)=\frac{2n\choose n}{n+1}$
改编不是乱编，戏说不是胡说。
程序设计题
凯撒密码
问题描述
给定一个单词，请使用凯撒密码将这个单词加密。
凯撒密码是一种替换加密的技术，单词中的所有字母都在字母表上向后偏移3位后被替换成密文。即a变为d，b变为e，…，w变为z，x变为a，y变为b，z变为c。
例如，lanqiao会变成odqtldr。
输入格式
输入一行，包含一个单词，单词中只包含小写英文字母。
输出格式
输出一行，表示加密后的密文。
样例输入
lanqiao
样例输出
odqtldr
评测用例规模与约定
对于所有评测用例，单词中的字母个数不超过100。
思路与代码
利用ASCII值进行变换，注意处理x,y,z，直接给出代码
/**
* @Project lanqiao_provincial_simulation
* @Filename 5
* @Author Visors
* @Date 2020/4/25 8:48
* @Version 1.0
* @Description 凯撒密码
**/
#include <iostream>
#include <string>
using namespace std;
string s;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> s;
int len = s.length();
for (int i = 0; i < len; i++) s[i] = (s[i] + 3 - 'a') % 26 + 'a';
cout << s << endl;
return 0;
}
不用写很多if，一个公式就可以解决了。
本题的一个好的测试方法是，输入abcdefghijklmnopqrstuvwxyz，看看结果是否为defghijklmnopqrstuvwxyzabc
反倍数
问题描述
给定三个整数 a, b, c，如果一个整数既不是 a 的整数倍也不是 b 的整数倍还不是 c 的整数倍，则这个数称为反倍数。
请问在 1 至 n 中有多少个反倍数。
输入格式
输入的第一行包含一个整数 n。
第二行包含三个整数 a, b, c，相邻两个数之间用一个空格分隔。
输出格式
输出一行包含一个整数，表示答案。
样例输入
30
2 3 6
样例输出
10
样例说明
以下这些数满足要求：1, 5, 7, 11, 13, 17, 19, 23, 25, 29。
评测用例规模与约定
对于 40% 的评测用例，1 <= n <= 10000。
对于 80% 的评测用例，1 <= n <= 100000。
对于所有评测用例，1 <= n <= 1000000，1 <= a <= n，1 <= b <= n，1 <= c <= n。
思路与代码
就这个范围，暴力应该就可以了，不过我还是敲了个筛法。最关键的地方是，不要重复统计！
/**
* @Project lanqiao_provincial_simulation
* @Filename 6
* @Author Visors
* @Date 2020/4/25 8:53
* @Version 1.0
* @Description 反倍数
**/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e6 + 5;
int n;
bool book[N]; //记录非反倍数
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
vector<int> v(3);
for (auto &it:v) cin >> it;
sort(v.begin(), v.end()); //对题目的a,b,c从小到大排序，至于为什么，见后面
long long a, b, c; //因为要乘所以开long long，不然如果题目给个1和1000000
// 我的程序就会1000000*1000000导致int溢出
int tot = 0; //统计非反倍数个数
for (int i = 1; i <= n; i++) { //枚举倍数
a = v[0] * i;
b = v[1] * i;
c = v[2] * i;
//cout << a << ' ' << b << ' ' << c << endl;
if (a > n) break; //最小数的倍数都比n大，其它数肯定也大，直接结束
if (a <= n && !book[a]) { //a*i没超界且该数没被记录过（去重）
book[a] = true; //记录
tot++; //非反倍数+1
}
if (b <= n && !book[b]) {
book[b] = true;
tot++;
}
if (c <= n && !book[c]) {
book[c] = true;
tot++;
}
}
cout << n - tot << endl; //总个数-非反倍数个数=反倍数个数
return 0;
}
有点小题大做不是……
螺旋矩阵
问题描述
对于一个 n 行 m 列的表格，我们可以使用螺旋的方式给表格依次填上正整数，我们称填好的表格为一个螺旋矩阵。
例如，一个 4 行 5 列的螺旋矩阵如下：
1 2 3 4 5
14 15 16 17 6
13 20 19 18 7
12 11 10 9 8
输入格式
输入的第一行包含两个整数 n, m，分别表示螺旋矩阵的行数和列数。
第二行包含两个整数 r, c，表示要求的行号和列号。
输出格式
输出一个整数，表示螺旋矩阵中第 r 行第 c 列的元素的值。
样例输入
4 5
2 2
样例输出
15
评测用例规模与约定
对于 30% 的评测用例，2 <= n, m <= 20。
对于 70% 的评测用例，2 <= n, m <= 100。
对于所有评测用例，2 <= n, m <= 1000，1 <= r <= n，1 <= c <= m。
思路与代码
这题数据范围太小，四个while暴力一个一个填数，填到$r$行$c$列即可，下面是随便找的代码（网上博客里面填蛇形矩阵的，如果没记错估计是copy的紫书的）
tot = a[x = 0][y = 0] = 1;
while (tot<n*m)
{
while (y + 1<n&&!a[x][y + 1])a[x][++y] = ++tot;
while (x + 1<m&&!a[x + 1][y])a[++x][y] = ++tot;
while (y - 1 >= 0 && !a[x][y - 1])a[x][--y] = ++tot;
while (x - 1 >= 0 && !a[x - 1][y])a[--x][y] = ++tot;
}
这里只放了核心代码，对于初学者来说可能不太容易懂。我初接触算法竞赛时，看到紫书上这个代码，也有点迷糊（刘汝佳代码都比较精炼）。如果不懂，建议纸上跟着画一画，或者在Excel里面填着看。
不过我还是得整点活，上述代码时间复杂度肯定是$O(nm)$，数据范围再大点呢？显然容易超时。有没有公式可以让我们快速求解呢？
若用$rect[i][j]$表示螺旋矩阵$i$行$j$列的数字，那么对于$n$行$m$列的螺旋矩阵的最外圈，我们可以发现其遵循下面公式：
- $rect[1][j]=j$
- $rect[i][m]=m+i-1$
- $rect[n][j]=n+2*m-2-j+1$
- $rect[i][1]=2*(n+m)-4-i+2$
这只是最外圈的公式，还要不要继续推下去呢？再推太麻烦了，其实一个矩阵可以被拆成$(n+1)/2$个外圈，分治即可。
/**
* @Project lanqiao_provincial_simulation
* @Filename 7
* @Author Visors
* @Date 2020/4/25 9:14
* @Version 1.0
* @Description 螺旋矩阵
**/
#include <iostream>
using namespace std;
int n, m, r, c;
int calc(int row, int col, int i, int j) {
//如果在当前矩阵最外圈，直接公式求解
if (i == 1)
return j;
if (j == col)
return col + i - 1;
if (i == row)
return row + 2 * col - 2 - j + 1;
if (j == 1)
return 2 * (row + col) - 4 - i + 2;
//带着数字进入子矩阵求解
return calc(row - 2, col - 2, i - 1, j - 1) + 2 * (row + col) - 4;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> r >> c;
cout << calc(n, m, r, c) << endl;
return 0;
}
摆动序列
问题描述
如果一个序列的奇数项都比前一项大，偶数项都比前一项小，则称为一个摆动序列。即 a[2i]<a[2i-1], a[2i+1]>a[2i]。
小明想知道，长度为 m，每个数都是 1 到 n 之间的正整数的摆动序列一共有多少个。
输入格式
输入一行包含两个整数 m，n。
输出格式
输出一个整数，表示答案。答案可能很大，请输出答案除以10000的余数。
样例输入
3 4
样例输出
14
样例说明
以下是符合要求的摆动序列：
2 1 2
2 1 3
2 1 4
3 1 2
3 1 3
3 1 4
3 2 3
3 2 4
4 1 2
4 1 3
4 1 4
4 2 3
4 2 4
4 3 4
评测用例规模与约定
对于 20% 的评测用例，1 <= n, m <= 5；
对于 50% 的评测用例，1 <= n, m <= 10；
对于 80% 的评测用例，1 <= n, m <= 100；
对于所有评测用例，1 <= n, m <= 1000。
思路与代码
这题很多人都说是DP，其实也算不上是DP吧，因为递推就可以了，没有什么“决策”可言。
若令$f[m][n]$为长度为$m$，以$n$结尾的方案数，那么有
$f[i][j]=\sum{f[i-1][t]},(t<j)$
对这个式子不理解？看下后面的代码应该就明白了。
很明显我们需要枚举$i$和$j$，并且还要计算$\sum$值，这样做的时间复杂度是$O(mn^2)$，显然超出的范围限制（终于？？）。但无需惊慌，对于连续求和，我们可以用前缀和优化一下，时间复杂度即降到$O(mn)$
/**
* @Project lanqiao_provincial_simulation
* @Filename 8
* @Author Visors
* @Date 2020/4/25 9:27
* @Version 1.0
* @Description 摆动序列
**/
#include<iostream>
using namespace std;
const int N = 1000 + 5, MOD = 10000;
int m, n, ans = 0;
int f[N][N]; //f[i][j]为长度为i，以j结尾的方案数
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> m >> n;
for (int i = 1; i <= n; i++) f[1][i] = 1; //长度为1，以谁结尾都是一种方案，递推起点
for (int i = 2; i <= m; i++) {
int sum = 0;
if (i & 1) { //奇数与1得1
//奇数项，从前开始
for (int j = 1; j <= n; j++) {
//前缀和优化
f[i][j] += sum;
f[i][j] %= MOD;
sum += f[i - 1][j];
sum %= MOD;
}
} else {
//偶数项，从后开始
for (int j = n; j >= 1; j--) {
//前缀和优化
f[i][j] += sum;
f[i][j] %= MOD;
sum += f[i - 1][j];
sum %= MOD;
}
}
}
for (int i = 1; i <= n; i++) {
ans += f[m][i];
ans %= MOD;
}
cout << ans << endl;
return 0;
}
这题是NOIP2013花匠的弱化版，有兴趣可以深入了解一下。
户户通电
问题描述
2015年，全中国实现了户户通电。作为一名电力建设者，小明正在帮助一带一路上的国家通电。
这一次，小明要帮助 n 个村庄通电，其中 1 号村庄正好可以建立一个发电站，所发的电足够所有村庄使用。
现在，这 n 个村庄之间都没有电线相连，小明主要要做的是架设电线连接这些村庄，使得所有村庄都直接或间接的与发电站相通。
小明测量了所有村庄的位置（坐标）和高度，如果要连接两个村庄，小明需要花费两个村庄之间的坐标距离加上高度差的平方，形式化描述为坐标为 (x_1, y_1) 高度为 h_1 的村庄与坐标为 (x_2, y_2) 高度为 h_2 的村庄之间连接的费用为
$$\sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(h_1-h_2)^2}$$
在上式中 sqrt 表示取括号内的平方根。请注意括号的位置，高度的计算方式与横纵坐标的计算方式不同。
由于经费有限，请帮助小明计算他至少要花费多少费用才能使这 n 个村庄都通电。
输入格式
输入的第一行包含一个整数 n ，表示村庄的数量。
接下来 n 行，每个三个整数 x, y, h，分别表示一个村庄的横、纵坐标和高度，其中第一个村庄可以建立发电站。
输出格式
输出一行，包含一个实数，四舍五入保留 2 位小数，表示答案。
样例输入
4
1 1 3
9 9 7
8 8 6
4 5 4
样例输出
17.41
评测用例规模与约定
对于 30% 的评测用例，1 <= n <= 10；
对于 60% 的评测用例，1 <= n <= 100；
对于所有评测用例，1 <= n <= 1000，0 <= x, y, h <= 10000。
思路与代码
吐槽：这是什么魔怔距离计算公式？
不过好在题目“好心”提示了一下，所以问题不大。
读完题目，发现这是一道最小生成树板子题目。你只需，根据魔怔距离公式建出完全图，然后套上最小生成树算法得板子即可。值得注意的是，由于本题是完全图，总共有$\frac{n(n-1)}{2}$条边，属于稠密图确信，由于$prim$算法在稠密图上表现由于$Kruskal$算法，所以我们采用堆优化得$prim$算法（如果不知道为啥要堆优化，可以查阅一下相关资料，这两个算法应该是离散数学里面讲过的）
/**
* @Project lanqiao_provincial_simulation
* @Filename 9
* @Author Visors
* @Date 2020/4/25 9:47
* @Version 1.0
* @Description 户户通电
**/
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
const int N = 1000 + 5;
const double oo = sqrt(10000 * 10000 + 10000 * 10000) + 10000 * 10000 + 5;
int n;
double G[N][N], lowCost[N];
bool book[N];
struct Node {
double x, y, h;
Node() : x(0), y(0), h(0) {}
Node(double x, double y, double h) : x(x), y(y), h(h) {}
} node[N];
struct Elem {
int num;
double dist;
Elem() {}
Elem(int num, double dist) : num(num), dist(dist) {}
//重载<使优先队列为最小堆
bool operator<(const Elem &x) const {
return dist > x.dist;
}
};
priority_queue<Elem> pq;
double prim() {
//初始化
for (int i = 1; i <= n; i++) {
lowCost[i] = G[1][i];
pq.push(Elem(i,lowCost[i]));
}
lowCost[1] = -oo;
double tot = 0.0;
int count = 1;
Elem tmp;
while (1) {
if (count == n) break;
//取有效堆顶，即为最近顶点
while (!pq.empty()) {
tmp = pq.top();
pq.pop();
if (lowCost[tmp.num] != -oo) break;
}
tot += tmp.dist;
lowCost[tmp.num] = -oo;
for (int i = 1; i <= n; i++) {
if (lowCost[i] != -oo && G[tmp.num][i] < lowCost[i]) {
lowCost[i] = G[tmp.num][i];
pq.push(Elem(i,lowCost[i]));
}
}
count++;
}
return tot;
}
int main() {
scanf("%d", &n);
double x, y, h;
for (int i = 1; i <= n; i++) {
scanf("%lf%lf%lf", &x, &y, &h);
node[i] = Node(x, y, h);
}
//建图
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++) {
if (i == j) G[i][j] = 0;
else {
x = (node[i].x - node[j].x) * (node[i].x - node[j].x);
y = (node[i].y - node[j].y) * (node[i].y - node[j].y);
h = (node[i].h - node[j].h) * (node[i].h - node[j].h);
G[i][j] = G[j][i] = sqrt(x + y) + h;
}
}
printf("%.2lf\n",prim());
return 0;
}
因为这是我临场拼的板子，所以可能写的有点过长。
郊外植树
问题描述
小明和朋友们一起去郊外植树，他们带了一些在自己实验室精心研究出的小树苗。
小明和朋友们一共有 n 个人，他们经过精心挑选，在一块空地上每个人挑选了一个适合植树的位置，总共 n 个。他们准备把自己带的树苗都植下去。
然而，他们遇到了一个困难：有的树苗比较大，而有的位置挨太近，导致两棵树植下去后会撞在一起。
他们将树看成一个圆，圆心在他们找的位置上。如果两棵树对应的圆相交，这两棵树就不适合同时植下（相切不受影响），称为两棵树冲突。
小明和朋友们决定先合计合计，只将其中的一部分树植下去，保证没有互相冲突的树。他们同时希望这些树所能覆盖的面积和（圆面积和）最大。
输入格式
输入的第一行包含一个整数 n ，表示人数，即准备植树的位置数。
接下来 n 行，每行三个整数 x, y, r，表示一棵树在空地上的横、纵坐标和半径。
输出格式
输出一行包含一个整数，表示在不冲突下可以植树的面积和。由于每棵树的面积都是圆周率的整数倍，请输出答案除以圆周率后的值（应当是一个整数）。
样例输入
6
1 1 2
1 4 2
1 7 2
4 1 2
4 4 2
4 7 2
样例输出
12
评测用例规模与约定
对于 30% 的评测用例，1 <= n <= 10；
对于 60% 的评测用例，1 <= n <= 20；
对于所有评测用例，1 <= n <= 30，0 <= x, y <= 1000，1 <= r <= 1000。
思路与代码
如何判断两棵树是否干涉，其实就是利用高中学过的圆与圆间位置关系来判断即可，也就是两圆心（种树的位置）间距离小于两圆半径之和即为相交。
这题树很少，直接暴力即可，但纯暴力还是有点吃紧，我们可以稍作剪枝。前面已经说了判断两棵树是否干涉的方法，我们可以考虑预处理任意两树是否发生干涉的数组，在搜索时，一旦出现干涉，立刻返回，即采用可行性剪枝（听说也叫左剪枝，这是根据搜索树形态的变化命名的）。
/**
* @Project lanqiao_provincial_simulation
* @Filename 10
* @Author Visors
* @Date 2020/4/25 10:24
* @Version 1.0
* @Description 郊外植树
**/
#include<iostream>
using namespace std;
const int N = 35;
int n, ans;
int x[N], y[N], r[N];
bool book[N], isIntersect[N][N];
void dfs(int step) {
if (step > n) {
int sum = 0;
for (int i = 1; i <= n; i++)
if (book[i]) sum += (r[i] * r[i]); //PI*r*r/PI
ans = max(sum, ans);
return;
}
book[step] = false;
dfs(step + 1); //不种该树搜
for (int i = 1; i < step; i++)
if (book[i] && isIntersect[i][step]) return; //可行性剪枝
book[step] = true;
dfs(step + 1); //种该树搜
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> x[i] >> y[i] >> r[i];
//判断圆与圆间位置关系
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
isIntersect[i][j] = isIntersect[j][i] = ((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) <
(r[i] + r[j]) * (r[i] + r[j]));
dfs(1);
cout << ans << endl;
return 0;
}
总结
之前以为校赛模拟赛会比较简单，省赛模拟赛会难一些，事实上好像难度接近，甚至这场难度还低于前面某场（之前看星星的题目我线下没写出满分）？所以我估计省赛时也就是这样的难度。也就是说，更多的考察一些数学基础与思维，再带上一些常用算法。
由于蓝桥不能带板子，所以从练习时就要理解所有的算法，以便自己在赛场上能思路清晰的独立敲出来，背代码是吃力不讨好的。推荐备战蓝桥的同学多刷刷蓝桥题库，如果对算法题有进一步兴趣，也可以刷刷leetcode、Codeforces等网站的题目，对以后求职会有很大帮助。也欢迎来参加我们实验室组织的各项比赛XD