文章目录
- A: 带宽 25
- B: 纯质数 1903
- C: 完全日期 977
- D: 最小权值 2653631372
- E: 大写
- F: 123
- G: 异或变换（候补）
- H: 二进制问题
- I: 反转括号序列（候补）
- J: 异或三角形（候补）
- 总结
A: 带宽 25
B: 纯质数 1903
考场上用的欧拉筛，这里用埃氏筛。
#include <bits/stdc++.h>
using namespace std;
const int N = 20210606;
bool vis[N];
vector<int> primes;
void init()
{
int i;
for (i = 2; i < N; ++i) {
if (!vis[i]) primes.push_back(i);
for (int j = 0; i*primes[j] < N; ++j) {
vis[i*primes[j]] = 1;
if (i%primes[j] == 0) break;
}
}
}
int main()
{
init();
int ans = primes.size();
for (auto x : primes) {
while (x) {
int t = x%10;
if (t != 2 && t != 3 && t != 5 && t != 7) {
--ans; break;
}
x /= 10;
}
}
cout << ans; // 1903
return 0;
}
C: 完全日期 977
不熟悉 p y t h o n python python 的日期类，怕用错，于是手动模拟日期变化。
#include <bits/stdc++.h>
using namespace std;
class Date
{
int y, m, d;
public:
Date(int y, int m, int d) : y(y), m(m), d(d) {}
void add() {
int nums[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
if (y%400 == 0 || y%100 && y%4 == 0) ++nums[2];
if (++d > nums[m]) {
d = 1;
if (++m > 12) m = 1, ++y;
}
}
bool operator == (const Date &t) const {
return y == t.y && m == t.m && d == t.d;
}
bool valid() {
auto sum = [] (int x) {
int ret = 0;
while (x) ret += x%10, x /= 10;
return ret;
};
int t = sum(y)+sum(m)+sum(d);
int i = 0;
while (i*i < t) ++i;
return i*i == t;
}
};
int main()
{
Date s(2001, 1, 1), t(2022, 1, 1);
int ans = 0;
while (!(s == t)) {
ans += s.valid();
s.add();
}
cout << ans; // 977
return 0;
}
D: 最小权值 2653631372
题目直接给出状态转移方程，感觉 d p dp dp 的暗示还是蛮明显的。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL dp[2022];
int main()
{
for (int i = 1; i <= 2021; ++i) {
dp[i] = LLONG_MAX;
for (int j = 0; j < i; ++j) {
dp[i] = min(dp[i], 1+2*dp[j]+3*dp[i-1-j]+j*j*(i-1-j));
}
// cout << dp[i] << ' ';
}
cout << dp[2021] << endl; // 2653631372
return 0;
}
E: 大写
国赛遇上这种题应该挺难得吧。
#include <bits/stdc++.h>
using namespace std;
int main()
{
char c;
while (cin >> c) cout << char((c | 0x20) ^ 0x20);
return 0;
}
F: 123
这题公式其实蛮好推的。
只要知道
∑
i
=
1
n
i
=
n
(
n
+
1
)
2
,
∑
i
=
1
n
i
2
=
n
(
n
+
1
)
(
2
n
+
1
)
6
\sum_{i=1}^n i=\frac{n(n+1)}{2},\ \sum_{i=1}^n i^2=\frac{n(n+1)(2n+1)}{6}
∑i=1ni=2n(n+1), ∑i=1ni2=6n(n+1)(2n+1) 即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL calc(LL j) { return (j*(j+1)*(2*j+1)/6 + j*(j+1)/2)/2; }
LL solve(LL n) // 计算 1...n 项和
{
LL j = (sqrt(8*n+1)-1)/2;
LL res = n - j*(j+1)/2;
assert(res <= j);
return calc(j) + res*(res+1)/2;
}
int main()
{
LL T;
cin >> T;
while (T--) {
LL l, r;
cin >> l >> r;
cout << solve(r) - solve(l-1) << endl;
}
return 0;
}
/*
3
1 1
1 3
5 8
*/
G: 异或变换（候补）
没找到规律，只做了 40% 的子任务。
H: 二进制问题
这是很裸的数位 d p dp dp 吧。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL dp[100][2][100]; // 长度为i 首位为j 二进制中含k个1 dp代表满足条件的个数
void init()
{
dp[1][0][0] = dp[1][1][1] = 1;
for (int i = 2; i < 80; ++i) {
for (int k = 0; k <= i; ++k) {
dp[i][0][k] = dp[i-1][0][k] + dp[i-1][1][k];
if (k > 0) dp[i][1][k] = dp[i-1][0][k-1] + dp[i-1][1][k-1];
// cout << dp[i][0][k] << ',' << dp[i][1][k] << ' ';
}
// cout << endl;
}
}
int digit[100];
int len = 0;
LL calc(LL n, LL k) // 1..n中有多少个满足条件的数
{
LL t = n;
while (t) {
digit[++len] = t&1; t >>= 1;
}
LL ans = 0;
for (int i = len; i >= 1; --i) {
if (i == 1) {
ans += dp[i][ digit[i] ][k];
}
if (digit[i]) {
ans += dp[i][0][k];
--k;
}
}
return ans;
}
int main()
{
init();
LL n, k;
cin >> n >> k;
cout << calc(n, k);
}
I: 反转括号序列（候补）
很明显的线段树特征，不过还是没能想到怎么写，只做了 20% 的子任务。
J: 异或三角形（候补）
没想到思路，只做了 20% 的子任务。
总结
这是我本科第一次参加蓝桥杯，我想大概也是最后一次了。
感觉自己还是一如既往地菜，希望以后能不忘初心，继续学习。
如果研究生阶段还有机会参加蓝桥杯的话，希望到时候也可以向那些大佬一样骄傲地说出蓝桥杯 “有手就行、点击就送” 吧。