Cansult's blog

即使愿望永远无法实现
我也不愿就这样放手

0%

翻车笔记 这两天的AC和CF的几道水(神)题

Posted on Edited on In

被虐成狗了...woc...

打那场狗逼的CF打了一晚上没写AtCoder...没看CF的要求然后写第二题的时候就懵逼了...woc我怎么交不了啊...一看woc用十种语言写这是神经病吧....幸好打的unrated... 前面几道膜你就不说了...E是个链表模拟...FGHI看不懂题...那么也就剩下...

CF VK2018 Wild-card R1: J

首先可以线段树维护区间联通块个数写...然后还有一种神奇的set写法...

亦可赛艇...

线段树

好像没必要写查询函数 我脑残写了...以后做题一定要先想好怎么写再下笔动键盘...

具体就是维护节点所在区间的最左边和最右边是否是1, 如果都是1(一个联通块跨过了mid, 就--ans)他们dalao说这是经典做法???我怎么不知道啊QAQ你们大佬怎么什么都经典做法啊

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (200000 + 5)
#define pii pair<int, int>
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
using namespace std;
struct node
{
	int le, ri, zh, lc, rc, lazy;
}b[MAXN << 4];
int sora[MAXN << 2];
pii que[MAXN];
void push_up(int dq)
{
	b[dq].lc = b[LS(dq)].lc, b[dq].rc = b[RS(dq)].rc;
	b[dq].zh = b[LS(dq)].zh + b[RS(dq)].zh - (b[LS(dq)].rc & b[RS(dq)].lc);
}
void push_down(int dq)
{
	b[LS(dq)].lazy = b[RS(dq)].lazy = 1;
	b[LS(dq)].lc = b[RS(dq)].rc = b[LS(dq)].rc = b[RS(dq)].lc = 1;
	b[LS(dq)].zh = b[RS(dq)].zh = 1;
	b[dq].lazy = 0;
}
void js(int dq, int le, int ri)
{
	b[dq].le = le, b[dq].ri = ri;
	b[dq].lazy = b[dq].lc = b[dq].rc = b[dq].zh = 0;
	if (le == ri)
		return ;
	int mi = (le + ri) >> 1;
	js(LS(dq), le, mi);
	js(RS(dq), mi + 1, ri);
}
void xg(int dq, int le, int ri)
{
	if (b[dq].le == le && b[dq].ri == ri)
	{
		b[dq].lc = b[dq].rc = b[dq].zh = b[dq].lazy = 1;
		return ;
	}
	if (b[dq].lazy)
		push_down(dq);
	int mi = (b[dq].le + b[dq].ri) >> 1;
	if (le > mi)
		xg(RS(dq), le, ri);
	else if (ri <= mi)
		xg(LS(dq), le, ri);
	else
		xg(LS(dq), le, mi), xg(RS(dq), mi + 1, ri);
	push_up(dq);
}
node cx(int dq, int le, int ri)
{
	if (b[dq].le == le && b[dq].ri == ri)
		return b[dq];
	int mi = (b[dq].le + b[dq].ri) >> 1;
	if (le > mi)
		return cx(RS(dq), le, ri);
	else if (ri <= mi)
		return cx(LS(dq), le, ri);
	else
	{
		node ls = cx(LS(dq), le, mi), rs = cx(RS(dq), mi + 1, ri), re;
		re.lc = ls.lc, re.rc = rs.rc;
		re.zh = ls.zh + rs.zh - (ls.rc & rs.lc);
		return re;
	}
}
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d%d", &que[i].first, &que[i].second);
		sora[++sora[0]] = que[i].first;
		sora[++sora[0]] = que[i].second;
	}
	sort(sora + 1, sora + sora[0] + 1);
	sora[0] = unique(sora + 1, sora + sora[0] + 1) - sora - 1;
	js(1, 1, (sora[0] + 1) << 1);
	for (int i = 1; i <= n; i++)
		que[i].first = (lower_bound(sora + 1, sora + sora[0] + 1, que[i].first) - sora) << 1, 
		que[i].second = (lower_bound(sora + 1, sora + sora[0] + 1, que[i].second) - sora) << 1;
	for (int i = 1; i <= n; i++)
		xg(1, que[i].first, que[i].second), printf("%d ", b[1].zh);
	return 0;
}

