翻车笔记_ 某次辣鸡模拟赛 [奶牛, 翻车, 其实并没有什么算法]

今天爆零了


考了几道SB题…然而我比题目还SB就爆零了…
也许是下午状态不太好…也许是睡眠不足…也许是…
癌, 还是自己菜…
不知道怎么…考完试题目到似乎都很好做了…也许是潜意识里听见他们讨论做法了?
癌…_(:з」∠)_

懵逼的 题目

T1

usaco2016open bronze3 reduce
emmm…一道o(1)的SB题…被我写了200line+然后调不出来就弃了…(1.5h passed…
删除的奶牛一定在原先不删的时候最小的边界上…枚举哪个边界删几个就好了…

T2

传送至 Luogu

普通的区间DP…四重循环那叫一个暴力…然后考试的时候也没仔细看…就输了个样例…GG

1
2
bool f[i][j][k] // 在区间[i, j]是否能达到k这个值...
f[i][j][x] ||= (f[i][k][x - 1] && f[k + 1][j][x - 1]) //...

T3

传送至 Luogu

…本来以为这题能A的…离线倒序转成并查集加点…然后看任意一个点的祖先的rank是否 == 已经加入的点数…
结果没有考虑两个点已经连在一起的情况(就是祖宗一样)…结果卡成样例分…

T4

传送至 Luogu

也是非常水的一道题…但是不知道为什么考试的时候一头乱麻什么思路也没有…
刚考完就知道怎么做了…
一个类似于滑动窗口的东西…而且以前好像还做过…GG
先排序…
写一个队列…先从左向右push, 如果push的节点值比队首的节点值大k, 就弹队列…记录f[i] = max(q.size(), f[i - 1]), 就代表这个点到开头能放的最大的允许的钻石数
然后在从右向左跑一遍…
最后遍历一下就行了…

T5

传送至 Luogu

…没想到T5这么水…然后就想了一个奇奇怪怪的dijk…结果又是样例分…GG
其实就是枚举修改最短路上的哪条边…然后暴力跑最短路更新答案…GG
因为最短路的边个数最多是n - 1条…所以怎么也T不掉的…
改的时候WA90了一晚上…刚刚发现是转反向边的时候没加括号…^的优先级没有+高…GG
记住了反向边是这样的…

1
rev(a) (((a - 1) ^ 1) + 1) // 之前是 ((a - 1) ^ 1 + 1)....结果一直Wa...GG

然后…5个题全是样例分…

总之
这次考试的题…其实算法很简单..或者根本没有算法…但是确实我没有想到…
一个是思路不够开阔…一个是做题的时候太没有紧迫感了…是不是被数据结构弄傻了啊…
以后得听家父的话计着时间做题了…然后多做一做奶牛题提高一下姿势水平…

沙茶的 代码

T1

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

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN (50000 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define INF (0x7fffffff)
using namespace std;
struct cow
{
int x, y, bh;
}a[MAXN], b[MAXN], c[MAXN], d[MAXN];
int ans = INF;
int n;
bool cmpd(cow, cow);
bool cmpu(cow, cow);
bool cmpl(cow, cow);
void solve();
int cx(int, int, int, int);
int main()
{
freopen("reduce.in", "r", stdin);
freopen("reduce.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d%d", &a[i].x, &a[i].y);
a[i].bh = i;
b[i] = c[i] = d[i] = a[i];
}
solve();
printf("%d", ans);
return 0;
}
bool cmpd(cow x, cow y)
{
return x.y < y.y;
}
bool cmpu(cow x, cow y)
{
return x.y > y.y;
}
bool cmpl(cow x, cow y)
{
return x.x < y.x;
}
bool cmpr(cow x, cow y)
{
return x.x > y.x;
}
void solve()
{
sort(a + 1, a + n + 1, cmpu);
sort(b + 1, b + n + 1, cmpd);
sort(c + 1, c + n + 1, cmpl);
sort(d + 1, d + n + 1, cmpr);
for (int i = 0; i <= 3; i++)
{
for (int j = 0; i + j <= 3; j++)
{
for (int k = 0; k + i + j <= 3; k++)
{
for (int w = 0; w + k + i + j <= 3; w++)
{
ans = min(ans, cx(i, j, k, w));
}
}
}
}
}
int cx(int u, int dow, int l, int r)
{
int re;
bool v[MAXN];
memset(v, false, sizeof(v));
int maxx = d[1].x, minx = c[1].x, maxy = a[1].y, miny = b[1].y;
for (int i = 1; i <= u; i++)
{
if (!v[a[i].bh])
{
v[a[i].bh] = true;
}
else
{
u++;
}
}
for (int i = 1; i <= dow; i++)
{
if (!v[b[i].bh])
{
v[b[i].bh] = true;
}
else
{
dow++;
}
}
for (int i = 1; i <= l; i++)
{
if (!v[c[i].bh])
{
v[c[i].bh] = true;
}
else
{
l++;
}
}
for (int i = 1; i <= r; i++)
{
if (!v[d[i].bh])
{
v[d[i].bh] = true;
}
else
{
r++;
}
}
for (int i = 1; i <= n; i++)
{
if (!v[a[i].bh])
{
maxy = a[i].y;
}
}
for (int i = 1; i <= n; i++)
{
if (!v[b[i].bh])
{
miny = b[i].y;
}
}
for (int i = 1; i <= n; i++)
{
if (!v[c[i].bh])
{
minx = c[i].x;
}
}
for (int i = 1; i <= n; i++)
{
if (!v[d[i].bh])
{
maxx = d[i].x;
}
}
re = (maxx - minx) * (maxy - miny);
return re;
}

/*
6
1 1
7 8
10 9
8 12
4 100
50 7

*/

T2

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 MAXN (248 + 5)
#define INF (40 + 8)
using namespace std;
int n;
int a[MAXN];
bool f[MAXN][MAXN][INF];
void solve();
int main()
{
freopen("248.in", "r", stdin);
freopen("248.out", "w", stdout);
scanf("%d", &n);
memset(f, false, sizeof(f));
int maxa = 0;
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
maxa = max(a[i], maxa);
f[i][i][a[i]] = true;
}
solve();
for (int i = INF; i >= 0; i--)
{
for (int le = 1; le <= n; le++)
{
for (int ri = le; ri <= n; ri++)
{
if (f[le][ri][i])
{
printf("%d\n", i);
return 0;
}
}
}
}
printf("%d", maxa);
fclose(stdin);
fclose(stdout);
return 0;
}
void solve()
{
for (int i = 1; i <= n; i++)
{
for (int le = 1; le + i <= n; le++)
{
int ri = le + i;
for (int k = le; k < ri; k++)
{
for (int z = 0; z <= INF; z++)
{
if (f[le][k][z] && f[k + 1][ri][z])
f[le][ri][z + 1] = true;
}
}
}
}
}

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (200000 + 5)
#define MAXM (200000 + 5)
#define INF (0x7ffffff)
#define LL long long
#define DD double
#define pii pair<int, int>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define mabs(a) ((a) > 0 ? (a) : (-(a)))
using namespace std;
struct edg
{
int from;
int to;
int next;
} b[MAXM << 1];
int cntb = 0;
int g[MAXN];

