《算法竞赛进阶指南》0x18 总结与练习

一只野生彩色铅笔

发布于 2022-10-31 11:04:51

9020

发布于 2022-10-31 11:04:51

文章被收录于专栏：彩铅的随笔博客

章节总结

李煜东寄语：欢迎你入门算法竞赛，下一章节开始就要动真格的了

本章知识点汇总：

栈
1. 栈的基本实现，使用数组和栈顶位置变量模拟一个栈
2. 栈的灵活应用，例如使用辅助栈保存额外信息、对顶栈等
3. 表达式计算，后缀表达式、中缀转后缀、中缀表达式递归求值
4. 单调栈
队列
1. 一般队列、双端队列、循环队列的基本实现
2. 单调队列，理解使用单调性处理问题的思想
链表与邻接表
1. 双向链表的实现与操作，以及数组模拟链表
2. 邻接表结构，图和数的邻接表存储与遍历
Hash
1. Hash表，使用邻接表结构实现开散列法
2. 字符串 Hash，前缀与区间 Hash值、二分法的结合
字符串
1. KMP 模式匹配算法，next 数组的灵活运用
2. 最小表示法，循环同构问题
Trie
1. Trie 的插入、检索等基本操作
2. Trie 与 xor 问题
二叉堆
1. 二叉堆的基本操作及其实现，Insert、GetTop、Extract、Remove 等
2. 二叉堆的灵活应用、与贪心算法相结合，数据结构间 “建立映射” 的思想
3. k 叉 Huffman 树与 Huffman 编码

习题

括号画家

题目描述

达达是一名漫画家，她有一个奇特的爱好，就是在纸上画括号。

这一天，刚刚起床的达达画了一排括号序列，其中包含小括号 ( )、中括号 [ ] 和大括号 { }，总长度为

。

这排随意绘制的括号序列显得杂乱无章，于是达达定义了什么样的括号序列是美观的：

