抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

七つの海

今日、海を見た。もう怖くない

按照惯例还是先挂出来一些链接。

比赛地址:https://www.luogu.com.cn/contest/29004

官方题解:https://www.zhihu.com/question/388180965/answer/1163540927

但是已经不能在上面的比赛链接里上交题目了,所有的题目已经加入公共题库了,所以你可以搜索题目的名字然后在公共题库中找到它们;好像直接点进去就会自动切到公共题库,还行。

两个黄题没有做出来,这不太行啊。

A - 暴力模拟

暴力模拟,语言题。但是数据范围给的有些歧义。

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
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
using longs = long long;
using longd = long double;
using ulongs = unsigned long long;

const int inf = 0x3f3f3f3f;
const longs INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;

const char graph[100][100] =
{
R"(...........................,]]OOO@@@@OOO]`........)",
R"(....................,]OO@@@@@@@@@@@@@@@@@@@@O`....)",
R"(................./O@@@@@@@@@@@@@@@@@@@@@@@@@@@@^..)",
R"(............../O@@@@@@@@@@@@@@@OOOOOOO@@@@@@@@@@@.)",
R"(..........,/@@@@@@@@@@@@O/[.............[O@@@@@@@\)",
R"(........,O@@@@@@@@@@O/`..................,O@@@@@@O)",
R"(.......O@@@@@@@@@O`......]OO@@@O\`........O@@@@@@@)",
R"(.....,O@@@@@@@@/`.....]O@@@@@@@@@@^.......O@@@@@@@)",
R"(...,/@@@@@@@O/...../@@@@@@@@@@@@@@O....../@@@@@@@0)",
R"(..=@@@@@@@O`...../@@@@@@@@@@@@@@@@^.....O@@@@@@@O.)",
R"(./@@@@@@@/......O@@@@@@@@@@@@@@@O`..../@@@@@@@@O..)",
R"(=@@@@@@@O......O@@@@@@@@@@@@@@@^....O@@@@@@@@@O...)",
R"(O@@@@@@@^.....=@@@@@@@@@@@@@O[..../@@@@@@@@@O`....)",
R"(@@@@@@@O.......\@@@@@@@@O[...../O@@@@@@@@@O`......)",
R"(@@@@@@@@^.........[`.......]OO@@@@@@@@@@O`........)",
R"(O@@@@@@@@O\............]/@@@@@@@@@@@@O/...........)",
R"(=@@@@@@@OOOoo`........O@@@@@@@@@@@@/`.............)",
R"(..\OOOOO*,`*..........O@@@@@@@@@O`................)",
R"(.....,[[..............O@@@@@@O`...................)",
R"(......................O@@@@@@O....................)"
};

char campus[2060][2060];

int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);

int n, h, w;
int x, y, r;

auto initfill = [&]
{
for (int i = 0; i < h; ++ i)
{
for (int j = 0; j < w; ++ j)
campus[i][j] = '.';
campus[i][w] = '\0';
}
};

auto paint = [&](int x, int y)
{
for (int i = x, ii = 0; i < h; ++ i, ++ ii)
{
if (ii >= 20) break;
if (i < 0) continue;
for (int j = y, jj = 0; j < w; ++ j, ++ jj)
{
if (jj >= 50) break;
if (graph[ii][jj] == '.') continue;
if (j < 0) continue;
campus[i][j] = graph[ii][jj];
}
}
};

auto paint180 = [&](int x, int y)
{
for (int i = x, ii = 19; i < h; ++ i, -- ii)
{
if (ii < 0) break;
if (i < 0) continue;
for (int j = y, jj = 49; j < w; ++ j, -- jj)
{
if (jj < 0) break;
if (graph[ii][jj] == '.') continue;
if (j < 0) continue;
campus[i][j] = graph[ii][jj];
}
}
};

cin >> n >> h >> w;
initfill();
while (n --)
{
cin >> x >> y >> r;
if (r) paint180(x,y);
else paint(x,y);
}

for (int i = 0; i < h; ++ i)
cout << campus[i] << endl;

return 0;
}

或者说是贴标赞助题好一些?

B - 屑游戏

脑筋急转弯。考虑为0的边界情况之后,防御塔留一手给英雄,要是能鲨咯那就完事。

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 <cstring>
#include <algorithm>

using namespace std;
using longs = long long;
using longd = long double;
using ulongs = unsigned long long;

const int inf = 0x3f3f3f3f;
const longs INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;

int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);

int t; cin >> t;
longs h, x, y;
while (t --)
{
cin >> h >> x >> y;
if (!y) {cout << "No" << endl; continue;}
else if (!x) {cout << "Yes" << endl; continue;}
longs tt = h / x + 1;
longs mm = h % x;
if (!mm) mm += x, -- tt;
if (mm / y + bool(mm % y) <= tt) cout << "Yes" << endl;
else cout << "No" << endl;
}

