第十一届蓝桥杯国赛题解
美丽的二
提示：
stl的运用，用string的find函数找一下就可以了
#include <iostream>
#include <string>
using namespace std;
int main() {
int ans = 0;
string year;
for (int i = 1; i < 2021; ++i) {
year = to_string(i);
if (year.find('2') != year.npos) {
ans += 1;
}
}
cout << ans;
return 0;
}
- Ans: 563
扩散
提示：
其实还是stl的应用，会用标准库的话真的挺简单的。主要的思想就是用一个集合来存已经扩散后的格子，一个队列用来存储正在扩散的格子；
#include <iostream>
#include <set>
#include <queue>
using namespace std;
int loc[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};
struct ppair {
int xx; // x坐标
int yy; // y坐标
int ss; // 步数
ppair() {
xx = 0;
yy = 0;
ss = 0;
}
ppair(int x, int y, int s) {
xx = x;
yy = y;
ss = s;
}
};
int main() {
int ans = 4;
set<pair<int, int>> points; // 存储已经扩散的点
queue<ppair> que;
// 将初始点加入队列当中
que.push(ppair(0, 0, 0));
que.push(ppair(2020, 11, 0));
que.push(ppair(11, 14, 0));
que.push(ppair(2000, 2000, 0));
int i, j;
int x, y;
while (!que.empty()) {
ppair point = que.front();
x = point.xx;
y = point.yy;
if (!points.count(make_pair(x, y)) and point.ss <= 2020) {
points.insert(make_pair(x, y));
for (i = 0; i < 4; i++) {
que.push(ppair(x + loc[i][0], y + loc[i][1], point.ss + 1));
}
}
que.pop();
}
ans += points.size();
cout << ans;
}
- Ans: 20312092
阶乘约数
提示：
数论的题目，结论是每一个数都可以被分解为素数的乘积，将素数的乘积的幂次方加一后乘起来；
#include <iostream>
#include <map>
#include <vector>
using namespace std;
bool judge(int n) {
bool re = true;
if (n <= 2) return re;
for (int i = 2; i < n; ++i) {
if (n % i == 0) {
re = false;
break;
}
}
return re;
}
int main() {
vector<int> p;
// 计算100以内的所有素数
for (int i = 2; i <= 100; ++i) {
if (judge(i)) {
p.push_back(i);
}
}
map<int, int> count;
for (int i : p) {
count[i] = 1; // 在初始化的时候就+1
}
for (int i = 2; i <= 100; ++i) {
int num = i;
int j = 0;
while (num != 1) {
if (num % p[j] == 0) {
num = num / p[j];
count[p[j]]++;
} else {
j++;
}
}
}
long long res = 1;
for (int i:p) {
res *= count[i];
}
cout << res;
return 0;
}
- Ans: 39001250856960000
本质上升序列
提示：
动态规划：建立dp数组, dp[i]表示以num[i]为结尾的子序列个数，为什么可以这么想呢？因为我们已经确定了序列的最后一位是
num[i]A: 假如
num[j](j<i)是小于num[i]的, 那么dp[i]=dp[i]+dp[j]就是我们要求的答案。B: 假如
num[j](j<i)是等于num[i]的dp[i]=dp[i]-dp[j], 这是因为该种情况已经被加进去了。为了去重所以是dp[i] - dp[j]
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main() {
string S = "tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl";
int dp[201];
for (int i = 0; i < 201; ++i) {
dp[i] = 1;
}
for (int i = 0; i < S.size(); ++i) {
for (int j = 0; j < i; ++j) {
if (S[i] > S[j]){
dp[i] += dp[j];
}
if (S[i] == S[j]){
dp[i] -= dp[j];
}
}
}
int res = 0;
for (int i = 0; i < S.size(); ++i) {
res += dp[i];
}
cout << res << endl;
return 0;
}
- Ans: 3616159
玩具蛇
提示：
使用dfs进行搜索，如果走了16步了说明是满足题述的一种情况。
#include "iostream"
using namespace std;
// 方向控制
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int a[4][4] = {0};
int n = 0;
// x,y相当于正在放置的格子的坐标
void dfs(int stay, int x, int y) {
int tx, ty;
// 递归终止条件
if (stay == 16) {
n++;
return;
}
// 尝试向四个方向放置
for (int i = 0; i < 4; i++) {
tx = x + dx[i];
ty = y + dy[i];
// 该格子不可放置 或越界 跳过该方向
if (a[tx][ty] == 1 || tx < 0 || tx > 3 || ty < 0 || ty > 3)
continue;
// 对已放置的格子进行标记
a[tx][ty] = 1;
dfs(stay + 1, tx, ty);
// 清除标记
a[tx][ty] = 0;
}
}
int main() {
int i, k;
// 对4x4的格子 枚举玩具蛇第一个步放置的所有可能。
for (i = 0; i < 4; i++) {
for (k = 0; k < 4; k++) {
// 对已放置的格子进行标记
a[i][k] = 1;
dfs(1, i, k);
// 清除标记
a[i][k] = 0;
}
}
cout << n;
return 0;
}
- Ans：552