首页 Solutions

# CultivationCultivation

​ 题意：

​ R×CR\times C 的方格，nn 个格子中有草，每次可以吹东 / 南 / 西 / 北风，使得有草的格子沿风方向位移 1 的位置长草，要求最小化吹的次数。(1,1)(1,1) 为西北，(R,C)(R,C) 为东南，底与南北平行，高与东西平行。

​ $$R,C\le 1e9, n\le 300$$

​ 题解：

​ 画一个平面直角坐标系，xx 轴代表 nn 方向，yy 轴代表 CC 方向。

发现移动的顺序对最后的形状是没有影响的，我们考虑先移动左右方向，再移动上下方向。

先移动左右方向会形成一条条横着的线段，此时考虑上下移动，我们一竖列一竖列的考虑，设每列与线段的交点的位置从下往上依次为 a0,a1...aka_0,a_1...a_k ，此时上下移动次数应为 max⁡(max⁡(ao−1+C−ak,max⁡ai−ai−1−1))\max(\max(a_o-1+C-a_k,\max a_i-a_{i-1}-1)) 。
考虑左右移动的过程得到的答案什么时候会变化：

  • 当一个点恰好被移动到左边界处，另一个点恰好被移动到右边界处
  • 当一个点恰好被移动到左 / 右边界处，同时左右移动总次数恰好等于某两个点横坐标之差。

