2019杭电多校第五场

1002. three arrays

upsloved

你有两个长为\(n\)的序列\(a, b\),你可以任意打乱这两个序列,使得序列\(c\)字典序最小\((c_i = a_i\, xor\, b_i)\) 题解很神秘,看不懂。。。

两颗字典树dfs相互跑就好了

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

const int N = 1e5 + 10;

struct Trie {
int root, sz, cnt[N * 31], nxt[N * 31][2];
int newnode() {
cnt[sz] = 0;
memset(nxt[sz], 0, sizeof(nxt[sz]));
return sz++;
}
void init() {
sz = 0;
root = newnode();
}
void insert(int x) {
int p = root;
for(int i = 29; ~i; --i) {
int c = (x >> i) & 1;
if(!nxt[p][c])
nxt[p][c] = newnode();
p = nxt[p][c];
cnt[p]++;
}
}
}A, B;

int a[N], b[N], T, n;

vector< pair<int, int> > ans;

void dfs(int p1, int p2, int x, int s) {
int c = min(A.cnt[p1], B.cnt[p2]);
A.cnt[p1] -= c; B.cnt[p2] -= c;
if(s == 30) {
ans.push_back(make_pair(x, c));
//cout << x << " " << c << endl;
return;
}
if(A.cnt[A.nxt[p1][0]] && B.cnt[B.nxt[p2][0]])
dfs(A.nxt[p1][0], B.nxt[p2][0], x << 1, s + 1);
if(A.cnt[A.nxt[p1][1]] && B.cnt[B.nxt[p2][1]])
dfs(A.nxt[p1][1], B.nxt[p2][1], x << 1, s + 1);
if(A.cnt[A.nxt[p1][0]] && B.cnt[B.nxt[p2][1]])
dfs(A.nxt[p1][0], B.nxt[p2][1], x << 1 | 1, s + 1);
if(A.cnt[A.nxt[p1][1]] && B.cnt[B.nxt[p2][0]])
dfs(A.nxt[p1][1], B.nxt[p2][0], x << 1 | 1, s + 1);
}

int main() {
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
A.init(); B.init();
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
A.insert(a[i]);
}
for(int i = 1; i <= n; ++i) {
scanf("%d", &b[i]);
B.insert(b[i]);
}
ans.clear();
dfs(A.root, B.root, 0, 0);
sort(ans.begin(), ans.end());
for(int i = 0; i < ans.size(); ++i) {
for(int j = 1; j <= ans[i].second; ++j) {
printf("%d", ans[i].first);
if(j != ans[i].second)
printf(" ");
}
if(i + 1 != ans.size())
printf(" ");
}
puts("");
}
return 0;
}

1004. equation

solved at 03:02(+2)

队友做的,没看

1005. permutation1

solved at 02:25(+1)

T组数据,你有一个\(1-n\)的排列\(a\),定义\(d[i]=a[i+1]-a[i](1<=i<n)\)

求字典序第\(k\)小的\(d\)序列对应的原序列\(a\)

\(2<=n<=20, 1<=k<=min(factorial(n), 1e4), 1<=T<=40\)

题解是个搜索。。。

我的(实际上是队友的想法我的实现)做法是枚举\(d\)数组计算出剩下的方案数,复杂度\(O(Tn^3)\)

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

int a[25], T, n, k, b[25], vis[25][50], N = 25, s, ss, mx, mn;
long long f[25], tmp;

void get_a() {
int x = 0, s = 0, p = 1;
for(int i = 1; i < n; ++i) {
s += b[i];
if(s > x) {
p = 1 + i;
x = s;
}
}
a[p] = n;
for(int i = p + 1; i <= n; ++i) {
a[i] = b[i - 1] + a[i - 1];
}
for(int i = p - 1; i > 0; --i) {
a[i] = a[i + 1] - b[i];
}
}

int main() {
f[0] = f[1] = 1;
for(int i = 2; i <= 20; ++i)
f[i] = f[i - 1] * i;
scanf("%d", &T);
while(T--) {
memset(vis, 0, sizeof(vis));
scanf("%d%d", &n, &k);
vis[0][N] = 1; s = 0; mx = 0; mn = 0;
for(int i = 1; i < n; ++i) {
for(int j = 1 - n; j <= n - 1; ++j) {
if(vis[i - 1][N - j] || j == 0) continue;
ss = s + j;
bool flag = 0;
for(int l = N - n; l <= N + n; ++l) {
if(vis[i - 1][l] && (abs(l + j - N) >= n || l + j == N))
flag = 1;
}
if(flag) continue;
if(i == 1)
tmp = f[n - i - 1] * (n - abs(ss));
else
tmp = f[n - i - 1] * (n - max(max(abs(mx), abs(mn)), max(max(abs(ss - mx), abs(ss - mn)), max(abs(mx - mn), abs(ss)))));
if(tmp >= k) {
b[i] = j;
s += j;
int sp = 0;
vis[i][sp + N] = 1;
for(int l = i; l; --l) {
sp += b[l];
vis[i][sp + N] = 1;
}
mx = max(mx, ss);
mn = min(mn, ss);
break;
}
else {
k -= tmp;
}
}
}
get_a();
for(int i = 1; i <= n; ++i)
printf("%d%c", a[i], " \n"[i == n]);
}
return 0;
}

1006. string matching

solved at 00:28(+1)

没开long long wa了一发。。

exkmp裸题

1007. permutation2

solved at 00:57(+1)

有一个1-n的排列,你知道第一项和最后一项,且相邻项的差不超过2,求方案数

oeis+队友想的+瞎搞搞

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

const int N = 1e5 + 10, mod = 998244353;

int f[N], n, x, y, T;

int get(int x, int y) {
if(x == y - 1) {
if(x != 1 && y != n)
return 0;
return 1;
}
if(x != 1) x++;
if(y != n) y--;
return f[y - x];
}

int main() {
f[0] = f[1] = f[2] = 1;
for(int i = 3; i < N; ++i)
f[i] = (f[i - 1] + f[i - 3]) % mod;
scanf("%d", &T);
while(T--) {
scanf("%d%d%d", &n, &x, &y);
printf("%d\n", get(x, y));
}
return 0;
}