已删除

2020-08-12 13:41

关注

牛客算法周周练19 题解

牛客算法周周练19

在这里也能看到我们的LeetCode等比赛的题解

题目1：神秘钥匙

思路：数***算 + 快速幂

签到题。

根据题意，先要从n个人中选出队伍人数k，然后在k个人中选出一名队长，所以总方案数为：

$\sum_{k=1}^{n}{(C^k_n * C^1_k)}$

化简可得到： $\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}$

由于题目给定了n的范围在1e9数量级，所以可以用快速幂方式运算

实现细节：

为了防止奇奇怪怪的卡数据，全局声明long long型计算，最后输出即可。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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;
    }
    return res;    
}

int main() {
    ll n;
    scanf("%lld", &n);
    ll res = qpow(2, n - 1);
    res = res * n % M;
    printf("%lld", res);
}

复杂度分析：

快速幂运算，时间复杂度O(logN)；

空间复杂度为O(1)。

在这里也能看到我们的LeetCode等比赛的题解

题目2：战争

思路：二分 + 线段树

题意可简化为：给定若干个三元组(l, r, num)，保证num是区间[l, r]内的最小值，判断给定的三元组是否相互矛盾。

可以以num为关键字对三元组降序排序，对 $num$ 相同的线段，计算出交集 $[ll,rr]$ 与并集 $[ml,mr]$ ，那么最小值点一定位于交集中，此时要求最小值点在 $[ll,rr]$ 区间内存在某点，放置后不会影响 $num_2 > num$ 的并集的最小值。利用线段树维护即可

实现细节：

数据量较大，可以使用快读。

代码：

#include <bits/stdc++.h>
using namespace std;

inline int read() {
    int flag = 1, r = 0;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-') {
            flag = -1;
            ch = getchar();
        }
    }
    while(ch >= '0' && ch <= '9') {
        r = r * 10 + ch - '0';
        ch = getchar();
    }
    return r *= flag;
}

const int maxn = 5e5 + 100;
int n, k;
struct node {  // 三元组
    int l, r, num;
} A[maxn], B[maxn];

bool cmp(const node& a, const node& b) {  // 排序比较函数
    if (a.num == b.num) return a.l < b.l;
    return a.num > b.num;
}

int sum[maxn << 2], tag[maxn << 2];    // 求和数组、懒标记数组
#define ls p << 1  // 声明左右子树
#define rs p << 1 | 1
inline void pushdown(const int& l, const int& r, const int& p) {
    if (!tag[p]) return;
    int mid = l + r >> 1;
    sum[ls] = mid - l + 1;
    sum[rs] = r - mid;
    tag[ls] = tag[rs] = 1;
    tag[p] = 0;
}

void build(const int& l, const int& r, const int& p) {
    sum[p] = tag[p] = 0;
    if (l == r) return;
    int mid = l + r >> 1;
    build(l, mid, ls), build(mid + 1, r, rs);
}

void modify(const int& l, const int& r, const int& p, const int& ll, const int& 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);
    int mid = 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];
}

int ask(const int& l, const int& r, const int& p, const int& ll, const int& rr) {
    if (ll == 0 || rr == 0 || ll > rr) return 0;
    if (l >= ll && r <= rr) return sum[p];
    int mid = 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);
    return ans;
}

inline bool check(int x) {
    build(1, n, 1);
    for (int i = 1; i <= x; ++i) B[i] = A[i];
    std::sort(B + 1, B + 1 + x, cmp);
    B[x + 1].num = -1;
    int ll = 0, rr = 0, mr = 0, ml = n;
    for (int i = 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) return true;
            if (ask(1, n, 1, ll, rr) == rr - ll + 1) return true;
            modify(1, n, 1, ml, mr);
            ml = ll = B[i].l, rr = mr = B[i].r;
        }
    }
    return false;
}

