T1 乘方

题目描述

小文同学刚刚接触了信息学竞赛，有一天她遇到了这样一个题：给定正整数 $a$ 和 $b$，求 $a^b$ 的值是多少。

$a^b$ 即 $b$ 个 $a$ 相乘的值，例如 $2^3$ 即为 $3$ 个 $2$ 相乘，结果为 $2 \times 2 \times 2 = 8$。

“简单！”小文心想，同时很快就写出了一份程序，可是测试时却出现了错误。

小文很快意识到，她的程序里的变量都是 int 类型的。在大多数机器上，int 类型能表示的最大数为 $2^{31} - 1$，因此只要计算结果超过这个数，她的程序就会出现错误。

由于小文刚刚学会编程，她担心使用 int 计算会出现问题。因此她希望你在 $a^b$ 的值超过 ${10}^9$ 时，输出一个 -1 进行警示，否则就输出正确的 $a^b$ 的值。

然而小文还是不知道怎么实现这份程序，因此她想请你帮忙。

输入格式

输入共一行，两个正整数 $a, b$。

输出格式

输出共一行，如果 $a^b$ 的值不超过 ${10}^9$，则输出 $a^b$ 的值，否则输出 -1。

样例 #1

样例输入 #1

10 9

样例输出 #1

1000000000

样例 #2

样例输入 #2

23333 66666

样例输出 #2

-1

提示

对于 $10 \%$ 的数据，保证 $b = 1$。
对于 $30 \%$ 的数据，保证 $b \le 2$。
对于 $60 \%$ 的数据，保证 $b \le 30$，$a^b \le {10}^{18}$。
对于 $100 \%$ 的数据，保证 $1 \le a, b \le {10}^9$。

分析

签到题。进行计算 $a^b$ 时判断是否越界即可。朴素方法不会超时的原因是最多只能计算到 $10^9 \approx 2^{30}$ ，以最小底数 $2$ 来算也仅需 $30$ 次循环。注意 long long 即可。

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;

long long a, b, c;

int main() {
    scanf("%lld%lld", &a, &b);
    if (a == 1) {
        printf("1\n");
        return 0;
    }
    c = 1;
    for (int i = 1; i <= b; i++) {
        c *= a;
        if (c > 1e9) {
            printf("-1\n");
            return 0;
        }
    }
    printf("%lld\n", c);
    return 0;
}

T2 解密

题目描述

给定一个正整数 $k$，有 $k$ 次询问，每次给定三个正整数 $n_i, e_i, d_i$，求两个正整数 $p_i, q_i$，使 $n_i = p_i \times q_i$、$e_i \times d_i = (p_i - 1)(q_i - 1) + 1$。

输入格式

第一行一个正整数 $k$，表示有 $k$ 次询问。

接下来 $k$ 行，第 $i$ 行三个正整数 $n_i, d_i, e_i$。

输出格式

输出 $k$ 行，每行两个正整数 $p_i, q_i$ 表示答案。

为使输出统一，你应当保证 $p_i \leq q_i$。

如果无解，请输出 NO。

样例 #1

样例输入 #1

10
770 77 5
633 1 211
545 1 499
683 3 227
858 3 257
723 37 13
572 26 11
867 17 17
829 3 263
528 4 109

样例输出 #1

2 385
NO
NO
NO
11 78
3 241
2 286
NO
NO
6 88

提示

【样例 #2】

见附件中的 decode/decode2.in 与 decode/decode2.ans。

【样例 #3】

见附件中的 decode/decode3.in 与 decode/decode3.ans。

【样例 #4】

见附件中的 decode/decode4.in 与 decode/decode4.ans。

【数据范围】

以下记 $m = n - e \times d + 2$。

保证对于 $100\%$ 的数据，$1 \leq k \leq {10}^5$，对于任意的 $1 \leq i \leq k$，$1 \leq n_i \leq {10}^{18}$，$1 \leq e_i \times d_i \leq {10}^{18}$ ，$1 \leq m \leq {10}^9$。

