100 + 10 + 0 +0

T1 简单结论题

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

T3 群除我会的科技

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

点满科技树,锻炼思维!!!


# Solutions:

# sto

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

结论是:若 xx66 的倍数则可以,否则则不行。

手玩可以发现 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,ikmin{ij,jk}\forall i<j<k, i\oplus k\ge \min\{i\oplus j, j\oplus k\}.

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

  • i,j,(ij)ij\forall i, j, (i\oplus j)\ge |i - j|

于是可得答案的下界。

  • k[0,2×ij],(i+k)(j+k)=ij\exists k\in[0,2\times |i - j|], (i+k)\oplus (j+k) = |i-j|

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

kk 不在 2ij2|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,y1)(x+1,y-1)
  • (x+1,y)(x+1,y) 无棋子,就可移动至此

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

考虑一个棋子 aa ,能吃到什么棋子?一定是 yb=ya+1,xbxay_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;
}

更新于 阅读次数

请我喝[茶]~( ̄▽ ̄)~*

Odalys 微信支付

微信支付

Odalys 支付宝

支付宝