Post 59

Veröffentlicht am | Edited on

又来了场原题大战。

除掉输出个样例的有6个比我高的。。加上魏老师是7个qwq。除掉高二也是5个。

果然是联赛退役.jpg

题目还行，有点意思。

是2019 JAN铂金组题目

1、redistricting

奶牛们的特大城市，牛都，要进行重新分区了！——这总是一个在居住在这里的两大主要种族（荷斯坦牛和更赛牛）之间富有争议的政治事件，因为两大种族都想要在牛都政府中保持足够的影响力。

牛都的大都市圈由一列N 块牧草地（1≤N≤3⋅105 ）组成，每块里有一头奶牛，均为荷斯坦牛和更赛牛之一。

牛都政府想要将大都市圈划分为若干个连续的区，使得每个区至多包含K 块牧草地（1≤K≤N ），并且每块牧草地恰好属于一个区。由于政府当前由荷斯坦牛控制，她们想要找到一种分区方式能够最小化更赛牛较多或者均势的区的数量（如果更赛牛的数量与荷斯坦牛的数量相等那么这个区就是均势的）。

有一个关心政治的更赛牛团体想要知道政府的分区计划可能会对她们造成多少损害。帮助她们求出最坏情况，也就是更赛牛较多或是均势的区的最小可能的数量。

输入格式（文件名：redistricting.in）：

输入的第一行包含两个空格分隔的整数N 和K 。第二行包含一个长度为N 的字符串。每个字符均为’H’或者’G’，表示荷斯坦牛（Holstein）或者更赛牛（Guernsey）。

输出格式（文件名：redistricting.out）：

输出更赛牛较多的或者均势的分区的最小可能数量。

输入样例：

1
2
7 2
HGHGGHG

输出样例：

1
3

题解

这道题的DP不难想吧。

$f{i} = min({f{i-j}+[s{i}-s{i-j} \leq 0]})$

时间复杂度$O(nk)​$

然后能拿个几十分。

然后我输出了一下转移点感觉挺接近，就写了个周围转移的DP。

然后出乎我的意料只对了一个点。。。

然后CST告诉我这个DP可以用Treap来优化。。我一想好像挺对的qwq

我们把二元组$(s[i],f[i])​$插进去。

我们如何查询一个连续区间的合适的这个值呢？（就是和DP转移一样的那个值）

首先保证在区间外的要及时踢出，均摊分析可知每个元素最多被踢出一次，时间复杂度为$O(nlogn)$

然后Treap需要维护一个子树$k$的$f_k$的最小值。

查询的时候如果当前节点的$s_k$小于$s_i$，我们就更新答案，和右子树最小值取最小，递归左子树。

如果当前节点的$s_k$大于等于$s_i$，我们就更新答案，和当前点以及左子树的最小值取最小。

然后插入和查询复杂度都是严格的$O(logn)$

所以复杂度是$O(nlogn)​$

所以我从来没写过数据结构优化DP

由于十年没写Treap，结果删除写挂了，浪费了巨多时间调这玩意。

错误警示：

1
2
3
4
5
6
7
8
if(val[x] == v && d[x] == dt)
{
	if(!lc || !rc) clean(x) , x = lc + rc;
	else if(p[lc] < p[rc]) rot(x , 0) , del(x , v , dt);
	else rot(x , 1) , del(x , v , dt);
	pushup(x);
	return;
}

在旋转过后，我们想删除原来的元素应该是在相应的左右位置，所以不是继续递归删除$x$节点！！！

正确：

1
2
3
4
5
6
7
8
if(val[x] == v && d[x] == dt)
{
	if(!lc || !rc) clean(x) , x = lc + rc;
	else if(p[lc] < p[rc]) rot(x , 0) , del(rc , v , dt);
	else rot(x , 1) , del(lc , v , dt);
	pushup(x);
	return;
}

完整AC代码：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <iostream>
#define maxn 300005
#define random(a,b) (a) + rand() % ((b) - (a) + 1)
int f[maxn] , s[maxn] , n , k , p[maxn];

inline char gc()
{
	char ch = getchar();
	if(ch != 'H' && ch != 'G') ch = getchar();
	return ch;
}

