校内模拟赛 10.05

做题记录
, , , , , ,

井下矿工

Description

有一座地下的稀有金属矿有 $n$ 条隧道和一些连接点组成，其中每条隧道连接两个连接点。任意两个连接点之间最多只有一条隧道。为了降低矿工的危险，你的任务是在一些连接点处安装太平井和相应的逃生装置，使得不管哪个连接点倒塌，不在此连接点的所有矿工都能到达太平井逃生（假定除了倒塌的连接点不能通行外，其他隧道和连接点完好无损）。为了节约成本，你应当在尽量少的连接点安装太平井。还需要计算出当太平井的数目最小时安装方案总数。

Input

输入包含多组数据。每组数据第一行为隧道的条数 $n$； 以下 $n$ 行每行两个整数，即一条隧道两端的连接点编号（所有连接点从 $1$ 开始编号）。每组数据的所有连接点保证连通。 输入数据最后一行包含一个单独的整数 $0$ 表示结束。

Output

对于每组数据，输出两个整数，即最少需要安装的太平井数目以及对应的方案总数。方案保证在64位带符号整数的范围内。

Sample Input Sample Output 
9
1 3
4 1
3 5
1 2
2 6
1 5
6 3
1 6
3 2
6
1 2
1 3
2 4
2 5
3 6
3 7
0

Case 1: 2 4
Case 2: 4 1

Hint

$100\%$ 的数据： $n\le 50000$

这题输出就很唐。

漂亮数

题目描述

Smart 认为一个数能被它自己的每一位非零数字都整除的数是漂亮数。现在给你两个整> 数 $L, R$，输出区间 $[L, R]$ 中漂亮数的个数。

例如：若 $n=128$，需检查数字 $1,2,8$（非零位）是否都整除 $128$，若都整除则 $128$ 为漂亮数。

输入格式

第一行一个整数 $T$，表示测试数据组数。接下来 $T$ 行，每行包含两个整数 $L_i, R_i$，表示查询区间 $[L_i, R_i]$。

约束：$1 \le T \le 10,\quad 1 \le L_i, R_i \le 9\times 10^{18}$
（20% 的数据：$1 \le L_i, R_i \le 10^5$）

输出格式

输出 $T$ 行，每行一个整数，表示对应区间内漂亮数的个数。

样例

Sample Input Sample Output 
1
1 9

9

1
12 15

2

这题是数位 DP。

