Luobuyu's Blog

0%

nowcoder多校(第一场)

发表于 分类于 ， 热度： ℃ 评论：
本文字数： 7.7k 阅读时长 ≈ 7 分钟
2020年nowcoder暑期多校训练(第一场)，出题人:叉姐。不愧是叉姐，题目一堆需要结论做的，补题都补不动

A. B-Suffix Array

题目描述：

给定一个字符串，只有 a 和 b 两种字符。对于该字符串的每一个后缀，求 B-function 然后排序，输出 $ [1-n] $ 对应起始位置的排名

$ B-function $ 规则

  • If there is an index $ j<i $ where $ t_j = t_i $ , $ b_i = \min_{1 \leq j < i, t_j = t_i}\{i - j\} $
  • Otherwise, $ b_i = 0 $ .

题解：

存在一个定理，反过来从后往前求，记作数组 $ c[i] $

  • If there is an index $ j<i $ where $ t_j = t_i $ , $ b_i = \min_{1 \leq j < i, t_j = t_i}\{i - j\} $
  • Otherwise, $ b_i = n $ .
  • c[n + 1] = n + 1

举例说明，以样例为例

输入

1
2
5
abaab

输出

1
5 4 2 1 3

abaab 对应的 c 数组为 231556

c 数组的后缀为

后缀 231556 31556 1556 556 56 6

排名 2 3 1 4 5 6

$ sa $ 数组 3 1 2 4 5 6

直接倒序输出 $ sa $ 数组即可得到答案

显然需要使用数据结构后缀数组

下面是根据板子写的代码

• Detailed proof can be found in “Parameterized Suffix Arrays for Binary Strings
• http://www.stringology.org/event/2008/p08.html

代码：

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
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5 + 10;
const int maxm = 50000;
const ll mod = 998244353;
const int inf = 0x3f3f3f3f;
int t;
int n;
char s[maxn];
int c[maxn];

int sa[maxn], wa[maxn], wb[maxn], bucket[maxn];
// wa 第一关键字， wb 第二关键字
void getSA(int n, int m = 130)
{
    int *x = wa, *y = wb;
    for(int i = 0; i <= m; i++) bucket[i] = 0;
    for(int i = 0; i < n; i++) bucket[x[i] = c[i]]++;
    for(int i = 1; i <= m; i++) bucket[i] += bucket[i - 1];
    for(int i = n - 1; i >= 0; i--) sa[--bucket[x[i]]] = i;

    for(int k = 1; k <= n; k<<=1)
    {
        int p = 0;
        for(int i = n - k; i < n; i++) y[p++] = i;
        for(int i = 0; i < n; i++) if(sa[i] >= k) y[p++] = sa[i] - k;

        for(int i = 0; i <= m; i++) bucket[i] = 0;
        for(int i = 0; i < n; i++) bucket[x[y[i]]]++;
        for(int i = 1; i <= m; i++) bucket[i] += bucket[i-1];
        for(int i = n - 1; i >= 0; i--) sa[--bucket[x[y[i]]]] = y[i];

        swap(x, y);
        x[sa[0]] = 0;
        p = 1;
        for(int i = 1; i < n; i++)
            x[sa[i]]= (y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]) ? p - 1 : p++;
        if(p >= n) break;
        m = p;
    }
}


int main()
{
#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
//    freopen("in.txt", "r", stdin);
   freopen("out.txt", "w", stdout);
#endif // debug
//    ios::sync_with_stdio(false);
//    cin.tie(0);
    while(~scanf("%d", &n))
    {
        scanf("%s", s);
        int lasta = -1, lastb = -1;
        for(int i = n - 1; i >= 0; i--)
        {
            if(s[i] == 'a')
            {
                if(lasta == -1) c[i] = n;
                else c[i] = lasta - i;
                lasta = i;
            }
            else
            {
                if(lastb == -1) c[i] = n;
                else c[i] = lastb - i;
                lastb = i;
            }
        }
        c[n] = n + 1;

        getSA(n + 1, n + 2); // 需要注意传的参数
        for(int i = n - 1; i >= 0; i--)
        {
            cout << sa[i] + 1 << " \n"[i==0];
        }
    }
    return 0;
}

B.

题目描述：

题解：

代码：

1
2


C.

题目描述：

