2020-2021:teams:die_java:front_page_springtraining5
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:die_java:front_page_springtraining5 [2020/05/15 23:02] fyhssgss [B Operation] |
2020-2021:teams:die_java:front_page_springtraining5 [2020/05/23 12:10] (当前版本) fyhssgss [训练详情] |
||
|---|---|---|---|
| 行 3: | 行 3: | ||
| [[https://vjudge.net/contest/373163|比赛网址]] | [[https://vjudge.net/contest/373163|比赛网址]] | ||
| - | ===== 训练结果 ===== | + | ===== 训练详情 ===== |
| - | + | * 时间:2020-5-10 13:00~18:00 | |
| - | * rank:算了这个别说了 | + | * rank: |
| - | * 完成情况：3/6/13 | + | * 完成情况：''%%3/6/13%%'' |
| ===== 题解 ===== | ===== 题解 ===== | ||
| 行 24: | 行 24: | ||
| 开始想到线段树套线性基，发现时间和空间都爆了。后发现我们可以记录 $a[1... i]$ 的线性基，添加时候则从高位到低位，尽量用当前的基去替换之前的基，这样能使所有的基离r更近。查询的时候只用位置大于 $l$ 的基。 | 开始想到线段树套线性基，发现时间和空间都爆了。后发现我们可以记录 $a[1... i]$ 的线性基，添加时候则从高位到低位，尽量用当前的基去替换之前的基，这样能使所有的基离r更近。查询的时候只用位置大于 $l$ 的基。 | ||
| + | \\ | ||
| + | <hidden B> | ||
| <code cpp> | <code cpp> | ||
| #include<iostream> | #include<iostream> | ||
| 行 109: | 行 111: | ||
| } | } | ||
| </code> | </code> | ||
| + | </hidden> | ||
| + | \\ | ||
| ===== D Vacation ===== | ===== D Vacation ===== | ||
| solved by wxg | solved by wxg | ||
| 行 119: | 行 123: | ||
| 可以想象，最后几辆车一定是贴在一起通过的，我们只需要枚举 $x$ ，计算最后 $x$ 俩车贴贴后通过时间，取一个最大值即可。 | 可以想象，最后几辆车一定是贴在一起通过的，我们只需要枚举 $x$ ，计算最后 $x$ 俩车贴贴后通过时间，取一个最大值即可。 | ||
| + | \\ | ||
| + | <hidden D> | ||
| <code cpp> | <code cpp> | ||
| #include<iostream> | #include<iostream> | ||
| 行 155: | 行 160: | ||
| } | } | ||
| </code> | </code> | ||
| + | </hidden> | ||
| + | \\ | ||
| ===== E Path ===== | ===== E Path ===== | ||
| 行 166: | 行 173: | ||
| 求出最短路径的新图，可以看出答案为最小割 | 求出最短路径的新图，可以看出答案为最小割 | ||
| + | \\ | ||
| + | <hidden E> | ||
| <code cpp> | <code cpp> | ||
| #include<iostream> | #include<iostream> | ||
| 行 301: | 行 310: | ||
| } | } | ||
| </code> | </code> | ||
| + | </hidden> | ||
| + | \\ | ||
| ===== F Typewriter ===== | ===== F Typewriter ===== | ||
| 行 323: | 行 334: | ||
| 我们可以构建 $s[1... j]$ 的后缀自动机，当 dp 到 $i$ 时，我们在后缀自动机上匹配 $s[i]$ ,若匹配长度与 $j$ 的和大于等于 $i$ ,说明 $j$ 不用增加，反之则增加 $j$ 直到大于等于为止。 | 我们可以构建 $s[1... j]$ 的后缀自动机，当 dp 到 $i$ 时，我们在后缀自动机上匹配 $s[i]$ ,若匹配长度与 $j$ 的和大于等于 $i$ ,说明 $j$ 不用增加，反之则增加 $j$ 直到大于等于为止。 | ||
| + | \\ | ||
| + | <hidden f> | ||
| <code cpp> | <code cpp> | ||
| #include<iostream> | #include<iostream> | ||
| 行 418: | 行 430: | ||
| } | } | ||
| </code> | </code> | ||
| + | </hidden> | ||
| + | \\ | ||
| ===== I String ===== | ===== I String ===== | ||
| 行 431: | 行 445: | ||
| 然后就完了。【很不明白比赛是怎么没调出来，，】 | 然后就完了。【很不明白比赛是怎么没调出来，，】 | ||
| + | \\ | ||
| + | <hidden I> | ||
| <code cpp> | <code cpp> | ||
| #include<algorithm> | #include<algorithm> | ||
| 行 519: | 行 534: | ||
| } | } | ||
| </code> | </code> | ||
| + | </hidden> | ||
| + | \\ | ||
| ===== K Function ===== | ===== K Function ===== | ||
| 行 555: | 行 572: | ||
| 注意，读入要用%%__%%int128,但是在开数组的时候都要开int，否则会爆空间。 | 注意，读入要用%%__%%int128,但是在开数组的时候都要开int，否则会爆空间。 | ||
| + | \\ | ||
| + | <hidden K> | ||
| <code cpp> | <code cpp> | ||
| #include<bits/stdc++.h> | #include<bits/stdc++.h> | ||
| 行 639: | 行 658: | ||
| </code> | </code> | ||
| + | </hidden> | ||
| + | \\ | ||
| ===== 训练实况 ===== | ===== 训练实况 ===== | ||
2020-2021/teams/die_java/front_page_springtraining5.1589554930.txt.gz · 最后更改: 2020/05/15 23:02 由 fyhssgss