空的括号序列是美观的；
若括号序列 A 是美观的，则括号序列 (A)、[A]、{A} 也是美观的；
若括号序列 A、B 都是美观的，则括号序列 AB 也是美观的。
例如 [(){}]() 是美观的括号序列，而 )({)[}]( 则不是。

现在达达想在她绘制的括号序列中，找出其中连续的一段，满足这段子串是美观的，并且长度尽量大。

你能帮帮她吗？

输入格式

输入一行由括号组成的字符串。

输出格式

输出一个整数，表示最长的美观的子段的长度。

数据范围

字符串长度不超过

10^5

。

输入样例：

({({(({()}})}{())})})[){{{([)()((()]]}])[{)]}{[}{)

输出样例：

解析

维护一个栈，当栈顶元素与遍历到的字符匹配时，删掉栈顶元素；否则将新元素插入栈顶

则最终所有合法序列都不会在栈中；相反，所有的不合法括号都存在于栈里

自底向上遍历栈，找出元素之间最大差值，该差值即为最长合法序列长度

for (int i = 1; i <= n; i ++ )
{
   if (tt && str[stk[tt]] == mp[str[i]]) tt -- ;
   else stk[ ++ tt] = i;
}
int res = 0;
stk[ ++ tt] = n + 1;
for (int i = 1, last = 0; i <= tt; i ++ )
{
   res = max(res, stk[i] - last - 1);
   last = stk[i];
}

表达式计算4

题目描述

给出一个表达式,其中运算符仅包含 +,-,*,/,^（加减乘整除乘方）要求求出表达式的最终值。

数据可能会出现括号情况，还有可能出现多余括号情况。

数据保证不会出现大于或等于

2^{31}

的答案。

数据可能会出现负数情况。

输入格式

输入仅一行，即为表达式。

输出格式

输出仅一行，既为表达式算出的结果。

输入样例：

(2+2)^(1+1)

输出样例：

解析

毒瘤题，很难绷得住

参考 Tenshi 的做法，把 −x 处理成：(0−1)×x 的情况

这题左括号，右括号都会溢出不匹配，比起算法，更像工程题

void eval()
{
    int a = num.top(); num.pop();
    int b = num.top(); num.pop();
    char op = ops.top(); ops.pop();
    
    int res;
    if (op == '+') res = b + a;
    else if (op == '-') res = b - a;
    else if (op == '*') res = b * a;
    else if (op == '/') res = b / a;
    else res = power(b, a);
    
    num.push(res);
}
int main()
{
    cin >> str;
    string s;
    for (int i = 0; i < str.size(); i ++ )
    {
        if (str[i] == '-' && (!i || !isdigit(s[i-1])))
        {
            if (str[i - 1] == ')') s += "+(0-1)*";
            else s += "(0-1)*";
        }
        else s += str[i];
    }
    for (int i = 0; i < s.size(); i ++ )
    {
        if (isdigit(s[i]))
        {
            int j = i, sum = 0;
            while (j < s.size() && isdigit(s[j]))
                sum = sum * 10 + s[j ++ ] - '0';
            num.push(sum);
            i = j - 1;
        }
        else if (s[i] == '(') ops.push(s[i]);
        else if (s[i] == ')')
        {
            while(ops.size() && ops.top() != '(') eval();
            if (ops.size()) ops.pop();
        }
        else
        {
            while (ops.size() && mp[s[i]] <= mp[ops.top()]) eval();
            ops.push(s[i]);
        }
    }
    while (ops.size())
    {
        if (ops.top() == '(') ops.pop();
        else eval();
    }
    cout << num.top() << endl;
    return 0;
}

城市游戏

题目描述

有一天，小猫 rainbow 和 freda 来到了湘西张家界的天门山玉蟾宫，玉蟾宫宫主蓝兔盛情地款待了它们，并赐予它们一片土地。

这片土地被分成

N×M

个格子，每个格子里写着 R 或者 F，R 代表这块土地被赐予了 rainbow，F 代表这块土地被赐予了 freda。

现在 freda 要在这里卖萌。。。它要找一块矩形土地，要求这片土地都标着 F 并且面积最大。

但是 rainbow 和 freda 的 OI 水平都弱爆了，找不出这块土地，而蓝兔也想看 freda 卖萌（她显然是不会编程的……），所以它们决定，如果你找到的土地面积为

，它们将给你

3×S

两银子。

输入格式

第一行包括两个整数

N,M

，表示矩形土地有

行

列。

接下来

行，每行

个用空格隔开的字符

或

，描述了矩形土地。

每行末尾没有多余空格。

输出格式

输出一个整数，表示你能得到多少银子，即(

3×

最大

矩形土地面积)的值。

数据范围

1≤N,M≤1000

输入样例：

5 6
R F F F F F
F F F F F F
R R R F F F
F F F F F F
F F F F F F

输出样例：

解析

2021 头条笔试的原题，在一个

N \times M

的

矩阵里，求出全

的最大矩形面积

这题的原型是 “直方图最大矩形”，我们可以从上往下枚举矩形的下底边，则每一列

的个数为该列的最大高度

然后从左往右求一遍直方图最大矩形面积即可

以样例为例，如下：

R F F F F F              F F F
F F F F F F              F F F
R R R F F F   =>         F F F
F F F F F F        F F F F F F
F F F F F F        F F F F F F

从上往下枚举的同时，维护一个数组

height[j]

来记录当前下底边枚举到第

行时，第

列的高度

若

matrix[i][j] = 0

，则

height[j] = 0

若

matrix[i][j] = 1

，则

height[j] = height[j - 1] + 1

int res = 0;
height[0] = height[m + 1] = -1;
for (int i = 1; i <= n; i ++ )
{
    for (int j = 1; j <= m; j ++ )
    {
        if (g[i][j]) height[j] ++ ;
        else height[j] = 0;
    }
    tt = 0; stk[tt] = 0;
    for (int j = 1; j <= m; j ++ )
    {
        while (height[stk[tt]] >= height[j]) tt -- ;
        l[j] = stk[tt];
        stk[ ++ tt] = j;
    }
    tt = 0; stk[tt] = m + 1;
    for (int j = m; j; j -- )
    {
        while (height[stk[tt]] >= height[j]) tt -- ;
        r[j] = stk[tt];
        stk[ ++ tt] = j;
    }
    for (int j = 1; j <= m; j ++ )
        res = max(res, height[j] * (r[j] - l[j] - 1));
}

双栈排序

题目描述

Tom 最近在研究一个有趣的排序问题。

通过

个栈

S_1

和

S_2

，Tom 希望借助以下

种操作实现将输入序列升序排序。

操作 a

如果输入序列不为空，将第一个元素压入栈

S_1

操作 b - 如果栈

S_1

不为空，将

S_1

栈顶元素弹出至输出序列

操作 c

如果输入序列不为空，将第一个元素压入栈

S_2

操作 d

如果栈

S_2

不为空，将

S_2

栈顶元素弹出至输出序列

如果一个

1∼n

的排列

可以通过一系列操作使得输出序列为

1,2,…,(n−1),n

，Tom 就称

是一个 "可双栈排序排列"。

例如

(1,3,2,4)

就是一个”可双栈排序序列”，而

(2,3,4,1)

不是。

(1,3,2,4)

排序的操作序列：

<a, c, c, b, a, d, d, b>

当然，这样的操作序列有可能有几个，对于上例

(1,3,2,4)

，

<a, c, c, b, a, d, d, b>

是另外一个可行的操作序列。

Tom 希望知道其中字典序最小的操作序列是什么。

输入格式

第一行是一个整数

。

第二行有

个用空格隔开的正整数，构成一个

1∼n

的排列。

输出格式

输出共一行，如果输入的排列不是 "可双栈排序排列"，输出数字

。

否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。

数据范围

1≤n≤1000

输入样例：

4
1 3 2 4

输出样例：

a b a a b b a b

解析

如果只有一个栈，那么每个元素入栈出栈顺序是唯一确定的

当有两个栈时，就变成二分图问题了，需要用到以下性质：

两个数

i,j\ (i \le j)

不能被放入同一个栈中，当且仅当存在

k\ (k>j)

，且

a_k < a_i < a_j

存在元素

不能在元素

入栈之前就输出，则两元素一定不会放入同一个栈中

利用该性质，建图，然后用染色法判二分图

bool dfs(int u, int c)
{
    color[u] = c;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int ver = e[i];
        if (!color[ver] && !dfs(ver, 3 - c)) return false;
        else if(color[ver] == c) return false;
    }
    return true;
}
int main()
{
    memset(h, -1, sizeof h);
    scanf("%d", &n);
    f[n + 1] = n + 1;//哨兵
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = n; i >= 1; i -- ) f[i] = min(f[i + 1], a[i]);
    for (int i = 1; i <= n; i ++ )
        for (int j = i + 1; j <= n; j ++ )
            if (a[i] < a[j] && f[j + 1] < a[i])
                add(i, j), add(j, i);
    bool flag = true;
    for (int i = 1; i <= n; i ++ )
        if (!color[i] && !dfs(i, 1))
            flag = false;
    if (!flag) printf("0\n");
    else
    {
        stack<int> s1, s2;
        int now = 1;
        for (int i = 1; i <= n; i ++ )
        {
            if (color[i] == 1)
            {
                while (s1.size() && s1.top() == now)
                {
                    s1.pop();
                    printf("b ");
                    now ++ ;
                }
                if (s1.size() && s1.top() < a[i])
                {
                    while (true)
                    {
                        if (s1.size() && s1.top() == now)
                        {
                            s1.pop();
                            printf("b ");
                            now ++ ;
                        }
                        else if (s2.size() && s2.top() == now)
                        {
                            s2.pop();
                            printf("d ");
                            now ++ ;
                        }
                        else break;
                    }
                }
                s1.push(a[i]);
                printf("a ");
            }
            else
            {
                while (true)
                {
                    if (s1.size() && s1.top() == now)
                    {
                        s1.pop();
                        printf("b ");
                        now ++ ;
                    }
                    else if (s2.size() && s2.top() == now)
                    {
                        s2.pop();
                        printf("d ");
                        now ++ ;
                    }
                    else break;
                }
                s2.push(a[i]);
                printf("c ");
            }
        }
        while (true)
        {
            if (s1.size() && s1.top() == now)
            {
                s1.pop();
                printf("b ");
                now ++ ;
            }
            else if (s2.size() && s2.top() == now)
            {
                s2.pop();
                printf("d ");
                now ++ ;
            }
            else break;
        }
    }
    return 0;
}

