2020-2021:teams:die_java:front_page_summertrain6
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:die_java:front_page_summertrain6 [2020/07/31 13:57] fyhssgss 创建 |
2020-2021:teams:die_java:front_page_summertrain6 [2020/07/31 17:10] (当前版本) fyhssgss [训练结果] |
||
|---|---|---|---|
| 行 7: | 行 7: | ||
| * 时间:''2020-07-25 12:00~17:00'' | * 时间:''2020-07-25 12:00~17:00'' | ||
| * rank:''181/1116'' | * rank:''181/1116'' | ||
| - | * 完成情况：''4/7/11'' | + | * 完成情况：''4/9/11'' |
| ===== 题解 ===== | ===== 题解 ===== | ||
| 行 23: | 行 23: | ||
| 先考虑最暴力的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)$ | 先考虑最暴力的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)$ | ||
| - | <code cpp> | + | <hidden 代码><code cpp> |
| #include<bits/stdc++.h> | #include<bits/stdc++.h> | ||
| using namespace std; | using namespace std; | ||
| 行 72: | 行 72: | ||
| } | } | ||
| - | </code> | + | </code></hidden> |
| ===== B.Graph ===== | ===== B.Graph ===== | ||
| 行 89: | 行 89: | ||
| 由于异或的神奇性质，可以发现按照上述操作的话任意两点的边权都是由他们到根上的异或路径再异或得到的，也就是说是固定的，于是我们把到根的异或和变成点的点权，这个问题就变成了很经典的Xor-MST问题了。 | 由于异或的神奇性质，可以发现按照上述操作的话任意两点的边权都是由他们到根上的异或路径再异或得到的，也就是说是固定的，于是我们把到根的异或和变成点的点权，这个问题就变成了很经典的Xor-MST问题了。 | ||
| - | <code cpp> | + | <hidden 代码><code cpp> |
| #include<bits/stdc++.h> | #include<bits/stdc++.h> | ||
| using namespace std; | using namespace std; | ||
| 行 161: | 行 161: | ||
| return 0; | return 0; | ||
| } | } | ||
| - | </code> | + | </code></hidden> |
| ===== C.Easy ===== | ===== C.Easy ===== | ||
| 行 198: | 行 198: | ||
| $$\sum_{i=0}^{n-k}C_{k - i - 1}^{i}C_{k + n - k - i - 1}^{n - k - i}C_{k + m - k - i - 1}^{m - k - i}$$ | $$\sum_{i=0}^{n-k}C_{k - i - 1}^{i}C_{k + n - k - i - 1}^{n - k - i}C_{k + m - k - i - 1}^{m - k - i}$$ | ||
| - | <code cpp> | + | <hidden 代码><code cpp> |
| #include<algorithm> | #include<algorithm> | ||
| #include<iostream> | #include<iostream> | ||
| 行 249: | 行 249: | ||
| return 0; | return 0; | ||
| } | } | ||
| - | </code> | + | </code></hidden> |
| ===== D.Drop Voicing ===== | ===== D.Drop Voicing ===== | ||
| 行 260: | 行 260: | ||
| 枚举环断开的位置，就成了链上的插入排序问题，计算出LIS后剩下的就是最少移动次数 | 枚举环断开的位置，就成了链上的插入排序问题，计算出LIS后剩下的就是最少移动次数 | ||
| - | <code cpp> | + | <hidden 代码><code cpp> |
| #include<algorithm> | #include<algorithm> | ||
| #include<iostream> | #include<iostream> | ||
| 行 315: | 行 315: | ||
| return 0; | return 0; | ||
| } | } | ||
| - | </code> | + | </code></hidden> |
| ===== E.Bogo Sort ===== | ===== E.Bogo Sort ===== | ||
| 行 328: | 行 328: | ||
| 本次用的是高精度板子，下回碰到这种直接上python。 | 本次用的是高精度板子，下回碰到这种直接上python。 | ||
| - | <code cpp> | + | <hidden 代码><code cpp> |
| #include<bits/stdc++.h> | #include<bits/stdc++.h> | ||
| using namespace std; | using namespace std; | ||
| 行 419: | 行 419: | ||
| } | } | ||
| - | </code> | + | </code></hidden> |
| ===== F.DPS ===== | ===== F.DPS ===== | ||
| 行 430: | 行 430: | ||
| 大水题 | 大水题 | ||
| - | <code cpp> | + | <hidden 代码><code cpp> |
| - | </code> | + | </code></hidden> |
| ===== H.Interval ===== | ===== H.Interval ===== | ||
| 行 452: | 行 452: | ||
| 假设 每个 H 的四周都只有一个 G 和 E ，那么一个 G 和 E 最多可以满足四个 H ，所以占比就是 4/6 | 假设 每个 H 的四周都只有一个 G 和 E ，那么一个 G 和 E 最多可以满足四个 H ，所以占比就是 4/6 | ||
| - | <code cpp> | + | <hidden 代码><code cpp> |
| #include<iostream> | #include<iostream> | ||
| #include<cstdio> | #include<cstdio> | ||
| 行 470: | 行 470: | ||
| return 0; | return 0; | ||
| } | } | ||
| - | </code> | + | </code></hidden> |
| ===== K.Git Merge ===== | ===== K.Git Merge ===== | ||
| 行 481: | 行 481: | ||
| 首先给整个代码标号，第一个人写的部分标为1，第二个人写的部分标为2，公共部分为0，那么第一个人完整版就是01，第二个人是02，之后就是类似最长公共子序列的DP了来求融合代码总长度了。设$dp[i][j][0/1/2]$表示当前匹配到了第一份代码的第$i$行，第二份代码的第$j$行，$0$表示当前已经放下了endif，$1$表示还在branch1中，$2$表示在branch2中，转移是$O(1)$的。DP完之后从最后一步往回搜来进行还原源代码。 | 首先给整个代码标号，第一个人写的部分标为1，第二个人写的部分标为2，公共部分为0，那么第一个人完整版就是01，第二个人是02，之后就是类似最长公共子序列的DP了来求融合代码总长度了。设$dp[i][j][0/1/2]$表示当前匹配到了第一份代码的第$i$行，第二份代码的第$j$行，$0$表示当前已经放下了endif，$1$表示还在branch1中，$2$表示在branch2中，转移是$O(1)$的。DP完之后从最后一步往回搜来进行还原源代码。 | ||
| - | <code cpp> | + | <hidden 代码><code cpp> |
| #include<bits/stdc++.h> | #include<bits/stdc++.h> | ||
| using namespace std; | using namespace std; | ||
| 行 574: | 行 574: | ||
| return 0; | return 0; | ||
| } | } | ||
| - | </code> | + | </code></hidden> |
| ===== 训练实况 ===== | ===== 训练实况 ===== | ||
| 行 585: | 行 585: | ||
| hxm:这场比赛偏难，菜是原罪 | hxm:这场比赛偏难，菜是原罪 | ||
| - | fyh: | + | fyh:前俩小时还凑合，后程就一直想B题，当时一直执着于每一次找一个边权最大的树链，导致没有往别的思路想（其实当时王兴罡说到了两两边权是固定的，当时应该就能想到是Xor-MST了，但是却没有），应该认真听队友的讨论，然后最后的K题也是脑子一片混乱，应该在写之前和队友好好讨论。 |
2020-2021/teams/die_java/front_page_summertrain6.1596175055.txt.gz · 最后更改: 2020/07/31 13:57 由 fyhssgss