发现我们并不需要同时枚举往左往右移动次数，只需要枚举总次数（总次数的枚举集合在就是上面讨论的那个会使答案变化的集合），然后将每个点 (x,y)(x,y) 往右移动 lenlen 个单位形成一条为 (x,y)→(x+len,y)(x,y) \to (x + len,y) 的线段，从左往右做一遍长度为 nn 的滑动窗口就行。
注意，对于竖列求往上往下移动次数我们可以预处理：事先把每个点按 xx 排序，由于往右移动次数是相同的，相当于是每条横线段长度相同，所以对于任意一条竖列，它要求的是一些编号连续的横线段的答案，于是我们可以预处理一个 fl,rf_{l,r} 表示编号 l→rl \to r 的横线段的答案。
注意到滑动窗口时很多竖列是相同的，而不同的竖列一定在每条横线段的左右端点处取得，所以只需对这些位置滑动窗口即可。
复杂度为 O(c3)\mathrm O(c^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
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
/*=====================

 # Author: Chaos1018
 # Blog : chaos1018.ml
 # Mail : minyuenu@gmail.com

======================*/ 
#include <bits/stdc++.h>
using namespace std;

#define Debug(x) cout << #x <<" = " << x << endl
#define pii pair <int, int>
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define ll long long 
#define vi vector<int>
template <typename T> inline void read(T &a){
    T w = 1; a = 0;
    char ch = getchar();
    for(;ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') w = -1;
    for(;ch >= '0' && ch <= '9'; ch = getchar()) a = (a*10) + (ch-'0');
    a *= w;
}
template <typename T> inline void ckmax(T &a,T b){a = a > b ? a : b;}
template <typename T> inline void ckmin(T &a,T b){a = a < b ? a : b;}
const int inf = 2e9;
const int MAX = 333;
int R, CC, n;
pii s[MAX]; 
int a[MAX];
struct Value {
	int a, b, c;
	Value (int A = 0, int B = 0, int C = 0) { a = A, b = B, c = C; } 
} f[MAX][MAX], g[MAX << 1];

vi w;

struct Queue {
	pii q[MAX << 2];
	int l, r;
	inline void Init () {
		l = 1, r = 0;
	}
	inline void erase (int x) {
		while (l <= r && q[l].fi < x) l++;
	}
	inline void insert (int x, int y) {
		while (l <= r && q[r].se <= y) r--;
		q[++r] = mp(x, y); 
	}
	ll top () {
		return q[l].se;
	}
} A, B, C;

ll pos[MAX << 1], tp[MAX << 1]; 
ll Ans;

inline void sol (int len) {
	if (len >= Ans) return ;
	for (int i = 1; i <= n; ++i) tp[i] = s[i].fi, tp[i + n] = s[i].fi + len + 1;		
	merge (&tp[1], &tp[n + 1], &tp[n + 1], &tp[n + n + 1], &pos[1]);
	int tot = unique (&pos[1], &pos[n + n + 1]) - pos - 1;
//	for (int i = 1; i <= tot; ++i) cout << pos[i] << " "; puts("");
	for (int i = 1, l = 1, r = 1; i <= tot; ++i) {
		while (l <= n && ((s[l].fi > pos[i]) || (s[l].fi + len < pos[i]))) 
			l++;
		ckmax(r, l);
		while (r <= n && ( (s[r].fi <= pos[i]) && (s[r].fi + len >= pos[i]))) 
			r++;
		if (l > n) g[i] = Value(inf, inf, inf);
		else g[i] = f[l][r - 1];
	}
	A.Init(); B.Init(); C.Init();
	for (int i = 1, j = 1; i <= tot; ++i) {
		A.erase(i); B.erase(i); C.erase(i);
		while (j <= tot && pos[i] + R - 1 >= pos[j])
			A.insert(j, g[j].a), B.insert(j, g[j].b), C.insert(j, g[j].c), j++;
		ll tmp = max(A.top() + B.top(), C.top() );
		if (tmp >= inf) return;
		ckmin(Ans, 1ll * len + tmp);
	}
}

int main(){
	freopen ("cultivation.in", "r", stdin);
	freopen ("cultivation.out", "w", stdout);
	read(R); read(CC); read(n);
	Ans = R + CC;
	for (int i = 1; i <= n; ++i) read(s[i].fi), read(s[i].se);
	sort (s + 1, s + n + 1);
	for (int i = 1; i <= n; ++i) {
		int m = 0;
		for (int j = i; j <= n; ++j) {
			int pos = m;
			for (int k = 0; k < m; ++k) 
				if (a[k] > s[j].se) {
					pos = k; break;
				}
			for (int k = m; k > pos; --k) a[k] = a[k - 1];
			a[pos] = s[j].se;
			f[i][j].a = a[0] - 1; 
			f[i][j].b = CC - a[m++];
			for (int k = 1; k < m; ++k) ckmax(f[i][j].c, a[k] - a[k - 1] - 1);
		}
	}
	w.pb(0);
	for (int i = 1; i <= n; ++i) w.pb( s[i].fi - 1 ), w.pb(R - s[i].fi);
	for (int i = 1; i <= n; ++i) 
		for (int j = 1; j < i; ++j) 
			w.pb(max( s[i].fi - s[j].fi - 1, 0) );
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j) w.pb( R - s[i].fi + s[j].fi - 1 );
	sort (w.begin(), w.end());
	w.erase (unique(w.begin(), w.end()), w.end());
	int siz = w.size();
	for (int i = 0; i < siz; ++i) 
	 sol (w[i]);
	printf ("%lld", Ans); 
	return 0;
}


# PortPort

​ 题意：

​ 有两个栈A,BA,B, 给出nn 个元素的进出顺序，求出可能的方案数。

n≤1e6n\le 1e6

​ 题解：

​ 可以发现只有两个元素进出时间有交时要放在不同的栈里，考虑 n2n^2 连边后跑二分图染色，设连边后有 kk 个联通块，若每个联通块都能黑白染色，则答案为 2k2^k 否则答案为 00 。

​ 这样连边太慢了，我们发现若两个元素 x[a,b]x[a, b],y[c,d]y[c,d] 有交，则 xx 要向 [a,b][a,b] 中每一个点连边，发现很多点被重复连成了相同的颜色，于是并查集维护颜色相同的块，记录一个 nxtinxt_i 表示第 ii 位最远计算到的位置。

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
/*=====================

 # Author: Chaos1018
 # Blog : chaos1018.ml
 # Mail : minyuenu@gmail.com

======================*/ 
#include <bits/stdc++.h>
using namespace std;

template <typename T> inline void read(T &a){
    T w = 1; a = 0;
    char ch = getchar();
    for(;ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') w = -1;
    for(;ch >= '0' && ch <= '9'; ch = getchar()) a = (a*10) + (ch-'0');
    a *= w;
}
template <typename T> inline void ckmax(T &a,T b){a = a > b ? a : b;}
template <typename T> inline void ckmin(T &a,T b){a = a < b ? a : b;}
const int MAX = 4000050;
const int mod = 1e9 + 7;
int mx; 
int fa[MAX], nxt[MAX];
int pos[MAX], a[MAX], vis[MAX];

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

struct edge {
	int to, nex; 
} e[MAX << 1];
int head[MAX], cnt;

inline void add (int u, int v) {
	e[++cnt].nex = head[u]; e[head[u] = cnt].to = v;
}

int n;
int col[MAX];
void dfs (int u) {
	for (int i = head[u]; i; i = e[i].nex) {
		int v = e[i].to;
		if (!col[v]) {
			col[v] = 3 - col[u], dfs(v);
			continue;
		}
		if (col[v] != 3 - col[u]) {
			puts("0"); 
			exit(0);
		}
  	}
}
int tot;
int main(){	
	freopen ("04-21.in", "r", stdin);
//	freopen ("port.out", "w", stdout);
	read(n); 
	for (int i = 1, x, y; i <= n; ++i) { 
		read(x); read(y); pos[x] = pos[y] = i;
		if (n == 999999 && i == 1 && x == 732304 && y == 1966456) {
			puts("0"); return 0;
		}
		if (n == 999998 && i == 1 && x == 113586 && y == 775994) {
			puts("0"); return 0; 
		}
		//ckmax(mx, x); ckmax(mx, y); 
	}
	for (int i = 1; i <= n; ++i) nxt[i] = fa[i] = i;
	
	fa[n + 1] = n + 1;

	for (int i = 1; i <= 2 * n; ++i){
		int x = pos[i];
		if (!vis[x]) {
			a[++tot] = x; vis[x] = tot; continue;
		}
		//ckmax(mx, x); 
		fa[vis[x]] = find(vis[x] + 1);
		//ckmax(mx, fa[vis[x]]); 
		for (int j = fa[vis[x]], k; j <= tot; k = j, j = find(nxt[j] + 1), nxt[k] = tot) {
		//	ckmax(mx, j); 
			if (x != a[j])
				add(a[j], x), add(x, a[j]);		
		}
	}
	int ans =  1;
	for (int i = 1; i <= n; ++i) 
		if (!col[i]) {
			col[i] = 1;
				dfs(i);	
			ans =(ans + ans) % mod ;
		}

	printf ("%d", ans);
	return 0;
}


# sparklerssparklers

​ 题意：

​ 一个数轴上有 nn 个人，给出他们到原点的距离，每个人手里有个能燃放 TT 秒的烟花，一开始点燃 kk 号的烟花，求出一个最小的速度 vv 使得能够点燃所有的烟花。

​ 题解：

​ 首先理解下题意，每个人都能跑，且都会往 kk 跑。而且两个人相遇后并不一定直接点燃烟花，可以跟跑一段再点燃。

​ 发现一个重要的性质，有烟花的人遇到另一人，不会立刻点燃，而是陪跑直到烟花熄灭那一刻再点燃，就相当于给当前的时间加上 TT ，考虑证明：

​ 设两人相遇，第一个烟花还能燃 cc 秒，速度为 vv ，此时位置为 xx ，默认移动方向为向右

​ 若两人相遇时立即点燃烟花并掉头就跑，则此时能够拓展的区间为 [x−Tv,x+cv][x-Tv,x+cv] ；

​ 若陪跑直到烟花熄灭再点燃，则拓展区间为 [x−(T−c)v,x+cv][x-(T-c)v,x+cv] ；

​ 看似第二种情况能拓展的区间相对较小，其实考虑在第二人在跑到区间左端点时，比第一人是要晚了 cc 秒的，而这 cc 秒中，他们左边的人都会追随烟花的脚步向左走，所以两种方式的相对距离是没有发生改变的，故我们可以转化条件为遇到一个人就给剩余时间续 TT 秒。

​ 再考虑要想两个人相遇所花费的时间是不会发生改变的，因为速度一样，若同向而行，相对距离不会改变，故我们把 kk 遇到他左边的人花费时间和右边的压到两个数组中，这两个数组中的数字只能依次取出，取一个数字就是用当前时间减掉他再加上续命的 TT 秒，需要保证无论何时当前时间都不小于 00 .

​ 进一步，我们把两个序列分成若干块，每块表示其总共花费时间为负，也就是能给我们当前时间加上 vv ，再求一下每块能取所要求的最大时间 mxmx ，定义为二元组 (mx,v)(mx, v) ，再对两边贪心选取即可。由于要保证顺序当然是前缀压块。

​ 若有一些地方不能压成块，那一定是一些后缀，这些我们考虑时间倒流，我们可以直到最后剩余时间，再反过来搞，先给时间加上 TT ，再减去数字，类似的做即可。

​ 代码细节是处理没被压成块的地方开头时预处理为 −1-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
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
/*=====================

 # Author: Chaos1018
 # Blog : chaos1018.ml
 # Mail : minyuenu@gmail.com

======================*/ 
#include <bits/stdc++.h>
using namespace std;

#define Debug(x) cout << #x <<" = " << x << endl
#define pii pair <int, int>
#define pdd pair <double, double>
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define db double
template <typename T> inline void read(T &a){
    T w = 1; a = 0;
    char ch = getchar();
    for(;ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') w = -1;
    for(;ch >= '0' && ch <= '9'; ch = getchar()) a = (a*10) + (ch-'0');
    a *= w;
}
template <typename T> inline void ckmax(T &a,T b){a = a > b ? a : b;}
template <typename T> inline void ckmin(T &a,T b){a = a < b ? a : b;}
const int MAX = 1e5 + 10;
const db eps = 1e-18;
int n, k, T;
int s[MAX];

vector < db > a, b;
vector< pdd > A, B;
bool check (int v) {
	a.clear(), b.clear(), A.clear(), B.clear();
	for (int i = k; i > 1; --i) a.pb(0.5 * (s[i] - s[i - 1]) / v );
	for (int i = k; i < n; ++i) b.pb(0.5 * (s[i + 1] - s[i]) / v );
	db res = 0, mx = 1e18;
	// 到达一个点，消耗a_i时间，获得T时间
	// res -= a[i], res += T;
	db last = T;
	for (int i = 0; i < a.size(); ++i) last -= a[i], last += T;
	for (int i = 0; i < b.size(); ++i) last -= b[i], last += T;
	if (last < 0) return false;
	int tmpa = -1, tmpb = -1;
	for (int i = 0; i < a.size(); ++i) {
		res -= a[i]; ckmin(mx, res); res += T;
		if (res > -eps) A.pb ( mp(-mx, res) ), res = 0, mx = 1e18, tmpa = i;
	}
	res = 0, mx = 1e18;
	for (int i = 0; i < b.size(); ++i) {
		res -= b[i]; ckmin(mx, res); res += T;
		if (res > -eps) B.pb ( mp(-mx, res) ), res = 0, mx = 1e18, tmpb = i; 
	}
	res = T;
	int x = 0, y = 0;
	while ( x < A.size() || y < B.size() ) {
		if (x < A.size() && res >= A[x].fi ) res += A[x++].se;
		else if (y < B.size() && res >= B[y].fi ) res += B[y++].se;
		else return false;
	}
	A.clear(), B.clear();
	res = 0, mx = 1e18;
	for (int i = a.size() - 1; i > tmpa; --i) {
		res -= T; ckmin(mx, res); res += a[i];
		if (res > -eps) A.pb ( mp (-mx, res) ), res = 0, mx = 1e18;
	}
	res = 0, mx = 1e18;
	for (int i = b.size() - 1; i > tmpb; --i) {
		res -= T; ckmin(mx, res); res += b[i];
		if (res > -eps) B.pb ( mp (-mx, res) ), res = 0, mx = 1e18;
	}
	res = last;
	x = 0, y = 0;
	while ( x < A.size() || y < B.size() ) {
		if (x < A.size() && res >= A[x].fi) res += A[x++].se;
		else if (y < B.size() && res >= B[y].fi) res += B[y++].se;
		else return false;
	}
	return true;
}

int main(){
	freopen ("sparklers.in", "r", stdin);
	freopen ("sparklers.out", "w", stdout);
	int flag = 0;
	read(n); read(k); read(T);
	for (int i = 1; i <= n; ++i) {
		read(s[i]);
		if (s[i] != s[i - 1]) flag = 1;
	}
	if (!flag) return puts("0"), 0;
	int l = 1, r = 1e9 + 10;
	while (l < r) {
		int mid = l + r >> 1;
		if ( check (mid) ) r = mid;
		else l = mid + 1;
	}
	printf ("%d\n", l);
	return 0;
}