测试点编号	$k \leq$	$n \leq$	$m \leq$	特殊性质
$1$	$10^3$	$10^3$	$10^3$	保证有解
$2$	$10^3$	$10^3$	$10^3$	无
$3$	$10^3$	$10^9$	$6\times 10^4$	保证有解
$4$	$10^3$	$10^9$	$6\times 10^4$	无
$5$	$10^3$	$10^9$	$10^9$	保证有解
$6$	$10^3$	$10^9$	$10^9$	无
$7$	$10^5$	$10^{18}$	$10^9$	保证若有解则 $p=q$
$8$	$10^5$	$10^{18}$	$10^9$	保证有解
$9$	$10^5$	$10^{18}$	$10^9$	无
$10$	$10^5$	$10^{18}$	$10^9$	无

分析

很多大佬都用的数学方法，但其实这道题没有这么复杂。

对于每次询问，需要求出两个正整数 $p,q$ ，使 $p \times q = n$ , $(p - 1) \times (q - 1) + 1 = e \times d$ 。其中，$n,e,d$ 均为定值。

显然

$$n = p \times q,\\ e \times d = (p - 1)(q - 1) + 1\\ = p(q - 1) - (q - 1) + 1\\ = pq - p - q + 1 + 1\\ = pq - p - q + 2\\ \therefore n = pq, e \times d = p \times q - p - q + 2\\$$

考虑二分枚举 $p$ ，显然需要求得 $q$ 。易得

$$\because n = p \times q\\ \therefore e \times d = n - p - q + 2\\ \therefore e \times d + q = n - p + 2\\ \therefore q = n - p + 2 - e \times d\\$$

设 $k = p + q$ ，则有

$$k = n + 2 - e \times d$$

所以

$$q = k - p = n + 2 - e \times d - p$$

综上，当枚举到的 $p,q$ 通过计算等同于 $n$ 时，结束枚举；否则调整左右区间继续枚举。

注意初始右区间端点不可为 $k$ ，否则将有 $q = 0$ ，不满足题意。

不难发现需要二分的区间 $k$ 恰好为题目中给定的 $m$ ，故时间复杂度为 $O(Q \log m)$ ，其中 $Q$ 为询问数。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;

int Q;
long long n, e, d;

bool binary_search() {
    long long k = n + 2 - e * d;
    long long l = 1, r = k - 1;
    bool flag = 0;
    while (l <= r) {
        long long p = (l + r) >> 1;
        long long q = k - p;
        if (p * q < n) {
            l = p + 1;
        } else if (p * q > n) {
            r = p - 1;
        } else {
            printf("%lld %lld\n", p, q);
            flag = 1;
            break;
        }
    }
    return flag;
}

int main() {
    scanf("%d", &Q);
    while (Q--) {
        scanf("%lld%lld%lld", &n, &e, &d);
        bool flag = binary_search();
        if (!flag) {
            printf("NO\n");
        }
    }
    return 0;
}

T3 逻辑表达式

题目描述

逻辑表达式是计算机科学中的重要概念和工具，包含逻辑值、逻辑运算、逻辑运算优先级等内容。

在一个逻辑表达式中，元素的值只有两种可能：$0$（表示假）和 $1$（表示真）。元素之间有多种可能的逻辑运算，本题中只需考虑如下两种：“与”（符号为 &）和“或”（符号为 |）。其运算规则如下：

$0 \mathbin{\&} 0 = 0 \mathbin{\&} 1 = 1 \mathbin{\&} 0 = 0$，$1 \mathbin{\&} 1 = 1$；
$0 \mathbin{|} 0 = 0$，$0 \mathbin{|} 1 = 1 \mathbin{|} 0 = 1 \mathbin{|} 1 = 1$。

在一个逻辑表达式中还可能有括号。规定在运算时，括号内的部分先运算；两种运算并列时，& 运算优先于 | 运算；同种运算并列时，从左向右运算。

