2020-2021:teams:die_java:weeksummary8
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:die_java:weeksummary8 [2020/07/30 13:00] fyhssgss 创建 |
2020-2021:teams:die_java:weeksummary8 [2020/07/31 16:53] (当前版本) wxg [王兴罡] |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| ====== Update on Wiki ====== | ====== Update on Wiki ====== | ||
| * 创建了本周训练周报 | * 创建了本周训练周报 | ||
| - | * 创建了暑期牛客第三次集训界面 | ||
| - | * 创建了暑期牛客第四次集训界面 | ||
| * 创建了暑期牛客第五次集训界面 | * 创建了暑期牛客第五次集训界面 | ||
| + | * 创建了暑期牛客第六次集训界面 | ||
| ---- | ---- | ||
| ====== 团队训练 ====== | ====== 团队训练 ====== | ||
| - | [[front_page_SummerTrain3|2020牛客暑期多校训练营（第三场）]] | + | [[front_page_SummerTrain6|2020牛客暑期多校训练营（第五场）]] |
| - | \\ [[front_page_SummerTrain4|2020牛客暑期多校训练营（第四场）]] | + | \\ [[front_page_SummerTrain7|2020牛客暑期多校训练营（第六场）]] |
| - | \\ [[front_page_SummerTrain5|2020-2021 BUAA ICPC Team Supplementary Training 01]] | + | |
| ---- | ---- | ||
| ====== 每周推荐 ====== | ====== 每周推荐 ====== | ||
| - | fyh:cf658div2第五题 | + | fyh:牛客第五场A题 |
| - | \\ 题目大意是给你一个长度为2n的排列，问能否根据归并排序的规则将两个长度为n的不一定有序的序列进行合并 | + | \\ 题目大意： |
| - | \\ 题目做法：发现一个性质：一个数后面所有比他小的都应该属于同一个序列，然后进行区间划分，之后做背包即可。 | + | 有一个$n$个点$m$条边的带权图，你一开始在$1$号点，你要按顺序完成$k$个任务，第$i$个任务是先去$a_i$再走到$b_i$。当你走到一个点上的时候，你可以在这个点创建一个传送门。当同时存在两个传送门的时候， 你可以在传送门之间不耗代价地传送。如果已经存在了两个传送门，你想再创建一个，就必须选择之前 的一个传送门关掉（关掉这个操作不耗时间，并且是远程操作，不需要走过去）。问完成所有任务的最 短总行走距离。 |
| - | \\ 推荐理由：之前我在做的时候只是发现一个依次递减一定属于一个序列，导致最后的DP设计状态十分诡异，转移会更加诡异。 | + | \\ tag: 最短路，DP，DP状态优化 |
| + | \\ 做法:先考虑最暴力的DP，$f[i][u][a][b]$表示当前已经完成了前$i$个结点，当前在$u$，俩传送门分别在$a，b$的最小距离，这个玩意得通过Dijkstra转移。然后发现我们没有必要把俩传送门位置都记录，因为剩下一个我们就扔在脚底下就能完全包含，还得通过Dijkstra转移。继续想，直接把$u$扔掉，当前已经完成了前$i$个节点，传送门在$a$,那么我们考虑从$i$走到$i+1$有几种方式呢？我们可以直接走过去，还可以在脚下丢个传送门再瞬移到另一个传送门再去$i+1$。还可以考虑转移到$i+1$的时候传送门到$b$了，可以从$i$瞬移到$a$,然后走到$b$,在$b$处放下传送门，最后再走到$i+1$,还可以直接从$i$走到$b$放下传送门，然后再瞬移到$a$再去$i+1$或者直接走去$i+1$。复杂度$O(2k*N^2)$ | ||
| + | \\ comment:考虑优化状态的时候要想到什么是真正有用的 | ||
| - | wxg: | + | wxg: |
| - | [ZJOI2015]诸神眷顾的幻想乡 | + | Educational Codeforces Round 92 (Rated for Div. 2) ECalendar Ambiguity |
| + | \\ 题目大意：一年有 $m$ 个月，每个月 $d$ 天，一周是 $k$ 天，问你有多少点对（a，b），$a$ 月 $b$ 日和 $b$ 月 $a$ 日在按星期算是同一天 | ||
| + | \\ tag: 数学 | ||
| + | \\ 做法: (a,b),(b,a) 相差的天数是 $(b-a)(k-1)$ 天，我们只要保证 $(b-a)(k-1)%w = 0$ 即可，我们只需保证$b-a$ 是 $\frac{w}{gcd(w,d-1)}$ 的倍数，同时保证 $1 \le a \le b \le min(d,m)$ | ||
| - | tag：树上问题，后缀自动机 | + | 设$\frac{w}{gcd(w,d-1)}$ 为 $k$ ,答案就是 $\sum^{ik \le min(d,m)-1}_{i=1}{min(d,m)-ik}$ |
| + | \\ comment: 把点对问题转化为 $b-a$ 的计算同时考虑各种边界问题 | ||
| - | 题意&题解[[https://www.cnblogs.com/waing/p/13373174.html]] | + | hxm:M-SOLUTIONS Programming Contest 2020 F题 |
| - | + | \\ 题目大意：二维平面有若干架飞机($n \leq 10^5$)，以相同速度分别沿四个方向中的一个方向飞行，问最早什么时候会有飞机相撞？ | |
| - | comment：把树上的可以拐弯的路径转化为深度从大往小的路径，便于统计不同字串 | + | \\ tag:转化，二分 |
| - | + | \\ 做法:相向而行的飞机相撞很容易判断，主要讨论交叉相撞的。以向上和向右的飞机为例，如果两个飞机在某个位置相撞那么其实可以把这个相撞的位置上移到一个特定的直线上，同时将向右飞行的飞机向左平移等同于其距离该直线的距离，这样转化了，两者还是会相撞，但相撞点移到了这条直线。通过这种方法，我们可以把向右移动的飞机都移动到一条直线上，把将问题降维了，对于每个向上的飞机只需在上面二分查找即可。其它方向交叉类似。 | |
| - | hxm: | + | \\ comment:问题降维 |
| - | [[https://www.luogu.com.cn/problem/P4249|[WC2007]剪刀石头布]] [[http://112.74.186.118/doku.php?id=2020-2021:teams:die_java:weeksummary7_wc2007|题解]] | + | |
| - | + | ||
| - | comment：将选取三元环的问题转化为最小化式子，通过网络流建模 | + | |
| ---- | ---- | ||
| 行 38: | 行 39: | ||
| ====== 傅云濠 ====== | ====== 傅云濠 ====== | ||
| - | 补题：牛客第四场A | + | 补题：牛客第五场ABK 牛客第六场A |
| - | \\ 比赛：Codeforces Round #657 (Div. 2) 因突然有事开始挂机 | + | \\ 比赛：[[https://www.cnblogs.com/FYH-SSGSS/p/13408123.html|Codeforces Round #660 (Div. 2)]] |
| - | \\ 比赛：Codeforces Round #658 (Div. 2) | + | \\ 比赛：[[https://www.cnblogs.com/FYH-SSGSS/p/13408105.html|Educational Codeforces Round 92 (Rated for Div. 2)]] |
| - | \\ 研究了拟阵 | + | \\ 比赛：M-SOLUTIONS Programming Contest 2020 |
| + | \\ 整理板子： | ||
| ---- | ---- | ||
| ====== 王兴罡 ====== | ====== 王兴罡 ====== | ||
| - | + | 整理板子，cf的Educational Codeforces Round 92，及补了第五场的 H | |
| - | 补题 第四场 A，C | + | |
| - | \\ 整理各种字符串模板。 | + | |
| ---- | ---- | ||
| ====== 黄旭民 ====== | ====== 黄旭民 ====== | ||
| - | 补题： 2020牛客暑期多校训练营（第四场） [[https://www.cnblogs.com/Mychael/p/13372928.html|D]] | + | 补题：牛客第五场C、M-SOLUTIONS Programming Contest 2020 F题 |
| - | \\ 整理了网络流、费用流模板，进行了复习 | + | \\ 比赛：M-SOLUTIONS Programming Contest 2020 |
| + | \\ 整理板子： | ||
2020-2021/teams/die_java/weeksummary8.1596085223.txt.gz · 最后更改: 2020/07/30 13:00 由 fyhssgss