/*
9
10 20
50 60
30 40
70 80
90 100
60 70
10 40
40 50
80 90
*/

SET

感觉这个想法确实挺妙的_(:з」∠)_反正我是绝对想不出来了那应该是我菜啊...

  • lower_bound找到了右端点在当前线段左端点之右的线段
  • 如果那条线段的左端点在当前线段的右端点的右边说明不重合, 直接break (因为在set里的所有线段都不会有重合, 所以可以直接break)
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <set>
#define MAXN (200000 + 5)
#define INF (0x7ffffff)
#define pii pair<int, int>
#define mkp make_pair
using namespace std;
int n;
int main()
{
	set<pii> seg;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		int maxr, minl;
		scanf("%d%d", &minl, &maxr);
		set<pii>::iterator x;
		while (!seg.empty() && (x = seg.lower_bound(mkp(minl, 0))) != seg.end())
		{
			if (maxr < x->second)
				break;
			minl = min(minl, x->second);
			maxr = max(maxr, x->first);
			seg.erase(x);
		}
		seg.insert(mkp(maxr, minl));
		printf("%d ", seg.size());
	}
	return 0;
}

都挺好写的...一遍过了还是挺开心的毕竟我这种辣鸡码风 + 日常手残

AtCoder ARC 092: C

C好像是个二维黑白匹配的弱化版啊...set × 扫描线就过了... 其实忘记判断插入的元素是不是最小的元素还RE了一发 不过讲道理依着AtCoder的性格这个数据范围是不是有什么神做法啊...毕竟离散化都没写感觉良心不安啊

  • 离线, 把所有的点都按照 横坐标 -> 纵坐标 的顺序排序, 然后从 横坐标 == 0 的地方开始做扫描线
  • 遇到一个点, 如果是蓝点, 就insert到集合里, 如果是红点, 就贪心找一个纵坐标与他最接近(贪心)的蓝点直接删除, ++ans

没了

1ms出解还是挺快的...

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <vector>
#define MAXN (500 + 5)
#define pii pair<int, int>
using namespace std;
struct node
{
	pii poi;
	bool isB;
	bool operator < (const node x) const
	{ return poi < x.poi; }
}a[MAXN];
int n, ans;
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d%d", &a[i].poi.first, &a[i].poi.second), a[i].isB = false;
	for (int i = 1; i <= n; i++)
		scanf("%d%d", &a[n + i].poi.first, &a[n + i].poi.second), a[n + i].isB = true;
	sort(a + 1, a + (n << 1) + 1);
	set<int> qwq;
	for (int i = 1; i <= (n << 1); i++)
	{
		if (!a[i].isB)
			qwq.insert(a[i].poi.second);
		else if (!qwq.empty())
		{
			set<int>::iterator x = qwq.upper_bound(a[i].poi.second);
			if (x == qwq.begin())
				continue;
			--x;
			++ans;
			qwq.erase(x);
		}
	}
	printf("%d", ans);
	return 0;
}

AtCoder ARC 092: D

是个神题...参悟了好多大佬的题解...终于懂了吧...

这个dalao讲的神做法感觉比较奇怪... 被初中dalao踩爆感觉非常愉悦 这个初中dalao感觉更加的神

感觉我还是太Naïve...感觉南方爷们都好强啊...他们都好强啊...就我最菜了...凉了凉了

Emmmmm一开始想这道题...一看这种二进制异或肯定是拆位啊...然后...拆出来发现有进位不可做....然后又想会不会不拆也能做呢...是不是什么\(N^2\)朴素再加个什么神级优化就行呢...然后发现也不行...最后一晚上各种分类讨论YY了一个十分沙茶的用树状数组维护进位的东西...发现不可写+应该是错的

那么我们来看正解....我们发现进位不好进...那么怎么办呢...退赛炸rating换号 因为只有一位, 我们很难判断当前是不是进位(比这一位低的位可能会对当前的这一位产生贡献), 那么我们就保留下比这一位低的位...