滑动窗口

题目描述

给定一个大小为

n≤10^6

的数组。

有一个大小为

的滑动窗口，它从数组的最左边移动到最右边。

你只能在窗口中看到

个数字。

每次滑动窗口向右移动一个位置。

你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

输入格式

输入包含两行。

第一行包含两个整数

和

，分别代表数组长度和滑动窗口的长度。

第二行有

个整数，代表数组的具体数值。

同行数据之间用空格隔开。

输出格式

输出包含两个。

第一行输出，从左至右，每个位置滑动窗口中的最小值。

第二行输出，从左至右，每个位置滑动窗口中的最大值。

输入样例：

8 3
1 3 -1 -3 5 3 6 7

输出样例：

-1 -3 -3 -3 3 3
3 3 5 5 6 7

解析

板子

// 最小值窗口
{
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i ++ )
    {
        while (hh <= tt && w[q[tt]] >= w[i]) tt -- ;
        q[ ++ tt] = i;
        if (hh <= tt && i - q[hh] + 1 > m) hh ++ ;
        if (i >= m) printf("%d ", w[q[hh]]);
    }
    puts("");
}
// 最大值窗口
{
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i ++ )
    {
        while (hh <= tt && w[q[tt]] <= w[i]) tt -- ;
        q[ ++ tt] = i;
        if (hh <= tt && i - q[hh] + 1 > m) hh ++ ;
        if (i >= m) printf("%d ", w[q[hh]]);
    }
    puts("");
}

内存分配

题目描述

内存是计算机重要的资源之一，程序运行的过程中必须对内存进行分配。

经典的内存分配过程是这样进行的：

内存以内存单元为基本单位，每个内存单元用一个固定的整数作为标识，称为地址。地址从

开始连续排列，地址相邻的内存单元被认为是逻辑上连续的。我们把从地址

开始的

个连续的内存单元称为首地址为

长度为

的地址片。

运行过程中有若干进程需要占用内存，对于每个进程有一个申请时刻

，需要内存单元数

及运行时间

。在运行时间

内（即

时刻开始，

T+P

时刻结束），这

个被占用的内存单元不能再被其他进程使用。

假设在

时刻有一个进程申请

个单元，且运行时间为

，则：

时刻内存中存在长度为

