T20201113

Posted on Edited on In Word count in article: 1.6k Reading time ≈ 6 mins.
大东辰的测试

T1

显然，两边的差距要越大最后的答案才能最优。

这个就不用证明了。

然后就是二分答案就可以了，然后我的二分是挂了的，所以最后要对答案进行一个微调，然后就可以过了。

Code

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
64
65
66
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
ll ans, n, k;
inline ll read()
{
	ll x(0);
	char o(getchar());
	while (o < '0' || o > '9') o = getchar();
	for (; o >= '0' && o <= '9'; o = getchar())
		x = (x << 1) + (x << 3) + (o ^ 48);
	return x;
}

inline ll C(ll p)
{
	if (p == 1) return 0;
	return 1ll * p * (p - 1) / 2;
}

inline bool check(ll p)
{
	if (C(p) > k) return 0;
	if (n == p) return C(p) == k;
	return 1ll * C(p) + 1ll * p * (n - p) >= k;
}

int main()
{
	freopen ("game.in", "r", stdin);
	freopen ("game.out", "w", stdout);
	n = read(), k = read();
	if (k == 0 || C(n) < k) return puts("-1") & 0;
	
	if (k < n) ans = C(n - 1);
	
	ll l(1), r(n), pr(n + 1), pl(n);
	while (l <= r) {
		ll mid = (l + r) >> 1;
		if (C(mid) <= k) pr = mid, l = mid + 1;
		else r = mid - 1;
	}
	
	l = 1, r = pr;
	while (l <= r) {
		ll mid = (l + r) >> 1;
		if (check(mid)) pr = mid, l = mid + 1;
		else {
			if (mid <= (1 + n) / 2) l = mid + 1;
			else r = mid - 1;
		}
	}
	
	l = 2, r = pr;
	while (l <= r) {
		ll mid = (l + r) >> 1;
		if (check(mid)) pl = mid, r = mid - 1;
		else l = mid + 1;
	}
	
	while (check(pr + 1)) pr++;
	while (check(pl - 1)) pl--;
	printf ("%lld\n", max(C(pl) + C(n - pl), C(pr) + C(n - pr)));
}

T2

特别妙的一题。

依次考虑每个字符串的所属，假设当前考虑到第 i 个字符串，那么前 i - 1 个字符已经被分为了两个字序列，显然 a[i - 1] 是某个子序列的末尾，或者说每次考虑的最后一个字符串必然为一个子序列的末尾，假设另一个序列末尾为 a[j] ，若 a[i] 跟在 a[i - 1] 后面，那么 a[j] 依旧是另一个子序列的末尾，若 a[i] 跟在 a[i-1] 后面，那么 a[i - 1] 变成另一个序列的末尾，故不需要考虑另一个序列具体是哪一个字符串， 只需要知道另一个序列末尾的状态即可。

以 f[i][j][k] 表示前 \(i\) 个字符串分好后，不以 a[i] 为结尾的字序列后 \(j\) 位状态位 \(k\) 时 \(S\) 的最小值，那么根据 a[i] 的所属有转移：

  1. 若 a[i] 跟在 a[i - 1] 后面，那么另一个序列后 \(j\) 位的状态都不会改变，此时对 \(S\) 值的影响位 a[i - 1] 接上 a[i] 所增长的串长，也即 \(f[i][j][k]+=len-deal(a_{i-1},a_i)\)，其中 \(len\) 为每个字符串的串长，\(deal(x,y)\) 表示求出 \(x\) 的后缀与 \(y\) 的前缀的最长公共部分。

  2. 若 a[i] 跟在另一个序列后面，那么此时的所谓的另一个序列变成以 a[i - 1] 结尾，那么其末尾 \(j\) 位状态即为 a[i - 1] 后 \(j\) 位的状态，记为 \(suf(a_{i-1},j)\)，而此时对 \(S\) 值的影响是将 a[i] 姐在了另一个字序列上，枚举另一个字序列末尾与 a[i] 的公共部分的长度 \(k\) 有转移： \[ f[i][j][suf(a_{i-1},j)]=\min_{k}(f[i-1[k][pre(a_i,k)]]+len-k) \]

其中 \(pre(a_i,j)\) 表示 a[i] 的前 \(j\) 位状态。

