xxyQwQ's Blog
0%

发表于 分类于

题目描述

ACMOJ - 14151 - 出栈序列

现有 $n$ 个整数 $1,2,\dots ,n$ 依次入栈，判断出栈序列的合法性

题目存在 $T$ 组测试数据，每组数据规模为 $n$，保证 $T\leq 10,n\leq 10^6$

问题分析

事实上，我们直接对出入栈操作进行模拟即可

按照出栈顺序遍历每一个整数 $a_i$，若其未曾入栈，将所有不大于 $a_i$ 的整数依次入栈，并将 $a_i$ 弹出，若其已在栈中，倘若其在栈顶，弹出即可，否则断言该出栈序列不合法

该算法的时间复杂度为 $O(T\cdot n)$

代码

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
#include <cstdio>
#include <cctype>
#include <cstdarg>
#include <cstring>
const int NMAX = 1000005;

template <typename T>
void read(T &value)
{
    T result = T(0);
    bool sign = false;
    char word = getchar();
    while (!isdigit(word))
        sign |= (word == '-'), word = getchar();
    while (isdigit(word))
        result = result * 10 + T(word - '0'), word = getchar();
    value = sign ? -result : result;
}

int stack[NMAX], top, current, a[NMAX], T, n;

int main()
{
    read(T);
    while (T--)
    {
        bool fail = false;
        top = 0, current = 0;
        read(n);
        for (int i = 1; i <= n; i++)
            read(a[i]);
        for (int i = 1; i <= n; i++)
        {
            if (a[i] <= current && stack[top] != a[i])
            {
                fail = true;
                break;
            }
            if (stack[top] == a[i])
            {
                top--;
                continue;
            }
            while (current < a[i])
            {
                current++;
                stack[++top] = current;
            }
            top--;
        }
        printf("%s\n", fail ? "No" : "Yes");
    }
    return 0;
}

发表于 分类于

题目描述

ACMOJ - 1080 - 后缀表达式

计算给定后缀表达式的值，其中@为表达式终止符，.为操作数结束标识

问题分析

按照后缀表达式的规则计算即可，推荐使用字符串进行处理，注意操作数的完整提取

代码

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
#include <cstdio>
#include <cctype>
const int NMAX = 10005;

char suffix[NMAX];
int stack[NMAX], top = 0;

int main()
{
    scanf("%s", suffix);
    for (int p = 0; suffix[p] != '@'; p++)
    {
        if (isdigit(suffix[p]))
        {
            int oprand = 0;
            while (suffix[p] != '.')
                oprand = oprand * 10 + suffix[p] - '0', p++;
            stack[++top] = oprand;
        }
        else if (suffix[p] == '+')
            top--, stack[top] = stack[top] + stack[top + 1];
        else if (suffix[p] == '-')
            top--, stack[top] = stack[top] - stack[top + 1];
        else if (suffix[p] == '*')
            top--, stack[top] = stack[top] * stack[top + 1];
        else if (suffix[p] == '/')
            top--, stack[top] = stack[top] / stack[top + 1];
    }
    printf("%d\n", stack[top]);
    return 0;
}

发表于 分类于

题目描述

ACMOJ - 1058 - 单循环链表

按模板代码实现单循环链表，支持如下操作：

  1. 返回链表长度
  2. 在位置 $i$ 插入一个数
  3. 输出位置 $i$ 的数
  4. 删除位置 $i$ 的数
  5. 删除位置 $i$ 的数并将其插入链表尾端
  6. 输出链表中最大的数

无复杂度要求，但不允许发生内存泄漏

问题分析

标准的单链表实现，注意动态内存管理即可

代码

此处给出核心部分代码实现

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
115
116
117
118
119
120
121
122
123
124
125
126
127
namespace LIST
{
    struct NODE
    {
        int data;
        NODE *next;
        NODE() : next(nullptr) {}
        NODE(int d, NODE *n = nullptr) : data(d), next(n) {}
        ~NODE() {}
    };

    NODE *head = nullptr;
    int len = 0;

    void init()
    {
        len = 0;
    }

    NODE *move(int i)
    {
        NODE *p = head;
        while (i-- > 0)
            p = p->next;
        return p;
    }

    void insert(int i, int x)
    {
        if (i == 0)
        {
            NODE *p = move(len - 1);
            if (len == 0)
            {
                head = new NODE(x);
                head->next = head;
            }
            else
                head = p->next = new NODE(x, head);
        }
        else
        {
            NODE *p = move(i - 1);
            p->next = new NODE(x, p->next);
        }
        len++;
    }

    void remove(int i)
    {
        if (i == 0)
        {
            NODE *p = move(len - 1), *q = p->next;
            head = p->next = q->next;
            delete q;
        }
        else
        {
            NODE *p = move(i - 1), *q = p->next;
            p->next = q->next;
            delete q;
        }
        len--;
        if (len == 0)
            head->next = nullptr;
    }

    void remove_insert(int i)
    {
        int x;
        if (i == 0)
        {
            NODE *p = move(len - 1), *q = p->next;
            head = p->next = q->next;
            x = q->data;
            delete q;
        }
        else
        {
            NODE *p = move(i - 1), *q = p->next;
            p->next = q->next;
            x = q->data;
            delete q;
        }
        len--;
        insert(len, x);
    }

    void get_length()
    {
        cout << len << endl;
    }