比如，表达式 0|1&0 的运算顺序等同于 0|(1&0)；表达式 0&1&0|1 的运算顺序等同于 ((0&1)&0)|1。

此外，在 C++ 等语言的有些编译器中，对逻辑表达式的计算会采用一种“短路”的策略：在形如 a&b 的逻辑表达式中，会先计算 a 部分的值，如果 $a = 0$，那么整个逻辑表达式的值就一定为 $0$，故无需再计算 b 部分的值；同理，在形如 a|b 的逻辑表达式中，会先计算 a 部分的值，如果 $a = 1$，那么整个逻辑表达式的值就一定为 $1$，无需再计算 b 部分的值。

现在给你一个逻辑表达式，你需要计算出它的值，并且统计出在计算过程中，两种类型的“短路”各出现了多少次。需要注意的是，如果某处“短路”包含在更外层被“短路”的部分内则不被统计，如表达式 1|(0&1) 中，尽管 0&1 是一处“短路”，但由于外层的 1|(0&1) 本身就是一处“短路”，无需再计算 0&1 部分的值，因此不应当把这里的 0&1 计入一处“短路”。

输入格式

输入共一行，一个非空字符串 $s$ 表示待计算的逻辑表达式。

输出格式

输出共两行，第一行输出一个字符 0 或 1，表示这个逻辑表达式的值；第二行输出两个非负整数，分别表示计算上述逻辑表达式的过程中，形如 a&b 和 a|b 的“短路”各出现了多少次。

样例 #1

样例输入 #1

0&(1|0)|(1|1|1&0)

样例输出 #1

1
1 2

样例 #2

样例输入 #2

(0|1&0|1|1|(1|1))&(0&1&(1|0)|0|1|0)&0

样例输出 #2

0
2 3

提示

【样例解释 #1】

该逻辑表达式的计算过程如下，每一行的注释表示上一行计算的过程：

0&(1|0)|(1|1|1&0)
=(0&(1|0))|((1|1)|(1&0)) //用括号标明计算顺序
=0|((1|1)|(1&0))   //先计算最左侧的 &，是一次形如 a&b 的“短路”
=0|(1|(1&0))       //再计算中间的 |，是一次形如 a|b 的“短路”
=0|1               //再计算中间的 |，是一次形如 a|b 的“短路”
=1

【样例 #3】

见附件中的 expr/expr3.in 与 expr/expr3.ans。

【样例 #4】

见附件中的 expr/expr4.in 与 expr/expr4.ans。

【数据范围】

设 $\lvert s \rvert$ 为字符串 $s$ 的长度。

对于所有数据，$1 \le \lvert s \rvert \le {10}^6$。保证 $s$ 中仅含有字符 0、1、&、|、(、) 且是一个符合规范的逻辑表达式。保证输入字符串的开头、中间和结尾均无额外的空格。保证 $s$ 中没有重复的括号嵌套（即没有形如 ((a)) 形式的子串，其中 a 是符合规范的逻辑表 达式）。

测试点编号	$\lvert s \rvert \le$	特殊条件
$1 \sim 2$	$3$	无
$3 \sim 4$	$5$	无
$5$	$2000$	1
$6$	$2000$	2
$7$	$2000$	3
$8 \sim 10$	$2000$	无
$11 \sim 12$	${10}^6$	1
$13 \sim 14$	${10}^6$	2
$15 \sim 17$	${10}^6$	3
$18 \sim 20$	${10}^6$	无

其中：
特殊性质 1 为：保证 $s$ 中没有字符 &。
特殊性质 2 为：保证 $s$ 中没有字符 |。
特殊性质 3 为：保证 $s$ 中没有字符 ( 和 )。

【提示】

以下给出一个“符合规范的逻辑表达式”的形式化定义：

• 字符串 0 和 1 是符合规范的；
• 如果字符串 s 是符合规范的，且 s 不是形如 (t) 的字符串（其中 t 是符合规范的），那么字符串 (s) 也是符合规范的；
• 如果字符串 a 和 b 均是符合规范的，那么字符串 a&b、a|b 均是符合规范的；
• 所有符合规范的逻辑表达式均可由以上方法生成。