考虑最朴素的做法：
设置状态 $ f \begin{bmatrix} d & \begin{matrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \\ x_7 \\ x_8 \\ x_9 \end{matrix} & \begin{matrix} s_1 \\ s_2 \\ s_3 \\ s_4 \\ s_5 \\ s_6 \\ s_7 \\ s_8 \\ s_9 \end{matrix} & eq \end{bmatrix} $ 表示从左往右处理到了第 $d$ 位，
现在数字和原来 $ \begin{cases} eq=1: 相等 \\ eq=0: 不相等 \end{cases} $ ，
（从左往右）前 $i$ 位数 $\bmod m$ 的值是 $x_m$，前 $i$ 位数中 $\begin{cases} s_n=0: 不含 n \\ s_n=1: 含 n \end{cases}$ ，
此时所有合法数字的个数。

转移：
$$
\begin{array}{l}
\textbf{For } d = 1 \dots d_{\max} &\small{d: 当前枚举从前往后位数（从小到大）} \\
\quad \textbf{For } \forall i \in \{0 \dots 9\} &\small{i: 当前枚举数位} \\
\qquad \textbf{For } \forall j=\{x_1 \dots x_9\} &\small{j: 当前枚举模数状态} \\
\qquad\quad \textbf{For } \forall k=\{s_1 \dots s_9\} &\small{k: 当前枚举数字存在状态} \\
\qquad\qquad \begin{cases}
i < n_d: \quad \textbf{Let } f[i, x(j), s(k), 0] \operatorname{ Plus } f[i-1, j, k, 0] + f[i-1, j, k, 1] \\\\
i = n_d: \quad \begin{matrix} \textbf{Let } f[i, x(j), s(k), 0] \operatorname{ Plus } f[i-1][j][k][0] \\ \textbf{Let } f[i,x(j), s(k), 1] \operatorname{Plus} f[i-1][j][k][1] \end{matrix} \\\\
i > n_d: \quad \textbf{Let } f[i, x(j), s(k), 0] \operatorname{ Plus } f[i-1][j][k][0]
\end{cases} &\small{x(j): j 在末尾加上一位 i 后的状态 \\ s(j): 同理 \\ n_d: 原数字中从左往右数的第d位数}
\end{array}
$$

显然这种做法存都存不下，更别提这惊人的时间复杂度了。令总位数为 $n$，时间 $\mathcal O(T \cdot n \cdot 9! \cdot 2^9 \cdot 10 \cdot 2)$，空间 $\mathcal O(9! \cdot 2^9 \cdot 10 \cdot 2)$（在使用滚动数组的情况下）。

容易想到优化：对于 $ x_1, x_2, \dots, x_n $ 一个一个存储记录显然有些浪费，如果记录这个数字 $\bmod \operatorname{lcm}(1,2,\dots,9)$ 效果是一样的。
于是得到了状态 $ f\,[d, x, s, eq] $，时间是 $\mathcal O(T \cdot n \cdot 2520 \cdot 2^9 \cdot 10) $。

Code (20pts) 
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
#include <stdio.h>
#include <string.h>
#define Now f[i&1][s][m]
#define To f[i&1^1][j ? s | 1 << j-1 : s][((m<<3) + (m<<1) + j) % LCM]
constexpr int LCM = 2520, SN = 1 << 9;
static long long f[2][SN][LCM][2]; // 1= 0<
inline long long work(long long x) {
    int a[20]{}, n = 0;
    for (; x > 0; x /= 10) a[n++] = x % 10;
    for (int i = 0; i < (n>>1); i++) a[i] ^= a[n-i-1] ^= a[i] ^= a[n-i-1];
    memset(f, 0, sizeof(f) >> 1);
    f[0][0][0][1] = 1;
    for (int i = 0; i < n; i++) {
        memset(f[i&1^1], 0, sizeof(f) >> 1);
        for (int s = 0; s < SN; ++s)
            for (int m = 0; m < LCM; ++m) {
                long long now0 = Now[0], now1 = Now[1];
                if (!now0 && !now1) continue;
                for (int j = 0; j < 10; j++) {
//                    printf("Upd: [%d] (%d %d %d) -> (%d %d %d)\n", j, i, s, m, i+1, j ? s | 1 << j-1 : s, ((m<<3) + (m<<1) + j) % LCM);
                    if (j < a[i])
                        To[0] += now0 + now1;
                    else if (j == a[i])
                        To[1] += now1, To[0] += now0;
                    else
                        To[0] += now0;
                }
            }
    }
    int i = n;
    long long ans = 0;
    for (int s = 0; s < SN; ++s)
        for (int m = 0; m < LCM; ++m) {
            bool addable = true;
            for (int i = 1; i <= 9; i++)
                if ((s & 1 << i-1) && m % i)
                    { addable = false; break; }
            if (addable && Now[0] + Now[1])
//                fprintf(stderr, "Add! (%d, %d) = %d\n", s, m, Now[0] + Now[1]),
                ans += Now[0] + Now[1];
        }
//    printf("%d\n", ans);
    return ans;
}
int main() {
    freopen("number.in", "r", stdin);
    freopen("number.out", "w", stdout);
    int T;	
    long long L, R;
    scanf("%d", &T);
    while (T--) {
        scanf("%lld%lld", &L, &R);
        printf("%lld\n", work(R) - work(L-1));
    }
    return 0;
}

为什么拿不到满分呢？？？
实际上，一部分原因是 OJ 太慢了。。。
但是！注意到！
我刚刚推的 DP 实际上是重复算了大量子问题：那就是 $eq=0$ 的情况！
对于这个子问题单独处理为一个 $g$，然后每次 dfs 式地去算答案，这题就能获得正解。

Code (std) 
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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int P = 2520;

int T, a[20];
ll l, r, ans, f[20][2520][256];

//表示从高到低考虑前i个数位模2520为j,已经出现的非零的数字集合为S,当前数是否等于n的情况为k的方案数
ll dfs(int i, int j, int S, bool k) {
    if (i == 0) {
        for (int t = 2; t <= 9; ++t) //枚举非零数字,1能整除任何数不需要判断
            if (S & (1 << (t - 2)) && j % t)
                return 0;
        return 1;
    }
    if (!k && f[i][j][S] != -1)
        return f[i][j][S]; //状态搜索过
    int Max = 9;
    if (k)
        Max = a[i]; //这一位的最大数字
    ll ret = 0;
    for (int t = 0; t <= Max; ++t) //枚举第i位取的数字为t
    {
        int tj = (j * 10 + t) % P;
        int tS = t > 1 ? S | (1 << (t - 2)) : S;
        int tk = k && t == Max;
        ret += dfs(i - 1, tj, tS, tk);
    }
    if (!k)
        f[i][j][S] =
            ret; //只能记小于的情况:因为只有小于的时候后面的数可以随便取
    return ret;
}

ll cal(ll x) {
    int n = 0;
    while (x) {
        a[++n] = x % 10;
        x /= 10;
    }
    return dfs(n, 0, 0, 1);
}

int main() {
    memset(f, -1, sizeof(f));
    scanf("%d", &T);
    while (T--) {
        scanf("%lld %lld", &l, &r);
        ans = cal(r) - cal(l - 1);
        printf("%lld\n", ans);
    }
    return 0;
}

迷宫（动态围墙）

题面描述

Zdrcl 不慎进入了一个迷宫。这个迷宫是一个空的 $N\times M$ 网格，之后会发生 $Q$ 件事件，事件类型如下：

  1. 1 x1 y1 x2 y2：在由格子 $(x_1,y_1)$ 到 $(x_2,y_2)$ 所构成的矩形外围出现一堵围墙（围墙沿格边，与格子边重合）。
  2. 2 x1 y1 x2 y2：上述那堵围墙消失（保证该围墙之前确实出现过）。
  3. 3 x1 y1 x2 y2：询问 Zdrcl 是否能从 $(x_1,y_1)$ 走到 $(x_2,y_2)$（不能翻越围墙，只能沿网格的四个方向移动）。

题目保证：任意两堵围墙之间不相交、没有公共边也没有公共点（即围墙互相独立）。

输入格式

第一行：三个正整数 $N, M, Q$。
接下来有 $Q$ 行，每行五个整数：t x1 y1 x2 y2，表示一条事件。
其中对于添加/删除围墙的事件（即 t=1 或 t=2），保证
$
2 \le x_1 \le x_2 \le N-1,\qquad 2 \le y_1 \le y_2 \le M-1.
$

输出格式

对于每个 t=3 的查询，输出一行：能到则输出 Yes，否则输出 No。

约束

$
N, M \le 2500, Q \le 10^5.
$

样例

Sample Input Sample Output 
5 6 5
1 2 2 4 5
1 3 3 3 3
3 4 4 1 1
2 2 2 4 5
3 1 1 4 4

No
Yes

显然呢这题我们立刻可以想到 矩阵区间加 和 差分思想。
想要解决这道题目，我们要先明白：使用 Hash 算法根本目的都是为了使用有限的数字去衡量一个较大的数据块，并且做到尽量唯一。
对于本题而言，我们需要一种 Hash 可以快速处理加入和删除。
我想到了使用 unsigned long long 自然溢出，并且对每一次“矩阵加”都赋上一个随机权值，区间加上这个权值，删除时直接减去这个权值。
std 使用的是亦或处理加入删除，但是我觉得比加减还容易被卡，但是这题数据也不强，所以就随便玩玩。
需要用到二维树状数组！这是一个非常简单的数据结构，但是想起来应用确实不容易啊。

Code 
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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <time.h>
#include <random>
#include <unordered_map>
using u64 = unsigned long long;
constexpr int N = 2505;
constexpr u64 B = 31;
int n, m;
namespace BIT {
    u64 tr[N][N];
    inline void upd(const int px, const int py, const u64 &x) {
        for (int i = px; i <= n; i += i & -i)
            for (int j = py; j <= m; j += j & -j)
                tr[i][j] += x;
    }
    inline u64 query(const int px, const int py) {
        u64 res = 0;
        for (int i = px; i > 0; i -= i & -i)
            for (int j = py; j > 0; j -= j & -j)
                res += tr[i][j];
        return res;
    }
} using BIT::upd; using BIT::query;
inline u64 keygen(const int a, const int b, const int c, const int d) {
    return (u64)a << 48 | (u64)b << 32 | c << 16 | d;
}
std::unordered_map<u64, u64> mp;
int main() {
    int q;
    scanf("%d%d%d", &n, &m, &q);
    std::mt19937 seed(time(nullptr));
    std::uniform_int_distribution<int> rnd(1, (int)B-1);
    u64 base = 1;
    for (int t, x1, x2, y1, y2; q--; ) {
        scanf("%d%d%d%d%d", &t, &x1, &y1, &x2, &y2);
        switch (t) {
        case 1: {
            u64 key = keygen(x1, x2, y1, y2);
            u64 id = base * rnd(seed);
            upd(x1, y1, id);
            upd(x1, y2+1, -id);
            upd(x2+1, y1, -id);
            upd(x2+1, y2+1, id);
            mp[key] = id;
            base *= B;
            break;
        }
        case 2: {
            u64 key = keygen(x1, x2, y1, y2);
            u64 id = mp[key];
            upd(x1, y1, -id);
            upd(x1, y2+1, id);
            upd(x2+1, y1, id);
            upd(x2+1, y2+1, -id);
            break;
        }
        case 3: 
            puts(query(x1, y1) == query(x2, y2) ? "Yes" : "No");
        }
        
    }
    return 0;
}

平衡字符串

Description

尼克对研究字符串非常着迷。他喜欢翻转它们、排序它们，或者将一个字符串的字母重新排列。一次他写下了一个仅包含字母 a、b、c 的字符串 $S$（长度为 $N$），并可以对该字符串重复执行下面两类操作中的任意一个：

  1. 选择两个相邻字母，将第二个替换第一个（例如将 “ab” 变为 “bb”）。
  2. 选择两个相邻字母，将第一个替换第二个（例如将 “ab” 变为 “aa”）。

例如，从 “abc” 可以得到的字符串包括 “bbc”、“abb”、“acc” 等。

记字母 $x$ 在字符串中的频率为 $|x|$（即出现次数）。当对字符串应用上述操作后，若字符串中任意两种字母的频率差不超过 $1$，则称该字符串为平衡串。也就是说要求同时满足
$-1 \le |a|-|b| \le 1$，$-1 \le |a|-|c| \le 1$，$-1 \le |b|-|c| \le 1$。

给定初始字符串 $S$，请计算能够通过对 $S$ 进行一次或多次上述操作得到的不同平衡串的数量（若初始字符串已平衡，也应计入）。结果对 $51123987$ 取模后输出。

输入

第一行是整数 $N$，表示字符串 $S$ 的长度。
第二行是字符串 $S$，仅包含字符 a、b、c。

注意初始字符串也可能已经是平衡串并应被计入。

输出

输出一行：不同的可达平衡串的数量对 $51123987$ 取模的结果。

样例

样例组 Sample Input Sample Output
#1 
4
abca
 
7
#2 
4
abbc
 
3
#3 
2
ab
 
1

样例说明：样例 #1 中合法的字符串有 7 个：“abca”、“aabc”、“abbc”、“abcc”、“bbca”、“bcca”、“bcaa”。

约束与提示

  • $45\%$ 的数据： $N \le 100$；
  • $100\%$ 的数据： $N \le 150$。
  • 模数：$51123987$。