解题报告_ NOIp2017 普及组 [单调队列优化DP, GG]

没错我们又考了一次普及组的题
被普及组的题折磨了两天我也是没救了…

这里写图片描述

懵逼的 题目

哈哈哈老娘又能上Luogu辣

扯淡的 题解

记得D1晚上听他们说题目来着, 听中初中部的人说题目好难啊, 然后就去找学弟萌玩♂耍…学弟一脸懵逼 “不难啊”威武我大实验!, 要被学弟碾了…

T1T2没啥好说的…只要T2别脑子抽了写trie就没啥问题…似乎当成字符串暴力匹配都能过? 还是普及组良心!

T3是一个最短路…吧

听到题目就想到酱的一个事实

如果从一个有颜色的格子走到一个没有颜色的格子, 最优方案应该把没有颜色的格子的颜色变成当前在的格子的颜色

然后就是把白格子分成两部分: 一部分将(江)要变成红色, 一部分将(江)要变成黄色, 然后连边跑dijk就行…数据范围小的一批…0ms稳如poi~我才不会告诉你我读错题目改了2h+
最后注意一个细节…题目只说了起点是有颜色的…终点可能是白色…所以最终答案其实是min(d[终点变成红色], d[终点变成黄色])…不过数据非常良心没有给我卡成0分…

T4是一个二分答案×单调队列优化DP

woc单调队列优化DP都是普及组考点了嘛…????
我用实际行动告诉泥萌数据点里每一个-1的点…所以我也就没有判断…

首先二分答案很好想到…但是当时和学弟坐在床上聊♂天也没有听的太懂题目…
回来以后做题…读错题目…以为一步必须走一格的意思是必须走一个单位距离…然后发现这题没法做了…发现woc这个判断怎么写啊….???然后写了个puts(-1)一分没有…伤人感情…好歹咱也是花了1h+看了这道题是吧…

首先明确一下题目: 每次必须走一格的意思就是每一次都要到达下一个 [有分数的点] (两点间的距离 >= 最小步长 || <= 最大步长),

然后应该比较容易想到一个n ^ 2DP…f[i] = max{f[j] + a[i]} , j = 0 ~ (i - 1) (i, j间可到达)

然后你就有了50’…
发现f[i]的取值其实就是max{f[j]} + a[i]…而a[i]是固定的…所以其实转移就是要求一个能到达的最大的f[j]!
而一个点能到的范围很容易发现是一个连续的区间, 而且这个区间是一个滑动窗口!(两点(i, j)距离 < 当前最短步长, 那么i之前的点和j的距离肯定也小于最短步长, 两点距离 > 当前最长步长, 那么i之后的点和j的距离肯定也大于最长步长)
于是就可以写一个优雅的单调队列来优化转移惹…

注意单调队列为空的处理…(push(make_pair(0, 0))和当单调队列为空, 你又往里面加了一个(0, 0)的时候, 是不能转移的…

沙茶的 代码

T1(用double好像会WA)

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL long long
#define DD double
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))

using namespace std;
typedef pair<int, int> pii;

const int homework = 2;
const int normaltest = 3;
const int finalexam = 5;

int main()
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
printf("%lld", ((LL)(a * homework) + (b * normaltest) + (c * finalexam)) / 10);
fclose(stdout);
fclose(stdin);
return 0;
}

T2(一开始以为要输出编号就蛋疼的加了个pair)

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define MAXN (1000 + 5)
#define MAXQ (1000 + 5)
#define LL long long
#define DD double
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))

using namespace std;
typedef pair<int, int> pii;

int n;
int q;
pii a[MAXN];

bool cmp(const pii&, const pii&);
int cx(pii&);
int mpow(int, int);
int main()
{

scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i].first);
a[i].second = i;
}
sort(a + 1, a + n + 1, cmp);
pii srx;
for (int i = 1; i <= q; i++)
{
scanf("%d%d", &srx.second, &srx.first);
srx.second = mpow(10, srx.second);
printf("%d\n", cx(srx));
}
fclose(stdout);
fclose(stdin);
return 0;
}
bool cmp(const pii& x, const pii& y)
{
return x.first < y.first;
}
int cx(pii& x)
{
for (int i = 1; i <= n; i++)
{
if ((a[i].first % x.second) == x.first)
{
return a[i].first;
}
}
return -1;
}
int mpow(int di, int zhi)
{
int re = 1;
for (int i = 1; i <= zhi; i++)
{
re *= di;
}
return re;
}

/*
5 5
2123
1123
23
24
24
2 23
3 123
3 124
2 12
2
12
*/

T3(蜜汁码长)

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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#define MAXN (10000 + 5)
#define MAXM (40000 + 5)
#define MAXL (100 + 5)
#define INF (0x7ffffff)
#define TW (2)
#define TD (1)
#define TS (0)
#define LL long long
#define DD double
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define bh(a, b) ((a - 1) * srn + b)