的空闲地址片，则系统将这

个空闲单元分配给该进程。若存在多个长度为

个空闲地址片，则系统将首地址最小的那个空闲地址片分配给该进程。

如果

时刻不存在长度为

的空闲地址片，则该进程被放入一个等待队列。对于处于等待队列队头的进程，只要在任一时刻，存在长度为

的空闲地址片，系统马上将该进程取出队列，并为它分配内存单元。注意，在进行内存分配处理过程中，处于等待队列队头的进程的处理优先级最高，队列中的其它进程不能先于队头进程被处理。

现在给出一系列描述进程的数据，请编写一程序模拟系统分配内存的过程。

输入格式

第一行是一个数

，表示总内存单元数（即地址范围从

到

N−1

）。

从第二行开始每行描述一个进程的三个整数

、

（

M≤N

）。

最后一行用三个

表示结束。

数据已按

从小到大排序。

输入文件最多

10000

行，且所有数据都小于

10^9

。

输入文件中同一行相邻两项之间用一个或多个空格隔开。

输出格式

输出包括

行。

第一行是全部进程都运行完毕的时刻。

第二行是被放入过等待队列的进程总数。

输入样例：

输出样例：

12
2

解析

屑模拟，用双链表实现空闲块控制

等待队列：（内存长度，占用时间）queue
内存使用情况：（起始下标，长度 + 线性扫描、删除、插入功能）双链表
小根堆：（释放时间key，起始下标）priority_queue

bool distribute_memory(int len, int end_time)
{
    //printf("len:%d  end_time:%d\n", len, end_time);
    for (int i = head; i != tail; i = node[i].next)
    {
        Node &a = node[i], &b = node[node[i].next];
        int l = a.addr + a.size, r = b.addr;
        if (r - l >= len)
        {
            task.push({end_time, insert(i, l, len)});
            return true;
        }
    }
    return false;
}
void free_block(int t)
{
    while (task.size() && task.top().x <= t)
    {
        //同一时间的全部释放
        int free_time = task.top().x;
        while (task.size() && task.top().x == free_time)
        {
            remove(task.top().y);
            task.pop();
        }
        cur_time = free_time;
        //释放一轮后，处理等待队列
        while (wait.size() && distribute_memory(wait.front().x, cur_time + wait.front().y))
        {
            wait.pop();
        }
    }
}
int main()
{
    scanf("%d", &n);
    initialize();

    int cnt = 0;
    while (scanf("%d%d%d", &t, &m, &p), t || m || p)
    {
        free_block(t), cur_time = t;
        if (!distribute_memory(m, cur_time + p))
        {
            //printf("t=%d m=%d p=%d\n", t, m, p);
            wait.push({m, p});
            cnt ++ ;
        }
    }
    free_block(2e9);
    printf("%d\n%d", cur_time, cnt);
    return 0;
}

矩阵

题目描述

给定一个

行

列的

矩阵（只包含数字

或

的矩阵），再执行

次询问，每次询问给出一个

行

列的

矩阵，求该矩阵是否在原矩阵中出现过。

输入格式

第一行四个整数

M,N,A,B

。

接下来一个

行

列的

矩阵，数字之间没有空格。

接下来一个整数

。

接下来

个

行

列的

矩阵，数字之间没有空格。

输出格式

对于每个询问，输出

表示出现过，

表示没有出现过。

数据范围

A≤100，M,N,B≤1000，Q≤1000

输入样例：

输出样例：

1
0
1

解析

二维字符串哈希，先回忆一下一维情况下我们是怎么定义和递推的：

对于字符串

S = s_0 s_1 \cdots s_{n-1}

的哈希值为

H(S) = s_0 \times P^{n-1} + s_1 \times P^{n-2} + \cdots \times s_{n-1}

递推式为

H(S+T) = H(S) \times P^{len(T)} + H(T)

是一个根据前缀从大到小的思路去规定的

根据该规则推广到二维哈希，对于二维矩阵

A_{n \times m}

，考虑将降维成一维，给定元素编号：

[ \begin{pmatrix} s_{nm-1} & s_{nm-2} & \cdots & s_{nm-m+1} & s_{nm-m} \\ s_{nm-m-1} & s_{nm-m-2} & \cdots & s_{nm-2m+1} & s_{nm-2m} \\ \cdots & \cdots & \cdots & \cdots & \cdots \\ s_{m-1} & s_{m-2} & \cdots & s_1 & s_0\\ \end{pmatrix}_{n\times m} ]

于是有递推式:

[ H\begin{pmatrix} A_{n\times m} \\ B_{k\times m} \end{pmatrix} = H(A_{n\times m}) \times P^{km} + H(B_{k\times m}) ]

于是，我们可以对该矩阵的每一行，做一遍字符串哈希，然后利用上述递推式，将哈希从行推广到列

