水题笔记_ 最近CF和BZ月赛和AT的几道水(shén)题 [二分, 主席树, 筛法, 清奇脑回路, 翻车]

无非做了些无聊的事情,等于什么也没有做。

但是有些题还是挺有意思的…

ARC098D

Asia: 这场比赛感觉30min就能AK啊

Aufun: 这场比赛怎么全是傻~~~~逼题

Orzzzzzz

一开始好像想错了点地方…觉得是个sb题…然后一写发现不是这么回事…

我写了个…模拟…Emmmmm…就是模拟他们的xorsum是否相等…然后扫一遍, 再去个重…就A了…

去重

所谓去重就是上面的情况…蓝色和红色都是合法的区间(区间内的数满足xor == sum)…然后因为是扫描过来的, 中间可能重叠一个绿色的区间, 所以要去重…

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
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN (200000 + 5)
#define INF (0x7fffffff)
#define LL long long
using namespace std;
int n, a[MAXN];
LL ans;
LL solve()
{
LL sum = 0, xsum = 0;
int he = 1, ta = 0, lastt = 0;
while (true)
{
sum += a[++ta];
xsum ^= a[ta];
if (xsum != sum)
{
LL dqn = ta - he, emm = max(0, (lastt - he + 1));
ans += (dqn * (dqn + 1)) >> 1;
ans -= (emm * (emm + 1)) >> 1;
lastt = ta - 1;
while (xsum != sum)
{
sum -= a[he];
xsum ^= a[he++];
}
if (ta == n)
{
dqn = n - he + 1, emm = max(0, (lastt - he + 1));
ans += (dqn * (dqn + 1)) >> 1;
ans -= (emm * (emm + 1)) >> 1;
break;
}
}
else if (ta == n)
{
LL dqn = ta - he + 1, emm = max(0, (lastt - he + 1));
ans += (dqn * (dqn + 1)) >> 1;
ans -= (emm * (emm + 1)) >> 1;
break;
}
}
return ans;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
printf("%lld\n", solve());
return 0;
}

BZOJ M5A

分解质因数, 然后用主席树维护区间内每一个质因数的分布情况克拉斯姐姐好像有别的做法?