    void query(int i)
    {
        if (i < 0 || i >= len)
        {
            cout << -1 << endl;
            return;
        }
        cout << move(i)->data << endl;
    }

    void get_max()
    {
        NODE *p = head;
        int k = -1;
        for (int i = 0; i < len; i++)
        {
            if (p->data > k)
                k = p->data;
            p = p->next;
        }
        cout << k << endl;
    }

    void clear()
    {
        NODE *p = head, *q;
        for (int i = 0; i < len; i++)
        {
            q = p->next;
            delete p;
            p = q;
        }
    }
}

发表于 分类于

题目描述

ACMOJ - 11617 - 字符串相加

给定仅包含数字的字符串 $a,b$，将其按整数规则相加，并返回相应字符串，要求使用指针风格实现

问题分析

这是一道朴素的高精度加法问题，按照竖式加法规则实现即可，若 $a,b$ 长度不同，先对齐后计算

注意如下问题：

  • 处理好字符与整数之间的转换关系
  • 在字符串末尾添加'\0'作为结束符
  • 释放动态内存以避免Memory Leak错误

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
const int NMAX = 1005;

char a[NMAX], b[NMAX], *answer;
int n, m;

char *add(char *p, char *q)
{
    int p_len = strlen(p), q_len = strlen(q), s_len = 0;
    char *s = new char[NMAX];
    for (int i = 0; i < 1000; i++)
        s[i] = '0';
    for (int i = 0; i < 1000; i++)
    {
        int u = i < p_len ? p[i] - '0' : 0, v = i < q_len ? q[i] - '0' : 0, c = s[i] - '0', w = u + v + c;
        s[i] = '0' + w % 10, s[i + 1] = '0' + w / 10;
        if (s[i] != '0')
            s_len = i + 1;
    }
    s[s_len] = '\0';
    return s;
}

int main()
{
    scanf("%d%d%s%s", &n, &m, a, b);
    printf("%s\n", answer = add(a, b));
    delete[] answer;
    return 0;
}

发表于 分类于

题目描述

ACMOJ - 11038 - 约瑟夫环

有 $n$ 个人编号 $1,2,\dots ,n$ 轮流报数（首轮从 $1$ 号开始报数），给定一组 $k_1,k_2,\dots ,k_{n-1}$，第 $i$ 轮报数 $k_i$ 的人出圈，并从下家开始重新报数，问最后留下的人的编号，保证 $n\leq 10^4,k_i\leq 10^8$

问题分析

注意到 $k_i$ 的规模并不重要，对剩余人数取模即有 $k_i\leq n$，利用循环链表可以实现 $O(n^2)$ 的模拟

下面介绍一种递推做法：

逆向考虑过程，尝试通过第 $i$ 轮的起始位置反推第 $i-1$ 轮的起始位置，在保证相对顺序不变的前提下，我们认为第 $i$ 轮开始时圈内 $n-i+1$ 人的相对位置即为 $0,1,2,\dots ,n-i$

记第 $i$ 轮的起始位置为 $a_i$，其中 $a_n=0$，反推即有关系 $a_i=(a_{i+1}+k_i)\mod (n-i+1)$，所求 $a_1$ 即为最后留下的人与 $1$ 号的相对位置，此时 $a_1+1$ 即为答案

该算法的时间复杂度为 $O(n)$，即使 $n\leq 10^8$ 仍可以高效解决问题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <cstdio>
const int NMAX = 10005;

int k[NMAX], n, answer = 0;

int main()
{
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
        scanf("%d", &k[i]);
    for (int i = 2; i <= n; i++)
        (answer += k[n - i + 1]) %= i;
    printf("%d\n", ++answer);
    return 0;
}

发表于 更新于 分类于

题目描述

ACMOJ - 1033 - 行列式求值