ULL get_hash(ULL h[], int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}
void initialize_hash()
{
    p[0] = 1;
    for (int i = 1; i <= n * m; i ++ ) p[i] = p[i - 1] * P;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            h[i][j] = h[i][j - 1] * P + str[i][j];
}
int main()
{
    scanf("%d%d%d%d", &n, &m, &a, &b);
    for (int i = 1; i <= n; i ++ ) scanf("%s", str[i] + 1);
    initialize_hash();
    for (int j = b; j <= m; j ++ )
    {
        ULL value = 0;
        int l = j - b + 1, r = j;
        for (int i = 1; i <= n; i ++ )
        {
            value = value * p[b] + get_hash(h[i], l, r);
            if (i > a) value = value - get_hash(h[i - a],l, r) * p[b * a];
            if (i >= a) S.insert(value);
        }
    }
    scanf("%d", &T);
    while (T -- )
    {
        ULL value = 0;
        for (int i = 1; i <= a; i ++ )
        {
            scanf("%s", str[i] + 1);
            for (int j = 1; j <= b; j ++ ) value = value * P + str[i][j];
        }
        puts(S.count(value) ? "1" : "0");
    }
    return 0;
}

树形地铁系统

题目描述

一些主要城市拥有树形的地铁系统，即在任何一对车站之间，有且只有一种方式可以乘坐地铁。

此外，这些城市大多数都有一个中央车站。

想象一下，你是一名在拥有树形地铁系统的城市游玩的游客，你想探索该城市完整的地铁线路。

你从中央车站出发，随机选择一条地铁线，然后乘坐地铁行进。

每次到达一个车站，你都将选择一条尚未乘坐过的地铁线路进行乘坐。

如果不存在未乘坐过的线路，则退回到上一个车站，再做选择。

直到你将所有地铁线路都乘坐过两次（往返各一次），此时你将回到中央车站。

之后，你以一种特殊的方式回忆自己的坐车过程，你将你的完整地铁乘坐路线编码为一个二进制字符串。

其中 0 编码表示你乘坐地铁线路到达距离中央车站更远的一站，1 编码表示你乘坐地铁线路到达距离中央车站更近的一站。

输入格式

第一行输入一个正整数

，代表测试用例数量。

每个测试用例由两行组成，每行输入一个由字符 0 和 1 构成的字符串，长度最多为

3000

，两个字符串都描述了一种树形地铁系统的正确探索路线。

输出格式

对于每个测试用例，如果两个字符串描述的探索路线可以视为同一个地铁系统的两种探索路线，则输出 same。

否则，输出 different。

每行输出一个结果。

输入样例：

2
0010011101001011
0100011011001011
0100101100100111
0011000111010101

输出样例：

same
different

解析

树哈希问题，用树的最小表示法，即遍历子树的顺序按照子树最小字典序从小到大遍历

string dfs(string &s, int &u)
{
    vector<string> sqs;
    u ++ ;
    while (s[u] == '0') sqs.push_back(dfs(s, u));
    u ++ ;
    
    sort(sqs.begin(), sqs.end());
    string res;
    for (auto &it: sqs) res += it;
    res = '0' + res + '1';
    return res;
}
int main()
{
    scanf("%d", &T);
    while (T -- )
    {
        string a, b;
        cin >> a >> b;
        a = '0' + a + '1', b = '0' + b + '1';
        int ua = 0, ub = 0;
        puts(dfs(a, ua) == dfs(b, ub) ? "same" : "different");
    }
    return 0;
}

项链

题目描述

有一天，达达捡了一条价值连城的宝石项链，但是，一个严重的问题是，他并不知道项链的主人是谁！

在得知此事后，很多人向达达发来了很多邮件，都说项链是自己的，要求他归还（显然其中最多只有一个人说了真话）。

达达要求每个人都写了一段关于自己项链的描述：项链上的宝石用数字

至

来标示。

一个对于项链的表示就是从项链的某个宝石开始，顺指针绕一圈，沿途记下经过的宝石，比如项链：

0−1−2−3

，它的可能的四种表示是

0123、1230、2301、3012

。

达达现在心急如焚，于是他找到了你，希望你能够编写一个程序，判断两个给定的描述是否代表同一个项链（注意，项链是不会翻转的）。

也就是说给定两个项链的表示，判断他们是否可能是一条项链。

输入格式

输入文件只有两行，每行一个由字符

至

构成的字符串，描述一个项链的表示（保证项链的长度是相等的）。

输出格式

如果两个对项链的描述不可能代表同一个项链，那么输出 No，否则的话，第一行输出一个 Yes，第二行输出该项链的字典序最小的表示。

数据范围

设项链的长度为

L，1≤L≤1000000

输入样例：

2234342423
2423223434

输出样例：

Yes
2234342423

解析

循环同构的板子题，用字符串的最小表示即可

