整体而言偏简单，没有考察高级的算法和数据结构。（当然也许是我不会用...），只能保证样例能过，如果有什么问题欢迎交流。
T1 送分题
15.125GB是多少MB
ans = 15.125 * 1024 = 15488
T2 水题
1200000有多少个约数，只算正的
循环跑一跑就ok了，约数的含义是：如果一个数能够被另一个数整除，另一个数就是这个数的约数。比方说6可以被1，2，3，6整除，那么这四个数就是6的约数。
#include<iostream>
using namespace std;
int cnt = 0;
int main() {
int a = 1200000;
for(int i = 1; i <= a ; ++i) {
if(a % i == 0)
cnt ++;
}
cout << cnt << endl;
return 0;
}
T3 基本概念
有2019个节点的二叉树，最多有多少个叶子节点
最多的叶子节点，那就是完全二叉树，因为二叉树有一个性质：\(n_0=n_2+1\)，如果叶子节点最多说明度为2的节点最多，那就是完全二叉树了，完全二叉树算叶子节点的公式：\(n_0=\left( n+1 \right) /2\)。所以最后的结果是1010。
T4 模拟
1到2019中，统计包含数字9的个数
去年蓝桥杯的原题，直接模拟就行了。
#include<iostream>
using namespace std;
int cnt;
bool is_ans(int i) {
int x;
while(i) {
x = i % 10; //分别模拟个位百位千位...
if(x == 9)
return true;
i /= 10;
}
return false;
}
int main() {
for(int i = 1; i <= 2019 ; i++) {
if(is_ans(i)) { //如果包含9
cnt ++; //记录+1
}
}
cout << cnt;
return 0;
}
T5 模拟
小明对类似于 hello这种单词非常感兴趣，这种单词可以正好分为四段，第一段由一个或多个辅音字母组成，第二段由一个或多个元音字母组成，第三段由一个或多个辅音字母组成，第四段由一个或多个元音字母组成。
给定一个单词，请判断这个单词是否也是这种单词，如果是请输出yes，否则请输出no。
元音字母包括a,e,i,o,u共五个，其他均为辅音字母。
输入：一个单词，只含小写字母
输出：如果满足上述输出yes，不满足输出no
这个题直接模拟，首先用string保存这个单词，然后遍历，将元音字母变成y，辅音字母变成f。第二遍遍历，如果发现前一个字符和后一个字符不同，计数+1。如果第一个字符是y，输出no，如果计数正好为3，输出yes。 talk is cheap, show my code.
#include<iostream>
#include<string>
using namespace std;
char yuanyin[5] = {'a', 'e', 'i', 'o', 'u'};
bool is_yuanyin(char a) { //判断字符a是否为元音
for(int i = 0 ; i < 5 ; ++i) {
if(a == yuanyin[i])
return true;
}
return false;
}
int main() {
string word;
cin >> word;
int num = 0; //表示次数
bool state = false; //表示初始状态，为false为辅音
for(int i = 0 ; i < word.length() ; ++i) {
if(is_yuanyin(word[i])) {
word[i] = 'y';
} else
word[i] = 'f';
}
if(word[0] == 'y') {
cout << "no" << endl;
return 0;
}
int len = word.length();
for(int i = 1 ; i < len ; ++i) {
if(word[i] != word[i - 1]) {
num ++;
}
}
if(num == 3) //如果恰好转换了三次，输出yes
cout << "yes";
else
cout << "no";
return 0;
}
时间复杂为\(O\left( n \right) \)，常系数估计会有点大，不过单词中的字母个数不超过100肯定应该是没啥问题了。（题目中没给限定时间有点坑，另外我还没见过20个字母以上单词😄）
T6 暴力模拟
在数列\(a\left[ 1 \right] ,a\left[ 2 \right] ,…,a\left[ n \right]\) 中，如果对于下标\(i,j,k\)满足\(0<i<j<k<n+1\)且\(a\left[ i \right] <a\left[ j \right] <a\left[ k \right]\) ，则称\(a\left[ i \right] ,a\left[ j \right] ,a\left[ k \right]\) 为一组递增三元组，\(a\left[ j \right]\) 为递增三元组的中心。给定一个数列，请问数列中有多少个元素可能是递增三元组的中心。
对于 50% 的评测用例，\( 2<=n<=100 \) \( 0<=Num<=1000 \) 。
对于所有评测用例， \( 2<=n<=1000 \) \( 0<=Num<=10000 \) 。
直接三重循环暴力枚举
#include<cstdio>
using namespace std;
int a[1005] , cnt;
bool vis[1005];
int main () {
int n;
scanf("%d" , &n);
for(int i = 0 ; i < n ; ++i) {
scanf("%d" , a + i);
}
for(int i = 0 ; i < n - 2 ; ++i) {
for(int j = i + 1 ; j < n - 1 ; ++j) {
for(int k = j + 1 ; k < n ; ++k) {
if(!vis[j] && a[i] < a[j] && a[j] < a[k]){
cnt ++;
vis[j] = true;
}
}
}
}
printf("%d" , cnt);
return 0;
}
这道题估计只能拿一大半的分，时间复杂度为\(O\left( n^3 \right) \)，问题规模最大为10的三次方。所以总共运行的次数大概需要10的9次方，计算机一秒可以处理10的8次方到9次方的数，所以有些点可能过不了。
T7 模拟
一个正整数如果任何一个数位不大于右边相邻的数位，则称为一个数位递增的数，例如 1135 是一个数位递增的数，而 1024不是一个数位递增的数。 给定正整数 \( n \)，请问在整数 1 至 \( n \) 中有多少个数位递增的数？
输入的第一行包含一个整数 \( n \)
输出一行包含一个整数，表示答案。
对于 40%的评测用例，\( 1<=n<=1000 \)
对于 80% 的评测用例， \( 1<=n<=100000 \)
对于所有评测用例，\(1<=n<=1000000\)
和T4一样，将数字拆分然后比较
#include<iostream>
using namespace std;
bool is_increase(int i) {
int x = 10;
while(i) {
if(x >= i % 10) {
x = i % 10;
i /= 10;
}
else
return false;
}
return true;
}
int n, cnt;
int main() {
cin >> n;
for(int i = 1 ; i <= n ; ++i) {
if(is_increase(i)) {
cnt++;
}
}
cout << cnt << endl;
return 0;
}
时间复杂度为\(O\left( n^2 \right) \)，还是只能拿一点分。
T8 dfs
小明想知道，满足以下条件的正整数序列的数量。
1、第一项为\(n\) 2、第二项不超过 \(n\) 3、从第三项开始，每一项小于前两项的差的绝对值。
计算，对于给定的 \(n\) ，有多少种满足条件的序列。
输入：一个整数 \(n\)
输出：一个整数，表示答案，可能很大，输出除以10000的余数
对于 20% 的评测用例，\(1<=n<=5\)
对于 50%的评测用例，\(1<=n<=10\)
对于 80%的评测用例，\(1<=n<=100\)
对于所有评测用例，\(1<=n<=1000\)
这道题应该是用动态规划做，我不会...最后还是用的dfs来搜索，暴力dfs能过50%的数据，如果剪纸应该可以过80%，但是剪枝我学的很菜所以也没用上（tcl），如果剪枝成功的话，可以打表。。。
第一项是题目给的：\(n\)，第二项就是从1到\(n\)，第三项是从1到abs(前两项的差)，abs表示绝对值，递归边界就是这个差小于1。
#include<iostream>
#include<cmath>
using namespace std;
int cnt, a[1005];
void dfs(int x , int y) { //分别表示前一项和当前项
cnt ++;
int subtract = abs(x - y);
if(subtract < 1)
return;
for(int k = 1; k < subtract ; ++k)
dfs(y, k);
}
int main() {
int n;
cin >> n;
for(int i = 1 ; i <= n ; ++i)
dfs(n, i);
cout << cnt % 10000 << endl;
return 0;
}
递归的时间复杂度用主定理推，这里推不推都无所谓了。。（要开始好好学剪枝和动规了）
T9 bfs
小明有一块空地，他将 他将这块空地划分为\(n\)行\( m \)列的小块，每行和每列的长度都为 1，小明选了其中的一些小块空地，种上了草，其他小块仍然保持是空地。 这些草长得很快，每个月，草都会向外长出一些，如果一个小块种了草，则它将向自己的上、下、左、右四小块空地扩展，这四小块空地都将变为有草的小块。 请告诉小明，\(k\) 个月后空地上哪些地方有草。
输入：第一行包含\(n\)和 \(m\) ，接下来的 \(n\) 行和 每行\(m\)个字母，表示空地的状态，如果为点表示为空地，如果为g表示长草。接下来的一行包含一个整数\(k\)。
输出：将 \(k\) 个月后的空地输出
对于30%的数据，\(2<=n, m<=20\)。
对于70%的数据，\(2<=n, m<=100\)。
对于所有的额数据，\(2<=n, m <= 1000, 1<=k<=1000\)。
地图题一般用dfs或者bfs，显然这个题是每个月扩散一圈，所以就是bfs了。模板题，唯一需要注意的是，刚开始就需要将所有的起点均加入到队列中，而且标记访问过。（如果你对dfs和bfs不熟悉的可以看看蓝桥杯省赛训练中的内容，讲的很不错）
#include<iostream>
#include<queue>
using namespace std;
char maze[1005][1005];
bool vis[1005][1005];
int dir[4][2] = {{1,0} , {-1,0} , {0,1} , {0,-1}};
int n , m , k;
struct node {
int x, y , time;
node (int xx , int yy, int tt) {
x = xx;
y = yy;
time = tt;
}
};
queue <node> q;
void bfs() {
int dx, dy;
while(q.size()) {
node now = q.front();
q.pop();
if(now.time == k) //如果到达了第k个月，则退出
break;
for(int i = 0 ; i < 4; ++i) { //邻居入队
dx = now.x + dir[i][0];
dy = now.y + dir[i][1];
if(0 <= dx && dx < n && 0 <= dy && dy < m) {
maze[dx][dy] = 'g';
if(!vis[dx][dy])
q.push(node(dx, dy, now.time + 1));
}
}
}
}
int main() {
cin >> n >> m;
for(int i = 0 ; i < n ; ++i) {
for(int j = 0 ; j < m ; ++j) {
cin >> maze[i][j];
if(maze[i][j] == 'g') {
vis[i][j] = true;
q.push(node(i, j, 0)); //将起点均加入队列
}
}
}
cin >> k;
bfs();
for(int i = 0 ; i < n ; ++i) {
for(int j = 0 ; j < m ; ++j) {
cout << maze[i][j];
}
cout << endl;
}
return 0;
}
时间复杂度为\(O\left( n*m \right) \)，如果细节不出错的话满分应该没啥为题。
T10 贪心？
小明要组织一台晚会，总共准备了 \(n\)个节目。然后晚会的时间有限，他只能最终选择其中的 \(m\) 个节目。 这 \(n\) 个节目是按照小明设想的顺序给定的，顺序不能改变。 小明发现，观众对于晚上的喜欢程度与前几个节目的好看程度有非常大的关系，他希望选出的第一个节目尽可能好看，在此前提下希望第二个节目尽可能好看，依次类推。 小明给每个节目定义了一个好看值，请你帮助小明选择出 \(m\) 个节目，满足他的要求。
输入：第一行两个整数 \(n\) 和 \(m\) ，表示节目的数量和要选择的数量。
第二行包含 \(n\) 个整数，依次为每个节目的好看值。
输出：包含 \(m\) 个整数，为选出的节目的好看值。
由于最近几天一直在研究各种背包问题，看这个题的第一眼觉得应该是01背包的变体，物品种数为 \(n\)，背包容量为\(m\) ，每个物品的价值就是节目的好看值，物品重量都为1。但是这个和普通01背包不同的是，这道题需要输出具体有哪些物品，而我之前看的基本都是输出最大价值，思考了很久。然后看到了“ 选出的第一个节目尽可能好看，在此前提下希望第二个节目尽可能好看 ”，才意识到应该用贪心的思想，先取最大的、再取第二大的......这样一想之后就很容易了。
我这里使用优先级队列来进行维护：
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int a[100005];
bool vis[100005];
priority_queue<int> pq;
int main () {
int m , n;
cin >> n >> m;
for(int i = 0 ; i < n ; ++i) {
cin >> a[i];
pq.push(a[i]);
}
while(m--) {
int t = pq.top();
for(int i = 0 ; i < n ; ++i) {
if(t == a[i]) {
vis[i] = true;
break;
}
}
pq.pop();
}
for(int i = 0 ; i < n ; ++i) {
if(vis[i]) {
cout << a[i] << " ";
}
}
return 0;
}
需要注意的是，输出顺序要按照输入的序列顺序，所以我这里用了一个vis数字来判定这个节目有没有被选。
总结：其实题目难度都不大，最复杂的也就是dfs、bfs。但是主要考察的是优化算法的能力。
Comments NOTHING