求 $n$ 阶行列式 $\begin{vmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\
a_{21} & a_{22} & \cdots & a_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
a_{n1} & a_{n2} & \cdots & a_{nn}\end{vmatrix}$ 的值，保证 $n\leq 10$ 且答案在int范围内

问题分析

行列式的求解有多种方法，具体参见《线性代数》教材

此处介绍以下三种方法：

  • 全排列法：利用行列式的全排列定义直接计算
  • 余子式法：利用行列式的按行展开性质递归计算
  • 高斯消元：利用初等变换将行列式化为上三角阵简化计算

全排列法

设 $A=(a_{ij})_{n\times n}\in \mathbb{K}^{n\times n}$，则 $|A|=\sum \limits _{j_1j_2\dots j_n}(-1)^{\tau(j_1j_2\dots j_n)}a_{1j_1}a_{2j_2}\dots a_{nj_n}$

利用std::next_permutation函数构造 $1,2,\dots ,n$ 的全排列，借助函数统计逆序对数，完成计算

时间复杂度为 $O(n^2\cdot n!)$，利用分治求逆序对可以优化到 $O(n\log n\cdot n!)$

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
#include <cstdio>
#include <algorithm>

int a[15][15], p[15], n, answer;

int invertion(int v[], int k)
{
    int r = 0;
    for (int i = 1; i <= k; i++)
        for (int j = i + 1; j <= k; j++)
            if (v[i] > v[j])
                r++;
    return r;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", &a[i][j]);
    for (int i = 1; i <= n; i++)
        p[i] = i;
    do
    {
        int term = 1;
        for (int i = 1; i <= n; i++)
            term *= a[i][p[i]];
        term *= (invertion(p, n) & 1) ? -1 : 1;
        answer += term;
    } while (std::next_permutation(p + 1, p + n + 1));
    printf("%d\n", answer);
    return 0;
}

余子式法

设 $D=|a_{ij}|_{n\times n}$，则 $D=\sum \limits _{j=1}^na_{1j}A_{1j}$，其中 $A_{1j}$ 为 $D$ 的代数余子式

为实现递归计算，我们动态开辟数组，并且将二维数组压缩至一维，即构造映射 $a_{ij}\rightarrow a_{in+j}$，以此解决函数传参问题

时间复杂度为 $O(n!)$，实际运行快于全排列法

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
#include <cstdio>

int a[105], n;

int det(int *v, int k)
{
    if (k == 1)
        return *v;
    int r = 0;
    for (int p = 0; p < k; p++)
    {
        int *s = new int[(k - 1) * (k - 1)];
        for (int i = 0; i < k - 1; i++)
            for (int j = 0; j < k - 1; j++)
                *(s + i * (k - 1) + j) = *(v + (i + 1) * k + (j < p ? j : (j + 1)));
        r += ((p & 1) ? -1 : 1) * *(v + p) * det(s, k - 1);
        delete[] s;
    }
    return r;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", a + i * n + j);
    printf("%d\n", det(a, n));
    return 0;
}

高斯消元

  • 依次遍历第 $i=1,2,\dots ,n$ 行，将 $a_{ii}$ 作为主元
  • 依次遍历第 $j=i+1,i+2,\dots ,n$ 行，通过初等变换将 $a_{ji}$ 消为 $0$
  • 特别地，若 $a_{ii}=0$，则遍历 $j=i+1,i+2,\dots ,n$ 寻找 $a_{ji}\neq 0$，并将第 $i$ 行与第 $j$ 行交换
    （每次交换两行会使结果的正负性反转）
  • 若 $a_{ji}$ 全为 $0$，行列式的值即为 $0$
  • 消元完成得到上三角阵 $D’$，其对角线元素乘积即为行列式的结果

时间复杂度为 $O(n^3)$，远优于前两种方法，但存在浮点数精度的局限性，代码实现中需要思考如下问题：

  • 如何判定两个浮点数相等？
  • 输出结果是否可以强制转换为整数？
  • 如果不行，应该怎么做？
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
#include <cstdio>
#include <cmath>
const double eps = 1e-5;

double a[15][15];
int n;

bool equal(double x, double y)
{
    return fabs(x - y) < eps;
}

template <typename T>
void swap(T &x, T &y)
{
    T temp = x;
    x = y, y = temp;
}

double determination()
{
    double r = 1;
    for (int i = 1; i <= n; i++)
    {
        if (equal(a[i][i], 0))
        {
            int j;
            for (j = i + 1; j <= n; j++)
                if (!equal(a[j][i], 0))
                    break;
            if (j == n + 1)
                return 0;
            r *= -1;
            for (int k = 1; k <= n; k++)
                swap(a[i][k], a[j][k]);
        }
        for (int j = i + 1; j <= n; j++)
        {
            double p = -(a[j][i] / a[i][i]);
            for (int k = i; k <= n; k++)
                a[j][k] += p * a[i][k];
        }
    }
    for (int i = 1; i <= n; i++)
        r *= a[i][i];
    return r;
}

int regularize(double x)
{
    double y = fabs(x);
    return (x >= 0 ? 1 : -1) * int(y + 0.5);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%lf", &a[i][j]);
    double result = determination();
    printf("%d\n", regularize(result));
    return 0;
}

发表于 分类于

题目描述

ACMOJ - 1014 - 数列操作

给出两个整数序列 $a_1,a_2,\dots ,a_n$ 和 $b_1,b_2,\dots ,b_n$，对 $\{ a_n\}$ 存在如下两种操作：

  • 将某个区间的数全部 $+1$
  • 将某个区间的数全部 $-1$

试求至少经过多少次操作可以将序列 $\{ a_n\}$ 变为 $\{ b_n\}$

问题分析

事实上，通过等价变换，可以使问题大大简化

首先，我们并不关心 $\{ a_n\}$ 和 $\{ b_n\}$ 具体的数值，影响问题答案的是两者的差异，因此我们对两序列作差，即令 $c_n=a_n-b_n$，此时我们只需要对 $\{ c_n\}$ 进行同样的操作，使得 $\forall i=1,2,\dots ,n$ 都有 $c_i=0$

现在我们引入差分序列的概念

对于序列 $x_1,x_2,\dots ,x_n$，特别规定 $x_0=0$，令 $y_n=x_n-x_{n-1}$ 可以得到新序列 $y_1,y_2,\dots ,y_n$，则 $\{ y_n\}$ 记为 $\{ x_n\}$ 的差分序列，相应地，$\{ x_n\}$ 记为 $\{ y_n\}$ 的前缀和序列

差分与前缀和是一对互逆的序列变换，在静态的区间求和与区间修改问题中，可以将单次操作的复杂度降低为 $O(1)$

引入上述概念后，我们重新审视问题

对序列 $\{ c_n\}$ 作差分，得到差分序列 $\{ d_n\}$，则 $d_i$ 表示原序列中后一项与前一项的差值，我们将原序列中区间 $c_i,c_{i+1},\dots ,c_j$ 全部 $+1$，相当于在差分序列中令 $d_i+1$，并令 $d_{j+1}-1$，该等价性可以通过求前缀和的方式进行验证

至此，问题已经简化为：

已知序列 $d_1,d_2,\dots ,d_n$，每次选取 $i\leq j$，可以令 $d_i+1,d_{j+1}-1$ 或 $d_i-1,d_{j+1}+1$，求将 $\{ d_n\}$ 全部变为 $0$ 的最小操作次数

不难想到贪心策略，每次选取正负性相反的一对 $d_i,d_{j+1}$，其中正数 $-1$，负数 $+1$，最终无法配对的数字与 $d_{n+1}$ 相消（相当于在原序列中，操作该数之后的整个区间）

因此，最终答案即为 $\max \left \{ \sum \limits _{d_i>0} |d_i|,\ \sum \limits _{d_i<0} |d_i| \right \}$，其正确性不难验证，算法的时间复杂度为 $O(n)$

一些细节

  1. 目标要使所有的 $d_i=0$，因此 $d_1$ 也需要被考虑
  2. 求和变量应当使用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 <cstdio>
#include <cctype>
#include <cstdarg>
using LL = long long;
const int NMAX = 100005;

LL p, q;
int a[NMAX], n;

template <typename T>
void read(T &value)
{
    T result = T(0);
    bool sign = false;
    char word = getchar();
    while (!isdigit(word))
        sign |= (word == '-'), word = getchar();
    while (isdigit(word))
        result = result * 10 + T(word - '0'), word = getchar();
    value = sign ? -result : result;
}

template <typename T, typename... Ts>
void read(T &value, Ts &...remain)
{
    read(value);
    read(remain...);
}

int main()
{
    read(n);
    for (int i = 1; i <= n; i++)
        read(a[i]);
    for (int i = 1, x; i <= n; i++)
        read(x), a[i] -= x;
    for (int i = 1; i <= n; i++)
    {
        int x = a[i] - a[i - 1];
        if (x > 0)
            p += x;
        else
            q -= x;
    }
    printf("%lld\n", p > q ? p : q);
    return 0;
}

发表于 分类于

题目描述

ACMOJ - 1572 - 填满棋盘

在 $n$ 行 $m$ 列的棋盘上，挖去 $k$ 个格子，用若干 $1\times 2$ 的棋子不可重叠地放置在剩余格子中，问是否可以铺满剩余棋盘

共有 $T$ 组测试数据（$T\leq 3$），每组数据保证 $n,m\leq 32$，$k<n\times m$

问题分析

数据范围很小，即使 $O(n^2m^2)$ 的算法也可以轻松解决

题目以棋盘为背景，因此很容易想到国际象棋棋盘的黑白交错。我们以相同的方式给棋盘染色，则放置的棋子有如下性质：

  • 棋子必然位于一对相邻的黑白格上
  • 只要存在一对相邻的黑白格，必然可以放置一枚棋子

我们不妨将每个格子视为一个节点，从每个黑色格子出发，向与其相邻的每个白色格子连边，这样便形成了一张二分图。该二分图完美建模了棋子放置的情况，一对匹配恰好代表一枚棋子被放置，二分图的最大匹配恰好代表放置棋子的最大数目，故有结论：

  • 棋子可以铺满剩余棋盘的充要条件是：对应二分图的最大匹配等于剩余格数的一半

在此二分图上跑匈牙利算法，即有 $O(n^2m^2)$ 的复杂度，但是也可以考虑复杂度更加优秀的网络流方法

我们以如下方式构造网络图：

  • 从超级源点出发，向每个黑色格子连一条容量为 $1$ 的边
  • 从每个白色格子出发，向超级汇点连一条容量为 $1$ 的边
  • 从每个黑色格子出发，向与其相邻的每个白色格子连一条容量为 $1$ 的边

在此网络图上采用 Dinic 算法跑最大流，即为二分图的最大匹配，由于约有 $nm$ 个节点和 $2nm$ 条边，时间复杂度为 $O(m^{\frac{3}{2}}n^{\frac{3}{2}})$（实际上根本跑不满）

一些细节

  1. 由于存在多组测试数据，每次要清空head数组和broken数组，并重置原点和汇点的标号
  2. 每次total要重置且初始值为 $1$（老生常谈）
  3. 数组大小至少为 $32\times 32+2=1026$，我起初开到 $1025$ 发生了一些不可预知的 TLE（悲）

代码

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <cstdio>
#include <cctype>
#include <cstdarg>
#include <cstring>
#include <queue>
#include <algorithm>
const int NMAX = 1035, INF = 0x3f3f3f3f;
const int dx[5] = {-1, 0, 1, 0}, dy[5] = {0, -1, 0, 1};

template <typename T>
void read(T &value)
{
    T result = T(0);
    bool sign = false;
    char word = getchar();
    while (!isdigit(word))
        sign |= (word == '-'), word = getchar();
    while (isdigit(word))
        result = result * 10 + T(word - '0'), word = getchar();
    value = sign ? -result : result;
}

template <typename T, typename... Ts>
void read(T &value, Ts &...remain)
{
    read(value);
    read(remain...);
}

struct Edge
{
    int t, w, n;
    Edge(int _t = 0, int _w = 0, int _n = 0) : t(_t), w(_w), n(_n) {}
} edge[NMAX << 3];
int head[NMAX], start[NMAX], depth[NMAX], T, n, m, k, s, t, total;
bool broken[35][35];

inline void insert(int u, int v, int w)
{
    edge[++total] = Edge(v, w, head[u]);
    head[u] = total;
}

bool bfs()
{
    memset(depth, 0, sizeof(depth)), memcpy(start, head, sizeof(head));
    std::queue<int> q;
    q.push(s), depth[s] = 1;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i; i = edge[i].n)
        {
            int v = edge[i].t;
            if (edge[i].w && !depth[v])
                depth[v] = depth[u] + 1, q.push(v);
        }
    }
    return depth[t];
}

