2019杭电多校第二场

发表于 分类于 阅读次数： 本文字数： 10k 阅读时长 ≈ 9 分钟

太菜了，被学弟暴打

1002. Beauty of Unimodal Sequence

upsolved

要求输出字典序最小和最大的最长单峰子序列 对于每一个位置，维护以这个位置结尾的前缀/后缀最长上升/单峰子序列长度，然后贪心输出（如果只要求长度正反求LIS就好了)

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

const int N = 3e5 + 10;

int n, a[N];

struct Seg_Tree {
	int mx[N << 2];
	void init(int rt = 1, int l = 1, int r = n + 2) {
		mx[rt] = 0;
		if(l == r) return;
		int mid = l + r >> 1;
		init(rt << 1, l, mid);
		init(rt << 1 | 1, mid + 1, r);
	}
	void pushup(int rt) {
		mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]);
	}
	void update(int rt, int l, int r, int pos, int val) {
		if(l == r) {
			mx[rt] = max(mx[rt], val);
			return;
		}
		int mid = l + r >> 1;
		if(pos <= mid)
			update(rt << 1, l, mid, pos, val);
		else
			update(rt << 1 | 1, mid + 1, r, pos, val);
		pushup(rt);
	}
	int query(int rt, int l, int r, int L, int R) {
		if(L <= l && r <= R)
			return mx[rt];
		int mid = l + r >> 1, ans = 0;
		if(L <= mid)
			ans = max(ans, query(rt << 1, l, mid, L, R));
		if(R > mid)
			ans = max(ans, query(rt << 1 | 1, mid + 1, r, L, R));
		return ans;
	}
}zero, one;

int dp[2][N][2], len;
vector<int> ans[2], all, up[N], down[N];

void init() {
	len = 0;
	zero.init();
	one.init();
	all.clear();
	ans[0].clear();
	ans[1].clear();
	for(int i = 0; i <= n + 1; ++i)
		up[i].clear(), down[i].clear();
}

int main() {
	while(~scanf("%d", &n)) {
		init();
		for(int i = 1; i <= n; ++i) {
			scanf("%d", &a[i]);
			all.push_back(a[i]);
		}
		all.push_back(0);
		all.push_back(0x3f3f3f3f);
		sort(all.begin(), all.end());
		all.erase(unique(all.begin(), all.end()), all.end());
		for(int i = 1; i <= n; ++i) {
			a[i] = lower_bound(all.begin(), all.end(), a[i]) - all.begin() + 1;
		}
		for(int i = 1; i <= n; ++i) {
			dp[0][i][0] = zero.query(1, 1, n + 2, 1, a[i] - 1) + 1;
			dp[0][i][1] = max(one.query(1, 1, n + 2, a[i] + 1, n + 2) + 1, dp[0][i][0]);
			zero.update(1, 1, n + 2, a[i], dp[0][i][0]);
			one.update(1, 1, n + 2, a[i], dp[0][i][1]);
		}
		zero.init(); one.init();
		for(int i = n; i; --i) {
			dp[1][i][0] = zero.query(1, 1, n + 2, 1, a[i] - 1) + 1;
			dp[1][i][1] = max(one.query(1, 1, n + 2, a[i] + 1, n + 2) + 1, dp[1][i][0]);
			zero.update(1, 1, n + 2, a[i], dp[1][i][0]);
			one.update(1, 1, n + 2, a[i], dp[1][i][1]);
		}
		for(int i = 1; i <= n; ++i) {
			len = max(len, dp[0][i][0] + dp[1][i][1] - 1);
		}
		for(int i = 1; i <= n; ++i) {
			assert(len >= dp[0][i][1] + dp[1][i][0] - 1);
		}
		for(int i = 1; i <= n; ++i) {
			if(dp[0][i][0] + dp[1][i][1] - 1 == len) {
				up[dp[0][i][0]].push_back(i);
			}
			if(dp[0][i][1] + dp[1][i][0] - 1 == len) {
				down[dp[1][i][0]].push_back(i);
			}
		}
		int cur = 0, flag = 0;
		for(int i = 1; i <= len; ++i) {
			if(!flag) {
				vector<int> &v = up[i];
				int p = upper_bound(v.begin(), v.end(), cur) - v.begin();
				if(p == v.size() || a[v[p]] <= a[cur]) {
					flag = 1;
				}
				else {
					vector<int> &vv = down[len - i + 1];
					int pp = upper_bound(v.begin(), v.end(), cur) - v.begin();
					if(pp != vv.size() && a[vv[pp]] < a[cur] && vv[pp] < v[p]) {
						flag = 1;
					}
					else {
						cur = v[p];
						ans[0].push_back(v[p]);
					}
				}
			}
			if(flag) {
				vector<int> &v = down[len - i + 1];
				int p = upper_bound(v.begin(), v.end(), cur) - v.begin();
				assert(a[v[p]] < a[cur]);
				assert(p < v.size());
				cur = v[p];
				ans[0].push_back(v[p]);
			}
		}
		cur = flag = 0;
		for(int i = 1; i <= len; ++i) {
			if(!flag) {
				vector<int> &v = up[i];
				int p = lower_bound(v.begin(), v.end(), cur, [&](int i, int j){return a[i] > a[j];}) - v.begin() - 1;
				if(p < 0 || a[v[p]] <= a[cur]) {
					flag = 1;
				}
				else {
					cur = v[p];
					ans[1].push_back(v[p]);
				}
			}
			if(flag) {
				vector<int> &v = down[len - i + 1];
				int p = lower_bound(v.begin(), v.end(), cur, [&](int i, int j){return a[i] < a[j];}) - v.begin() - 1;
				assert(p >= 0);
				assert(a[v[p]] < a[cur]);
				cur = v[p];
				ans[1].push_back(v[p]);
			}
		}
		for(int _ = 0; _ < 2; ++_) {
			for(int i = 0; i < len; ++i)
				printf("%d%c", ans[_][i], " \n"[i + 1 == len]);
		}
	}
	return 0;
}

