网站内侧网编大连开发区网站开发公司电话
前言
题解
因为这场七夕节，所以出的特别友好。
整体还是偏思维。
T6 额外提供组合数学解，还是蛮有趣的。
A. 喜鹊罢工
题型: 签到
365 可以有多少个 7 组成 365可以有多少个7组成 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
d i f f = ∑ i = 0 i = 25 a b s ( v 1 ( i ) − v 2 ( i ) ) diff = \sum_{i=0}^{i=25} abs(v_1(i) - v_2(i)) diff=i=0∑i=25abs(v1(i)−v2(i))
这样的时间复杂度为 O ( n + 26 ) O(n+26) 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 ∗ 2 ) , V 为边数 {O(V * 2) , V为边数} O(V∗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结尾的方案数
d p [ j ] = ∑ i = 0 i = j − k d p [ i ] dp[j] = \sum_{i=0}^{i=j-k} dp[i] dp[j]=i=0∑i=j−kdp[i]
公式转移代价为k，但是 n , k ≤ 1 0 5 n, k \le 10^5 n,k≤105, 所以必须加以优化
这边可以简单地使用前缀和优化，因为只有一侧有限制，控制右侧边界即可。
如果两侧有限制，则需要额外引入双端队列。
#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 ∈ [ 0 , ( n − k x ) ] y \in [0, (n-kx)] y∈[0,(n−kx)]
∑ y = 0 y = n − k x C ( y + x − 1 , y − 1 ) = C ( n − k x + x , x ) = C ( n − ( k − 1 ) ∗ x , x ) \sum_{y=0}^{y=n-kx} C(y+x-1, y-1) = C(n-kx+x, x) = C(n - (k-1)*x, x) y=0∑y=n−kxC(y+x−1,y−1)=C(n−kx+x,x)=C(n−(k−1)∗x,x)
然后在枚举x
最终结果为
∑ x = 0 x = n / k C ( n − ( k − 1 ) ∗ x , x ) \sum_{x=0}^{x=n/k} C(n - (k-1)*x, x) x=0∑x=n/kC(n−(k−1)∗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;
}
写在最后