分析

不难发现这又是一道继承了去年普及 T3 的大模拟。与 CSP-J 2020 T3 类似，考虑采用计算后缀表达式的方式。

这样，题目就转化为了：

1. 给定一中缀表达式 $s$ ，求 $s$ 的后缀表达式形式 $t$ ；
2. 通过给定的运算法则计算后缀表达式 $t$ 的值。

至于题目中所求的短路次数，在运算时进行标记即可。

对于问题 (1) ，我们可以考虑维护两个栈，运算符栈 $s_1$ 和结果栈 $s_2$ 。其中，运算符栈存储转换过程中所用的运算符，以便计算结果；结果栈则存储最终转换的后缀表达式 $t$ 。

具体操作流程如下：

• 若当前字符为左括号 ( ，则直接将其压入 $s_1$ 中；
• 若当前字符为右括号 ) ，则依次弹出 $s_1$ 中的运算符并压入 $s_2$ 中，直到 $s_1$ 为空或 $s_1$ 栈顶为左括号 ( ；
• 若当前字符为运算数 1 、0 ，则直接压入 $s_2$ 中；
• 若当前字符为运算符 & 、| ，则依次弹出 $s_1$ 中优先级大于等于当前运算符的字符并压入 $s_2$ 中，直到 $s_1$ 栈顶运算符的优先级小于当前运算符，并将当前运算符压入 $s_1$ 中。

特别地，我们规定左括号的优先级最低，即在情况 (4) 中无论何时左括号都不会被压入 $s_1$ 中。

对于问题 (2) ，我们仍然考虑维护一个临时栈 $s_3$ ，用来存储中间运算结果。具体操作流程如下：

• 若当前字符为运算数 1 、0 ，则直接压入 $s_3$ 中；
• 若当前字符为运算符 & 、| ，则依次从 $s_3$ 栈顶中取出两个节点，记为 $l,r$ ：
  • 若当前字符为与运算符 & ，则：
    • 若 $l$ 的值为 0 ，则发生短路，将运算结果 0 压入 $s_3$ 中并记当前与短路次数为 $l$ 的与短路次数 $+\ 1$ ，或短路次数为 $l$ 的或短路次数；
    • 若 $l$ 的值为 1 ，则没有发生短路，运算结果记为 l & r ，并将运算结果压入 $s_3$ ，记当前与短路次数为 $l$ 的与短路次数 $+$ $r$ 的与短路次数，或短路次数为 $l$ 的或短路次数 $+$ $r$ 的或短路次数；
  • 若当前字符为或运算符 | ，则：
    • 若 $l$ 的值为 0 ，则没有发生短路，运算结果记为 l | r ，并将运算结果压入 $s_3$ ，记当前与短路次数为 $l$ 的与短路次数 $+$ $r$ 的与短路次数，或短路次数为 $l$ 的或短路次数 $+$ $r$ 的或短路次数；
    • 若 $l$ 的值为 1 ，则发生短路，将运算结果 1 压入 $s_3$ 中并记当前与短路次数为 $l$ 的与短路次数，或短路次数为 $l$ 的或短路次数 $+ \ 1$ 。

此时，结果即为 $s_3$ 栈顶所存储的信息。

维护时需要注意不可使用 STL 自带 stack ，因为 stack 不支持随机访问，需要自行手写。

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
const int N = 1e6 + 10;

template<typename T>
struct Stack {
    T val[N];
    int stackTop = 0;

    void push(T x) {
        val[++stackTop] = x;
    }

    T pop() {
        return val[stackTop--];
    }

    T top() {
        return val[stackTop];
    }

    bool empty() {
        return stackTop == 0;
    }

    int size() {
        return stackTop;
    }
};

struct Node {
    bool val;
    int or_, and_;

    Node() {}

    Node(bool _val) {
        val = _val;
        or_ = 0, and_ = 0;
    }

    Node(bool _val, int _or_, int _and_) {
        val = _val, or_ = _or_, and_ = _and_;
    }
};

int priority(char op) {
    if (op == '&') return 2;
    if (op == '|') return 1;
    return 0;
}

Stack<char> op, res;

auto midToSuffix(string s) {
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') {
            op.push(s[i]);
        } else if (s[i] == ')') {
            while (!op.empty()) {
                if (op.top() == '(') {
                    op.pop();
                    break;
                }
                int cur = op.top();
                res.push(cur);
                op.pop();
            }
        } else if (s[i] == '0' || s[i] == '1') {
            res.push(s[i]);
        } else if (s[i] == '&' || s[i] == '|') {
            while (!op.empty()) {
                if (priority(op.top()) >= priority(s[i])) {
                    res.push(op.top());
                    op.pop();
                } else {
                    break;
                }
            }
            op.push(s[i]);
        }
    }
    while (!op.empty()) {
        res.push(op.top());
        op.pop();
    }
    return res;
}