int dfs(int u, int a)
{
    if (u == t || !a)
        return a;
    int f, r = 0;
    for (int &i = start[u]; i; i = edge[i].n)
    {
        int v = edge[i].t;
        if (edge[i].w && depth[v] == depth[u] + 1 && (f = dfs(v, std::min(a, edge[i].w))))
        {
            r += f, a -= f;
            edge[i].w -= f, edge[i ^ 1].w += f;
            if (!a)
                break;
        }
    }
    return r;
}

int dinic()
{
    int flow = 0;
    while (bfs())
        flow += dfs(s, INF);
    return flow;
}

void construct()
{
    memset(head, 0, sizeof(head)), memset(broken, 0, sizeof(broken));
    read(n, m, k), s = 0, t = n * m + 1, total = 1;
    for (int i = 1, x, y; i <= k; i++)
        read(x, y), broken[x][y] = true;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (broken[i][j])
                continue;
            int p = (i - 1) * m + j;
            if ((i + j) & 1)
                insert(p, t, 1), insert(t, p, 0);
            else
            {
                insert(s, p, 1), insert(p, s, 0);
                for (int _k = 0; _k < 4; _k++)
                {
                    int _i = i + dx[_k], _j = j + dy[_k];
                    if (_i < 1 || _i > n || _j < 1 || _j > m || broken[_i][_j])
                        continue;
                    int _p = (_i - 1) * m + _j;
                    insert(p, _p, 1), insert(_p, p, 0);
                }
            }
        }
}