此时转移和复杂度为 \(O(n\cdot len\cdot 2^{len})\)，但注意到，记 \(temp=len-deal(a_{i-1},a_i)\)，则第二种转移等价于： \[ f[i][j][suf(a_{i-1},j)]=\min_k(f[i-1][k][pre(a_i,k)]+len-k-temp)+temp \] 如此每次从 \(f[i-1]\) 转移到 \(f[i]\) 都会加上 \(temp\) 这一定值，若在转移中不考虑该定制，而是累加该值在转移结束后直接加到答案中，那么就不需要进行第一种转移，此时时间复杂度为 \(O(n\cdot len)\)。

Code

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 <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 5;
int n, len, val[maxn], f[21][1 << 20];
char s[21];

inline int pre(int S, int i)
{
	return S >> (len - i);
}

inline int suf(int S, int i)
{
	return S & ((1 << i) - 1);
}

inline int deal(int S, int T)
{
	for (int i = len; i; --i) 
		if (suf(S, i) == pre(T, i)) return i;
	return 0;
}

inline int read()
{
	int x(0);
	char o(getchar());
	while (o < '0' || o > '9') o = getchar();
	for (; o >= '0' && o <= '9'; o = getchar())
		x = (x << 1) + (x << 3) + (o ^ 48);
	return x;
}

int main()
{
	freopen ("puzzle.in", "r", stdin);
	freopen ("puzzle.out", "w", stdout);
	n = read();
	for (int i = 1; i <= n; ++i) {
		scanf ("%s", s);
		len = strlen(s);
		for (int j(0); j < len; ++j)
			val[i] = (val[i] << 1) + (s[j] ^ 48);
	}

	int res(0);
	memset (f, 0x3f, sizeof f);
	f[0][0] = len;
	for (int i = 2; i <= n; ++i) {
		int l = len - deal(val[i - 1], val[i]);
		res += l;
		int mn = inf;
		for (int j = 0; j <= len; ++j) mn = min(mn, f[j][pre(val[i], j)] + len - j - l);
		for (int j = 0; j <= len; ++j) f[j][suf(val[i - 1], j)] = min(f[j][suf(val[i - 1], j)], mn);
	}
	printf ("%d\n", f[0][0] + res);
}

T3

就是最后的序列显然是递增的，所以可以二分答案。

现在问题就可以转化为：满足区间中位数不超过 \(x\) 的区间数量，就可以二分 \(x\)。

定义 \(p\) 数组，满足 p[i] = p[i - 1] + [a[i] > x]，即前 \(i\) 个数中有多少个数超过了 \(x\)。

那么如果一个序列满足条件，就可以转化为满足这个条件的式子：r - l > ((p[r] - p[l]) << 1)。

注意，这里是严格大于。

这个式子的意思就是：这个区间中，大于 \(x\) 的树不会到达一半。

然后在稍微转化一下就是：(r - (p[r] << 1)) > (l - (p[l] << 1))。

然后就可以树状数组，把这些东西插进树状数组，然后查血有多少个合法的左端点，就可以了。

Code

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 5;
const int inf = 0x7fffffff;

ll n, m, f, l(inf), r;
ll a[maxn], p[maxn];
ll t[maxn << 2];

inline int read()
{
    int x(0);
	char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    for (; c >= '0' && c <= '9'; c = getchar()) 
		x = (x << 1) + (x << 3) + (c ^ 48);
    return x;
}

inline int lowbit(int x)
{
	return x & (-x);
}

inline void update(int x, int v)
{
	while (x <= n * 4) {
		t[x] += v;
		x += lowbit(x);
	}
}

inline ll query(int x)
{
	ll res(0);
	while (x) {
		res += t[x];
		x -= lowbit(x);
	}
	return res; 
}

bool check(int x)
{
	ll res(0);
	memset(t, 0, sizeof(t));
	
	for(int i = 1; i <= n; ++i)
		p[i] = p[i - 1] + 2 * (a[i] > x);
		
	for(int i = 1; i <= n; ++i) {
		update(i - p[i] + 2 * n, 1);
		res += query(i - p[i] - 1 + 2 * n);
	}
	return res >= n * (n + 1) / 4;
}

int main()
{
	freopen("median.in", "r", stdin);
	freopen("median.out", "w", stdout);
	n = read();
	for(int i = 1; i <= n; ++i) {
		a[i] = read();
		l = min(l, a[i]);
		r = max(r, a[i]); 
	}
	int mid, ans;
	
	while(l <= r) {
		mid = (l + r) >> 1;
		if(check(mid)) r = mid - 1, ans = mid;
		else l = mid + 1;
	}
	
	printf("%d\n", ans);
}