2020第十一屆藍橋杯第二場省賽C++B組，總結

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有兩種方法：

1. 建圖，比如a可以到b和f，最后隨便從一個亮的點開始跑聯通，判斷是否所有的點都能跑到，
2. 并查集，相鄰的燈算一個集合，每次初始化父親節點為自己，如果一個燈是亮著的，就把他相鄰的燈中也亮的燈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