void get_min(char *s)
{
    int n = strlen(s);
    for (int i = n; i < n << 1; i ++ ) s[i] = s[i % n];
    
    int i = 0, j = 1, k;
    while (i < n && j < n)
    {
        for (k = 0; k < n && s[i + k] == s[j + k]; k ++ );
        if (k == n) break;
        if (s[i + k] > s[j + k])
        {
            i = i + k + 1;
            if (i == j) i ++ ;
        }
        else
        {
            j = j + k + 1;
            if (i == j) j ++ ;
        }
    }
    
    int start = min(i, j);
    for (int c = 0; c < n; c ++ ) s[c] = s[start + c];
    s[n] = '\0';
}

奶牛矩阵

题目描述

每天早上，农夫约翰的奶牛们被挤奶的时候，都会站成一个

行

列的方阵。

现在在每个奶牛的身上标注表示其品种的大写字母，则所有奶牛共同构成了一个

行

列的字符矩阵。

现在给定由所有奶牛构成的矩阵，求它的最小覆盖子矩阵的面积是多少。

如果一个子矩阵无限复制扩张之后得到的矩阵能包含原来的矩阵，则称该子矩阵为覆盖子矩阵。

输入格式

第

行：输入两个用空格隔开的整数，

和

。

第

2..R+1

行：描绘由奶牛构成的

行

列的矩阵，每行

个字符，字符之间没有空格。

输出格式

输出最小覆盖子矩阵的面积。（每个字符的面积为

）

数据范围

1≤R≤10000, 1≤C≤75

输入样例：

2 5
ABABA
ABABA

输出样例：

提示

样例中给出的矩阵的最小覆盖子矩阵为

，面积为

。

解析

在之前的 “字符串” 的章节，我额外介绍了 “前缀函数求字符串周期”，本题就可以活用该方法

字符串长度 - 字符串相等前后缀长度 = 字符串的周期

字符串的最小正周期

= 字符串长度

- 字符串最长相等前后缀

\pi[n]

而字符串次长相等前后缀为：

\pi[\pi[n] - 1]

，同理可以求出次小正周期；以此类推，可以求出字符串所有可能周期

再观察易得，字符串行的周期与列的周期相互独立，因此我们可以先把整行看做一个单位元素，求一遍前缀函数；再把整列看做一个单位元素，再做一遍前缀函数，两者答案之积即为所求

时间复杂度为：

O(NM)

虽然KMP求前缀函数是线性的，但是每次比较的时间复杂度为字符串长度，而之前证明过，KMP至多比较

次，因此时间复杂度为

O(NM)

scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%s", row[i] + 1);
for (int i = 1; i <= n; i ++ )
    for (int j = 1; j <= m; j ++ )
        col[j][i] = row[i][j];
for (int i = 2, j = 0; i <= n; i ++ )
{
    while (j && strcmp(row[i] + 1, row[j + 1] + 1)) j = ne[j];
    if (!strcmp(row[i] + 1, row[j + 1] + 1)) j ++ ;
    ne[i] = j;
}
int x = n - ne[n];

for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && strcmp(col[i] + 1, col[j + 1] + 1)) j = ne[j];
    if (!strcmp(col[i] + 1, col[j + 1] + 1)) j ++ ;
    ne[i] = j;
}
int y = m - ne[m];
printf("%d\n", x * y);

匹配统计

题目描述

阿轩在纸上写了两个字符串，分别记为

和

。

利用在数据结构与算法课上学到的知识，他很容易地求出了 “字符串

从任意位置开始的后缀子串” 与 “字符串

”匹配的长度。

不过阿轩是一个勤学好问的同学，他向你提出了

个问题：

在每个问题中，他给定你一个整数

，请你告诉他有多少个位置，满足 “字符串

从该位置开始的后缀子串” 与

匹配的长度恰好为

。

例如：

A=aabcde，B=ab

，则

有

aabcde、abcde、bcde、cde、de、e

这

个后缀子串，它们与

B=ab

的匹配长度分别是

1、2、0、0、0、0

。

因此

有

个位置与

的匹配长度恰好为

，有

个位置的匹配长度恰好为

，有

个位置的匹配长度恰好为

。

输入格式

第一行输入三个整数

N,M,Q

，分别表示

A4 串长度、

B$ 串长度、问题个数。

第二行输入字符串

，第三行输入字符串

。

接下来

行每行输入

个整数

，表示一个问题。

输出格式

输出共

行，依次表示每个问题的答案。

数据范围

1≤N,M,Q,x≤200000

输入样例：

6 2 5
aabcde
ab
0
1
2
3
4

输出样例：

解析一

直接枚举字符串后缀，然后直接比较的时间复杂度为

O(N^2)

考虑用 字符串哈希 + 二分 优化 字符串的比较时间，可以将时间复杂度优化为：

O(N \log N)

for (int i = n; i; i -- )
{
    int l = 0, r = n - i + 1;
    while (l < r)
    {
        int mid = (l + r + 1) >> 1;
        ULL va = get_hash(ha, i, i + mid - 1);
        ULL vb = get_hash(hb, 1, 1 + mid - 1);
        if (va == vb) l = mid; else r = mid - 1;
    }
    cnt[r] ++ ;
}
while (Q -- )
{
    int t;
    scanf("%d", &t);
    printf("%d\n", cnt[t]);
}