using namespace std;
typedef pair<int, int> pii;

struct cmp
{
bool operator () (const pii x, const pii y)
{
return x.second > y.second;
}
};

struct edg
{
int from;
int to;
int next;
int cost;
} b[MAXM << 1];
int g[MAXN << 1];
int cntb;

int n;
int m;

int srn, srh;

int dis[MAXN << 1];

pii a[MAXN << 1];

void ade(int*, edg*, int&, int, int, int);
void init();
void dijk();
inline int calcost(const int, const int);
int main()
{


scanf("%d%d", &srn, &srh);
n = srn * srn;
int srx, sry, srz;
for (int i = 1; i <= srh; i++)
{
scanf("%d%d%d", &srx, &sry, &srz);
a[bh(srx, sry)].second = srz + 1;
}
init();
dijk();
if (dis[n] < INF || dis[n << 1] < INF)
printf("%d", min(dis[n], dis[n << 1]));
else
puts("-1");
fclose(stdout);
fclose(stdin);
return 0;
}
void ade(int* gx, edg* bx, int& cntx, int from, int to, int cost)
{
bx[++cntx].next = gx[from];
bx[cntx].from = from;
bx[cntx].to = to;
bx[cntx].cost = cost;
gx[from] = cntx;
}
void init()
{
for (int i = 1; i <= srn; i++)
{
for (int j = 1; j <= srn; j++)
{
int t = bh(i, j);
a[t + n].first = a[t].first = t;
}
}
for (int i = 1; i <= srn; i++)
{
for (int j = 1; j <= srn; j++)
{
int srf = bh(i, j);
if (a[srf].second)
{
if (i != 1)
{
int srt = bh(i - 1, j);
if (!a[srt].second)
{
if (a[srf].second == 2)
srt += n;
ade(g, b, cntb, srf, srt, TW);
}
else
{
ade(g, b, cntb, srf, srt, calcost(srf, srt));
}
}
if (i != srn)
{
int srt = bh(i + 1, j);
if (!a[srt].second)
{
if (a[srf].second == 2)
srt += n;
ade(g, b, cntb, srf, srt, TW);
}
else
{
ade(g, b, cntb, srf, srt, calcost(srf, srt));
}

}
if (j != 1)
{
int srt = bh(i, j - 1);
if (!a[srt].second)
{
if (a[srf].second == 2)
srt += n;
ade(g, b, cntb, srf, srt, TW);
}
else
{
ade(g, b, cntb, srf, srt, calcost(srf, srt));
}
}
if (j != srn)
{
int srt = bh(i, j + 1);
if (!a[srt].second)
{
if (a[srf].second == 2)
srt += n;
ade(g, b, cntb, srf, srt, TW);
}
else
{
ade(g, b, cntb, srf, srt, calcost(srf, srt));
}
}
}
else
{
a[srf].second = 1;
if (i != 1)
{
int srt = bh(i - 1, j);
if (a[srt].second)
{
ade(g, b, cntb, srf, srt, calcost(srf, srt));
}
}
if (i != srn)
{
int srt = bh(i + 1, j);
if (a[srt].second)
{
ade(g, b, cntb, srf, srt, calcost(srf, srt));
}
}
if (j != 1)
{
int srt = bh(i, j - 1);
if (a[srt].second)
{
ade(g, b, cntb, srf, srt, calcost(srf, srt));
}
}
if (j != srn)
{
int srt = bh(i, j + 1);
if (a[srt].second)
{
ade(g, b, cntb, srf, srt, calcost(srf, srt));
}
}
srf += n;
a[srf].second = 2;
if (i != 1)
{
int srt = bh(i - 1, j);
if (a[srt].second)
{
ade(g, b, cntb, srf, srt, calcost(srf, srt));
}
}
if (i != srn)
{
int srt = bh(i + 1, j);
if (a[srt].second)
{
ade(g, b, cntb, srf, srt, calcost(srf, srt));
}
}
if (j != 1)
{
int srt = bh(i, j - 1);
if (a[srt].second)
{
ade(g, b, cntb, srf, srt, calcost(srf, srt));
}
}
if (j != srn)
{
int srt = bh(i, j + 1);
if (a[srt].second)
{
ade(g, b, cntb, srf, srt, calcost(srf, srt));
}
}
a[srf].second = a[srf - n].second = 0;
}
}
}
}
inline int calcost(int from, int to)
{
if (!a[to].second)
{
return TW;
}
else
{
return ((a[from].second == a[to].second) ? (TS) : (TD));
}
}
void dijk()
{
int startDash = 1;
priority_queue<pii, vector<pii>, cmp> q;
q.push(make_pair(startDash, 0));
bool vis[MAXN << 1];
memset(vis, false, sizeof(vis));
memset(dis, 0x7f, sizeof(dis));
dis[startDash] = 0;
while (!q.empty())
{
pii dq = q.top();
q.pop();
if (vis[dq.first])
{
continue;
}
vis[dq.first] = true;
for (int i = g[dq.first]; i; i = b[i].next)
{
if (dis[dq.first] < INF && dis[b[i].to] > dis[dq.first] + b[i].cost)
{
dis[b[i].to] = dis[dq.first] + b[i].cost;
q.push(make_pair(b[i].to, dis[b[i].to]));
}
}
}
}

