2020/10/18
上一届蓝桥打了个铁，这届蓝桥的填空题还是蛮开心的，作为一个粗心的人，第一次感受到填空题全对的快感，大题做的马马虎虎，第一题大题没啥好说的；第二题回文日期对于AAAAAAAA是否属于ABABBABA的情况还不清楚；第三题字串序列值菜了。。。比赛沾沾自喜用O（nlogn*26)的复杂度做了出来，结果出来大佬跟我说可以O（n），回看数据好像是1e6，感觉要翻车，希望是1e5的；第四题没判重边，正确性未知，过了样例；第五题随便写了些，过了样例就交了；
许愿省一，希望能改个名！！！！！
废话不多说，这里只写填空题，主要是分享问题和答案，代码非原创（主要是懒），侵删。
A. 门牌制作
问题描述：计算1-2020中出现了多少次2，注意不是多少个数字出现2。
思路：直接计算即可
代码：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int cnt = 0;
for (int i = 1; i <= 2020; i++) {
int x = i;
while (x) {
if (x % 10 == 2) ++cnt;
x /= 10;
}
}
cout << cnt << "\n";
return 0;
}
答案：624
B. 既约分数
问题描述：求多少个分数使得分子和分母的最大公约数为1，且同时分子和分母均在1-2020之间。
思路：直接两层for枚举判断gcd即可
代码：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int cnt = 0;
for (int i = 1; i <= 2020; i++) {
for (int j = 1; j <= 2020; j++) {
if (__gcd(i, j) == 1)
++cnt;
}
}
cout << cnt << "\n";
return 0;
}
答案：2481215
C. 蛇形填数
问题描述：规定一个矩阵如下：
1 2 6 7
3 5 8
4 9
10
问你第20行第20列的多少
思路：可以开个数组，每次斜边顺序或者逆序构造即可
代码：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int x = 1, y = 1;
int a[100][100] = { };
int num = 1;
for (int i = 1; x <= 50; i++) {
for (int j = 0; j < i; j++) {
a[x][y] = num++;
if (j != i - 1) {
if (i & 1) --x, ++y;
else ++x, --y;
}
}
if (i & 1) ++y;
else ++x;
}
cout << a[20][20] << "\n";
return 0;
}
答案：761
D.跑步
问题描述：每个月的第一天或每周的第一天跑2千米，其余天跑1千米，问你2000年1月1日（包含）到2020年10月1日（包含）共跑多少千米。
思路：模拟平闰年的天数，标记它是一周的第几天，计算出有多少天的2千米的，最后用天数+计算的额外天数。
代码：
// #pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <stack>
#include <map>
#include <sstream>
#include <cstring>
#include <set>
#include <cctype>
#include <bitset>
#define IO \ ios::sync_with_stdio(false); \ // cout.tie(0);
using namespace std;
// int dis[8][2] = {0, 1, 1, 0, 0, -1, -1, 0, 1, -1, 1, 1, -1, 1, -1, -1};
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> P;
const int maxn = 2e8 + 10;
const int maxm = 2e5 + 10;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = acos(-1);
int dis[4][2] = { 1, 0, 0, -1, 0, 1, -1, 0};
int m[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int w=6;
bool rui(int n)
{
if(n%400==0||(n%4==0&&n%100!=0))
return true;
return false;
}
int count(int year)
{
int cnt=0;
if(rui(year))
m[2]+=1;
if(year==2020)
{
for(int i=1;i<=9;i++)
{
for(int j=1;j<=m[i];j++)
{
if(w==1||j==1)
{
cnt++;
}
w++;
if(w==8)
w=1;
}
}
}
else
{
for(int i=1;i<=12;i++)
{
for(int j=1;j<=m[i];j++)
{
if(w==1||j==1)
{
cnt++;
}
w++;
if(w==8)
w=1;
}
}
}
if(rui(year))
m[2]-=1;
return cnt;
}
int main()
{
IO;
int ans=0;
for(int i=2000;i<=2020;i++)
{
ans+=count(i);
}
cout<<ans+7580+1;// 还要加上10.1这天
return 0;
}
答案：8879
E.七段码
问题描述：七段数码管的a,b,c,d,e,f,g的七个灯，问你最多可以表示为多少种字符（必须要求灯相连）
思路：先dfs，对于7个灯用0，1表示该灯是否亮，共有（2^7-1)种状态（全灭不算），对于每次dfs的结果进行一次judge；
judge有两种方法：
- 建图，比如a可以到b和f，最后随便从一个亮的点开始跑联通，判断是否所有的点都能跑到。
- 并查集，相邻的灯算一个集合，每次初始化父亲节点为自己，如果一个灯是亮着的，就把他相邻的灯中也亮的灯join到一起，最后判断所有亮着的灯是否都是一个集合的。
代码：
#include <bits/stdc++.h>
using namespace std;
bool light[7];
vector<vector<int> > G(7);
int ans;
bool judge(vector<int> &v1) {
vector<int> v2;
queue<int> que;
bool vis[7] = { };
que.push(v1[0]);
vis[v1[0]] = true;
while (!que.empty()) {
int u = que.front();
que.pop();
v2.push_back(u);
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (find(v1.begin(), v1.end(), v) != v1.end() && !vis[v]) {
que.push(v);
vis[v] = true;
}
}
}
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
return v2 == v1;
}
void dfs(int dep) {
if (dep == 7) {
vector<int> v;
for (int i = 0; i < 7; i++) if (light[i]) v.push_back(i);
if (v.size() && judge(v)) ++ans;
return;
}
light[dep] = true;
dfs(dep + 1);
light[dep] = false;
dfs(dep + 1);
}
void build_graph() {
G[0].push_back(1), G[0].push_back(5);
G[1].push_back(0), G[1].push_back(2), G[1].push_back(6);
G[2].push_back(1), G[2].push_back(3), G[2].push_back(6);
G[3].push_back(2), G[3].push_back(4);
G[4].push_back(3), G[4].push_back(5), G[4].push_back(6);
G[5].push_back(0), G[5].push_back(4), G[5].push_back(6);
G[6].push_back(1), G[6].push_back(2), G[6].push_back(4), G[6].push_back(5);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
build_graph();
dfs(0);
cout << ans << "\n";
return 0;
}
答案：80