int main() {
    n = read();
    k = read();
    for(int i = 1; i <= k; i++) {
        A[i].l = read();
        A[i].r = read();
        A[i].num = read();
    }
    int l = 1, r = k, mid;
    int ans = k + 1;
    B[0].num = -1;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (check(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    printf("%d\n", ans);
    return 0;
}

复杂度分析：

时间复杂度O(logN)；

空间复杂度为O(1)。

在这里也能看到我们的LeetCode等比赛的题解

题目3：粉嘤花之恋

思路：矩阵快速幂

根据题意，实际上就是求斐波那契数列前n + 1项的和，设第n项为fn，前n项和为Sn，则根据斐波那契数列运算规律，有： $f_{n+1} = f_n + f_{n - 1}\\ S_{n+1} = S_n + f_n$

转换为矩阵相乘形式，有：

$\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}$

利用矩阵快速幂运算即可。

实现细节：

与题1相同，使用long long型运算，最后输出即可。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 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}
};

void mul(ll a[][N],ll b[][N]) {
    ll c[N][N] = {0};
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            for(int k = 0; k < 3; k++) {
                c[i][j] = (c[i][j] + a[i][k] * b[k][j] % M) % M;
            }
        }
    }
    memcpy(a, c, sizeof c);    //将运算结果赋值给 A 矩阵
}

void quick_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);
}

int main() {
    cin >> n;
    quick_pow(A, n);
    mul(f1, A); // 最后用 f1 乘以 A 的 n 次幂
    cout << f1[0][2] << endl;
    return 0;
}

复杂度分析：

矩阵快速幂，时间复杂度为O(logN)；

利用二维数组存储矩阵，空间复杂度为O(N^2)。

在这里也能看到我们的LeetCode等比赛的题解

题目4：神器大师泰兹瑞与威穆

思路：模拟

建立两个字符数组，首先把字符串全部存入第二个字符数组b，处理过程中加入第一个字符数组a，并利用topa和topb分别标识光标所在位。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
char a[N], b[N];
char s[N], t[N];
int topa, topb;
int main() {
    int mode = 0;
    cin >> s >> t;
    int n = strlen(s), m = strlen(t);
    for (int i = n - 1; i >= 0; i--) b[topb++] = s[i];
    for (int i = 0; i < m; i++) {
        if (!mode) {
            if (t[i] == 'i') mode = 1;
            else if (t[i] == 'f') {
                i++;
                if (i < m && t[i]) {
                    for (int j = topb - 2; j >= 0; j--) {
                        if (b[j] == t[i]) {
                            int ti = topb - j - 1;
                            while (topb && ti--) a[topa++] = b[--topb];
                            break;
                        }
                    }
                }
            } else if (t[i] == 'x') {
                if (topb) --topb;
            } else if (t[i] == 'h') {
                if (topa) b[topb++] = a[--topa];
            } else if (t[i] == 'l') {
                if (topb) a[topa++] = b[--topb];
            }
        } else {
            if (t[i] == 'e') {
                mode = 0;
            } else {
                a[topa++] = t[i];
            }
        }
    }
    for (int i = 0; i < topa; i++) printf("%c", a[i]);
    for (int i = topb - 1; i >= 0; i--) printf("%c", b[i]);
    printf("\n");
    return 0;
}

复杂度分析：

遍历字符串，时间复杂度为O(N)；

维护了两个字符数组，空间复杂度为O(N)。

在这里也能看到我们的LeetCode等比赛的题解

题目5：地、颜色、魔法

思路：深度优先搜索DFS

本题与昨天公众号发的（）意思基本一致，先找出所有不经过标记点的连通点，用其他字符保护，最后遍历矩阵将非保护字符计数即可。

实现细节：

矩阵最多有1e6量级的元素，要进行访问标记，维护二维布尔数组vis记录每个点已标记情况，防止重复搜索。

代码：

#include <bits/stdc++.h>
using namespace std;

int n, m;

void dfs(vector<vector<char>>& board, vector<vector<bool>>& vis, int x, int y) {
    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);
}

int main() {
    cin >> n >> m;
    vector< vector<char> > board(n, vector<char>(m));
    vector< vector<bool> > vis(n, vector<bool>(m, 0));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> board[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        dfs(board, vis, i, 0);
        dfs(board, vis, i, m - 1);
    }
    for (int i = 1; i < m - 1; i++) {
        dfs(board, vis, 0, i);
        dfs(board, vis, n - 1, i);
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (board[i][j] != 'a') {
                res++;
            }
        }
    }
    cout << res << endl;
}