Atcoder爽题集合

Atcoder爽题集合

口胡和完整代码参见代码仓库

AtcoderGC024B

对于$[1 .. n]$的排列$A$, 每次可以选择一个数放到开头, 最后使得数列有序, 求最少操作次数. 简单dp

1
2
3
4
5
scanf("%d", &n);
for (R int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (R int i = 1; i <= n; ++i)
f[a[i]] = f[a[i] - 1] + 1, ans = max(ans, f[a[i]]);
printf("%d", n - ans);

AtcoderGC022C

对于数列$A$, $B$, 每一次可以选择$A$中任意多个数, 然后选择一个数$k$, 使得每个选择的数$a_i$ 变成$a_i \; mod \; k$.然后代价是$2^k$, 最后使得$A$和$B$相同, 求代价最小值. 贪心 + 状压dp

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
scanf("%d", &n);
for (int j = 0; j <= 50; ++j)
{
f[j] = 0, f[j] |= (1ll << j);
for (int k = 1; k <= j; ++k)
if(((1ll << 51) - 1) & (1ll << k)) f[j] |= f[j % k];
}
for (R int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (R int i = 1; i <= n; ++i) scanf("%d", &b[i]);
int flag = 1;
for (R int j = 1; j <= n; ++j)
if((f[a[j]] & (1ll << b[j])) == 0) flag = 0;
if(flag == 0) return printf("%lld\n", -1ll), void();
for (int i = 50; i; --i)
{
for (int j = 0; j <= 50; ++j)
{
f[j] = 0, f[j] |= (1ll << j);
for (int k = 1; k <= j; ++k)
if((ans + (1ll << i) - 1) & (1ll << k)) f[j] |= f[j % k];
}
int flag = 1;
for (R int j = 1; j <= n; ++j)
if((f[a[j]] & (1ll << b[j])) == 0) flag = 0;
if(!flag) ans += (1ll << i);
}
printf("%lld\n", ans);

AtcoderGC024C

对于初始为0的数列$A$, 每次可以选择一个$ai$变成$a{i - 1} + 1$.最后使得$A$变成$B$, 求最少操作次数. 蜜汁性质

1
2
3
4
5
6
7
8
9
10
11
scanf("%d", &n);
for (R int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (R int i = 1; i <= n; ++i)
if(a[i] >= i) return puts("-1"), 0;
for (R int i = 2; i <= n; ++i)
{
if(a[i] - a[i - 1] > 1) return puts("-1"), 0;
if(a[i] == a[i - 1] + 1) ++ans;
else ans += a[i];
}
printf("%d\n", ans);

AtcoderGC020C

对于数列$A$的所有子集之和, 进行排序, 然后求出排序后的中位数
这道题值得提一提 补集思想很重要

1
2
3
4
5
scanf("%d", &n);
f[0] = 1;
for (R int i = 1; i <= n; ++i) scanf("%d", &val), f |= (f << val), sum += val;
if(n == 1) return printf("%d", sum), 0;
for (R int i = (sum >> 1); i; --i) if(f[i]) return printf("%d", sum - i), 0;

「题解」「AGC022C」Reminder Game

Reminder Game

题目大意

给出数组$a$, $b$, 每次可以选择$a$中的任意多个数,然后选择一个$k$,把所有的选中的数变为$a_i \% k$。每次操作的成本是$2^k$,求把$a$变为$b$的最小代价。

题目解释

太妙啦!!!
求助q234rty神犇后…
太妙啦!!!我再感叹一次!!!
本来是LR安利的题,但是当时以为是图论建模,一直没做。
但是这道题的确从图论建模好像要好思考一些。
这样吧,首先拆分题目。
我们知道了,$2^k$一定有鬼qwq,肯定要贪。
然后,这里有一个值得总结的,“处理任意多个数”。
这道题的处理方式是$f[i][j]$表示在“处理结束后”,数$i$能否到达$j$。这样,就可以巧妙地绕开“处理仍以多个数”,而是一次性对数列中所有的某一个数值进行处理,喵喵喵~
然后是一个我半天没理解到的地方,如何贪心呢。
这道题的贪心策略如下,从高到低位枚举二进制位。
每一个对于表示$2^i$的第$i$个二进制位,我们用这一位表示对原数组进行一次$\%i$的操作之后的$f$数组。考虑这一位,因为二进制的性质,如果其所有后面的位都为1,依然不能满足$a$数组能够转化为$b$数组,那么当前位一定需要,那么我们就从高到底枚举位,假如说满足需要该位的条件,那么就$ans += (1ll << i)$。

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
#define ll long long
#define R register
#include <bits/stdc++.h>

using namespace std;

namespace ARC022C
{
int n, a[55], b[55];
ll f[55], ans;

inline void solve()
{
scanf("%d", &n);
for (int j = 0; j <= 50; ++j)
{
f[j] = 0, f[j] |= (1ll << j);
for (int k = 1; k <= j; ++k)
if(((1ll << 51) - 1) & (1ll << k)) f[j] |= f[j % k];
}
for (R int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (R int i = 1; i <= n; ++i) scanf("%d", &b[i]);
int flag = 1;
for (R int j = 1; j <= n; ++j)
if((f[a[j]] & (1ll << b[j])) == 0) flag = 0;
if(flag == 0) return printf("%lld\n", -1ll), void();
for (int i = 50; i; --i)
{
for (int j = 0; j <= 50; ++j)
{
f[j] = 0, f[j] |= (1ll << j);
for (int k = 1; k <= j; ++k)
if((ans + (1ll << i) - 1) & (1ll << k)) f[j] |= f[j % k];
}
int flag = 1;
for (R int j = 1; j <= n; ++j)
if((f[a[j]] & (1ll << b[j])) == 0) flag = 0;
if(!flag) ans += (1ll << i);
}
printf("%lld\n", ans);
}
}

int main()
{
return ARC022C::solve(), 0;
}

「题解」「BZOJ4456」 旅行者

oi

「BZOJ4456」 旅行者


妈耶,这道题的难度。
两个小时吧…题解大大帮了不少的忙。
我第一次跑的时候第一个点17s…
顺着题解的各种思路优化优化,然后才优化到了这份代码。
为啥没人解释SPFA那段该怎么优化啊!那里明明是性能瓶颈。
这道题要好好解释一下,太神了。

首先解释这道题的核心…分治方法。
一开始看的我一脸懵逼,这道题咋做。
后来一看标签,分治啊分治…
然后kd-tree的思路就该上了。
我们每一次对一个矩形进行划分,用最长的一个边对半分,然后对分成两半的矩形里的点进行讨论,
对于做全在左右半边的点,我们先不考虑,我们考虑跨越左右矩形的点。
对于每个点点距离,我们进行以下计算:枚举划分点到点点的距离,然后类floyd跑出最短距离。
然后递归对剩下的矩形进行处理。

但是…这道题的细节很蛋疼。
有两个难度较大的细节,如何保证每次计算的都是在矩形内的查询。
细节2,怎么优化SPFA。
嗯…明天写(咕咕咕)

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
157
158
// by kririae
#define inf 0x3f3f3f3f
#define R register
#define ll long long
#define pii pair<int, int>
#include <bits/stdc++.h>

using namespace std;

namespace IO
{
inline char gc()
{
static char buf[1 << 18], *fs, *ft;
return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}
inline int read()
{
register int k = 0, f = 1;
register char c = gc();
for (; !isdigit(c); c = gc()) if (c == '-') f = -1;
for (; isdigit(c); c = gc()) k = (k << 3) + (k << 1) + (c - '0');
return k * f;
}
}

namespace BZOJ4456
{
const int maxn = 2e5 + 5, maxq = 1e5 + 5;

struct Edge
{
int to, val;
Edge(int t, int v) : to(t), val(v) {}
};
vector<Edge> edges[maxn];
struct Query
{
int x, y, id;
} q[maxq], tmp[maxq];
int n, m, val, Q, dis[maxn], res[maxq];
pii idx[maxn];
bitset<maxn> vis;
queue<int> qwq;

inline void addedge(int from, int to, int val)
{
edges[from].push_back(Edge(to, val));
edges[to].push_back(Edge(from, val));
}

inline int calc(int x, int y)
{
return (x - 1) * m + y;
}

inline void SPFA(int xs, int ys, int xl, int xr, int yl, int yr, bool flag)
{
// 一个骚优化
int d = dis[calc(xs, ys)];
for (R int i = xl; i <= xr; ++i)
for (R int j = yl; j <= yr; ++j)
dis[calc(i, j)] = flag ? dis[calc(i, j)] + d : inf;
int s = calc(xs, ys);
dis[s] = 0, vis[s] = 1, qwq.push(s);
while(!qwq.empty())
{
int curr = qwq.front(); qwq.pop(); vis[curr] = 0;
for (int i = 0; i < edges[curr].size(); ++i)
{
Edge &e = edges[curr][i];
int tox = idx[e.to].first, toy = idx[e.to].second;
if(tox >= xl && tox <= xr && toy >= yl && toy <= yr)
if(dis[e.to] > dis[curr] + e.val)
{
dis[e.to] = dis[curr] + e.val;
if(!vis[calc(tox, toy)]) qwq.push(calc(tox, toy)), vis[calc(tox, toy)] = 1;
}
}
}
}

inline void solve(int xl, int xr, int yl, int yr, int l, int r)
{
if(l > r) return;
if(xr - xl <= yr - yl)
{
int mid = (yl + yr) >> 1;
for (R int i = xl; i <= xr; ++i)
{
SPFA(i, mid, xl, xr, yl, yr, i != xl);
for (R int j = l; j <= r; ++j)
res[q[j].id] = min(res[q[j].id], dis[q[j].x] + dis[q[j].y]);
}
int tl = l - 1, tr = r + 1;
for (R int i = l; i <= r; ++i)
{
int y1 = idx[q[i].x].second, y2 = idx[q[i].y].second;
if(y1 < mid && y2 < mid) tmp[++tl] = q[i];
else if(y1 > mid && y2 > mid) tmp[--tr] = q[i];
}
for (R int i = l; i <= tl; ++i) q[i] = tmp[i];
for (R int i = tr; i <= r; ++i) q[i] = tmp[i];
solve(xl, xr, yl, mid - 1, l, tl);
solve(xl, xr, mid + 1, yr, tr, r);
} else {
int mid = (xl + xr) >> 1;
for (R int i = yl; i <= yr; ++i)
{
SPFA(mid, i, xl, xr, yl, yr, i != yl);
for (R int j = l; j <= r; ++j)
res[q[j].id] = min(res[q[j].id], dis[q[j].x] + dis[q[j].y]);
}
int tl = l - 1, tr = r + 1;
for (R int i = l; i <= r; ++i)
{
int x1 = idx[q[i].x].first, x2 = idx[q[i].y].first;
if(x1 < mid && x2 < mid) tmp[++tl] = q[i];
else if(x1 > mid && x2 > mid) tmp[--tr] = q[i];
}
for (R int i = l; i <= tl; ++i) q[i] = tmp[i];
for (R int i = tr; i <= r; ++i) q[i] = tmp[i];
solve(xl, mid - 1, yl, yr, l, tl);
solve(mid + 1, xr, yl, yr, tr, r);
}
}

inline void solve()
{
memset(dis, 0x3f, sizeof(dis));
memset(res, 0x3f, sizeof(res));
using namespace IO;
n = read(), m = read();
for (R int i = 1; i <= n; ++i)
for (R int j = 1; j <= m; ++j)
idx[calc(i, j)] = make_pair(i, j);
for (R int i = 1; i <= n; ++i)
for (R int j = 1; j < m; ++j)
addedge(calc(i, j), calc(i, j + 1), read());
for (R int i = 1; i < n; ++i)
for (R int j = 1; j <= m; ++j)
addedge(calc(i, j), calc(i + 1, j), read());
Q = read();
for (R int i = 1; i <= Q; ++i)
{
int a = read(), b = read(), c = read(), d = read();
q[i].x = calc(a, b), q[i].y = calc(c, d), q[i].id = i;
}
solve(1, n, 1, m, 1, Q);
for (R int i = 1; i <= Q; ++i)
printf("%d\n", res[i]);
}
}

int main()
{
return BZOJ4456::solve(), 0;
}