1005. Everything Is Generated In Equal Probability

solved at 01:45(+1)

求当前序列的逆序对数并且将当前序列随机替换成一个子序列(\(2^n\))种，递归处理每次结果相加直到序列为空为止

每次给定一个\({\rm N}\), 你随机取一个\(n\in[1,{\rm N}]\)，然后随机取一个\(n\)个数的排列作为初始序列，求总逆序对数的期望

设\(f(n)\)代表长为\(n\)的序列的期望

显然\[f(n) = \frac {n(n-1)} 4 + \sum\limits_{i = 0}^{n}\frac {C_n^i} {2^n}f(i)\]

\(n\)只有\(3000\),\(n^2\)递推即可，最后再求个前缀和

群里有老哥一眼看出答案是\(\frac {n^2-1} 9\) ....

1006. Fantastic Magic Cube

upsolved

题意转化之后就是你有一个\(n \ast n \ast n\)的立方体，每个\(1 \ast 1 \ast 1\)的小立方体都有自己的权值（权值为三个坐标的异或），你每次沿着一个方向把一个立方体切成两个立方体，获得的价值是两个立方体的权值和的乘积，你需要把它们都切成\(1 \ast 1 \ast 1\)的，求最大价值

听了dls题解，发现是个阅读理解，不管怎么切都是一样的

考虑两个不同的小立方体，它们的权值乘积一定被加到了最终的价值里，并且只加了一次

于是只要\(FWT\)求出每个权值的小立方体有多少个然后求一求和就好了

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 <bits/stdc++.h>
using namespace std;
using LL = long long;
const int mod = 998244353, N = 1048576 + 10, g = 3;

