四道题新鲜题解！！！
神秘钥匙
https://ac.nowcoder.com/acm/contest/6889/A
题目1：神秘钥匙
思路：数***算 + 快速幂
签到题。
根据题意，先要从n个人中选出队伍人数k，然后在k个人中选出一名队长，所以总方案数为：
\sum_{k=1}^{n}{(C^k_n * C^1_k)}∑k=1n(Cnk∗Ck1)
化简可得到： \sum_{k=1}^{n}{(C^k_n * C^1_k)} = \sum_{k=1}^{n}{(kC^k_n)}=\sum_{k=1}^{n}{nC^ {k-1}_{n-1}} = n\sum_{k=1}^{n}{C^ {k-1}_{n-1}}=n*2^{n - 1}∑k=1n(Cnk∗Ck1)=∑k=1n(kCnk)=∑k=1nnCn−1k−1=n∑k=1nCn−1k−1=n∗2n−1
由于题目给定了n的范围在1e9数量级，所以可以用快速幂方式运算
实现细节：
为了防止奇奇怪怪的卡数据，全局声明long long型计算，最后输出即可。
代码：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | #include <bits/stdc++.h> using namespace std; typedef longlongll; ll M = 1000000007; ll qpow(ll base,ll p){ ll res = 1; while(p) { if(p & 1) { res = res * base % M; } base = base * base % M; p >>= 1; } returnres; } intmain() { ll n; scanf("%lld", &n); ll res = qpow(2, n - 1); res = res * n % M; printf("%lld", res); } |
复杂度分析：
快速幂运算，时间复杂度O(logN)；
空间复杂度为O(1)。
题目2：战争
思路：二分 + 线段树
题意可简化为：给定若干个三元组(l, r, num)，保证num是区间[l, r]内的最小值，判断给定的三元组是否相互矛盾。
可以以num为关键字对三元组降序排序，对 numnum 相同的线段，计算出交集 [ll,rr][ll,rr] 与并集 [ml,mr][ml,mr]，那么最小值点一定位于交集中，此时要求最小值点在 [ll,rr][ll,rr] 区间内存在某点，放置后不会影响 num_2 > numnum2>num 的并集的最小值。利用线段树维护即可
实现细节：
数据量较大，可以使用快读。
代码：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 | #include <bits/stdc++.h> using namespace std; inline intread() { intflag = 1, r = 0; charch = getchar(); while(ch < '0'|| ch > '9') { if(ch == '-') { flag = -1; ch = getchar(); } } while(ch >= '0'&& ch <= '9') { r = r * 10+ ch - '0'; ch = getchar(); } returnr *= flag; } constintmaxn = 5e5 + 100; intn, k; struct node { // 三元组 intl, r, num; } A[maxn], B[maxn]; bool cmp(constnode& a, constnode& b) { // 排序比较函数 if(a.num == b.num) returna.l < b.l; returna.num > b.num; } intsum[maxn << 2], tag[maxn << 2]; // 求和数组、懒标记数组 #define ls p << 1 // 声明左右子树 #define rs p << 1| 1 inline voidpushdown(constint& l, constint& r, constint& p) { if(!tag[p]) return; intmid = l + r >> 1; sum[ls] = mid - l + 1; sum[rs] = r - mid; tag[ls] = tag[rs] = 1; tag[p] = 0; } voidbuild(constint& l, constint& r, constint& p) { sum[p] = tag[p] = 0; if(l == r) return; intmid = l + r >> 1; build(l, mid, ls), build(mid + 1, r, rs); } voidmodify(constint& l, constint& r, constint& p, constint& ll, constint& rr) { if(ll > rr || ll == 0) return; if(l >= ll && r <= rr) { sum[p] = r - l + 1; tag[p] = 1; return; } pushdown(l, r, p); intmid = l + r >> 1; if(ll <= mid) modify(l, mid, ls, ll, rr); if(rr > mid) modify(mid + 1, r, rs, ll, rr); sum[p] = sum[ls] + sum[rs]; } intask(constint& l, constint& r, constint& p, constint& ll, constint& rr) { if(ll == 0|| rr == 0|| ll > rr) return0; if(l >= ll && r <= rr) returnsum[p]; intmid = l + r >> 1, ans = 0; pushdown(l, r, p); if(ll <= mid) ans = ask(l, mid, ls, ll, rr); if(rr > mid) ans += ask(mid + 1, r, rs, ll, rr); returnans; } inline bool check(intx) { build(1, n, 1); for(inti = 1; i <= x; ++i) B[i] = A[i]; std::sort(B + 1, B + 1+ x, cmp); B[x + 1].num = -1; intll = 0, rr = 0, mr = 0, ml = n; for(inti = 1; i <= x + 1; ++i) { if(B[i].num == B[i - 1].num) { ll = std::max(ll, B[i].l); rr = std::min(rr, B[i].r); ml = std::min(ml, B[i].l); mr = std::max(mr, B[i].r); } else{ if(ll > rr) returntrue; if(ask(1, n, 1, ll, rr) == rr - ll + 1) returntrue; modify(1, n, 1, ml, mr); ml = ll = B[i].l, rr = mr = B[i].r; } } returnfalse; } intmain() { n = read(); k = read(); for(inti = 1; i <= k; i++) { A[i].l = read(); A[i].r = read(); A[i].num = read(); } intl = 1, r = k, mid; intans = k + 1; B[0].num = -1; while(l <= r) { mid = (l + r) >> 1; if(check(mid)) ans = mid, r = mid - 1; elsel = mid + 1; } printf("%d\n", ans); return0; } |
复杂度分析：
时间复杂度O(logN)；
空间复杂度为O(1)。
题目3：粉嘤花之恋
思路：矩阵快速幂
根据题意，实际上就是求斐波那契数列前n + 1项的和，设第n项为fn，前n项和为Sn，则根据斐波那契数列运算规律，有： f_{n+1} = f_n + f_{n - 1}\\ S_{n+1} = S_n + f_nfn+1=fn+fn−1Sn+1=Sn+fn
转换为矩阵相乘形式，有：
\begin{bmatrix} f_n&f_{n-1}&S_n \end{bmatrix} * \begin{bmatrix} 0&1&0\\ 1&1&0\\ 0&1&1 \end{bmatrix} =\begin{bmatrix} f_{n+1}&f_{n}&S_{n+1} \end{bmatrix}[fnfn−1Sn]∗⎣⎡010111001⎦⎤=[fn+1fnSn+1]
利用矩阵快速幂运算即可。
实现细节：
与题1相同，使用long long型运算，最后输出即可。
代码：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | #include <bits/stdc++.h> using namespace std; typedef longlongll; constintN = 3; ll n; ll M = 998244353; ll f1[N][N] = {{1, 1, 1}}; //声明[f{n}, f{n - 1}, S{n}]序列 ll A[N][N] = { //声明要进行幂次运算的矩阵 {0,1,0}, {1,1,1}, {0,0,1} }; voidmul(ll a[][N],ll b[][N]) { ll c[N][N] = {0}; for(inti = 0; i < 3; i++) { for(intj = 0; j < 3; j++) { for(intk = 0; k < 3; k++) { c[i][j] = (c[i][j] + a[i][k] * b[k][j] % M) % M; } } } memcpy(a, c, sizeof c); //将运算结果赋值给 A 矩阵 } voidquick_pow(ll a[][N],ll k) { ll E[N][N] = { //单位阵 {1,0,0}, {0,1,0}, {0,0,1} }; while(k) { if(k & 1) mul(E, a); mul(a, a); k >>= 1; } memcpy(a, E, sizeof E); } intmain() { cin >> n; quick_pow(A, n); mul(f1, A); // 最后用 f1 乘以 A 的 n 次幂 cout << f1[0][2] << endl; return0; } |
复杂度分析：
矩阵快速幂，时间复杂度为O(logN)；
利用二维数组存储矩阵，空间复杂度为O(N^2)。
题目4：神器大师泰兹瑞与威穆
思路：模拟
建立两个字符数组，首先把字符串全部存入第二个字符数组b，处理过程中加入第一个字符数组a，并利用topa和topb分别标识光标所在位。
代码：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | #include<bits/stdc++.h> using namespace std; constintN = 200010; chara[N], b[N]; chars[N], t[N]; inttopa, topb; intmain() { intmode = 0; cin >> s >> t; intn = strlen(s), m = strlen(t); for(inti = n - 1; i >= 0; i--) b[topb++] = s[i]; for(inti = 0; i < m; i++) { if(!mode) { if(t[i] == 'i') mode = 1; elseif(t[i] == 'f') { i++; if(i < m && t[i]) { for(intj = topb - 2; j >= 0; j--) { if(b[j] == t[i]) { intti = topb - j - 1; while(topb && ti--) a[topa++] = b[--topb]; break; } } } } elseif(t[i] == 'x') { if(topb) --topb; } elseif(t[i] == 'h') { if(topa) b[topb++] = a[--topa]; } elseif(t[i] == 'l') { if(topb) a[topa++] = b[--topb]; } } else{ if(t[i] == 'e') { mode = 0; } else{ a[topa++] = t[i]; } } } for(inti = 0; i < topa; i++) printf("%c", a[i]); for(inti = topb - 1; i >= 0; i--) printf("%c", b[i]); printf("\n"); return0; } |
复杂度分析：
遍历字符串，时间复杂度为O(N)；
维护了两个字符数组，空间复杂度为O(N)。
题目5：地、颜色、魔法
思路：深度优先搜索DFS
本题与昨天公众号发的（）意思基本一致，先找出所有不经过标记点的连通点，用其他字符保护，最后遍历矩阵将非保护字符计数即可。
实现细节：
矩阵最多有1e6量级的元素，要进行访问标记，维护二维布尔数组vis记录每个点已标记情况，防止重复搜索。
代码：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | #include <bits/stdc++.h> using namespace std; intn, m; voiddfs(vector<vector<char>>& board, vector<vector<bool>>& vis, intx, inty) { if(x < 0|| x >= n || y < 0|| y >= m || board[x][y] == '#'|| vis[x][y]) { return; } //printf("() = %d, %d\n", x, y); board[x][y] = 'a'; vis[x][y] = true; dfs(board, vis, x + 1, y); dfs(board, vis, x - 1, y); dfs(board, vis, x, y + 1); dfs(board, vis, x, y - 1); } intmain() { cin >> n >> m; vector< vector<char> > board(n, vector<char>(m)); vector< vector<bool> > vis(n, vector<bool>(m, 0)); for(inti = 0; i < n; i++) { for(intj = 0; j < m; j++) { cin >> board[i][j]; } } for(inti = 0; i < n; i++) { dfs(board, vis, i, 0); dfs(board, vis, i, m - 1); } for(inti = 1; i < m - 1; i++) { dfs(board, vis, 0, i); dfs(board, vis, n - 1, i); } intres = 0; for(inti = 0; i < n; i++) { for(intj = 0; j < m; j++) { if(board[i][j] != 'a') { res++; } } } cout << res << endl; } |
复杂度分析：
最坏情况全矩阵搜索，时间复杂度为O(NM)；
维护了二维数组标记访问，空间复杂度为O(NM)。
投递华为等公司10个岗位 >