Binary search,two pinters, meet-in-the-middle, divide-and-conquer Trees

这次真是学到很多新东西，KMP，双指针，点分治，meet in middle等，枚举也是一个技术活，只有正确的枚举才能解决问题。

  • KMP
  • 前缀和
  • 树上点分治
  • 双指针，二分
  • 并查集

A. Password

 

KMP模板题

唯一需要注意的是KMP求得的是最大前缀后缀长度，而本题需要任意长度的公共前缀后缀，不过根据KMP的思想，递归next数组就可以了。

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
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
const int maxn = 1e6 + 5;
#define ll long long
int nxt[maxn];
void getNextVal(string p) {
	int plen = p.length();
	nxt[0] = -1;
	int k = -1;
	int j = 0;
	while (j < plen) {
		if (k == -1 || p[j] == p[k]) {
			j++;
			k++;
			if (p[j] != p[k]) {
				nxt[j] = k;
			}
			else{
				nxt[j] = nxt[k];
			}
		}
		else { 
			k = nxt[k];
		}
	}
}
int kmp(string s, string p) {
	int i = 0, j = 0;
	getNextVal(p);
	int slen = s.length();
	int plen = p.length();
	while (i < slen&&j < plen) {
		if (j == -1 || s[i] == p[j]) {
			i++;
			j++;
		}
		else {
			j = nxt[j];
		}
	}
	if (j == plen) {
		return i - j;
	}
	else {
		return -1;
	}
}
int main() {
	string s;
	cin >> s;
	getNextVal(s);
	int len = s.length();
	int k = nxt[len];
	while (k != 0) {
		string p = s.substr(0, k);
		string s1 = s.substr(1,len-2);
		if (kmp(s1, p) != -1) {
			cout << p;
			return 0;
		}
		k = nxt[k];
	}
	cout << "Just a legend";
	return 0;
}

 

B. Another Problem on Strings

 

前缀和，记录第0到i位有几个1，由于sum[0]=0，所以当要求的‘1’个数k=0时，需要另外讨论。

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
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int maxn = 1e6 + 5;
#define ll long long
int k;
string s;
int dp[maxn];
ll ans;
int main() {
	cin >> k;
	cin >> s;
	int len = s.length();
	for (int i = 1; i <= s.length(); i++) {
		if (s[i - 1] == '1') {
			dp[i] = dp[i - 1] + 1;
		}
		else dp[i] = dp[i - 1];
	}
	if (k != 0) {
		for (int i = k; i <= dp[len]; i++) {
			ll num1 = upper_bound(dp, dp + len + 1, i) - lower_bound(dp, dp + len + 1, i);
			ll num2 = upper_bound(dp, dp + len + 1, i - k) - lower_bound(dp, dp + len + 1, i - k);
			ans += num1*num2;
		}
		cout << ans;
	}
	else {
		for (int i = 0; i <= dp[len]; i++) {
			ll num = upper_bound(dp , dp + len + 1, i) - lower_bound(dp , dp + len + 1, i)-1;
			ans += (1 + num)*num / 2;
		}
		cout << ans;
	}
	return 0;
}

 

C. Maximum Value

 

数学+枚举，要求a%b最大我们知道当a=kb时，a%b=0，而当a=kb-1时，a%b最大，所以我们需要找到距离b的倍数最近，且小于b的倍数的数。

建立一个数组dp[i]，表示题目给定的数组a[]中，距离i最近，且小于i等于的数，建立方法很简单，先把a[]中数都填入dp中，然后在中间都填上dp[i-1]即可。