struct bcj
{
int fa;
int rank;
} f[MAXN];

int n;
int m;
bool ans[MAXN];
int a[MAXN];
int find(int);
void uni(int, int);
void adn(int, int);
void solve();
int main()
{
freopen("closing.in", "r", stdin);
freopen("closing.out", "w", stdout);
memset(ans, false, sizeof(ans));
scanf("%d%d", &n, &m);
int srx, sry;
for (int i = 1; i <= n; i++)
{
f[i].fa = i;
f[i].rank = 0;
}
for (int i = 1; i <= m; i++)
{
scanf("%d%d", &srx, &sry);
adn(srx, sry);
adn(sry, srx);
}
for (int i = n; i >= 1; i--)
{
scanf("%d", &a[i]);
}
solve();
for (int i = n; i >= 1; i--)
{
if (ans[i])
puts("YES");
else
puts("NO");
}
fclose(stdin);
fclose(stdout);
return 0;
}
void adn(int from, int to)
{
b[++cntb].next = g[from];
b[cntb].from = from;
b[cntb].to = to;
g[from] = cntb;
}
void uni(int x, int y)
{
int fx = find(x);
int fy = find(y);
if (f[fx].rank > f[fy].rank)
{
f[fy].fa = fx;
f[fx].rank += f[fy].rank;
}
else
{
f[fx].fa = fy;
f[fy].rank += f[fx].rank;
}
}
int find(int x)
{
return ((x == f[x].fa) ? (x) : (f[x].fa = find(f[x].fa)));
}
void solve()
{
for (int i = 1; i <= n; i++)
{
f[a[i]].rank = 1;
for (int j = g[a[i]]; j; j = b[j].next)
{
if (f[b[j].to].rank)
{
if (find(a[i]) != find(b[j].to)) // GG
uni(a[i], b[j].to);
}
}
if (f[find(a[i])].rank == i)
{
ans[i] = true;
}
}
}