struct Treap
{
#define lc ch[0][x]
#define rc ch[1][x]
	int ch[2][maxn] , tot , mn[maxn] , val[maxn] , d[maxn] , p[maxn] , rt;
	Treap(){
		srand(14129523);
		std::memset(mn,0x5f,sizeof(mn));
		std::memset(d,0x5f,sizeof(d));
	}
	inline void pushup(int x){
		mn[x] = std::min(std::min(d[x] , mn[lc]) , mn[rc]);
	}
	inline void newnode(int& x , int v , int dt)
	{
		x = ++tot;
		val[x] = v;
		d[x] = mn[x] = dt;
		p[x] = rand() % 998244353;
	}
	inline void clean(int x){
		p[x] = 0;
		d[x] = val[x] = 0x7ffffff;
	}
	inline void rot(int& x , int tp)
	{
		int s = ch[tp][x];
		ch[tp][x] = ch[tp^1][s];
		ch[tp^1][s] = x;
		pushup(x);
		x = s;
	}	
	void ins(int& x , int v,  int dt)
	{
		if(!x){
			newnode(x , v , dt);
			return ;
		}
		if(v < val[x]) {
			ins(lc , v , dt);
			if(p[lc] < p[x]) rot(x , 0);
		}
		else if(v == val[x] && dt < d[x]){
			ins(lc , v , dt);
			if(p[lc] < p[x]) rot(x , 0);
		}
		else{
	   		ins(rc , v , dt);
			if(p[rc] < p[x]) rot(x , 1);
		}	
		pushup(x);
	}
	void del(int& x , int v, int dt)
	{
		if(val[x] == v && d[x] == dt)
		{
			if(!lc || !rc) clean(x) , x = lc + rc;
			else if(p[lc] < p[rc]) rot(x , 0) , del(rc , v , dt);
			else rot(x , 1) , del(lc , v , dt);
			pushup(x);
			return;
		}
		if(v < val[x]) del(lc , v , dt);
		else if(val[x] == v && dt < d[x]) del(lc , v , dt);
		else del(rc , v , dt);
		pushup(x);
	}

	inline int find(int x , int v)
	{
		int ans = 0x7fffffff;
		while(x)
		{
			if(val[x] >= v) ans = std::min(ans , d[x] + 1) , ans = std::min(ans , mn[rc] + 1) , x = lc;
			else ans = std::min(ans , d[x]) , ans = std::min(ans , mn[lc]) , x = rc;
		}
		return ans;
	}
}t;

int main()
{
//	freopen("3.in","r",stdin);
//	freopen("redistricting.out" , "w" , stdout);
	scanf("%d%d",&n,&k);
	for(int i = 1 ; i <= n ; ++i)
		s[i] = s[i-1] + (gc() == 'H' ? 1 : -1);
	std::memset(f,0x3f,sizeof(f));
	f[0] = 0;
	t.ins(t.rt , 0 , 0);
	for(int i = 1 ; i <= n ; ++i)
	{
		if(i > k)	{
//			puts("DEBUG!!!");
//			printf("DELETE! %d %d\n",s[i-k-1] , f[i-k-1]);
//			puts("CTZ TXDY");
			t.del(t.rt , s[i-k-1] , f[i-k-1]);
//			puts("FINISH!!!");
//			puts("") , puts("");
		}
//		printf("[1]%d\n",t.tot);
		f[i] = t.find(t.rt , s[i]);
		t.ins(t.rt , s[i] , f[i]);
//		printf("[3]%d\n",t.tot);
//		if(t.tot == 59){
//			puts("OOKKKKKKKKOKOKOK");
//		}
//		puts("--------------------------OK------------------------------");
	}
//	for(int i = 1 ; i <= n ; ++i)
//		printf("%d " ,f[i]);
	printf("%d\n",f[n]);
}

HDOJ 4630 - No Pain No Game

描述

给定一个 $1\sim n(n\le 50000)$的排列 $a_1, a_2, \ldots, a_n$。现在有 $q(q\le 50000)$次询问，每次询问区间 $[l, r]$内任选两个不同的数得到的 $\gcd$ 的最大值。

题解

翻了翻Sengxian的blog看到了这道题。

先口胡一个我的做法，主要是基于前$n$个数的约数个数很少（是$O(nlogn)$）

所以我们预处理所有数的约数，存进vector，时间复杂度$O(n\sqrt{n})$

然后对端点分块排序（如果每次移动端点是$O(1)$的复杂度那最后是$O(n\sqrt{n})$的复杂度）

但是每次把一个数的约数全都丢进一个数据结构然后查询出现两次以上的最大值并没法$O(1)$搞定….

这个东西应该只能用分块来做。

维护每个块的元素出现两次以上的最大值，每次删除一个数所有约数（最大个数$O(\sqrt{n})$都需要期望$O(\sqrt{n}logn)$实际最坏$O(\sqrt{n}\sqrt{n})=O(n)​$的时间。。

加入和维护答案没有任何问题，是$O(\sqrt{n})$的。