接着把a[]中每个数都作为a%b中的b，枚举k，找到距离kb-1最近的数，和最终答案比较，取大的。

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
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 2e5 + 5, maxm = 1e6 + 5;
#define ll long long
int n;
int a[maxn];
int ans;
int dp[maxm];
bool vis[maxm];
int main() {
	cin.sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		dp[a[i]] = a[i];
	}
	sort(a, a + n);
	for (int i = 0; i <= a[n - 1]; i++) {
		dp[i] = max(dp[i], dp[i - 1]);
	}
	for (int i = 0; i < n ; i++) {
		if (!vis[a[i]]) {
			int tp = a[i];
			int b = 2 * a[i];
			while (b < a[n - 1]+1) {
				ans = max(ans, dp[b - 1] % tp);
				b += tp;
			}
			ans = max(ans, a[n - 1] % tp);
			vis[a[i]] = 1;
		}
	}
	cout << ans;
	return 0;
}

 

D. Little Elephant and Interval

 

枚举，找到[l，r]区间中第一位和最后一位相等的数的个数。

solve(x)函数确定[ 0 , x ]区间中满足条件的数个数，之后solve®-solve(l-1)。

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<iostream>
#include<algorithm>
#include<string>
using namespace std;
#define ll long long
const ll maxn = 1e18 + 5;
ll l, r;
ll ans;
int get_dig(ll a) {
	int ans = 1;
	while (a / 10) {
		ans++;
		a /= 10;
	}
	return ans;
}
ll pow(int n) {
	ll ans = 1;
	for (int i = 0; i < n; i++)
		ans *= 10;
	return ans;
}
ll solve(ll x) {
	int n = get_dig(x);
	ll ans = 10;
	ll t = 9;
	if (x < 10) {
		return x+1 ;
	}
	for (int i = 0; i < n - 2;i++) {
		ans += t;
		t *= 10;
	}
	int l = x / pow(n - 1);
	int r = x % 10;
	if (l <= r)ans++;
	x /= 10;
	x -= pow(n - 2);
	return ans + x;
}
int main() {
	cin >> l >> r;
	cout << (solve(r) - solve(l-1));
	return 0;
}

 

G. Ciel the Commander

 

树上点分治

给定一棵树，找到它的重心，重心上填上最高级的officer，再对它的子树递归。

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<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5;
#define ll long long
int n;
vector<int>G[maxn];
void add_edge(int u, int v) {
	G[u].push_back(v);
	G[v].push_back(u);
}
int root;
int Siz;
int mxsz[maxn], sz[maxn], ans[maxn];
bool vis[maxn];
void get_rt(int u,int fa) {
	mxsz[u] = 0;
	sz[u] = 1;
	for (int i = 0; i < G[u].size(); i++) {
		int v = G[u][i];
		if (!vis[v] && v != fa) {
			get_rt(v, u);
			sz[u] += sz[v];
			mxsz[u] = max(mxsz[u], sz[v]);
		}
	}
	mxsz[u] = max(mxsz[u], Siz - sz[u]);
	if (mxsz[u] <= mxsz[root])root = u;
}
void dfs(int rt,int dep) {
	ans[rt] = dep;
	vis[rt] = 1;
	for (int i = 0; i < G[rt].size(); i++) {
		int v = G[rt][i];
		if (!vis[v]) {
			root = 0;
			Siz = sz[v];
			get_rt(v, rt);
			dfs(root, dep + 1);
		}
	}
}
int main() {
	cin.sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		add_edge(u, v);
	}
	mxsz[0] = n;
	Siz = n;
	get_rt(1, 0);
	dfs(root, 0);
	for (int i = 1; i <= n; i++) {
		char c = 'A' + ans[i];
		cout << c << ' ';
	}
	return 0;
}

 

H. Prime Gift

 

双指针，meet in middle，二分

给定一个素数集，要找到只有集合中素数相乘得到的数中第k大。

经典双指针题，相乘得到的数个数是非常大的，如果挨个找过来，不仅时间不够，也肯定存不下，所以我们分两个数组存。

先把给定的素数集分成两个集合，这里怎么分又是一个问题，如果只是平分的话，到时候查找还是n2n^2的复杂度，所以我们设置第一个集合大小不超过5，多的都放到第二个集合去。

之后两个集合各自搞出他们中元素相乘得到的数，这里可以用dfs来做。