题解：

代码：

1
2


D.

题目描述：

题解：

代码：

1
2


E.

题目描述：

题解：

代码：

1
2


F. Infinite String Comparision

题目描述：

For a string xxx, Bobo defines $ x^\infty = x x x \dots $ ，which is xxx repeats for infinite times, resulting in a string of infinite length.

Bobo has two strings aaa and bbb. Find out the result comparing $ a^\infty $ and $ b^\infty $ in lexicographical order.

You can refer the wiki page for further information of Lexicographical Order.

题解：

1594565828266.png

玄学定理，

1594565911029.png

证明链接

因为两个字符串相同的话就是有两个循环节，因此就可以判断了

代码：

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
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e6 + 10;
const int maxm = 8 + 5;
const ll mod = 998244353;
const int inf = 0x3f3f3f3f;

ll n, m;
string a, b;
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif // debug
    while(cin >> a >> b)
    {
        int tag = 0;
        ll len = a.length() + b.length() - __gcd(a.length(), b.length());
        int j = 0, k = 0;
        for(int i = 0; i < len; i++)
        {
            tag = a[j] - b[k];
            if(tag != 0) break;
            j = (j + 1) % a.length();
            k = (k + 1) % b.length();
        }
        if(tag == 0) cout << '=' << endl;
        else if(tag < 0) cout << '<' << endl;
        else if(tag > 0) cout << '>' << endl;
    }
    return 0;
}

G.

题目描述：

题解：

代码：

1
2


H.

题目描述：

题解：

代码：

1
2


I. 1 or 2

题目描述：

一个图，无自环和重边， $ n $ 个点， $ m $ 条边

给出一个数组 $ 1 <= d[i] <= 2 $ ，是否可以选出一些边，满足第 $ i $ 个结点有 $ d[i] $ 条直接相连的边

题解：

假如所有点 $ d_i $ 都为 $ 1 $ ，那么就是一般图最大匹配问题

尝试将 $ d_i=2 $ 的点拆开，让他们各自找一个点匹配。那么就会有这样一个问题，由一个点拆开的两个点可能正好和另外两个由一个点拆开的点相匹配。所以我们不能将原边照搬，应当加以限制。

将一条边 $ e $ 拆成拆成两个点 $ e, e’ $ 按照题解中的方式连边。这样的话如果 $ e $ 和 $ e’ $ 匹配的话，出现矛盾，说明不选这条边，否则选这条边。这样问题就转化成了 $ d_i = 1 $ 的情况，可以使用一般图完美匹配做了。

直接套板子，注意点的个数发生了变化

1594825322205.png

代码：

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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn =  300 + 10;
const int maxm = 4000 + 10;
const ll mod = 998244353;
const int inf = 0x3f3f3f3f;

queue<int> q;
int pre[maxn], tp[maxn], head[maxn], match[maxn];
int cnt, n, m;
int tim; // 花的数量
struct Edge
{
    int v, next;
}edge[maxm];
inline void addEdge(int u, int v)
{
    cnt++;
    edge[cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt;
}
int fa[maxn];
int findFa(int u)
{
    return fa[u] == u ? u : (fa[u] = findFa(fa[u]));
}

int dfn[maxn];
int getLca(int x, int y)
{
    tim++;
    x = findFa(x); y = findFa(y);
    while(dfn[x] != tim)
    {
        dfn[x] = tim;
        x = findFa(pre[match[x]]);
        if(y) swap(x, y);
    }
    return x;
}

void blossom(int x, int y, int lca)
{
    while(findFa(x) != lca)
    {
        pre[x] = y; y = match[x];
        if(tp[y] == 2)
        {
            tp[y] = 1; q.push(y);
        }
        if(findFa(x) == x) fa[x] = lca;
        if(findFa(y) == y) fa[y] = lca;
        x = pre[y];
    }
}

bool bfs(int s)
{
    for(int i = 1; i <= n * 2 + m * 2; i++) fa[i] = i;
    memset(pre, 0, sizeof(pre));
    memset(tp, 0, sizeof(tp));
    while(!q.empty()) q.pop();
    tp[s] = 1; // 标记类型
    q.push(s);
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for(int i = head[u]; i; i = edge[i].next)
        {
            int v = edge[i].v;
            if(findFa(v) == findFa(u) || tp[v] == 2) continue;
            if(!tp[v]) // 未标记的
            {
                pre[v] = u; tp[v] = 2;
                if(!match[v]) // 未匹配，记为匹配
                {
                    for(int now = v, last; now != 0; now = last)
                    {
                        last = match[pre[now]];
                        match[now] = pre[now];
                        match[pre[now]] = now;
                    }
                    return true;
                }
                tp[match[v]] = 1, q.push(match[v]);
            }
            else // 标记的（找过了，环）
            {
                int lca = getLca(u, v);
                blossom(u, v, lca);
                blossom(v, u, lca);
            }
        }
    }
    return false;
}
int D[maxn], tot, deg[maxn];