解析二

把

串作为主串，

串作为模式串，做一轮 KMP 匹配，然后记录下每一轮匹配中

A_i

匹配的

的最长前缀

即

A[i-j+1 \cdots i] = B[1 \cdots j]

，则

的一个后缀

A[i-j+1 \cdots n]

与

的最长相等前缀长度至少为

又

\pi[j]

表示

串中前缀

B[1 \cdots j]

的最长相等前后缀长度，因此也存在相等后缀：

A[i-\pi[j]+1 \cdots i] = B[1 \cdots \pi[j]]

同理：

\pi[\pi[j]], \pi[\pi[\pi[j]]], \cdots, 0

都是

于是我们可以去统计一个数组

f[i]

表示：

串的后缀子串中与

串匹配的长度至少为

的个数

则

串的后缀子串中与

串匹配的长度恰好为

的个数为：

f[i] - f[i + 1]

考虑如何统计

f[i]

：先做一遍 KMP 对于完成的第

轮的匹配，此时

的位置表示存在一个长度至少为

的后缀子串

由于每个

只对应有一个

\pi[j]

，且

j > \pi[j]

，所以如果将状态

f[j]

绘图，一定是一个 DAG

因此我们可以在 DAG 上采用递推的方式求出每个状态

f[j]

，最后统计答案即可

scanf("%d%d%d%s%s", &n, &m, &Q, a + 1, b + 1);
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && b[i] != b[j + 1]) j = ne[j];
    if (b[i] == b[j + 1]) j ++ ;
    ne[i] = j;
}
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && a[i] != b[j + 1]) j = ne[j];
    if (a[i] == b[j + 1]) j ++ ;
    f[j] ++ ;
}
for (int i = m; i; i -- ) f[ne[i]] += f[i];
while (Q -- )
{
    int t;
    scanf("%d", &t);
    printf("%d\n", f[t] - f[t + 1]);
}

电话列表

题目描述

给出一个电话列表，如果列表中存在其中一个号码是另一个号码的前缀这一情况，那么就称这个电话列表是不兼容的。

假设电话列表如下：

Emergency 911
Alice 97 625 999
Bob 91 12 54 26

在此例中，报警电话号码（911）为 Bob 电话号码（91 12 54 26）的前缀，所以该列表不兼容。

输入格式

第一行输入整数

，表示测试用例数量。

对于每个测试用例，第一行输入整数

，表示电话号码数量。

接下来

行，每行输入一个电话号码，号码内数字之间无空格，电话号码不超过

位。

输出格式

对于每个测试用例，如果电话列表兼容，则输出 YES。

否则，输出 NO。

数据范围

1≤t≤40, 1≤n≤10000

输入样例：

输出样例：

NO
YES

解析

用一棵 Trie 来维护所有的串

如果在某次插入时，路径上有其他串的结尾标识，说明其他某串是该串的前缀
如果在某次插入时，该串结尾结点不是通过创建新结点创建出来的，说明该串是其他某串的前缀

bool insert(char *s)
{
    int p = 0;
    bool has_new = true, has_found = false;
    for (int i = 0; s[i]; i ++ )
    {
        int ch = s[i] - '0';
        if (!trie[p][ch]) trie[p][ch] = ++ tot, has_new = true;
        else has_new = false;
        p = trie[p][ch];
        if (end[p]) has_found = true;
    }
    end[p] ++ ;
    return !has_found && has_new;
}

黑盒子

题目描述

黑盒子代表一个原始的数据库。

它可以用来储存整数数组，并且它拥有一个特殊变量

。

在最开始，黑盒子是空的，并且

i=0

。

现在对黑盒子进行一系列的操作处理，操作包括以下两种：

ADD(x)：表示将

加入到黑盒子中。

GET：使

增加

，输出黑盒子中第

小的数值（即将所有数按升序排序后的第

个数）。

下面给出一个具体例子：

序号 操作        i     盒子内数（升序排列后）             输出的值 
1    ADD(3)      0     3   
2    GET         1     3                                    3 
3    ADD(1)      1     1, 3   
4    GET         2     1, 3                                 3 
5    ADD(-4)     2     -4, 1, 3   
6    ADD(2)      2     -4, 1, 2, 3   
7    ADD(8)      2     -4, 1, 2, 3, 8   
8    ADD(-1000)  2     -1000, -4, 1, 2, 3, 8   
9    GET         3     -1000, -4, 1, 2, 3, 8                1 
10   GET         4     -1000, -4, 1, 2, 3, 8                2 
11   ADD(2)      4     -1000, -4, 1, 2, 2, 3, 8

为了方便描述，下面我们定义两个序列：

A(1),A(2),…,A(M)：这个序列由加入到黑盒子内的所有元素按加入顺序排列后得到，上例中的