完成之后这还只是各自集合内的元素乘，那如果集合间乘怎么办呢？

这就关系到确定一个数在所有素数乘得的集合中的排位，由于我们并没有找出完整的集合，所以不能直接找，要用到了双指针，一个从集合A的后面找，另一个从集合B的前面找，如果g1[i] * g2[j]<x，则x的排位+1，否则向g1[i] 减小的方向移动 i，继续找。

还有一个细节，当移动了指针 i 后，j 并不需要从0开始，因为g1[i]减小了，所以 g1[i] g2[j] 也减小了，而我们更新i时，g1[i] g2[j] 是小于x的，那么 0 到 j-1 的g2[j] g1[i]肯定是小于 x 的，就不用看了，j 继续往大了找就好了。

能确定 x 的排位之后，还需要二分可行集，找到正确的 x。

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
#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long
const ll INF = 1e18;
ll n, k;
int a[17], b[17];
vector<ll>g1, g2;
int cnt1, cnt2;
void dfs1(int dep,ll ans) {
	if (dep >= cnt1) {
		g1.push_back(ans);
		return;
	}
	if (a[dep] <= INF / ans) {
		dfs1(dep, ans*a[dep]);
	}
	dfs1(dep + 1, ans);
}
void dfs2(int dep, ll ans) {
	if (dep >= cnt2) {
		g2.push_back(ans);
		return;
	}
	if (b[dep] <= INF / ans) {
		dfs2(dep, ans*b[dep]);
	}
	dfs2(dep + 1, ans);
}
ll pos(ll x) {
	ll res = 0;
	int i = g1.size() - 1, j = 0;
	while (i >= 0) {
		while (j < g2.size() && g2[j] <= x / g1[i])j++;
		res += j;
		i--;
	}
	return res;
}
int main() {
	cin.sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		if (cnt1 < 5) {
			cin >> a[cnt1++];
		}
		else cin >> b[cnt2++];
	}
	cin >> k;
	dfs1(0,1);
	dfs2(0,1);
	sort(g1.begin(), g1.end());
	sort(g2.begin(), g2.end());
	ll st = 1, ed = INF;
	while (st < ed) {
		ll mid = (st + ed) / 2;
		if (pos(mid) >= k) {
			ed = mid;
		}
		else st = mid + 1;
	}
	cout << st;
	return 0;
}

 

I. Vessels

 

并查集

刚开始想用区间更新的懒标记，等到询问的时候再更新，但还是TLE了。

后来查了一下，要用并查集，当当前盆p满了，就把它和下面的盆p+1合并。

注意，由于一定是往下合并，所以不能用rank数组优化。

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<string>
using namespace std;
#define ll long long
const int maxn = 2e5 + 5;
int n, m;
int par[maxn];
int rak[maxn];
ll a[maxn];
ll b[maxn];
void init(int n) {
	for (int i = 1; i <= n; i++) {
		par[i] = i;
	}
}
int find(int x) {
	if (par[x] == x) {
		return x;
	}
	else {
		return par[x] = find(par[x]);
	}
}
void unit(int x, int y) {
	y = find(y);
	par[x] = find(y);
}
bool same(int x, int y) {
	return find(x) == find(y);
}
int main() {
	cin.sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	init(n);
	cin >> m;
	for (int i = 0; i < m; i++) {
		int instr;
		cin >> instr;
		if (instr == 1) {
			int p, x;
			cin >> p >> x;
			while (x > 0) {
				int pf = find(p);
				if (x < a[pf] - b[pf]) {
					b[pf] += x;
					x = 0;
				}
				else {
					x -= (a[pf] - b[pf]);
					b[pf] = a[pf];
					if (same(n, pf)) {
						x = 0;
					}
					else {
						unit(pf, pf + 1);
						pf = find(pf + 1);
					}
				}
			}
		}
		else {
			int k;
			cin >> k;
			cout << b[k] << endl;
		}
	}
	return 0;
}