联赛Day1

Posted on Edited on In Word count in article: 1.3k Reading time ≈ 5 mins.
联赛Day1

T1

应该是水的，所有前后缀减重复的应该就可以了

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

typedef long long ll;
const int maxn = 1e7 + 10;

char s[maxn], t[maxn];
int cnts[26], cntt[26];

int main()
{
	scanf ("%s %s", s, t);
	int strs = strlen(s), strt = strlen(t);
	ll ans = 1ll * (strs + 1) * (strt + 1);
	for (int i = 0; i < strs; ++i) cnts[s[i] - 'a']++;
	for (int i = 0; i < strt; ++i) cntt[t[i] - 'a']++;
	for (int i = 0; i < 26; ++i) ans -= 1ll * cntt[i] * cnts[i];
	cout << ans << endl;
}

T2

好像还是不太好搞，先跳

可以十分暴力的。。。

T3

首先贪心的考虑，最后的答案可以写成这样的形式：\(r-l+1+len-s\)：

  • 其中 \(r-l+1+len\) 表示把所有的数先删除，再把目标串插回序列
  • \(s\) 表示被重复计算的部分
    • 可以被替换的数，多计算了一次
    • 原本就相等的数，多计算了两次

那么可以定义 \(d(i,j)\) 表示从 \(S_l\) 开始匹配到 \(T_i\) 时，被重复计算的次数为 \(j\) 的最小的 \(r\)

那么就有转移如下： \[ \begin{aligned} d(i+1, j)&=\min(d(i+1, j), d(i,j))\\ d(i+1, j+1)&=\min(d(i+1,j+1), d(i,j)+1)\\ d(i+1, j+2)&=\min(d(i+1,j+2), next(i+1,t_{i+1}))\\ \end{aligned} \] 怎么理解？

\(d(i+1,j)=\min(d(i+1,j),d(i,j))\)

就是说没有多的重复计算的部分，那么就是可以没有多的字符来进行有效匹配，就可以直接继承

\(d(i+1, j+1)=\min(d(i+1,j+1), d(i,j)+1)\)

多了一次重复计算，那么就是有一个可以被替换的，你用了一次删除和一次插入

那么随便加一个数进去就可以实现

\[d(i+1, j+2)=\min(d(i+1,j+2), next(r,t_{i+1}))\\\]

多了两次重复计算，既原本这两个数时匹配的，那么右端点可以直接跳到这个字符的下一个位置

那么最后一定是找到最大的 \(s\) 剪掉，得到的答案最小

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

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

char S[maxn], T[maxn];
int nxt[maxn][26 << 1];
int d[26][26 << 1];

int main()
{
    scanf ("%s %s", S + 1, T + 1);
    int lens = strlen (S + 1), lent = strlen (T + 1);

    for (int i = 0; i < 26; ++i)
        nxt[lens][i] = lens + 1;

    for (int i = lens; i; --i) {
        for (int j = 0; j < 26; ++j)
            nxt[i - 1][j] = nxt[i][j];
        nxt[i - 1][S[i] - 'a'] = i;
    }

    int q = __read();
    while (q--) {
        int l = __read(), r = __read(), len = r - l + 1;

        memset (d, 0x3f, sizeof d);
        d[0][0] = l - 1;

        for (int i = 0; i <= lent; ++i)
            for (int j = 0; j <= (lent << 1); ++j) {
                if (d[i][j] > r) continue;
                d[i + 1][j] = min(d[i + 1][j], d[i][j]);
                d[i + 1][j + 1] = min(d[i + 1][j + 1], d[i][j] + 1);
                d[i + 1][j + 2] = min(d[i + 1][j + 2], nxt[d[i][j]][T[i + 1] - 'a']);
            }

        int s = lent << 1;
        while (d[lent][s] > r) s--;
        printf ("%d\n", len + lent - s);
    }
}

T4

30

十分阶乘暴力，不管那么多了

然后对于所有点的父节点都是 \(1\) 的数据，就可以用康托展开：

  • 如果给定的 \(a_i=1\)，那么就求这个序列的康托展开即可
  • 否则呢就直接是 \((n-1)!\)，这个应该还是很好证明的

Code(30)

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

#define lowbit(x) (x & -x)

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 10;
const int Mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

int n, cnt, tot(1);
int f[maxn], a[maxn], b[maxn], fm;
bool vis[maxn];
vector <int> edge[maxn];

int Tree[maxn], Fac[maxn] = {1};

inline void Add(int X, int Val)
{
    while (X <= n)
    {
        Tree[X] += Val;
        X += lowbit(X);
    }
}

inline int Query(int X)
{
    int Ans(0);
    while (X)
    {
        Ans = (Ans + Tree[X]) % Mod;
        X -= lowbit(X);
    }
    return Ans;
}

inline int Getans(int Arr[], int Tmp[], int N)
{
    int Ans = 1;
    sort(Tmp + 1, Tmp + 1 + N);
    for (int i = 1; i <= N; ++i) Arr[i] = lower_bound(Tmp + 1, Tmp + 1 + N, Arr[i]) - Tmp;
    for (int i = 1; i <= N; ++i) Fac[i] = 1ll * Fac[i - 1] * i % Mod, Add(i, 1);
    for (int i = 1; i <= N; ++i)
    {
        Ans = (Ans + ((1ll * Query(Arr[i]) - 1) * Fac[N - i]) % Mod) % Mod;
        Add(Arr[i], -1);
    }
    return Ans;
}

inline bool check () {
    bool equ(1);
    for (int i = 1; i <= n; ++i) {
        if (equ && b[i] > a[i]) return 1;
        if (b[i] < a[i]) equ = 0;
    }
    return 0;
}

bool Check(int u)
{
    for (int i = 0; i < edge[u].size(); ++i) {
        int v = edge[u][i];
        if (Check(v) || b[v] < b[u]) return 1;
    }
    return 0;
}

void dfs(int step)
{
    if (step >= n) {
        if (check()) return;
        if (!Check(1) && (++cnt) == 1){
            for (int i = 1; i <= n; ++i) {
                printf ("%d ", b[i]);
            }
        }
        return ;
    }
    for (int i = n; i; --i) {
        if (vis[i]) continue;
        b[step + 1] = i;
        vis[i] = 1;
        dfs(step + 1);
        vis[i] = 0;
    }
}

int main()
{
    n = __read();
    for (int i = 1; i < n; ++i) 
        tot = 1ll * tot * i % Mod;
    for (int i = 2; i <= n; ++i) {
        int f = __read();
        fm = max(fm, f);
        edge[f].push_back(i);
    }
    for (int i = 1; i <= n; ++i) 
        a[i] = b[i] = __read();
    if (fm > 1) dfs(0), printf("\n%d\n", cnt);
    else {
        if (a[1] == 1) {
            for (int i = 1; i <= n; ++i) printf ("%d ", a[i]);
            puts("");
            printf("%d\n", Getans(a, b, n));
        }
        else {
            printf ("%d ", a[1]);
            for (int i = 2; i <= n; ++i) printf ("%d ", n - i + 2);
            printf("\n%d\n", tot);
        }
    }
}