int main()
{
    read(T);
    while (T--)
    {
        construct();
        int flow = dinic();
        printf("%s\n", (2 * flow == n * m - k) ? "YES" : "NO");
    }
    return 0;
}

发表于 更新于 分类于

入学前的暑假

高考结束后，大家各自奔赴，享受生活。年级里留下约二十人备战强基。

蹲在教室自习实在是闲不住，我买了一本同济高数自学。这些高数知识看似复杂，实际上并没有很大的思维难度。同济教材的编写逻辑有一种离散的美，索性囫囵吞枣，面向习题学习。所幸配套教辅很不错，扫一遍知识点就可以开始做题。习题大多很简单，偶尔有不会写的就看一眼答案，写完习题知识点也就比较熟练了。

高考出分，比我预期的好很多，既然大家都考得不好，心里顿时平衡了。THU强基笔试，数学77/100，物化25/100，由于没有评级，作文60/200，直接滚蛋。（THU强基一如既往地黑，没有评级就别去陪跑，不如报PKU强基/享受生活）现在回想起来，强基没过也未必是一件坏事。如果不学数学和信息类专业，我大学以前积攒的所有优势就在顷刻间湮灭了，若是在天坑中摸爬滚打，前途尚未可知，那未来才是暗无天日。

疫情让我放弃了出游计划，遂闷在家里吃喝玩乐看高数，另给学妹辅导了高三数学，备课教学实在是很有意思的一件事。暑假均摊地看完了高数，心想大学数学不过如此，后来了解到培养计划里是数分，这下成小丑了。（也不能说完全白学，毕竟刷完了两册习题）

21级交大的军训改在了入学的暑假，于是早早地去报到了。

致远工科

入学前，我对交大政策的了解相当匮乏，甚至不知道致远学院的存在。致远工科是在志愿填报的时候签约的，于是填表、面谈，走完流程就莫名其妙地进了。开学前，我听了某新生群的讲座，又刷了很多知乎，才了解到前两年的致远工科在网络上差评如潮。一度想要跑路，最后为了5000的低保抱着试试看的心态留了下来。

第一学期，致远工科把我的数分、线代、离散都换成了荣誉课，课程难度确实有所加深，更重要的是能感受到身边高手如云，这些同学的刻苦和专注都令我倍感压力。因为这些特殊安排，我大多数的课程并不和本专业的同学一起上，这潜移默化地影响着我的社交范围。

即使在交大内部，对于致远工科的评价也是毁誉参半，细致的讨论和评述已经不在本文的范围之内。

数分选拔考

学期刚开始的几周，我过得相当轻松。C++和离散对我而言并没有什么难度，唯独需要花费精力的就是数分和线代。而老师只会在课后留少量的习题，这些任务很快就可以完成，之后便可以随意摸鱼了。此时，我对大学的考试并没有什么概念，自然也不会产生忧虑。

对于致远工科的同学而言，数分选拔考并不产生选拔作用，只是老师强制要求参加的一次检测。大概由于是选拔性考试，题目难度偏高，我只考了78/100。虽然只是一次无关紧要的考试，这个分数依旧震撼了我。老师告诉我们，选拔进入荣誉课的分数线是70左右，而我所在教学班的均分不到50。这表明很多致远工科的同学其实并不具备足够的实力（至少在考试排名上）学习荣誉课。当然，也有不少大佬80+甚至90+的分数震撼着我。

