Before the Beginning

转载请将本段放在文章开头显眼处，如有二次创作请标明。
原文链接：https://www.codein.icu/nowcoderweekly19/

前言

整体难度不大的比赛，然而场上发挥不算好。

A: 数学签到题
B: 二分+思维题
C: 斐波那契数列矩乘优化题
D: 链表模拟题
E: 搜索/并查集题

A

考虑选出每个人当队长时，被选数组的方案数为多少。
每个人状态有2种：选与不选，而选定队长必须选，因此有 $2^{n-1}$ 种包含该人且为队长的选人方案。
总方案数即为 $n \times 2^{n – 1}$，注意取模即可。

#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(char *s)
{
    static char c;
    for (; !isalpha(c); c = nc());
    for (; isalpha(c); c = nc()) *s++ = c;
    *s = '\0';
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int mod = 1e9 + 7;
long long n;
inline long long fastpow(long long x,long long k)
{
    long long res = 1;
    while(k)
    {
        if(k & 1) res = (res * x) % mod;
        x = (x * x) % mod;
        k >>= 1;
    }
    return res % mod;
}
int main()
{
    read(n);
    printf("%lld\n",(n * fastpow(2,n - 1)) % mod);
    return 0;
}

C

第 $i$ 次长出来的花瓣数记为 $g(i)$，可以得到 $g(i) = f(i+1)$，进而推知 $g(i) = g(i-1) + g(i-2)$，而记录所有 $g(i)$ 的和即为答案。
构造 $1 \times 3$ 的初始矩阵，分别代表 $g(i)$ $g(i+1)$ 和 $\sum_{j=0}^{i-1}g(j)$，$g(0) = 1$，构造一个 $3 \times 3$ 的转移矩阵矩阵，用矩阵快速幂即可。
建议自己手写个表感受一下数据，方便初始构造。
当然，具体构造方法各位按自己顺手的来吧。

#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
#define DEBUG
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(char *s)
{
    static char c;
    for (; !isalpha(c); c = nc());
    for (; isalpha(c); c = nc()) *s++ = c;
    *s = '\0';
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int mod = 998244353;
const int maxn = 10;
struct matrix
{
    int n,m;
    long long a[maxn][maxn];
    matrix()
    {
        for(int i = 0;i<=4;++i) for(int j = 0;j<=4;++j) a[i][j] = 0;
    }
    matrix operator*(const matrix b)
    {
        matrix res;
        res.n = n,res.m = b.m;
        for(int i = 1;i<=n;++i)
            for(int j = 1;j<=m;++j)
                for (int k = 1; k <= b.m; ++k) res.a[i][k] = (res.a[i][k] + a[i][j] * b.a[j][k]) % mod;
        return res;
    }
};
long long k;
int main()
{
    read(k);
    matrix A,S,X;
    A.n = A.m = 3;
    A.a[1][2] = 1,A.a[1][3] = 1,A.a[2][1] = 1,A.a[2][2] = 1,A.a[3][3] = 1;
    X.n = X.m = 3;
    for(int i = 1;i<=3;++i) X.a[i][i] = 1;
    S.n = 1,S.m = 3;
    S.a[1][1] = 1,S.a[1][2] = 1,S.a[1][3] = 0;
    while(k)
    {
        if(k & 1) X = X * A;
        A = A * A;
        k >>= 1;
    }
    S = S * X;
//    printf("%lld %lld %lld",S.a[1][1],S.a[1][2],S.a[1][3]);
    printf("%lld\n",(S.a[1][1] + S.a[1][3]) % mod);
    return 0;
}

E

看上去就很水的题目，然而给的限制是 $n \times m$ 导致必须使用 vector 存图，于是频繁出锅，卡了我很久。
一开始使用并查集做法，具体思路如下：
使用维护 $size$ 的并查集，将边界放在同一集合中，将 # 点看做障碍，每个 . 点四方向合并集合，最后统计非边界集合的大小和，加上 # 点数量即为答案。
由于不明原因锅了，改写搜索。

搜索的思路就更加简单了，从每个未访问过的点开始搜索，同时维护当前搜索到的联通块的大小，若遇到边界则打一个标记，代表该联通块大小不计入答案中。复杂度为 $O(n)$。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <ctype.h>
const int bufSize = 1e6;
using namespace std;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(char *s)
{
    static char c;
    for (; c != '.' && c != '#'; c = nc());
    for (; c == '.' || c == '#'; c = nc()) *s++ = c;
    *s = '\0';
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 2e6 + 100;
vector<char> a[maxn];
char s[maxn];
int n,m,ans,siz,flag;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
void dfs(int x,int y)
{
    ++siz;
    a[x][y] = 'a';
    for(int i = 0;i<4;++i)
    {
        int nx = x + dx[i],ny = y + dy[i];
        if(nx < 0 || nx >= n || ny < 0 || ny >= m) {flag = 1;continue;}
        if(a[nx][ny] == '.') dfs(nx,ny);
    }
}
int main()
{
    read(n),read(m);
    for(int i = 0;i < n;++i)
    {
        read(s);
        for(int j = 0;j < m;++j) a[i].push_back(s[j]);
    }
    for(int i = 0;i < n;++i)
    {
        for(int j = 0;j<m;++j)
        {
            if(a[i][j] == '#') ++ans;
            else if(a[i][j] == '.')
            {
                flag = 0,siz = 0;
                dfs(i,j);
                if(!flag) ans += siz;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

D

一道看上去就很链表的模拟题。
vim 使用者对此题有些莫名的感慨……

在 Normal Mode 下

• 按下 i ：进入 Insert Mode 。
• 按下 f ：紧接着一个小写字母 char，若当前光标后（右）方有至少一个 char ，将光标移动到其所在位置，否则不移动。
• 按下 x ：删除当前光标所在位的字符，后面的字符均会前移一格。
• 按下 h ：将光标向左（前）移动一格，若无法移动就不移动。
• 按下 l ：将光标向右（后）移动一格，若无法移动就不移动。
• 若按下了其他字符：无任何效果。

在 Insert Mode 下

• 按下非 e 小写字母 char ：在光标当前位置前插入这个字母 char。
• 按下 e ：退出 Insert Mode（进入 Normal Mode）。

如果使用链表，绝大部分操作都是 $O(1)$ 的，唯一看起来具有威胁的就是按下 f 的操作，单次操作极限可以达到 $O(n)$，但均摊复杂度是正确的。
因为 f 操作单调右移，而题中唯一的左移操作每次只能移动一个单位，也就是说，每次 f 消耗的势能，都只能通过按下 h 来补充，对总体复杂度无影响。

#include <cstdio>
#include <list>
#include <cstring>
#include <algorithm>
#include <ctype.h>
using namespace std;
const int bufSize = 1e6;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(char *s)
{
    static char c;
    for (; !isalpha(c); c = nc());
    for (; isalpha(c); c = nc()) *s++ = c;
    *s = '\0';
}
const int maxn = 2e5 + 100;
char s[maxn],t[maxn];
list<char> now;
int len,num;
int main()
{
    read(s + 1),read(t + 1);
    len = strlen(s + 1),num = strlen(t + 1);
    for(int i = 1;i<=len;++i) now.push_back(s[i]);
    int mode = 0;//0 for normal mode,1 for insert mode
    list<char>::iterator cur = now.begin();
    for(int i = 1;i<=num;++i)
    {
        char opt = t[i];
        if(mode == 0)
        {
            if(opt == 'i') mode = 1;
            else if(opt == 'f') 
            {
                char tar = t[++i];
                list<char>::iterator it = cur;
                ++it;
                while(it != now.end() && it != now.end())
                {
                    if(*it == tar) 
                    {
                        cur = it;
                        break;
                    }
                    ++it;
                }
            }
            else if(opt == 'x') cur = now.erase(cur);
            else if(opt == 'h') 
            {
                if(cur == now.begin()) continue;
                --cur;
            }
            else if(opt == 'l')
            {
                if(cur == now.end()) continue;
                ++cur;
            }
        }
        else
        {
            if(opt == 'e') mode = 0;
            else now.insert(cur,opt);
        }
    }
    for(list<char>::iterator it = now.begin();it!=now.end();++it) putchar(*it);
    return 0;
}

B

赛上看错题，导致一直不知道如何下手。
解说一下题意，给出若干个三元组 $(l,r,num)$，要求满足对于 $i \in [l,r]$ $\min{a_i} = num$，找出第一个三元组，在添加该三元组前可满足条件，在添加该三元组后无法满足。

这种最值问题，很容易联想到二分。若前 $x_1$ 个三元组时不满足条件，则前 $x_2(x_2 > x_1)$ 个三元组时一定也不满足，二分找出分界点即为答案。

接下来考虑如何有效地判断是否有满足条件的解。

对三元组按 $num$ 分类，同 $num$ 下的若干线段 $[l,r]$，由于数字两两不相同，也就是 $a_i = num$ 有唯一确定的 $i$，因此线段一定有交集，否则无解。

此外，还需要保证在 $[\min{l},\max{r}]$ 中，最小值为 $num$，因此若有 $num_2 < num$ 的线段 $[l,r]$ 位于其中，一定也不满足条件。

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

可以用线段树维护，每次查询 $[ll,rr]$ 的区间和，再将 $[ml,mr]$ 赋值为 $1$，若区间和等于区间长度，说明之前已经被并集覆盖完全，由于 $num$ 降序，此时 $[ll,rr]$ 区间内任一点设置为 $num$ 都会影响之前的最小值。

#include <algorithm>
#include <cstdio>
#include <ctype.h>

const int bufSize = 1e6;
#define DEBUG
inline char nc()
{
#ifdef DEBUG
    return getchar();
#endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline T read(T& r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    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()
{
    read(n), read(k);
    for (int i = 1; i <= k; ++i) read(A[i].l), read(A[i].r), read(A[i].num);
    int l = 1, r = k, mid, 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;
}