LL qp(LL a, LL n) {
	LL res = 1;
	while(n) {
		if(n & 1) 
			res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

const int inv2 = qp(2, mod - 2);

void FWT(int a[], int n) {  
    for(int d = 1; d < n; d <<= 1)  
        for(int m = d << 1, i = 0; i < n; i += m)  
            for(int j = 0; j < d; ++j) {  
                int x = a[i + j], y = a[i + j + d];  
                a[i + j] = (x + y) % mod, a[i + j + d] = (x - y + mod) % mod;   
            }  
}  

void IFWT(int a[], int n)   {  
    for(int d = 1; d < n; d <<= 1)  
        for(int m = d << 1, i = 0; i < n; i += m)  
            for(int j = 0; j < d; ++j) {  
                int x = a[i + j], y = a[i + j + d];  
                a[i + j] = 1LL * (x + y) * inv2 % mod, a[i + j + d] = (1LL * (x - y) * inv2 % mod + mod) % mod; 
            }  
} 

int n, a[N], m;
LL sum, ans;

int main() {
	while(~scanf("%d", &n)) {
		m = n;
		sum = ans = 0;
		for(; m & (m - 1); m += m & -m);
		for(int i = 0; i < m; ++i) 
			a[i] = 0;
		for(int i = 0; i < n; ++i)
			a[i] = 1;
		FWT(a, m);
		for(int i = 0; i < m; ++i)
			a[i] = 1LL * a[i] * a[i] % mod * a[i] % mod;
		IFWT(a, m);
		for(int i = 0; i < m; ++i)
			sum = (sum + 1LL * i * a[i]) % mod;
		for(int i = 0; i < m; ++i)
			ans = (ans + (1LL * i * a[i] % mod * (sum - i) % mod + mod) % mod) % mod;
		printf("%lld\n", ans * inv2 % mod);
	}
	return 0;
}

##1009. I Love Palindrome String

待补, PAM待学

##1010. Just Skip The Problem

solved at 00:31

直接输出\(n!\)就好了，\(1\)特判掉（不过我看有的人没特判就过了，怕不是没这数据。。。）

1011. Keen on Everything But Triangle

solved at 00:44

\(Q\)次询问一个区间里的数能构成的最大周长的三角形

因为数据范围是\(1e9\)所以大概四十几个数就一定能构成三角形，从大到小排序，先找\(123\)，不行就\(234\)，找个四十几次就行了

主席树实现的，线段树维护前\(45\)大暴力合并据说也可以

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 <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN = 100010;
struct node {
	int l, r, sum;
}Tree[MAXN * 30];
int root[MAXN];

struct num {
	int x, id;
	bool operator < (const num &rhs) const {
		return x < rhs.x;
	}
}a[MAXN];

int rnk[MAXN];
int n, m, i, j, k, cnt, l, r, x, y, z;

void init() {
	cnt = 0;
	root[0] = 0;
	Tree[0].l = Tree[0].r = Tree[0].sum = 0;
}

void update(int &rt, int l, int r, int num) {
	Tree[++cnt] = Tree[rt];
	rt = cnt;
	Tree[rt].sum++;
	if(l == r)
		return;
	int mid = l + r >> 1;
	if(num <= mid)
		update(Tree[rt].l, l, mid, num);
	else
		update(Tree[rt].r, mid + 1, r, num);
}

int query(int i, int j, int k, int l, int r) {
	if(l == r)
		return l;
	int mid = l + r >> 1;
	int d = Tree[Tree[j].l].sum - Tree[Tree[i].l].sum;
	if(k <= d)
		return query(Tree[i].l, Tree[j].l, k, l, mid);
	else
		return query(Tree[i].r, Tree[j].r, k - d, mid + 1, r);
}

int main() {
	while(~scanf("%d %d", &n, &m)) {
		init();
		for(int i = 1; i <= n; ++i) {
			scanf("%d", &a[i].x);
			a[i].id = i;
		}
		sort(a + 1, a + n + 1);
		for(int i = 1; i <= n; ++i) {
			rnk[a[i].id] = i;
		}
		for(int i = 1; i <= n; ++i) {
			root[i] = root[i - 1];
			update(root[i], 1, n, rnk[i]);
		}
		while(m--) {
			scanf("%d %d", &l, &r);
			if(r - l < 2) {
				printf("-1\n");
				continue;
			}
			cnt = r - l + 1;
			x = a[query(root[l - 1], root[r], cnt, 1, n)].x;
			y = a[query(root[l - 1], root[r], cnt - 1, 1, n)].x;
			z = a[query(root[l - 1], root[r], cnt - 2, 1, n)].x;
			if(x < y + z) {
				printf("%lld\n", 0LL + x + y + z);
				continue;
			}
			bool flag = 0;
			for(int i = 3; i < cnt; ++i) {
				x = y;
				y = z;
				z = a[query(root[l - 1], root[r], cnt - i, 1, n)].x;
				if(x < y + z) {
					flag = 1;
					printf("%lld\n", 0LL + x + y + z);
					break;
				}
			}
			if(!flag) {
				printf("-1\n");
			}
		}
	}
	return 0;
}

1012. Longest Subarray

upsolved

自闭题

求最长的连续子序列满足序列里出现的数都至少出现了\(k\)次

枚举右端点，线段树维护不合法的区间，每次询问最左边的合法位置即可

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

const int N = 1e5 + 10;

int mn[N << 2], lazy[N << 2];

void pushdown(int rt) {
	if(lazy[rt]) {
		lazy[rt << 1] += lazy[rt];
		lazy[rt << 1 | 1] += lazy[rt];
		mn[rt << 1] += lazy[rt];
		mn[rt << 1 | 1] += lazy[rt];
		lazy[rt] = 0;
	}
}

void pushup(int rt) {
	mn[rt] = min(mn[rt << 1], mn[rt << 1 | 1]);
}

void build(int rt, int l, int r) {
	lazy[rt] = mn[rt] = 0;
	if(l == r)
		return;
	int mid = l + r >> 1;
	build(rt << 1, l, mid);
	build(rt << 1 | 1, mid + 1, r);
}

void update(int rt, int	l, int r, int L, int R, int val) {
	if(L <= l && r <= R) {
		mn[rt] += val;
		lazy[rt] += val;
		return;
	}
	pushdown(rt);
	int mid = l + r >> 1;
	if(L <= mid)
		update(rt << 1, l, mid, L, R, val);
	if(R > mid)
		update(rt << 1 | 1, mid + 1, r, L, R, val);
	pushup(rt);
}

int query(int rt, int l, int r) {
	if(mn[rt] > 0) return 0;
	if(l == r) return l;
	pushdown(rt);
	int mid = l + r >> 1;
	if(mn[rt << 1] == 0)
		return query(rt << 1, l, mid);
	return query(rt << 1 | 1, mid + 1, r);
}

int a[N], n, c, k, ans, i, j, x, y;
vector<int> pos[N];

int main() {
	while(~scanf("%d%d%d", &n, &c, &k)) {
		if(k == 1) {
			for(int i = 1; i <= n; ++i)
				scanf("%*d");
			printf("%d\n", n);
			continue;
		}
		build(1, 1, n);
		ans = 0;
		for(i = 1; i <= n; ++i) {
			scanf("%d", &a[i]);
			if(pos[a[i]].empty()) {
				update(1, 1, n, 1, i, 1);
				pos[a[i]].push_back(i);
			}
			else {
				x = pos[a[i]].size() - k;
				y = pos[a[i]].back();
				if(x < 0) {
					update(1, 1, n, 1, y, -1);
				}
				else {
					update(1, 1, n, pos[a[i]][x] + 1, y, -1);
				}
				pos[a[i]].push_back(i);
				x = pos[a[i]].size() - k;
				y = pos[a[i]].back();
				if(x < 0) {
					update(1, 1, n, 1, y, 1);
				}
				else {
					update(1, 1, n, pos[a[i]][x] + 1, y, 1);
				}
			}
			j = query(1, 1, n);
			if(j) ans = max(ans, i - j + 1);
		}
		for(int i = 1; i <= c; ++i)
			pos[i].clear();
		printf("%d\n", ans);
	}
	return 0;
}

1007dls发了ppt, 估计是学不会，1008队友补了，1009看什么时候有时间去学