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

被虐成狗了…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: E


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