2020-2021:teams:die_java:front_page_springtraining5
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:die_java:front_page_springtraining5 [2020/05/15 22:28] fyhssgss |
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%%'' |
| ===== 题解 ===== | ===== 题解 ===== | ||
| 行 13: | 行 13: | ||
| 补题 | 补题 | ||
| - | ==== 题意 ==== | + | === 题意 === |
| 给了一个序列，要求实现两种操作 | 给了一个序列，要求实现两种操作 | ||
| 行 22: | 行 22: | ||
| === 题解 === | === 题解 === | ||
| - | 开始想到线段树套线性基，发现时间和空间都爆了。后发现我们可以记录 $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 ===== | ||
| solved by wxg | solved by wxg | ||
| - | ==== 题意 ==== | + | === 题意 === |
| 给了一个字符串，你现在要花最小代价构造出该字符串，有两种构造方法 | 给了一个字符串，你现在要花最小代价构造出该字符串，有两种构造方法 | ||
| 行 316: | 行 327: | ||
| - $dp[i]=dp[i-1]+p$ | - $dp[i]=dp[i-1]+p$ | ||
| - | - $dp[i]=dp[j]+q$ , $j$ 为满足 $s[1...j]$ 中存在 $s[j+1...i]$ 的子串 | + | - $dp[i]=dp[j]+q$ , $j$ 为满足 $s[1... j]$ 中存在 $s[j+1... i]$ 的子串 |
| 问题是 $j$ 怎么求？ | 问题是 $j$ 怎么求？ | ||
| 行 322: | 行 333: | ||
| 首先随着 $i$ 增加，$j$ 是单调的 | 首先随着 $i$ 增加，$j$ 是单调的 | ||
| - | 我们可以构建 $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 ===== | ||
| 补题 by hxm | 补题 by hxm | ||
| - | ==== 题意 ==== | + | === 题意 === |
| 给定一个只包含小写字母的字符串，要求选出一个长度为$K$的子序列，满足字典序最小，同时子序列中每个字母的出现次数都在一个各自给定的范围$[L,R]$内 | 给定一个只包含小写字母的字符串，要求选出一个长度为$K$的子序列，满足字典序最小，同时子序列中每个字母的出现次数都在一个各自给定的范围$[L,R]$内 | ||
| 行 431: | 行 445: | ||
| 然后就完了。【很不明白比赛是怎么没调出来，，】 | 然后就完了。【很不明白比赛是怎么没调出来，，】 | ||
| - | + | \\ | |
| - | <code> | + | <hidden I> |
| + | <code cpp> | ||
| #include<algorithm> | #include<algorithm> | ||
| #include<iostream> | #include<iostream> | ||
| 行 519: | 行 534: | ||
| } | } | ||
| </code> | </code> | ||
| + | </hidden> | ||
| + | \\ | ||
| ===== K Function ===== | ===== K Function ===== | ||
| 补题 by fyh | 补题 by fyh | ||
| - | ==== 题意 ==== | + | === 题意 === |
| $$ | $$ | ||
| 行 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.1589552892.txt.gz · 最后更改: 2020/05/15 22:28 由 fyhssgss