Stack<Node> tmp;

auto calcSuffix(Stack<char> suffix) {
    for (int i = 1; i <= suffix.size(); i++) {
        char val = suffix.val[i];
        if (val == '0' || val == '1') {
            tmp.push(Node(val - '0'));
        } else if (val == '&') {
            Node r = tmp.top();
            tmp.pop();
            Node l = tmp.top();
            tmp.pop();
            if (l.val == 0) {
                tmp.push(Node(0, l.or_, l.and_ + 1));
            } else {
                tmp.push(Node(l.val & r.val, l.or_ + r.or_, l.and_ + r.and_));
            }
        } else if (val == '|') {
            Node r = tmp.top();
            tmp.pop();
            Node l = tmp.top();
            tmp.pop();
            if (l.val == 1) {
                tmp.push(Node(1, l.or_ + 1, l.and_));
            } else {
                tmp.push(Node(l.val | r.val, l.or_ + r.or_, l.and_ + r.and_));
            }
        }
    }
    return tmp.top();
}

int main() {
    string s;
    cin >> s;
    auto suffix = midToSuffix(s);
    auto root = calcSuffix(suffix);
    cout << root.val << endl << root.and_ << ' ' << root.or_ << endl;
    return 0;
}

T4 上升点列

题目描述

在一个二维平面内，给定 $n$ 个整数点 $(x_i, y_i)$，此外你还可以自由添加 $k$ 个整数点。

你在自由添加 $k$ 个点后，还需要从 $n + k$ 个点中选出若干个整数点并组成一个序列，使得序列中任意相邻两点间的欧几里得距离恰好为 $1$ 而且横坐标、纵坐标值均单调不减，即 $x_{i+1} - x_i = 1, y_{i+1} = y_i$ 或 $y_{i+1} - y_i = 1, x_{i+1} = x_i$。请给出满足条件的序列的最大长度。

输入格式

第一行两个正整数 $n, k$ 分别表示给定的整点个数、可自由添加的整点个数。

接下来 $n$ 行，第 $i$ 行两个正整数 $x_i, y_i$ 表示给定的第 $i$ 个点的横纵坐标。

输出格式

输出一个整数表示满足要求的序列的最大长度。

样例 #1

样例输入 #1

8 2
3 1
3 2
3 3
3 6
1 2
2 2
5 5
5 3

样例输出 #1

8

样例 #2

样例输入 #2

4 100
10 10
15 25
20 20
30 30

样例输出 #2

103

提示

【样例 #3】

见附件中的 point/point3.in 与 point/point3.ans。

第三个样例满足 $k = 0$。

【样例 #4】

见附件中的 point/point4.in 与 point/point4.ans。

【数据范围】

保证对于所有数据满足：$1 \leq n \leq 500$，$0 \leq k \leq 100$。对于所有给定的整点，其横纵坐标 $1 \leq x_i, y_i \leq {10}^9$，且保证所有给定的点互不重合。对于自由添加的整点，其横纵坐标不受限制。

