2020年藍橋杯省賽第二場C++B組題解
2020-10-19 11:00:55
A.
暴力計算即可。
// #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 ans = 0;
int count(int n)
{
int cnt = 0;
while (n)
{
int t = n % 10;
if (t == 2)
cnt++;
n = n / 10;
}
return cnt;
}
int main()
{
#ifdef WXY
freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
IO;
for (int i = 1; i <= 2020; i++)
ans += count(i);
cout << ans;
return 0;
}
624
容易找規律發現相鄰兩項之間的關係。
// #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 main()
{
#ifdef WXY
freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
IO;
int a[50];
int t = 1;
a[1] = 1;
for (int i = 2; i <= 20;i++)
a[i] = a[i - 1] + t * 4, t++;
cout << a[20];
return 0;
}
761
C.
暴力判斷即可。
// #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 gcd(int a, int b)
{
if (b == 0)
return a;
else
return gcd(b, a % b);
}
int main()
{
#ifdef WXY
freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
IO;
int ans = 0;
for (int i = 1; i <= 2020; i++)
for (int j = 1; j <= 2020; j++)
if (gcd(i, j) == 1)
ans++;
cout << ans;
return 0;
}
2481215
D.
比賽的時候因為怕數迷，就沒用日曆表數,現在回想一下真該檢查的時候數一遍。
這題我寫的8880，就是因為列印函數返回值出的鍋（呼叫函數會導致全域性變數改變），但凡當時用變數存一下函數返回值也不會錯了，一念之間。。。省一沒了。。。。
// #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 = 5;
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 == 0 || j == 1)
{
cnt++;
}
w = (w + 1) % 7;
}
}
}
else
{
for (int i = 1; i <= 12; i++)
{
for (int j = 1; j <= m[i]; j++)
{
if (w == 0 || j == 1)
{
cnt++;
}
w = (w + 1) % 7;
}
}
}
if (rui(year))
m[2] -= 1;
return cnt;
}
int main()
{
#ifdef WXY
freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
IO;
int ans = 0;
for (int i = 2000; i <= 2020; i++)
{
// cout << count(i) << endl;
// 一念之間 天堂地獄
// 閒的沒事非列印幹嘛？！
// 列印完了還不註釋掉？！
ans += count(i);
}
cout << ans + 7580 + 1; // 最後再加上10.1這一天
return 0;
}
E.
可以用二維陣列建圖然後跑bfs判斷是否連通。
#include<bits/stdc++.h>
using namespace std;
int dis[6][2] = {1, -1, -1, 1, -1, -1, 1, 1, 2, 0, -2, 0};
struct Node
{
int x, y;
Node(){};
Node(int a, int b)
{
x = a, y = b;
}
};
int g[10][10];
bool book[10][10];
bool vis[10];
int a[10];
int C, ans;
bool BFS(int all)
{
memset(book, false, sizeof book);
int sx, sy;
for (int i = 1; i <= 5; i++)
for (int j = 1; j <= 3; j++)
if (g[i][j] == 1)
{
sx = i, sy = j;
break;
}
queue<Node> q;
q.push(Node(sx, sy));
book[sx][sy] = true;
int cnt = 0;
while (!q.empty())
{
Node now = q.front();
q.pop();
cnt++;
if (now.y == 2)
{
for (int i = 0; i < 4; i++)
{
int tx = now.x + dis[i][0];
int ty = now.y + dis[i][1];
if (tx >= 1 && tx <= 5 && ty >= 1 && ty <= 3 && g[tx][ty] == 1 && book[tx][ty] == false)
{
book[tx][ty] = true;
q.push(Node(tx, ty));
}
}
}
else
{
for (int i = 0; i < 6; i++)
{
int tx = now.x + dis[i][0];
int ty = now.y + dis[i][1];
if (tx >= 1 && tx <= 5 && ty >= 1 && ty <= 3 && g[tx][ty] == 1 && book[tx][ty] == false)
{
book[tx][ty] = true;
q.push(Node(tx, ty));
}
}
}
}
return cnt == all;
}
void draw(int val)
{
if (val == 1)
g[1][2] = 1;
if (val == 2)
g[2][3] = 1;
if (val == 3)
g[4][3] = 1;
if (val == 4)
g[5][2] = 1;
if (val == 5)
g[4][1] = 1;
if (val == 6)
g[2][1] = 1;
if (val == 7)
g[3][2] = 1;
return;
}
void DFS(int now, int sum)
{
if (sum == C)
{
memset(g, 0, sizeof g);
for (int i = 0; i < sum; i++)
draw(a[i]);
if (BFS(sum))
ans++;
return;
}
for (int i = now; i <= 7; i++)
{
if (vis[i] == false)
{
vis[i] = true;
a[sum] = i;
DFS(i + 1, sum + 1);
vis[i] = false;
}
}
return;
}
int main()
{
for (int i = 1; i <= 7; i++)
{
C = i;
DFS(1, 0);
}
cout << ans;
return 0;
}80
F
// #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[6][2] = {1, -1, -1, 1, -1, -1, 1, 1, 2, 0, -2, 0};
int m[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int main()
{
#ifdef WXY
freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
IO;
int n, x;
int cnt1, cnt2 = 0;
char c = '%';
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> x;
if (x >= 60)
cnt1++;
if (x >= 85)
cnt2++;
}
printf("%.0lf", round(100.0 * double(cnt1) / double(n)));
printf("%c\n", c);
printf("%.0lf", round(100.0 * double(cnt2) / double(n)));
printf("%c", c);
return 0;
}
G
當時抽瘋寫了個200+的弱智暴力（還不一定能對），其實只要列舉年份構造出迴文串，然後把符合條件的日期存起來，二分答案即可。
H
太菜了只會暴力做，O（n^3)
I
輸出樣例
當時如果仔細想想，應該能把n<=4的情況暴力模擬出來。。
J
輸出樣例
不出意外，省一應該沒了，還是太菜了。。。。