首页 Tests

100 + 10 + 0 +0

T1 简单结论题

T2 一个结论都不会被杀疯了

T3 群除我会的科技

T4 又胡了做法，又开始冲，又看错题了哈哈

点满科技树，锻炼思维！！！

# Solutions:

# sto

数轴上初始只有原点有一个球，你有两种操作， 一是把一个球删掉在它两边加两个，二是删掉旁边两个球在中间加入一个，询问能否多次操作后使只有 xx 位置有球。

结论是：若 xx 是 66 的倍数则可以，否则则不行。

手玩可以发现 66 可以，自然 66 的倍数也可以，那要证不是 66 的倍数不行。

# as

nn 个数字，∀s∈[0,k],min⁡{(ai+s)⊕(aj+s)}\forall s\in [0, k], \min\{(a_i + s)\oplus (a_j + s)\}.

一些结论是：

  • ∀i<j<k,i⊕k≥min⁡{i⊕j,j⊕k}\forall i<j<k, i\oplus k\ge \min\{i\oplus j, j\oplus k\}.

由于相加差距不变，所以我们排序后相邻两个就能到答案，O(nk)\mathrm O(nk) 算法就出来了

  • ∀i,j,(i⊕j)≥∣i−j∣\forall i, j, (i\oplus j)\ge |i - j|

于是可得答案的下界。

  • ∃k∈[0,2×∣i−j∣],(i+k)⊕(j+k)=∣i−j∣\exists k\in[0,2\times |i - j|], (i+k)\oplus (j+k) = |i-j|

这个我也不会证，然后这题就做完了。

若 kk 不在 2∣i−j∣2|i-j| 内直接 O(nk)O(nk) 否则就是最小差。

在解个不等式即可证明暴力 O(nk)O(nk) 时复杂度正确。

# lky

斯特林数 + 范德蒙德卷积板子题

在学了

# orz

一个无限大的棋盘，有 nn 个黑色棋子(x,y)(x, y) ，你要放白棋将其全部吃掉，移动规则如下:
白棋在 (x,y)(x,y) 处

  • 若 (x+1,y+1)(x+1,y+1) 有黑棋 ，就可以移动至此吃掉黑棋
  • 若 (x+1,y−1)(x+1,y-1) …
  • 若 (x+1,y)(x+1,y) 无棋子，就可移动至此

考场上看错题了，然后一个基于随机化的东西看起来正确性没问题的东西过不了样例…

考虑一个棋子 aa ，能吃到什么棋子？一定是 yb=ya+1,xb≥xay_b = y_a + 1, x_b \ge x_a 的黑棋子

那这是一个 DAGDAG 上统计不交路径覆盖的问题。

注意我们一定能根据一组覆盖方案还原一组移动方法

即当你要往右走被黑棋挡住时，先让吃它的白棋先动就好。

那套路的拆点为入点和出点我们就有 n2n^2 连边的网络流求二分图最大匹配的做法了

二分图最大匹配不好求？转换成求二分图最大独立集。

我们设 yy 坐标为偶数的点为偶点，发现一对边的两个点奇偶性不同，于是我们把图拆成两个，奇入 - 偶出，偶入 - 奇出，对这两张图分别求最大独立集

考虑一个出点，若它被选入独立集中，意味着连它的入点不在独立集中，则它同行后面的点也可被选出独立集中

发现出点 / 入点所选入独立集的情况是个前缀 / 后缀的形式，于是我们可以使用单指针跑 dp 解决。

不太会实现于是贺了 deltax 的代码

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
#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<<3)+(a<<1)+(ch^48);
	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;}
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mii map<int, int> 
#define pii pair<int, int> 
#define vi vector<int> 
#define Debug(x) cout << #x << " = " << x << endl
#define For(i,l,r) for (int i = l; i <= r; ++i) 
#define foR(i,l,r) for (int i = l; i >= r; --i)
const int N = 5e5 + 10;
struct Node {
	int x, y;
	Node (int X = 0, int Y = 0) { x = X, y = Y; }
	bool operator < (const Node &a) const {
		if ( x == a.x ) return y < a.y;
		return x < a.x;
	}
} a[N];

vi dot[N];
int n; 
pii sta[N];
vector < pii > dp; // fi the x, se the val 
inline int Dp (int op) {
	int cur = 0;
	dp.clear();
	dp.pb(mp(0, 0)); 
	For (i, 1, N - 10) {
		if ( (i ^ op) & 1 ) {
			int p = dp.size() - 1, tmp = dp[0].se;
			int top = 0, sz = dot[i].size() - 1; 
			foR (j, sz, 0) {
				int x = dot[i][j];
				while (p >= 0 && dp[p].fi >= x) ckmax(tmp, dp[p--].se);
				sta[++top] = mp(x, tmp + j + 1); 
			}
			while ( p >= 0 ) ckmax(tmp, dp[p--].se);
			dp.clear();
			dp.pb(mp(0, tmp));
			reverse (sta + 1, sta + top + 1);	
			For (j, 1, top) dp.pb(sta[j]); 
		} // In
		else {
			int tmp = 0, p = 0, sz = dot[i].size() - 1;
			int top = 0;
			For (j, 0, sz)  {
				int x = dot[i][j];
				while (p < dp.size() && dp[p].fi <= x) ckmax(tmp, dp[p++].se);
				sta[++top] = mp(x, tmp + sz - j + 1);
			}
			while ( p < dp.size() ) ckmax(tmp, dp[p++].se);
			dp.clear();
			dp.pb(mp(0, tmp));
			For (j, 1, top) dp.pb(sta[j]);
		} // Out
	}
	int res = 0;
	for (auto v : dp) ckmax(res, v.se);
	return res; 
}

int main() {
	read(n);
	For (i, 1, n) read(a[i].x), read(a[i].y);
	sort (a + 1, a + n + 1);
	For (i, 1, n) dot[a[i].y].pb(a[i].x); 
	printf ("%d\n", n - (n - Dp(0) + n - Dp(1) ));
	return 0;
}