然后数组开小了, 一场比赛就调了这一个题…

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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
/**************************************************************
Problem: 5358
User: Cansult
Language: C++
Result: Accepted
Time:2920 ms
Memory:248756 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#define MAXN (1000000 + 5)
#define MAXL (1000000 + 5)
#define MAXP (100000 + 5)
#define INF (100000 + 5)
#define pii pair<int, int>
#define cint int
#define rint int
using namespace std;
int root[MAXN];
pii rooot[MAXN];
struct node
{
int ls, rs, zh;
}b[MAXN * 20];
int prime[MAXP], n, cntb;
bool is_p[MAXL];
inline int read()
{
rint re = 0;
register char x = 0;
while (x < '0' || x > '9')
x = getchar();
while (x <= '9' && x >= '0')
{
re = (re << 1) + (re << 3) + x - '0';
x = getchar();
}
return re;
}
void ins(cint pre, int& dq, cint le, cint ri, cint wz, cint zh)
{
dq = ++cntb;
if (le == ri)
{
b[dq].zh = b[pre].zh + zh;
return ;
}
cint mi = (le + ri) >> 1;
if (wz > mi)
b[dq].ls = b[pre].ls, ins(b[pre].rs, b[dq].rs, mi + 1, ri, wz, zh);
else
b[dq].rs = b[pre].rs, ins(b[pre].ls, b[dq].ls, le, mi, wz, zh);
b[dq].zh = b[b[dq].ls].zh + b[b[dq].rs].zh;
}
int cx(cint pre, cint dq, cint le, cint ri, cint wz)
{
if (le == ri)
return b[dq].zh - b[pre].zh;
cint mi = (le + ri) >> 1;
if (wz > mi)
return cx(b[pre].rs, b[dq].rs, mi + 1, ri, wz);
else
return cx(b[pre].ls, b[dq].ls, le, mi, wz);
}
void init()
{
memset(is_p, true, sizeof(is_p));
for (rint i = 2; i < MAXL; ++i)
{
if (is_p[i])
prime[++prime[0]] = i;
for (rint j = 1; j <= prime[0] && prime[j] * i < MAXL; ++j)
{
is_p[prime[j] * i] = false;
if (i % prime[j] == 0)
break;
}
}
}
int main()
{
init();
int t;
// t = read();
scanf("%d", &t);
while (t--)
{
for (int i = 0; i <= cntb; i++)
b[i].ls = b[i].rs = b[i].zh = 0;
cntb = 0;
memset(root, 0, sizeof(0));
int q;
// n = read(), q = read();
scanf("%d%d", &n, &q);
for (int i = 0; i <= n; i++)
rooot[i] = make_pair(0, 0);
for (rint i = 1; i <= n; ++i)
{
// rint x = read();
rint x;
scanf("%d", &x);
rooot[i].first = rooot[i - 1].second + 1;
rooot[i].second = rooot[i - 1].second;
for (rint j = 1; j <= prime[0] && !is_p[x]; ++j)
{
rint cntp = 0;
while (x % prime[j] == 0)
{
++cntp;
x /= prime[j];
}
if (!cntp)
continue;
ins(root[rooot[i].second], root[rooot[i].second + 1], 1, MAXL, prime[j], cntp);
++rooot[i].second;
}
ins(root[rooot[i].second], root[rooot[i].second + 1], 1, MAXL, x, 1);
++rooot[i].second;
}
for (rint i = 1, srx, sry, srd; i <= q; ++i)
{
// srx = read(), sry = read(), srd = read();
scanf("%d%d%d", &srx, &sry, &srd);
bool ok = true;
for (rint j = 1; j <= prime[0] && !is_p[srd]; ++j)
{
rint cntp = 0;
while (srd % prime[j] == 0)
{
++cntp;
srd /= prime[j];
}
if (!cntp)
continue;
if (cx(root[rooot[srx - 1].second], root[rooot[sry].second], 1, MAXL, prime[j]) < cntp)
{
ok = false;
break;
}
}
if (srd != 1 && !cx(root[rooot[srx - 1].second], root[rooot[sry].second], 1, MAXL, srd))
ok = false;
if (ok)
puts("Yes");
else
puts("No");
}
}
return 0;
}

ACC2018D Bookshelves

题意: 把一个序列分成$k$段(顺序不变), 让每段和的异或值最大

总算会做这玩意了…

ARC092D的启发, 如果按位分解不好做的话, 可以考虑按位延伸: 这一位能是$1$就是$1$, 否则就是$0$, 下一次判断的时候还跟着之前的位一起判断

然后判断就是可行性dp乱搞一下…

一点题外话

当时比赛的时候有点不舒服…也没有耐心读题…题都读不懂…就写了3个题…感觉要掉绿了…在床上躺了1h差点睡着…

然后想到这个题的做法非常开心, 在10min的时候过了pretest…

就在距离比赛结束还有两秒我非常高兴觉得今晚不用掉分的时候…

GG

GG

你大爷

又是数组开小了(一天了连着两个数组开小了真是开心)

当时是只想到位数不会大于$50$, 但是忘了他会加起来…然后就凉了…

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#define MAXN (62 + 5)
#define LL long long
#define INF (0x7ffffffffffffffll)
#define pii pair<int, int>
#define int LL
using namespace std;
int n, k;
LL a[MAXN], ans, fr[MAXN];
bool pd(int x)
{
bool f[MAXN][MAXN];
memset(f, false, sizeof(f));
f[0][0] = true;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < i; j++)
if (((fr[i] - fr[j]) & x) == x)
{
for (int z = 0; z < k; z++)
if (f[j][z])
f[i][z + 1] = true;
}
}
return f[n][k];
}
void solve()
{
LL dq = 0;
for (int i = 62; i >= 0; i--)
{
LL qwq = (1ll << i);
dq |= qwq;
if (pd(dq))
ans |= qwq;
else
dq ^= qwq;
}
}
main()
{
// freopen("in.in", "r", stdin);
scanf("%lld%lld", &n, &k);
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]), fr[i] = fr[i - 1] + a[i];
solve();
printf("%lld\n", ans);
return 0;
}

By 沙茶 Cansult