/*
10 28
1 1 1
2 2 1
3 2 1
4 7 0
4 8 1
4 4 1
4 3 1
5 3 1
6 6 0
6 5 1
6 3 0
6 4 0
6 7 1
7 2 1
7 4 0
7 3 1
8 5 1
8 2 0
8 4 1
9 4 0
9 3 0
9 10 1
9 7 1
9 6 1
10 9 1
10 6 0
10 7 1
10 5 0

*/

T4(注释里面的是没有优化的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
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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (500000 + 5)
#define INF (0x7ffffff)
#define LL long long
#define DD double
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
//#define GG

using namespace std;
typedef pair<int, int> pii;

struct moqueue// max
{
pii a[MAXN];
int cnt;
int CNT;
int p[MAXN];
int he, ta;
void init()
{
memset(a, 0, sizeof(a));
memset(p, 0, sizeof(p));
cnt = CNT = 0;
he = 1;
ta = 1;
}
pii ask()
{
return a[he + 1];
}
void ins(pii x)
{
while (he < ta && a[ta].second <= x.second)
{
--ta;
}
a[++ta] = x;
p[ta] = ++cnt;
}
void del()
{
if (he < ta && p[he + 1] == ++CNT)
{
++he;
}
}
bool empty()
{
return he >= ta;
}
}maxf;

int n;
int goal;
int fdis;
int ans;
int maxl;

pii a[MAXN];

void ef();
bool pd(int, int);
void solve();
int main()
{
#ifdef GG
freopen("jump.in", "r", stdin);
freopen("jump.out", "w", stdout);
#endif
scanf("%d%d%d", &n, &fdis, &goal);
LL sum = 0;
for (int i = 1; i <= n; i++)
{
scanf("%d%d", &a[i].first, &a[i].second);
sum += (a[i].second > 0 ? a[i].second : 0);
}
maxl = a[n].first;
if (sum < goal)
{
puts("-1");
return 0;
}
solve();
printf("%d", ans);
fclose(stdout);
fclose(stdin);
return 0;
}
void solve()
{
ef();
}
void ef()
{
int le = 1;
int ri = maxl + 1;
while (le < ri)
{
int mi = (le + ri) >> 1;
if (pd(max(1, fdis - mi), fdis + mi))
{
ans = mi;
ri = mi;
}
else
{
le = mi + 1;
}
}
}

/*
bool pd(int sm, int ga)
{
int re = 0;
int f[MAXN];
memset(f, -1, sizeof(f));
f[0] = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < i; j++)
{
if (a[j].first + ga >= a[i].first && a[j].first + sm <= a[i].first && f[j] != -1)
{
f[i] = max(f[j] + a[i].second, f[i]);
re = max(f[i], re);
}
}
}
return re >= goal;
}
*/

// first 璺濈, second 鍒嗘暟
bool pd(int sm, int ga)
{
int re = 0;
int f[MAXN];
memset(f, -1, sizeof(f));
f[0] = 0;
maxf.init();
int lastorder = 0;
for (int i = 1; i <= n; i++)
{
int ok = 1;
for (; lastorder < i; lastorder++)
{
if (a[lastorder].first + sm <= a[i].first)
{
if (f[lastorder] != -1)
maxf.ins(make_pair(a[lastorder].first, f[lastorder]));// 有问题...
}
else
{
ok = 0;
break;
}
}
pii fr = maxf.ask();
while (!maxf.empty() && fr.first + ga < a[i].first)
{
maxf.del();
fr = maxf.ask();
}
if (maxf.empty())
{
maxf.ins(make_pair(0, 0));
continue;
}
// lastorder += ok;
fr = maxf.ask();
if (fr.first + sm > a[i].first || fr.first + ga < a[i].first)
continue;
f[i] = fr.second + a[i].second;
re = max(re, f[i]);
}
return re >= goal;
}

/*
10 72 112
16 18
18 -5
45 32
95 43
126 46
168 42
214 14
256 4
302 6
347 0
*/

/*
7 4 10
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2
*/

By 写树状数组都能崩的 Cansult