数分选拔考提醒我，仅仅完成老师布置的习题只能混个及格，想要一个不错的分数还需要更多的努力。后来我刷了一些吉米多维奇，但是题量太大劝退，遂改变策略，把教材每一节的习题写完（交大版数分的习题其实并不多），也取得了不错的成绩，小测100/100，期中97/100，期末100/100。当然，这个分数完全不能体现真正的分析功底，只能说掌握了基本的知识和套路。

图书馆

图书馆是一个学习效率很高的地方，因此我常常去图书馆写作业。起初我喜欢去主图，因为主图很近，我很懒。我还记得开学第一天去图书馆，坐在我对面的是一个很可爱的女生，她在看陈纪修的《数学分析》，旁边的女生看的是交大版的《线性代数》，于是我立刻猜出了她们的专业，后来我果然在荣誉课上看到了其中一个女生。之后来主图也偶尔能看见熟悉的面孔。这就是致远吧，我如是对自己说。后来我发现，包图的设施更加完善，光线也明亮一些，也难怪包图的生意如此火爆。每次去包图，我都能看到不少致远的同学，其中有一些应该是图书馆的常客。（因为每次都能看见他们）

我观察到，去图书馆的频率能够反映我的学习状态。开始几周，我几乎每天都会去，毕竟怀着一腔热血进入交大，自然会想着好好努力。然而过了五六周以后，我开始看剧，先是火爆一时的《鱿鱼游戏》，接着去补《权力的游戏》，然后是各种国产剧，往往一看就是一整天。这样的生活节奏渐渐冲淡了学习的热情，于是变得懒散而颓废了。直到十二周左右，我心血来潮和室友Y去包图自习，久违的高效的学习状态重新唤醒了我，一段浑浑噩噩的日子才算结束。

考试周

大一上我对期末考试还是很重视的，提前两周就开始搜集复习材料和备考。从结果来看复习效果是不错的，但是过程上有很多无用功。比如花了不少时间复习思修和军理，事实上思修只需要把试卷填满，军理照着隔壁老师的重点半小时就可以复习完。印象比较深的是考数分前，我花了一天把范围内的书后习题全刷了一遍，现在回过头看，不禁感慨当时的效率奇高。（可能是包图有buff加成？）

考试的时候也是不紧不慢，有些题量很小的考试我都是考场里最后写完的。最大程度地利用时间，在一定程度上减少了犯错丢分的可能性。多数考试都是成竹在胸的感觉，除了大英（完全不会）和线代（战战兢兢）。有些课程出分很慢，但是结果还可以，数分、线代、离散、程设都满绩了也没什么遗憾。

寒假

大一上的寒假是极其短暂的，因为此前校历两次莫名其妙的改动，寒假从6周缩水成4周，算上往返掐头去尾只剩三周了。回家之前我买了基电和数据结构的教材，到家先颓废了几天，之后每天看几页书。数据结构比较简单，一周速通，顺便发现教材代码一堆错误，怀疑有些代码根本没跑过。过完春节，一天一章看完了大物第一册，然后寒假就基本结束了，基电看了几页一窍不通，数分也没来得及看（寄）。

末了参加了高中同学的聚餐，遂匆匆返校。

自律的前四周

发现一件怪事，每个学期开始的一段时间总会特别来劲。我计划在平时完成数分的所有书后习题，并且刷完基电辅导书。我发现这样做会搞得自己很忙，但还是坚持下来了，毕竟不刷点题这课属实是学不明白。

另一方面，大一下的课表比较阴间，集中体现在课程的时间分布不均匀，周三周四只有两节课，但是单周的周一可以撑满早八到晚九，想吃顿饭都赶不上。无奈我个人不能接受翘课，坚持每节课都认真上完。勤奋的日子在事后都显得模糊，只记得这四周仿佛是一晃而过。

封校

2022年3月9日是我难以忘却的第十九个生日，我在室友的叫唤中惊醒。我本已盘算了一周如何度过这个生日，或许请室友吃一顿吉姆丽德，也或许打一场酣畅淋漓的篮球赛，然而这些都随着封楼烟消云散了。学校的行动一如既往地悄无声息，当你想逃跑时已经太晚了，于是我们开始了长达一个半月的隔离生活，以及至今未能结束的网课生活。

最为难熬的应该是封楼之初的那几天，由于事发突然，后勤措施并不能准时到位，吃饭计划也要推迟几个小时。为了防止交叉感染，浴室也关闭了，这一周始终无法洗澡，只得任由自己在寝室里发臭。情况在3月15日有了变化，深夜里老师通知我们全员转运，在凌晨两点我住进了南洋北苑。南洋北苑是闲置的留学生公寓，单人间，独立卫浴。没想到因为疫情在上海体验了一次高档待遇，一番折腾之后我终于在凌晨四点入睡。两周之后，我们又被转运到汉庭酒店进行一周的健康管理，酒店的条件自然是不差，然而缺少适合学习的桌椅，只能躺在床上听网课，另外酒店的床过于柔软令我难以适应。住了一周汉庭酒店，最大的收获是凭借交大邮箱成为了尊贵的华住会铂金会员。

封校期间，网络成为了与外界沟通的唯一途径。我看到了太多，也明白了太多。形形色色的新闻和消息不断刷新我的世界观，以至于我开始麻木了，或许整个世界也在逐渐麻木。直至现在，无论多么离谱的消息，抑或是谣言出现在网络上，大家也并不觉得离谱，从而便轻易地相信了。永远不要指望所有人都有兼济天下的宽阔胸襟和修齐治平的崇高理想，唯有明哲保身才是第一要务。