序列为

(3,1,−4,2,8,−1000,2)

。 u(1),u(2),…,u(N)：这个序列的第

项表示的是第

次 GET 操作时，盒子内元素的数量。上例中的

序列为

(1,2,6,6)

。

现在请你根据给出的序列

和

求出操作过程中输出的所有数值。

输入格式

输入包括三行。

第一行包含两个整数

和

，表示

序列和

序列的长度。

第二行包含

个整数，表示

序列的每一个元素。

第三行包含

个整数，表示

序列的每一个元素。

同行每个数之间用空格隔开。

输出格式

输出操作过程中所有 GET 操作输出的数值。

每个数值占一行。

数据范围

|A(i)|≤2×10^9, 1≤N≤M≤30000

对于所有

p \ (1≤p≤N),\ p≤u(p)≤M

成立。

输入样例：

7 4
3 1 -4 2 8 -1000 2
1 2 6 6

输出样例：

解析

平衡树板中板，暂不展开

这题是 PAT 原题，我学对顶堆时做的一道例题，经典的对顶堆应用

不同于对顶堆维护中位数，此题需要动态上下堆的数量

若当前需要输出第

小数，则大根堆的大小为

，小根堆的大小为

size - i

void adjust(int n, int t)
{
    if (dw.size() > t)
    {
        up.push(dw.top());
        dw.pop();
    }
    else if (up.size() > n - t)
    {
        dw.push(up.top());
        up.pop();
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = 1; i <= m; i ++ ) scanf("%d", &b[i]);

    int t = 1;
    for (int i = 1, j = 1; i <= n; i ++ )
    {
        dw.push(a[i]);
        adjust(i, t);
        while (b[j] == i)
        {
            printf("%d\n", dw.top());
            j ++ , ++ t;
            adjust(i, t);
        }
    }
    return 0;
}

生日礼物

题目描述

翰翰 18 岁生日的时候，达达给她看了一个神奇的序列

A_1,A_2,…,A_N

。

她被允许从中选择不超过

个连续的部分作为自己的生日礼物。

翰翰想要知道选择元素之和的最大值。

你能帮助她吗？

输入格式

第一行包含两个整数

N,M

。

第二行包含

个整数

A_1∼A_N

。

输出格式

输出一个整数，表示答案。

数据范围

1≤N,M≤10^5, |Ai|≤10^4

输入样例：

5 2 
2 -3 2 -1 2

输出样例：

解析

在选择一个连续的片段时，连续的正数和连续的负数，要选一定是一起选，不会只选部分

反证法：

正数片段：显然我们把该连续的正数片段剩余部分也选上，不会使结果变差
负数片段：显然我们不选负数的片段，不会使结果变差

于是我们就可以把连续的正数和连续的负数看做成一个线段，则原问题为：选择不超过

个不连续的线段，使得总和最大

不妨设正数线段个数为

cnt

，当前选择的方案下的元素总和为

显然，如果可以的话，我们应该尽可能只选正数线段，不选负数线段，这样元素总和肯定更大

若

cnt \le m

，则最优方案毫无疑问是选出所有的

cnt

个正数线段

若

cnt \ge m

，则我们需要合并或者去掉

k = cnt - m

个线段

合并一个负数线段

a_i

：

S' = S - |a_i|

；去掉一个正数线段

a_i

：

S' = S - a_i

因此，两个操作对于全局的影响都可以处理成

S' = S - |a_i|

的形式

又由于负数线段和正数线段是交替存在的，即原问题就等价于 “在所有的正负数线段里选出

条两两互不相邻的线段，且选择的线段绝对值之和最小”

于是成功将模型转换为二叉堆章节的 “数据备份” 这题了

// 连续正负数分段（0可以被归为任意一段去）
int k = 1;
for (int i = 1; i <= n; i ++ )
{
    int t; scanf("%d", &t);
    if ((long long) a[k] * t < 0) a[ ++ k] = t;
    else a[k] += t;
}

n = k;

int cnt = 0, sum = 0;
for (int i = 1; i <= n; i ++ )
    if (a[i] > 0)
        cnt ++ , sum += a[i];

initialize();
for (int i = 1; i <= n; i ++ )
{
    int p = insert(node[tail].prev, a[i]);
    heap.push({abs(a[i]), p});
}

while (cnt > m)
{
    while (node[heap.top().y].st) heap.pop();
    PII top = heap.top(); heap.pop();
    int val = top.x, p = top.y;
    // 不删在左右两端的负数段（不减少正数段数），但可以删左右两端正数段
    if (node[p].prev != head && node[p].next != tail || node[p].value > 0)
    {
        cnt -- ;
        sum -= val;
        
        int prev = node[p].prev, next = node[p].next;
        node[p].value += node[prev].value + node[next].value;
        
        heap.push({abs(node[p].value), p});
        if (prev != head) remove(prev);
        if (next != tail) remove(next);
    }
}
printf("%d\n", sum);

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-02-09，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法