第十三届蓝桥杯大赛软件赛省赛C/C++ 大学 A 组
本文其他链接
纪念我参加的第一次蓝桥杯
2022年4月9日 9:00 - 13:00
这次蓝桥杯因为疫情，在线上举行听学长学姐们说蓝桥杯又叫“送钱杯”，省一有手就行
那我就在这里先求一个省一吧！
2k 奖学金！求求了！
序
因为鄙人才学不高，所以这份题解中的解法难免有纰漏之处，还望各路神犇指出，鄙人将感激不尽。
题目链接
试题A: 裁纸刀
我的思路
考虑记忆化搜索。后来听说怎么剪都是一样的？？？
记int mem[n][m]为有$n$行$m$列个二维码时，需要剪多少次（不考虑边框）
于是递归公式为
$$
mem[n][m] = \min(\min_{1 \leq i \leq n-1}(mem[i][m]+mem[n-i][m]+1), \min_{1 \leq i \leq m-1}(mem[n][i]+mem[n][m-i]+1))
$$
最后答案是 $mem[20][22] + 4 = 443$
我的代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf = 1 << 30;
int mem[30][30];
int cut(int n, int m)
{
if(n == 1 && m == 1) return 0;
if(mem[n][m]) return mem[n][m];
int r1 = inf;
for(int i = 1; i < n; i++)
r1 = min(r1, cut(i, m) + cut(n-i, m) + 1);
int r2 = inf;
for(int j = 1; j < m; j++)
r2 = min(r2, cut(n, j) + cut(n, m-j) + 1);
return mem[n][m] = min(r1, r2);
}
int main()
{
printf("%d\n", 4 + cut(20, 22));
return 0;
}试题B: 灭鼠先锋
我的思路
这应该就是一个普通的0/1博弈（这个博弈的名字似乎叫sg博弈）
状态一共就$2^8$种，一点也不多。
最后答案应该是LLLV
我的代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int f[300];
int rev(int st)
{
if(f[st]) return f[st];
f[st] = -1;
for(int i = 0; i < 8; i++)
{
if(!(st & (1 << i)))
{
if(rev(st | (1 << i)) == -1)
{
f[st] = 1;
break;
}
}
}
if(f[st] != 1) for(int i = 0; i < 7; i++) if(i != 3)
{
if(!(st & (3 << i)))
{
if(rev(st | (3 << i)) == -1)
{
f[st] = 1;
break;
}
}
}
return f[st];
}
int main()
{
f[0xff] = 1;
//这里取负是因为，先手已经下过了，所以就后手赢先手就输，后手输先手就赢
printf("%d\n", -rev(0b10000000));
printf("%d\n", -rev(0b11000000));
printf("%d\n", -rev(0b01000000));
printf("%d\n", -rev(0b01100000));
return 0;
}试题C: 求和
我的思路
签到题，预处理sum就可以了（而且这题还良心的不会爆long long），复杂度$O(n)$
我的代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 10;
int n, a[maxn];
long long sum_ = 0;
long long ans = 0;
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%d", &a[i]);
for(int i = 0; i < n; i++)
sum_ += a[i];
for(int i = 0; i < n; i++)
ans += a[i] * (sum_ - a[i]);
ans /= 2;
printf("%lld\n", ans);
return 0;
}试题D: 选数异或
我的思路
这个题考场上想了好久好久，最后居然还是只写了一个$O(n^2m)$的暴力，只能得2分，我人傻了
之后突然发现可以离线……
于是对每个询问的r排序，这个题就解决了
具体来说，就是开一个map<int,int> mp来存数字x出现的最晚的位置（由于$a_i\leq 2^{20}$所以直接开数组也可以）
再令int near为最近的可以满足要求的位置，初始化为0
然后从0开始遍历整个数列，每次遍历时更新near = max(near, mp[a[i]^x])，然后更新mp[a[i]] = i，然后处理所有r == i的询问，使得他们的答案ans = (l >= near)
我的代码
#include <map>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define yesno(x) \
do { \
if(x) printf("yes\n"); \
else printf("no\n"); \
} while(0)
const int maxn = 1e5 + 10;
map<int, int> mp;
int n, m, x, a[maxn];
struct Ques
{
int l, r, id;
bool ans;
}q[maxn];
bool cmp_1(const Ques& p, const Ques& q)
{
return p.r < q.r;
}
bool cmp_2(const Ques& p, const Ques& q)
{
return p.id < q.id;
}
int main()
{
scanf("%d%d%d", &n, &m, &x);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for(int i = 0; i < m; i++)
{
scanf("%d%d", &q[i].l, &q[i].r);
q[i].id = i;
}
sort(q, q+m, cmp_1);
int ptr = 0, near = 0;
for(int i = 0; i < m; i++)
{
while(ptr <= q[i].r)
{
near = max(near, mp[a[ptr] ^ x]);
mp[a[ptr]] = ptr;
ptr++;
}
q[i].ans = (near >= q[i].l);
}
sort(q, q+m, cmp_2);
for(int i = 0; i < m; i++)
{
yesno(q[i].ans);
}
return 0;
}试题E: 爬树的甲壳虫
我的思路
期望dp
其实也不是dp
就是一个单纯的递推式：
$$E(k) = P(k)*E(0) + (1-P(k))*E(k+1) + 1$$
显然要逆向计算。
注意到逆向计算时E(0)是未知的，但是始终只会出现一次项
不妨直接开一个结构体（或者pair）来表示期望，结构体中就存两个数：
一个是E(0)的系数，还有一个是常数
最后就递推得到关于E(0)的一个一次方程，就能求出E(0)了
另外就是常规的小费马定理求分数取模
我的代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int modp = 998244353;
int qpow(int base, int exp)
{
if(!exp) return 1;
if(exp & 1) return base * 1ll * qpow(base * 1ll * base % modp, exp >> 1) % modp;
return qpow(base * 1ll * base % modp, exp >> 1);
}
const int maxn = 1e5 + 10;
int n, P[maxn];
struct ANS
{
int r, t; // r是系数，t是常数；为什么用这两个字母？我乱选的
ANS() {}
ANS(int _r, int _t) { r = _r; t = _t; }
ANS operator * (const int ot) const
{
return ANS(r * 1ll * ot % modp, t * 1ll * ot % modp);
}
ANS operator + (const ANS &ot) const
{
return ANS((r + ot.r) % modp, (t + ot.t) % modp);
}
} ans[maxn];
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
int a, b;
scanf("%d%d", &a, &b);
P[i] = a * 1ll * qpow(b, modp - 2) % modp;
}
ans[n] = ANS(0, 0);
for(int k = n - 1; k >= 0; k--)
{
ans[k] = ANS(P[k], 0) + ans[k+1] * ((1 - P[k] + modp) % modp) + ANS(0, 1);
}
printf("%lld\n", ans[0].t * 1ll * qpow((1 - ans[0].r + modp) % modp, modp - 2) % modp);
return 0;
}试题F: 青蛙过河
我的思路
显然二分答案，关键是怎么进行check
这里我是贪心做的，不知道对不对。
也就是说每次都尽量往最远的地方跳
我的代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 10;
int n, x, h[maxn], h_copy[maxn];
long long cnt[maxn];
inline bool check(int y)
{
for(int i = 1; i < n; i++)
h_copy[i] = h[i];
int far = n - 1; // 用来记录当前可以到达的最远的地方
for(int i = n - 1; i > 0; i--)
{
cnt[i] = 0; // 考试的时候没写！我肯定寄了……
if(i + y >= n)
{
cnt[i] = h_copy[i];
continue;
}
far = min(far, i + y);
while(far > i)
{
if(cnt[far] <= h_copy[i])
{
h_copy[i] -= cnt[far];
cnt[i] += cnt[far];
cnt[far] = 0;
far--;
}
else
{
cnt[far] -= h_copy[i];
cnt[i] += h_copy[i];
h_copy[i] = 0;
break;
}
}
}
cnt[0] = 0;
for(int i = 1; i <= y; i++)
cnt[0] += cnt[i];
return cnt[0] >= 2 * x;
}
int main()
{
scanf("%d%d", &n, &x);
for(int i = 1; i < n; i++)
scanf("%d", &h[i]);
int l = 1, r = n;
while(l != r)
{
int mid = l + r >> 1;
if(check(mid))
r = mid;
else
l = mid + 1;
}
printf("%d\n", l);
return 0;
}后记
2022年4月9日 20:55
写这篇题解的时候发现F题忘记初始化肯定寄了，我瞬间裂开，所以后面的题就以后再说吧
–5d0b1a2d16c037fa9bbee561047fb875–