/*
4 3
1 2
2 3
3 4
3
4
1
2
*/

T4

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (50000 + 5)
#define INF (0x7ffffff)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
int n;
int le[MAXN];
int ri[MAXN];
int a[MAXN];
int k;
int ans;
bool cmp(const int x, const int y)
{
return x < y;
}
void init();
void solve();
int main()
{
freopen("diamond.in", "r", stdin);
freopen("diamond.out", "w", stdout);
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
sort(a + 1, a + n + 1, cmp);
init();
solve();
printf("%d", ans);
return 0;
}
void init()
{
queue<int> q;
for (int i = 1; i <= n; i++)
{
q.push(a[i]);
if (a[i] > q.front() + k)
{
q.pop();
}
le[i] = max(le[i - 1], q.size());
}
while (!q.empty())
q.pop();
for (int i = n; i >= 1; i--)
{
q.push(a[i]);
if (a[i] + k< q.front())
{
q.pop();
}
ri[i] = max(ri[i + 1], q.size()); // 可以向后延伸多少
}
}
void solve()
{
for (int i = 1; i < n; i++)
{
ans = max(ans, ri[i + 1] + le[i]);
}
}

T5

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#define MAXN (250 + 5)
#define MAXM (250000 + 5)
#define INF (0x7ffffff)
#define pii pair<int, int>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define rev(a) ((a - 1) ^ 1 + 1)
using namespace std;
struct cmp
{
bool operator () (const pii x, const pii y)
{
return x.second > y.second;
}
};
struct edg
{
int from;
int to;
int cost;
int next;
}b[MAXM << 1];
int cntb = 0;
int g[MAXN];

int n;
int m;
int ans;
int pre[MAXN];
int dis[MAXN];
void solve();
void dijk(int);
void adn(int, int, int);
int main()
{
freopen("rblock.in", "r", stdin);
freopen("rblock.out", "w", stdout);
scanf("%d%d", &n, &m);
int srx, sry, srz;
for (int i = 1; i <= m; i++)
{
scanf("%d%d%d", &srx, &sry, &srz);
adn(srx, sry, srz);
adn(sry, srx, srz);
}
solve();
printf("%d", ans);
return 0;
}
void adn(int from, int to, int cost)
{
b[++cntb].next = g[from];
b[cntb].from = from;
b[cntb].to = to;
b[cntb].cost = cost;
g[from] = cntb;
}
void dijk(int start)
{
bool v[MAXN];
memset(dis, 0x7f, sizeof(dis));
memset(v, false, sizeof(v));
priority_queue<pii, vector<pii>, cmp> q;
dis[start] = 0;
q.push(make_pair(start, dis[start]));
while (!q.empty())
{
pii dq = q.top();
q.pop();
if (v[dq.first])
continue;
v[dq.first] = true;
for (int i = g[dq.first]; i; i = b[i].next)
{
if (dis[b[i].to] > dis[dq.first] + b[i].cost)
{
pre[b[i].to] = i;
dis[b[i].to] = dis[dq.first] + b[i].cost;
q.push(make_pair(b[i].to, dis[b[i].to]));
}
}
}
}
void solve()
{
int ch[MAXN];
dijk(1);
for (int i = 1; i <= n; i++)
{
ch[i] = pre[i];
}
int dis0 = dis[n];
for (int i = n; i != 1; i = b[ch[i]].from)
{
b[ch[i]].cost <<= 1;
// b[rev(ch[i])].cost <<= 1;
dijk(1);
ans = max(ans, dis[n] - dis0);
b[ch[i]].cost >>= 1;
// b[rev(ch[i])].cost >>= 1;
}
}

By 又双叒叕倒数的 Cansult