谈谈网课

线上教学似乎有一种神奇的魔力，让所有人都失去学习的热情。从上网课开始，我身边很多人便彻底开摆了，我自己的学习效率也难免有所降低。

线下授课模式改为线上，彻底改变了一些课程的授课节奏。以数学分析课程为例，陈克应老师的教学无疑是一流的，板书清晰，节奏适中。由于腾讯会议的共享功能和屏幕大小的限制，只能通过纸上手写和PPT展示授课，这种方式令学生不得不在听课时反复切换界面，大大降低了听课效率。同时，没有了教室内的同学和环境，课堂的氛围感也大打折扣。主客观原因的共同作用下，我时常感到昏昏欲睡，只能挣扎着听完整节课。

封控的另一弊端体现在生活上。隔离使我只能在一块狭小的空间活动，阻断了所有户外锻炼。身体素质的下降直接导致活力的下降，于是做任何事都会缺乏斗志。学习不是关在屋子里闭门造车就能成功的，它还需要一些其他的活动补充动力，形成良性循环。

对于自制力差的群体，网课更为致命。没有了严格的时间约束和无形的集体压力，原本鞭策学习的客观因素全然消失，保持勤奋刻苦的状态简直是一种奢求了。

期末

临近期末无疑是一件非常痛苦的事情。十五周前后，所有的任务压力潮涌而来。且不论各门课程最后几章难度的提升，光是平时作业和大作业就可以压得我喘不过气。星火培训班也在周末开展培训和小组学习，把时间挤压殆尽。一想到期末考试即将来临，难免有一种黑云压城暗无天日的恐惧感。在那段日子里，我从早到晚都对着电脑写大作业和论文，时常熬到凌晨。在缺乏锻炼的情况下，我的身体耐力几乎到达了极限，所幸最后还是坚持下来。

我意识到，总有些时候会面临繁重的任务，被巨大的任务量压得喘不过气。而完成它们恰恰是没有捷径的。无法承受者或是自暴自弃，或是情绪崩溃，落得大败而归的结局。我的毅力和决心，正是在一次次磨砺中成长的。对于持久性的任务，不必苛求当日解决，也不必事事苛求完美，知天命尽人事即可。

考试周，我和室友Y相约每天去东下院自习。譬如数据结构这类课程比较简单，我便直接刷历年的期末真题了事。细细想来，工巧的算法被压缩成无趣的试题，深邃的思想被考成死记硬背的文科题，实在令人遗憾和痛心。而譬如数学分析、电路理论这样的硬骨头，我便大量地刷题，提高熟练度的同时精准查漏补缺，最后留下一些时间刷真题。我深知这学期的学习属实是一种敷衍，老师们大概也知道，因此我的考试成绩竟还说得过去。大物、电路、数电、数据结构都满绩了，唯独遗憾最有把握的数分翻了车，就当是为自己复习时的自以为是付出了代价。

我想，所谓的努力学习，追求的是高效率和高收益，而不是为了努力本身。盯着书本埋头苦学一整天，有时候还不如出门散散心，再专注地学上几个小时。保持一种轻松愉悦的心态，更容易专注于学习，亦不会因为密集的考试而倍感焦虑。

写在最后

高中的班主任曾说：别以为上了大学就轻松了。如今上了大学，深以为然。大一的忙碌远远超出了我的预期，好像一场快节奏的梦。当我以平静的眼光回顾这一年，我庆幸自己尚未迷失。这一年有诸多遗憾，没能多去校外走一走，甚至没能过上一个像样的大学生活，但这些都是琐碎的小事了。人生不如意十之八九，我想我可以算作幸运的。也与读者共勉，不负大学时光。

发表于 分类于

题目描述

ACMOJ - 1485 - 纯真丁一郎

给出一列 $n$ 个互不相同的数字 $a_1,a_2,\dots ,a_n$，定义一对 $i,j$ 满足性质当且仅当 $a_i,a_j$ 大于它们之间的所有数字 $a_{i+1},a_{i+2},\dots ,a_{j-1}$

子问题1：试求满足性质的数对总数

子问题2：给出 $m$ 次询问，每次限定 $i$ 范围为 $[l,r]$，但 $j$ 不限，求此时满足性质的数对总数

时间复杂度要求

虽然 $n,m\leq 10^6$ ，但要求实现 $O(n+m)$ 的算法

问题分析

时间复杂度要求已经明示线性解法了，我们大胆猜测本题正解是单调队列/单调栈

线性复杂度表明，对于每次询问我们要实现 $O(1)$ 查询，那么方案数一定满足可加性，所以要想办法求出：对于每个取定的位置 $i$ ，有多少相应的 $j\in[1,n]$ ，使得 $i,j$ 满足性质（记为 $v[i]$)

现在考虑 $v[i]$ 数组的求解，我们不妨先考虑 $a_i$ 的左侧，$a_1,a_2,\dots ,a_{i-1}$ 中哪些数与 $a_i$ 满足性质，不难发现以下特征：

  • $a_i$ 以左第一个比它大的数 $a_p$ 会“遮挡”住所有 $a_p$ 左侧的数，即 $a_1,a_2,\dots ,a_{p-1}$ 不会对方案数产生贡献
  • 若 $a_i$ 左侧两数 $a_m,a_n$ 满足 $m<n$ 且 $a_m<a_n$，则 $a_n$ 会“遮挡”住 $a_m$，换言之，对于单调增加的子列 $a_s,a_{s+1},\dots ,a_t$，只有最右边的 $a_t$ 产生贡献