bool solve()
{
    memset(dfn, 0, sizeof(dfn));
    tim = 0;
    memset(match, 0, sizeof(match));
    for(int i = 1; i <= n * 2 + m * 2; i++)
    {
        if(!match[i]) bfs(i);
    }
    int ans = 0;
    for(int i = 1; i <= n * 2 + m * 2; i++) if(match[i]) ans++;
    return ans == tot;
}

int main()
{
#ifndef ONLINE_JUDGE
//    freopen("1.in", "r", stdin);
    freopen("in.txt", "r", stdin);
//   freopen("out.txt", "w", stdout);
#endif // debug
//    ios::sync_with_stdio(false);
//    cin.tie(0);
    while(~scanf("%d %d", &n, &m))
    {
        cnt = 0;
        memset(head, 0, sizeof(head));
        tot = n;
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &D[i]);
            if(D[i] == 2) tot++;
        }
        memset(deg, 0, sizeof(deg));
        tot += m * 2;
        for(int i = 1; i <= m; i++)
        {
            int x, y;
            scanf("%d %d", &x, &y);
            deg[x]++, deg[y]++;
            if(D[x] == 2)
            {
                addEdge(x, 2 * n + i);
                addEdge(x + n, 2 * n + i);
                addEdge(2 * n + i, x);
                addEdge(2 * n + i, x + n);
            }
            else
            {
                addEdge(x, 2 * n + i);
                addEdge(2 * n + i, x);
            }
            if(D[y] == 2)
            {
                addEdge(2 * n + m + i, y);
                addEdge(2 * n + m + i, y + n);
                addEdge(y, 2 * n + m + i);
                addEdge(y + n, 2 * n + m + i);
            }
            else
            {
                addEdge(y, 2 * n + m + i);
                addEdge(2 * n + m + i, y);
            }
            addEdge(2 * n + i, 2 * n + m + i);
            addEdge(2 * n + m + i, 2 * n+ i);
        }
        bool op = 1;
        for(int i = 1; i <= n; i++)
        {
            if(deg[i] < D[i])
            {
                op = 0;
            }
        }
        if(!op)
        {
            printf("No\n");
            continue;
        }
        if(solve()) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

J. Easy Integration

题目描述：

本质是个数学题

Given n, find the value of $ \int_{0}^1 (x - x^2)^n \mathrm{d} x $
It can be proved that the value is a rational number pq\frac{p}{q}qp​.
Print the result as $ (p \cdot q^{-1}) \bmod 998244353 $ .

因为是多个样例输入，一直以为是打表，然后计算。最后发现是个数学题。

题解：

可以使用 $ n $ 次分部积分或者瓦里斯公式得到结果

1594564111433.png

代码：

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
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e6 + 10;
const int maxm = 8 + 5;
const ll mod = 998244353;
const int inf = 0x3f3f3f3f;

ll n, m;
ll qpower(ll a, ll b)
{
    ll ans = 1;
    ll tmp = a;
    while(b)
    {
        if(b & 1) ans = (ans * tmp) % mod;
        tmp = (tmp * tmp) % mod;
        b >>= 1;
    }
    return ans % mod;
}

int ans[maxn];

void init()
{
    ans[0] = 1;
    for(ll i = 1; i <= 1e6; i++)
    {
        ans[i] = ((((ans[i-1] * i) % mod) * i) % mod * qpower((2 * i)* (2*i + 1) % mod, mod - 2)) % mod;
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif // debug
    init();
    while(scanf("%lld", &n) != EOF)
    {
        cout << ans[n] << endl;
    }
    return 0;
}