对于当前的一位, 比他高的位显然是没有用的...那我们可以通过ak[k][i] = a[i] & ((1 << k) - 1)来去掉所有比他高的位...然后发现如果第k位(位数从1开始)是1的话, 只有两种区间满足要求:

  1. 1 << (k - 1) <= ak[k][i] + bk[k][i] <= 1 << k: 保证了这一位肯定是1, 否则不可能满足这个条件
  2. (1 << k) + (1 << (k - 1)) <= ak[k][i] + bk[k][i] <= (1 << k + 1) - 1: 我就是没有注意到这个条件WA了一下午样例...然后那着计算器试了试...发现可能进了一位后第k位还是1...GG

如果我们固定一个ak[k][i], 那么bk的值一定在一个区间里...那么我们就可以给bk排序, 然后直接二分答案了...

复杂度是\(O(29n \lg n)\)...可能需要卡卡常...我的程序完全没卡...有时候会T两个点...GG

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 <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL long long
#define MAXN (200000 + 5)
#define MAXL (32 + 5)
using namespace std;
LL n, a[MAXN], b[MAXN], ak[MAXL][MAXN], bk[MAXL][MAXN], k = 29, ans[MAXL];
int main()
{
//	freopen("in.in", "r", stdin);
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%lld", &a[i]);
		for (int j = 1; j <= k; j++)
			ak[j][i] = a[i] & ((1 << j) - 1);
	}
	for (int i = 1; i <= n; i++)
	{
		scanf("%lld", &b[i]);
		for (int j = 1; j <= k; j++)
			bk[j][i] = b[i] & ((1 << j) - 1);
	}
	for (int i = 1; i <= k; i++)
		sort(bk[i] + 1, bk[i] + n + 1);
	/*for (int i = 1; i <= k; i++)
	{
		for (int j = 1; j <= n; j++)
			printf("%d ", ak[i][j]);
		puts("");
	}
	for (int i = 1; i <= k; i++)
	{
		for (int j = 1; j <= n; j++)
			printf("%d ", bk[i][j]);
		puts("");
	}*/
	for (int i = 1; i <= n; i++) // ai + bj >= (1 << (k - 1)) && ai + bj < (1 << (k))
	{
		for (int j = 1; j <= k; j++)
		{
			int to = upper_bound(bk[j] + 1, bk[j] + n + 1, (1 << j) - ak[j][i] - 1) - bk[j];
			int to1 = upper_bound(bk[j] + 1, bk[j] + n + 1, (1 << (j + 1)) - 1 - ak[j][i]) - bk[j];
			int from = lower_bound(bk[j] + 1, bk[j] + n + 1, (1 <<(j - 1)) - ak[j][i]) - bk[j];
			int from1 = lower_bound(bk[j] + 1, bk[j] + n + 1, (1 << j) + (1 << (j - 1)) - ak[j][i]) - bk[j];
			ans[j] += to - from + to1 - from1;
		}
	}
	LL outp = 0;
	for (int i = 1; i <= k; i++)
		outp += (ans[i] & 1) << (i - 1);
	printf("%lld", outp);
	return 0;
}

/*
2
1 2
3 4
*/

AtCoder ARC 092: F

看上去是个连通性的搜索神题...先挖个坑吧...

参悟了一下这个和我同年却不知道比我高到哪里去的dalao

把翻转边看成删掉一条边再加入一条边, 如果输出diff, 必须要满足: 删除这条边的时候多了一个联通块 xor 加上这条边的时候少了一个联通块

  • 删除这条边多一个联通块, 需要满足:
    1. from不能通过别的边到达to
    2. to能到达from
  • 加上这条边少一个联通块, 需要满足:
    1. from能通过别的边到达to
    2. to不能到达from

然后....是不是就可做了?

每个点是否能到达另一个点可以通过n遍dfs\(O(N^2)\)地解决

通过另外的边...也许用tarjan?

稍微总结一下

对2进制的理解还不够透彻...脑洞也不够大...线段树熟练度不够...细节堪忧... 得抓紧时间开一下脑洞了... 感觉我好菜啊, 他们都好神啊...他们怎么这么神啊...省选凉了啊...stress.jpg

By Cansult