测试点编号	$n \leq$	$k \leq$	$x_i,y_i \leq$
$1 \sim 2$	$10$	$0$	$10$
$3 \sim 4$	$10$	$100$	$100$
$5 \sim 7$	$500$	$0$	$100$
$8 \sim 10$	$500$	$0$	${10}^9$
$11 \sim 15$	$500$	$100$	$100$
$16 \sim 20$	$500$	$100$	${10}^9$

分析

不难发现这是一道 DP 题。 但是由于本人太弱，此处仅介绍 $75$ 分解法

发现对于测试点 $1 \sim 2,5 \sim 10$ 有 $k = 0$ ，即无需添加点。不难发现，问题转化为求路径上点坐标单调不减且欧几里得距离为 $1$ 的最长路径。

显然在这种情况下，从 $(x,y)$ 出发的路径下一个点只有 $(x + 1,y)$ 和 $(x, y + 1)$ 这两种可能。那么我们不妨采用记忆化搜索来通过这部分数据点。具体实现方式如下：

每次选择一个点 $i$ ，从 $i$ 出发搜索路径，且每次只能到达当前点的正下方与正右方。搜索过程中记录当前经过点的数量并取最大值，循环 $n$ 次过后的结果即为答案。

再次观察数据，发现对于测试点 $1 \sim 2, 3 \sim 7, 11 \sim 15$ 有 $x_i, y_i \leq 100$ ，可以使用朴素 DP 解决。

记状态 $dp_{i,j,k}$ 表示在添加 $k$ 个点的情况下，到达坐标 $(i,j)$ 点所需经过点的个数。不难发现，转移方程为：

• 若当前不需要添加点，$dp_{i,j,k} = \max(dp_{i, j - 1, k}, dp_{i - 1, j, k})$ ；
• 若当前需要添加点，$dp_{i, j, k} = \max(dp_{i, j - 1, k - 1}, dp_{i - 1, j, k - 1})$ 。

答案即为转移过程中 $dp_{i, j, k}$ 的最大值。

这样，我们将两种策略组合便获得了对于测试点 $1 \sim 15$ 的解法。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 110, M = 1010;

struct Point {
    int x, y;
} a[M];

int n, K, ans;
bool mp[N][N];
int dp[N][N][N];
bool vis[M];
int sum;

int hasPoint(int x, int y) {
    for (int i = 1; i <= n; i++) {
        if (a[i].x == x && a[i].y == y) {
            return i;
        }
    }
    return -1;
}

void dfs(int dep, int cnt) {
    if (vis[dep]) return;
    vis[dep] = 1;
    sum = max(sum, cnt);
    int np = hasPoint(a[dep].x, a[dep].y + 1);
    if (np != -1) {
        dfs(np, cnt + 1);
    }
    np = hasPoint(a[dep].x + 1, a[dep].y);
    if (np != -1) {
        dfs(np, cnt + 1);
    }
}

int main() {
    scanf("%d%d", &n, &K);
    if (K == 0) {
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", &a[i].x, &a[i].y);
        }
        for (int i = 1; i <= n; i++) {
            memset(vis, 0, sizeof(vis));
            sum = 0;
            dfs(i, 1);
            ans = max(ans, sum);
        }
        printf("%d\n", ans);
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i].x, &a[i].y);
        mp[a[i].x][a[i].y] = 1;
    }
    for (int i = 1; i < N; i++) {
        for (int j = 1; j < N; j++) {
            for (int k = 0; k <= K; k++) {
                if (mp[i][j]) {
                    dp[i][j][k] = max(dp[i][j - 1][k], dp[i - 1][j][k]) + 1;
                } else if (k) {
                    dp[i][j][k] = max(dp[i][j - 1][k - 1], dp[i - 1][j][k - 1]) + 1;
                }
                ans = max(ans, dp[i][j][k]);
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}