蓝桥杯双周赛 第 16 场 小白入门赛 解题报告 | 珂学家 | 七夕娱乐场

---

前言

---

题解

因为这场七夕节，所以出的特别友好。

整体还是偏思维。

T6 额外提供组合数学解，还是蛮有趣的。

---

A. 喜鹊罢工

题型: 签到

$$365可以有多少个7组成$$

向上取整即可

#include <iostream>using namespace std;int main()
{cout << ((365 + 6) / 7) << endl;return 0;
}

---

B. 牛郎取名

思路: 模拟

对字符进行按序重排，考察字符串API知识点。

#include <bits/stdc++.h>using namespace std;int main()
{int n;string s;cin >> n >> s;string r;for (int i = 0; i < n; i++) {int p; cin >> p;r.push_back(s[p - 1]);}cout << r << endl;return 0;
}

---

C. 织女的考验

思路: 找规律

可以把字符串拍平为 26维的向量

那么两个字符串能否相等(彼此各删除1个字符)，在于这2个向量 差异 要么为0，要么为2

$$diff=\sum _{i=0}^{i=25}abs(v_1(i)-v_2(i))$$

这样的时间复杂度为$O(n+26)$

#include <bits/stdc++.h>using namespace std;int main()
{int t;cin >> t;while (t-- > 0) {string s1, s2;cin >> s1 >> s2;// 向量化vector<int> h1(26), h2(26);for (char c: s1) h1[c - 'a']++;for (char c: s2) h2[c - 'a']++;// 求向量差int diff = 0;for (int i = 0; i < 26; i++) {diff += abs(h1[i] - h2[i]);}if (diff == 0 || diff == 2) {cout << "YES\n";} else {cout << "NO\n";}}return 0;
}

当然这题，也可以大模拟，在构建26维向量后，枚举去掉的字符

然后对比是否相同

---

D. 仙男仙女

思路: 模拟

需要注意的是，给出的坐标并不是按序的，需要额外排序下。

然后模拟即可，即比对前一位/后一位的差值。

#include <bits/stdc++.h>using namespace std;int main()
{int n;cin >> n;vector<array<int, 2>> arr(n);for (int i = 0; i < n; i++) {cin >> arr[i][0];}for (int i = 0; i < n; i++) {cin >> arr[i][1];}sort(arr.begin(), arr.end());int res = 0;for (int i = 0; i < n; i++) {bool c1 = (i == 0 || arr[i][0] - arr[i - 1][0] > arr[i][1]);bool c2 = (i == n - 1 || arr[i + 1][0] - arr[i][0] > arr[i][1]);if (c1 && c2) {res++;}}cout << res << endl;return 0;
}

---

E. 牛郎的微信群

思路: 思维题

• 距离为1，就是节点的度
• 距离为2， 就是节点u的相邻节点度总和 - 节点u的度

那这样求解，会不会遇到复杂度问题，比如菊花图等

不会，因为它是一个树结构，并不是一个完全图形态

它的枚举量为$O(V\ast 2),V为边数$

#include <bits/stdc++.h>
using namespace std;int main()
{int n;cin >> n;vector<vector<int>> g(n);for (int i = 0; i < n - 1; i++) {int u, v;cin >> u >> v;u--; v--;g[u].push_back(v);g[v].push_back(u);}vector<int> res(n);for (int i = 0; i < n; i++) {for (int v: g[i]) {res[i] += g[v].size();}res[i] -= g[i].size();}for (int i = 0; i < n; i++) {cout << res[i] << " \n"[i == n - 1];}return 0;
}

---

F. 久别重逢

方法一：前缀和优化的DP

令dp[j] 为 以j结尾的方案数

$$dp[j]=\sum _{i=0}^{i=j-k}dp[i]$$

公式转移代价为k，但是$n,k\le 10^5$, 所以必须加以优化

这边可以简单地使用前缀和优化，因为只有一侧有限制，控制右侧边界即可。

如果两侧有限制，则需要额外引入双端队列。

#include <bits/stdc++.h>
using namespace std;const int64_t mod = (int64_t)1e9 + 7;int main()
{int n, k;cin >> n >> k;int64_t res = 1;int64_t acc = 0;vector<int64_t> dp(n + 1);dp[0] = 1;for (int i = k; i <= n; i++) {acc = (acc + dp[i - k]) % mod;dp[i] = acc;res = (res + dp[i]) % mod;}cout << res << endl;return 0;
}

---

题外话:

方法二：组合数学

其实我一开始想到的是，枚举步数x，然后采用组合数学的方式来计算.

利用插板法，固定步数为x，接下来枚举y, $y\in [0,(n-kx)]$

$$\sum _{y=0}^{y=n-kx}C(y+x-1,y-1)=C(n-kx+x,x)=C(n-(k-1)\ast x,x)$$

然后在枚举x

最终结果为

$$\sum _{x=0}^{x=n/k}C(n-(k-1)\ast x,x)$$

#include <bits/stdc++.h>
using namespace std;int64_t ksm(int64_t b, int64_t v, int64_t mod) {int64_t r = 1l;while (v > 0) {if (v % 2 == 1) r = r * b % mod;b = b * b % mod;v /= 2;}return r;
}int main()
{int n, k;cin >> n >> k;// 组合数计算const int64_t mod = (int64_t)1e9 + 7;vector<int64_t> fac(n + 1);vector<int64_t> inv(n + 1);fac[0] = 1;for (int i = 1; i <= n; i++) {fac[i] = fac[i - 1] * i % mod;}inv[n] = ksm(fac[n], mod - 2, mod);for (int i = n - 1; i >= 0; i--) {inv[i] = inv[i + 1] * (i + 1) % mod;}int64_t res = 0;    for (int i = 0; i * k <= n; i++) {int r = n - i * k;// C(r+i, i)res += fac[r + i] * inv[i] % mod * inv[r] % mod;res %= mod;}cout << res << endl;return 0;
}

---

写在最后