所以这不是比$O(n^2)$还慢吗，还不如直接暴力把区间的数扔桶里扫描。。傻了傻了。。。。

—————以上算法暴毙—————

然后看了下Sengxian的题解，发现这道题可能以我的水平确实想不出来，是个很巧妙的构造。

假设有这么一个序列$s$,询问$[l,r]$的答案就是$s[l,r]$的最大值（不要问我这种东西怎么可能想的出来。。。）

然后我们可以从右往左对每个数枚举约数，一个显而易见的事实，答案一定来自一个查询区间内数对的约数，考虑将每个这样的数对都计算贡献，不过暴力计算贡献是$O(n^2log^2n)$的。

对于每个约数$d$，我们找到它最靠近的右边的那个数（前驱可以直接由链表或者说一个数组来处理），对于这段区间以及包含这段区间的区间，答案肯定是不小于$d$的。因此对前驱位置的右边的$s$序列的每个元素与约数$d$取最大值。

然后处理左端点在当前位置$i$的询问， 至于为什么必须在处理完第$i$个数就立刻处理询问，因为后面的数的约数会对答案造成影响，这就是离线优化查询的巧妙应用（巧妙到想不出来）。

让我来一波胡乱总结：本题运用完全想不到的构造，凭着天马行空的创造力以优秀的复杂度构建了一个可以通过某些方式快速在离线优化查询顺序的情况下获得答案。最核心的一点是利用贪心的思想，每次只考虑相邻两个相同约数对某些询问的贡献，在保证正确性的情况下将枚举时间复杂度优化到了$O(nlogn)$，之所以只考虑相邻，是因为一个显而易见的事实：包含一个非相邻大的同约数对的区间，必然包含相邻的同约数对的区间，但这是贪心正确性的基础。这样最后总时间复杂度是$O(nlog^2n)$.正确性由于答案一定是某两个数的某个约数（由题可知），考虑到这种方法能够不重不漏对当前后缀所有约数在合适的位置都做了应有的贡献，使得对于每一对相邻约数的区间，包含其的查询区间均能得到贡献。

再来一个小问题。

Q:能不能从前往后？感觉没有区别！

A:可以！使用线段树即可（由于树状数组最大值不可减，因此不再适用，从后往前之所以可以是因为前面的假想序列$s$都是0….）

Q:离线排序的意义究竟是什么

A:只有一个一个按顺序加（从前往后和从后往前都可以的），才能利用上述算法，否则无规律的查询要求删除某些贡献，这对于求最大值的简单数据结构是很难胜任的。（不过貌似平衡树可以，但是复杂度还是没法保证的样子，操作次数不确定的）。

评价：很好的题，也有难度。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>
#define maxn 50005
int a[maxn] , c[maxn] , n , qn , pos[maxn] , ans[maxn];
std::vector<int> g[maxn];
struct Node{
	int r , num;
};
std::vector<Node> q[maxn];

namespace bit
{
	int b[maxn];
	inline void upd(int pos , int v)
	{
		for( ; pos <= n ; pos += pos & -pos)
			b[pos] = std::max(b[pos] , v);
	}
	inline int q(int pos)
	{
		int ans = 0;
		for( ; pos ; pos -= pos & -pos)
			ans = std::max(ans , b[pos]);
		return ans;
	}
}

inline void solve()
{
	std::memset(pos,-1,sizeof(pos));
	for(int i = n ; i >= 1 ; --i)
	{
		for(int j = 0 ; j < (int)g[a[i]].size() ; ++j)
		{
			if(pos[g[a[i]][j]] != -1)
				bit::upd(pos[g[a[i]][j]] , g[a[i]][j]);
			pos[g[a[i]][j]] = i;
		}
		for(int j = 0 ; j < (int)q[i].size() ; ++j)
			ans[q[i][j].num] = bit::q(q[i][j].r);
		
	}
}

int main()
{
	for(int i = 1 ; i < maxn ; ++i)
		for(int j = i ; j < maxn ; j += i)
			g[j].push_back(i);
	int t ;
	scanf("%d",&t);
	while(~--t)
	{
		scanf("%d",&n);
		for(int i = 1 ; i <= n ; ++i)
			scanf("%d",&a[i]);
		std::memset(bit::b , 0 , sizeof(bit::b));
		scanf("%d",&qn);
		for(int i = 1 ; i <= n ; ++i)
			q[i].clear();
		for(int i = 1 ; i <= qn ; ++i)
		{
			int l , r;
			scanf("%d%d",&l,&r);
			q[l].push_back((Node){r , i});
		}
		solve();
		for(int i = 1 ; i <= qn ; ++i)
			printf("%d\n",ans[i]);
	}
}