以上两个特征对于问题求解的简化至关重要，它告诉我们计算 $v[i]$ 时，不考虑：

  • “过大”的数，即 $a_p$ 以左的数
  • “过小”的数，即已经被自身右侧其他数“遮挡”的数

于是我们只需要维护一个单调栈，它满足从栈底到栈顶的元素单调递减，算法流程如下：

  • 让 $i$ 遍历 $1,2,\dots ,n$
  • 把栈顶部所有小于 $a[i]$ 的数全部弹出，每弹出一个数，$v[i]+1$ （这些数都会产生贡献)
  • 如果栈仍然非空，贡献再 $+1$（左侧第一个大于 $a[i]$ 的元素也会产生贡献）
  • 将 $a[i]$ 压入栈中

完成上述算法后，$v[i]$ 中已经得到了 $a_i$ 左侧能与之满足性质的匹配数

对于右侧，我们从右至左，完全对称地执行上述算法，即可得到相应的匹配数

正确求解 $v[i]$ 数组后，我们计算其前缀和 $r[i]$，对于每次询问 $x,y$ ，答案即为 $\sum \limits _{k=x}^y v[k]=r[y]-r[x-1]$，即可实现 $O(1)$ 查询

一些细节

  1. 题目允许 $i=j$ ，因此 $a_i$ 与自身的匹配也要计算一次贡献
  2. 前缀和数组类型应当为long long，避免求和时溢出int范围
  3. 完成左侧方案数的计算后应当将栈清空
  4. 对栈操作时刻注意判空
  5. 请学会高效的读入方式，cin容易直接超时

思考

为什么上述算法流程包含两重循环，但复杂度是 $O(n)$ 呢？

我们注意到对于每个 $a_i$，至多只会发生一次入栈，一次出栈，因此第二重循环的操作次数上限为 $2n$，请读者仔细体会

代码

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <cstdio>
const int SIZE = 1000005;

// ---------- 以下为链表栈的实现，可以忽略 ----------
template <typename ElementType>
class Stack
{
public:
    virtual ~Stack() {}
    virtual bool empty() const = 0;
    virtual void push(const ElementType &element) = 0;
    virtual ElementType pop() = 0;
    virtual ElementType top() const = 0;
    virtual void clear() = 0;
};

template <typename ElementType>
class LinkedStack : public Stack<ElementType>
{
private:
    struct StackNode
    {
        ElementType data;
        StackNode *next;
        StackNode() : next(nullptr) {}
        StackNode(const ElementType &_data, StackNode *_next = nullptr) : data(_data), next(_next) {}
        ~StackNode() {}
    };
    StackNode *head;

public:
    LinkedStack();
    ~LinkedStack();
    bool empty() const;
    void push(const ElementType &element);
    ElementType pop();
    ElementType top() const;
    void clear();
};

template <typename ElementType>
LinkedStack<ElementType>::LinkedStack()
{
    head = nullptr;
}

template <typename ElementType>
LinkedStack<ElementType>::~LinkedStack()
{
    clear();
}

template <typename ElementType>
bool LinkedStack<ElementType>::empty() const
{
    return head == nullptr;
}

template <typename ElementType>
void LinkedStack<ElementType>::push(const ElementType &element)
{
    head = new StackNode(element, head);
}

template <typename ElementType>
ElementType LinkedStack<ElementType>::pop()
{
    if (head == nullptr)
        throw Stack is already empty!;
    StackNode *temp = head;
    ElementType value = temp->data;
    head = head->next;
    delete temp;
    return value;
}

template <typename ElementType>
ElementType LinkedStack<ElementType>::top() const
{
    if (head == nullptr)
        throw Stack is already empty!;
    return head->data;
}

template <typename ElementType>
void LinkedStack<ElementType>::clear()
{
    StackNode *temp;
    while (head != nullptr)
    {
        temp = head;
        head = head->next;
        delete temp;
    }
}
// ---------- 以上为链表栈的实现，可以忽略 ----------

LinkedStack<int> s;
long long r[SIZE]; // Notice the summary can exceed range of int
int v[SIZE], h[SIZE], n, m;

int main()
{
    scanf(%d%d, &n, &m);
    for (int i = 1; i <= n; i++)
    {
        v[i] = 1; // Stand at the same position
        scanf(%d, &h[i]);
    }
    s.push(1);
    for (int i = 2; i <= n; i++) // Count on the left side
    {
        while (!s.empty() && h[s.top()] < h[i])
        {
            s.pop();
            v[i]++;
        }
        if (!s.empty())
            v[i]++;
        s.push(i);
    }
    while (!s.empty()) // Clear stack for next direction
        s.pop();
    s.push(n);
    for (int i = n - 1; i; i--) // Count on the right side
    {
        while (!s.empty() && h[s.top()] < h[i])
        {
            s.pop();
            v[i]++;
        }
        if (!s.empty())
            v[i]++;
        s.push(i);
    }
    for (int i = 1; i <= n; i++) // Calculate prefix summary to accelerate
        r[i] = r[i - 1] + v[i];
    printf(%lld\n, r[n]); // r[n] is the total summary
    while (m--)
    {
        int x, y;
        scanf(%d%d, &x, &y);
        printf(%lld\n, r[y] - r[x - 1]); // Summary from v[x] to v[y] is r[y] - r[x - 1]
    }
    return 0;
}