return 0;
}

记得开long long

C - 加大范围

比赛时候的数据只要暴力模拟就行了,但是需要使用更优的算法:最优的算法是O(n³)的

朴素的想法:枚举重心的高度和所在坐标,然后判断每个位置是否可行,这是跑不满的五次方算法;如果把遍历获得所需操作数的行为使用二维前缀和/差分优化的话就可以压到四次方;如果使用二维RMQ问题的解决方法,判断一个方形区域是否都大于某个值,就可以压到最优复杂度。

1

D - 迫真最短路

又是一个暴力。传送门问题往往是先最短路,然后枚举传送门的位置。这个题目只不过就是题面有些吓人,但是数据范围是小的可怜的100,就算是四次方算法也是可以接受的(

因为要求出所有的最短路之和,所以要用Floyd;然后再加上暴力枚举传送门位置,暴力枚举求出题目说的和,维护它的最小值即可。

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
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
using longs = long long;
using longd = long double;
using ulongs = unsigned long long;

const int inf = 0x3f3f3f3f;
const longs INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;

longs dis[105][105], ans = INF;
int n, m;

inline void floyd()
{
for (int k = 1; k <= n; ++ k) // Floyd:中转点要写在外面
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= n; ++ j)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}

longs sum(int ii, int jj)
{
longs tmp = 0;
for (int i = 1; i <= n; ++ i)
for (int j = i+1; j <= n; ++ j)
tmp += min(
dis[i][j],
min(
dis[i][ii] + dis[jj][j],
dis[i][jj] + dis[ii][j]
));
return tmp;
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);

cin >> n >> m;
memset(dis, 0x3f, sizeof dis);
while (m --)
{
int u, v, w;
cin >> u >> v >> w;
dis[u][v] = dis[v][u] = w;
}
for (int i = 1; i <= n; ++ i)
dis[i][i] = 0;
floyd();
for (int i = 1; i <= n; ++ i)
for (int j = i+1; j <= n; ++ j)
{
longs tmp = sum(i, j);
ans = min(tmp, ans);
}
cout << ans << endl;

return 0;
}

Floyd算法三重循环的中转点在最外层

E - 上课

本 次 比 赛 唯 一 的 一 个 绿 题

做法很多。我是找到所有连续的课程作为断点,然后对于每个连续的区间扫描一遍,记录扫描过的区域不同课出现的次数,然后加算贡献的。有点像是在乱搞,复杂度O(n)。

事实上这个题还可以DP,也可以莫队(?),还可以反向思维:也就是先算出所有大于l的点对,在用双指针法减掉各种不太行的情况,时间复杂度都是O(n)的。

贴的代码不是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
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
#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <algorithm>

using namespace std;
using longs = long long;
using longd = long double;
using ulongs = unsigned long long;

const int inf = 0x3f3f3f3f;
const longs INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;

const int N = 5e5+5;
int n, l, a[N], c[N];
vector<pair<int,int>> vv;
map<int,int> mm;

int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);

int t; cin >> t;

auto jump = [&]
{
int s = 1, t = 0;
for (int i = 1; i < n; ++ i)
{
if (c[i] != c[i+1])
{
a[i] = i+1;
t = i;
}
else
{
if (s != t) vv.emplace_back(s, i);
int j = i+1;
while (c[++ j] == c[i]);
for (int k = i; k < j; ++ k)
a[k] = j;
i = j - 1; s = t = j - 1;
}
}
if (s != n) vv.emplace_back(s, n);
a[n] = 0;
};

while (t --)
{
vv.clear();
cin >> n >> l;
for (int i = 1; i <= n; ++ i)
cin >> c[i];
if (n == 1 || n < l) cout << 0 << endl;
else
{
jump();
longs ans = 0;
for (auto ii : vv)
{
if (ii.second - ii.first + 1 < l) continue;
int lim = ii.second - l + 1, noko = 0;
for (int xx = ii.first + l - 1; xx <= ii.second; ++ xx)
{
++ mm[c[xx]];
++ noko;
}
for (int xx = ii.first; xx <= lim; ++ xx)
{
ans += noko - mm[c[xx]];
-- noko;
-- mm[c[xx + l - 1]];
}
mm.clear();
}
cout << ans << endl;
}
}

return 0;
}

然后就是DP版本:

1

写了半天,我紫菜(

后记

kkksc03:什么嘛,我的洛谷比赛系统还挺好用的嘛。

但是非专业性质的比赛打成这样,属实不太行。引人深思。

评论