Comet OJ - 模拟赛测试 Day2

发表于 | 更新于 | 分类于

$\Large{☞}$ $\Large{链接}$

第一场打 $Comet$ 的比赛,被吊打

$\huge\mathcal{T1}$

$\Large\mathcal{Description}$

小 $L$ 有 $n$ 本书(编号范围 $1$ 至 $n$)，现在他要把这些书全部放在书架上，并排成一排。

给定书架的初始状态(即书架上原来放着m本书，并且它们的相对位置规定)，把剩下的书逐一插入，使 得最后构成的排列字典序最小，并输出这个排列。

数据范围 $:$ $1 \le m \le n \le 10^5$

$\Large\mathcal{Solution}$

我们可以变一变，我们假设我们手上的书是已经排列好的，要把书架上的那些书插入。

这样做有什么好处呢 $?$

  • 我们手上的书顺序是不定的。所以只需要根据序号从小到大排就好了。
  • 要插入的书(即书架上的书)的相对位置是固定的。所以我们只要从前往后扫就行了。

接下来的思路就很显然了。两个指针疯狂往后跳就行了，每次输出较小值 跳就完事了

$\Large\mathcal{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
#include <iostream>
#include <cstdio>
#include <algorithm>

template <typename Tp>
inline void read(Tp &x) {
    x = 0;
    bool f = true; char ch = getchar();
    for ( ; ch < '0' || ch > '9'; ch = getchar()) f ^= ch == '-';
    for ( ; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + (ch ^ 48);
    x = f ? x : -x;
}

const int N = 1e5 + 7;

int a[N];
bool flg[N];

int main() {
    int n, m;
    read(n), read(m);
    for (int i = 1; i <= m; ++i) read(a[i]), flg[a[i]] = true;
    int x = 1;
    for (int i = 1; i <= n; ++i) {
        if (flg[i]) continue;
        while (a[x] < i && x <= m) {
            printf("%d\n", a[x]);
            ++x;
        }
        printf("%d\n", i);
    }
    while (x <= m) printf("%d\n", a[x++]);
    return 0;
}

$\huge\mathcal{T2}$

开题的时候看到天天，差点就自闭了

$\Large\mathcal{Description}$

有 $n$ 个由小写字母构成的单词(互不相同)。从中选取 $k$ 个单词连接构成字符串(显然最多能构成 $\frac{n!}{(n - k)!}$个)。现给你一个由 $k$ 个单词连成的字符串 $s$，问其在所有可能构成的字符串中从小到大排序后的排名。

数据保证不存在某个单词是另一个单词的前缀

数据范围 $:$ 所有单词总长度不超过 $10 ^ 6$

$\Large\mathcal{Solution}$

比赛的时候第一眼看上去像康托展开。但是这是从 $n$ 个数中选出 $k$ 个，并不是全排列，所以不行 反正我不会。所以我们另找思路。

注意到有一个很好的性质 $:$ 不存在某个单词是另一个单词的前缀

这就保证了，所有构成的字符串中没有相同的。所以，当我们知道了一个构成的字符串，我们可以确定它是有哪些单词构成的，也能确定这些单词的排列顺序。

字符串处理不太方便。我们可以用类似离散化的做法，把每个单词转成数字。这样每个构成的字符串都由 $k$ 个数字构成，可以用一个数组记录。

接下来，我们考虑如何求解。

考虑 $s$ 的第 $i$ 个的数字， 且前 $i - 1$ 个数字已经匹配上。

  • 该串的第 $i$ 个数字小于 $s$ 的第 $i$ 个数字，则满足。
  • 该串的第 $i$ 个数字等于 $s$ 的第 $i$ 个数字，则推到第 $i + 1$ 个数字。

这里需要记录比 $x$ 小且未被使用过的数字个数，我们可以用树状数组维护。

还有一点值得注意的是，这里求 $s$ 的构成时建议要用 $trie$ 。比赛的时候用 $map$，结果 $MLE$ 了一个点，同机房的好几个大佬也是，所以慎用！！！

$\Large\mathcal{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
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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>

#define int long long

template <typename Tp>
inline void read(Tp &x) {
    x = 0;
    bool f = true; char ch = getchar();
    for ( ; ch < '0' || ch > '9'; ch = getchar()) f ^= ch == '-';
    for ( ; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + (ch ^ 48);
    x = f ? x : -x;
}

const int N = 1e6 + 7, P = 1e9 + 7;

std::string s[N], S;
int a[N], c[N], n, k, cur = 0;

struct node {
    node *ch[30];
    int tot;
};
node *rt = new node();

inline int lowbit(int x) {
    return x & (-x);
}

inline void add(int x) {
    for ( ; x <= n; x += lowbit(x)) ++c[x];
}

inline int query(int x) {
    int ans = 0;
    for ( ; x > 0; x -= lowbit(x)) ans += c[x];
    return ans;
}

inline int power(int a, int x) {
    int ans = 1;
    while (x) {
        if (x & 1) ans = ans * a % P;
        a = a * a % P;
        x >>= 1;
    }
    return ans;
}

inline int inv(int x) {
    return power(x, P - 2);
}

inline void insert(std::string str, int k) {
    node *root = rt;
    int len = str.length();
    for (int i = 0; i < len; ++i) {
        int x = str[i] - 'a' + 1;
        if (root -> ch[x] == NULL) root -> ch[x] = new node(), root -> ch[x] -> tot = 0;
        root = root -> ch[x];
    }
    root -> tot = k;
}

inline void find(int k) {
    node *root = rt;
    while (1) {
        root = root -> ch[S[cur] - 'a' + 1];
        if (root -> tot) break;
        ++cur;
    }
    a[k] = root -> tot;
}

signed main() {
    read(n), read(k);
    for (int i = 1; i <= n; ++i) std::cin >> s[i];
    std::sort(s + 1, s + n + 1);
    for (int i = 1; i <= n; ++i) insert(s[i], i);
    std::cin >> S;
    for (int i = 1; i <= k; ++i) {
        find(i);
        ++cur;
    }
    int mul = 1;
    for (int i = 1; i < k; ++i) mul = (mul * (n - i)) % P;
    int ans = 1;
    for (int i = 1; i <= k; ++i) {
        ans = (ans + (a[i] - 1 - query(a[i])) * mul % P) % P;
        if (i < k) {
            add(a[i]);
            mul = mul * inv(n - i) % P;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

$\huge\mathcal{T3}$

$\Large\mathcal{Description}$

有一个 $n \times m$ 的阵列，每个点都有一个权值。现要删去一些行与列(不能全部删去)，使得剩下的阵列中，每一行以及每一列都是单调的(即点的权值单调递增或单调递减)。求方案数。

数据保证所有盆栽的高度排名组合起来为 $1$ 至 $n \times m$ 的一个排列。

数据范围 $:$ $1 \le n, m \le 20$

$\Large\mathcal{Solution}$

首先考虑暴力。

直接状压枚举行列的选取情况即可。复杂度 $O(2^{n + m} \times n \times m)$

(这道题暴力性价比还是很高的，可以拿到 $65$ 分的好成绩)

我们发现瓶颈只要在于枚举行列。所以只能枚举行(或列)，然后去确定列(或行)的选取方案。

接下来我们考虑如何优化。

我们先枚举行的选取情况，再去判断列。

首先不满足单调性的列肯定不能选取 果断删去 ，然后我们再记录下那些满足的列。

怎么求这些满足的列对答案的贡献呢？

  • 只选取一列。显然就是满足的列的数量。

  • 选取两列及以上。我们把行的单调性用二进制数 $s$ 来表示， 单调递增的行为 $1$, 单调递减或未选取的行为 $0$。我们可以得到状态转移方程：

    $+1$ 表示只选取 $j , k$ 两列。

    我们还可以发现，两列之间的递增递减关系是固定的，这就意味着对于 $j,k$ 两列，有效状态 $s$ 只有一个。而两列之间的递增递减关系是可以预处理出来的。

    所以 $DP$ 的复杂度为 $O(m^2)$

经过一番优化，我们已经将时间复杂度降至 $O(2 ^ n \times m ^ 2)$，可以通过本题。

$\Large\mathcal{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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>

#define int long long

template <typename Tp>
inline void read(Tp &x) {
    x = 0;
    bool f = true; char ch = getchar();
    for ( ; ch < '0' || ch > '9'; ch = getchar()) f ^= ch == '-';
    for ( ; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + (ch ^ 48);
    x = f ? x : -x;
}

const int N = 25, M = 1 << 20;

int a[N][N], p[N][N], c[N], f[M][N];

signed main() {
    int n, m;
    read(n), read(m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) read(a[i][j]);
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j < i; ++j) 
            for (int k = n; k; --k) p[i][j] = (p[i][j] << 1) | (a[k][i] > a[k][j]);
    int ans = 0;
    for (int i = (1 << n) - 1; i; --i) {
        int t = 0;
        for (int j = 1; j <= m; ++j) {
            int x = 0, flg = 0;
            for (int k = 1; k <= n; ++k) {
                if (!((1 << (k - 1)) & i)) continue;
                if (x && !flg) {
                    flg = a[k][j] < x ? -1 : 1;
                }
                else if (x && flg) {
                    int y = a[k][j] < x ? -1 : 1;
                    if (flg != y) {
                        flg = -2;
                        break;
                    }
                }
                x = a[k][j];
            }
            if (flg == -2) continue;
            c[++t] = j;
        }
        ans += t;
        for (int j = 2; j <= t; ++j) 
            for (int k = 1; k < j; ++k) f[p[c[j]][c[k]] & i][j] += f[p[c[j]][c[k]] & i][k] + 1, ans += f[p[c[j]][c[k]] & i][k] + 1;
        for (int j = 2; j <= t; ++j) 
            for (int k = 1; k < j; ++k) f[p[c[j]][c[k]] & i][j] = 0;   
    }
    printf("%lld\n", ans);
    return 0;
}

我写的可能不太好。如果还有什么不懂之处，可以去康一康官方题解。比我不知道高到哪里去了

$\huge{☞}$$\Large{戳这里}$

$\Large\mathcal{Impression}$

第一次打 $Comet OJ$ 的比赛，也是成功地一道题都没有 $AC$ 。

  • $T1$ 一个 $**$ 错误，挂 $10$ 分
  • $T2$ $map$ 内存炸掉，挂 $10$ 分 以前从来没有想过
  • $T3$ 还是一个 $**$ 错误，暴力挂 $5$ 分 数据再强点直接没了

会得还是太少，打代码也不够细节。我还是太菜了$……$

不在低谷时黯然离去，不在巅峰时慕名而来。