2020-2021:teams:die_java:front_page_summertrain3
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:die_java:front_page_summertrain3 [2020/07/24 19:56] fyhssgss |
2020-2021:teams:die_java:front_page_summertrain3 [2020/07/24 20:04] (当前版本) fyhssgss |
||
|---|---|---|---|
| 行 23: | 行 23: | ||
| 当前位置有鱼那必拿，剩下只能有无诱饵的决策问题了。当前位置什么都没有肯定拿诱饵置换，有诱饵的话就需要考虑是拿诱饵还是换鱼，二分位置$pos$，令在这之前全拿诱饵，显然是满足单调性。 | 当前位置有鱼那必拿，剩下只能有无诱饵的决策问题了。当前位置什么都没有肯定拿诱饵置换，有诱饵的话就需要考虑是拿诱饵还是换鱼，二分位置$pos$，令在这之前全拿诱饵，显然是满足单调性。 | ||
| + | <hidden 代码> | ||
| <code cpp> | <code cpp> | ||
| #include<bits/stdc++.h> | #include<bits/stdc++.h> | ||
| 行 79: | 行 80: | ||
| </code> | </code> | ||
| + | </hidden> | ||
| + | |||
| ===== B.Classical String Problem ===== | ===== B.Classical String Problem ===== | ||
| 行 92: | 行 95: | ||
| 发现无论怎么移动，这个字符串一定成环状，只是起始位置改变，我们直接维护起点的位置即可 | 发现无论怎么移动，这个字符串一定成环状，只是起始位置改变，我们直接维护起点的位置即可 | ||
| + | <hidden 代码> | ||
| <code cpp> | <code cpp> | ||
| #include<iostream> | #include<iostream> | ||
| 行 134: | 行 138: | ||
| | | ||
| </code> | </code> | ||
| + | </hidden> | ||
| + | |||
| ===== C.Operation Love ===== | ===== C.Operation Love ===== | ||
| 行 146: | 行 152: | ||
| 找到和手腕连接的部分，用叉积判断大拇指或者小拇指在左边还是右边。 | 找到和手腕连接的部分，用叉积判断大拇指或者小拇指在左边还是右边。 | ||
| + | <hidden 代码> | ||
| <code cpp> | <code cpp> | ||
| #include<bits/stdc++.h> | #include<bits/stdc++.h> | ||
| 行 206: | 行 213: | ||
| } | } | ||
| </code> | </code> | ||
| + | </hidden> | ||
| + | |||
| ===== D.Points Construction Problem ===== | ===== D.Points Construction Problem ===== | ||
| 行 216: | 行 225: | ||
| 发现按正方形涂是点对最小的做法，我们先按正方形涂，发现剩下的可以单独涂就单独涂 | 发现按正方形涂是点对最小的做法，我们先按正方形涂，发现剩下的可以单独涂就单独涂 | ||
| + | <hidden 代码> | ||
| <code cpp> | <code cpp> | ||
| #include<iostream> | #include<iostream> | ||
| 行 332: | 行 342: | ||
| | | ||
| </code> | </code> | ||
| + | </hidden> | ||
| + | |||
| ===== E.Two Matchings ===== | ===== E.Two Matchings ===== | ||
| 行 346: | 行 358: | ||
| 次优的在避免相邻的基础上还需要尽可能的进，容易发现要使配对尽可能的近，只有通过4个一组配对和6个一组配对，在此基础上进行dp即可 | 次优的在避免相邻的基础上还需要尽可能的进，容易发现要使配对尽可能的近，只有通过4个一组配对和6个一组配对，在此基础上进行dp即可 | ||
| + | <hidden 代码> | ||
| <code cpp> | <code cpp> | ||
| #include<algorithm> | #include<algorithm> | ||
| 行 395: | 行 408: | ||
| </code> | </code> | ||
| + | </hidden> | ||
| + | |||
| ===== F.Fraction Construction Problem ===== | ===== F.Fraction Construction Problem ===== | ||
| 行 407: | 行 422: | ||
| solved by fyh | solved by fyh | ||
| - | 移项再通分，$\frac{c}{d}=\frac{e//b+a//f}{b*f}$，这个分数必须约掉一个比$b$还大的约数才能保证$d<b$。 | + | 移项再通分，$\frac{c}{d}=\frac{e*b+a*f}{b*f}$，这个分数必须约掉一个比$b$还大的约数才能保证$d<b$。 |
| 开始分类讨论：假如$b$是质数，且$a$不是$b$的倍数，那么不可能找到一个比$b$还大的约数，显然无解。 | 开始分类讨论：假如$b$是质数，且$a$不是$b$的倍数，那么不可能找到一个比$b$还大的约数，显然无解。 | ||
| 行 413: | 行 428: | ||
| 假如$b$是质数，且$a$是$b$的倍数，那就把那$e$,$f$都取1就好了 | 假如$b$是质数，且$a$是$b$的倍数，那就把那$e$,$f$都取1就好了 | ||
| - | 假如$b$是合数，为了方便后续约分，令$b=f//k$，其中$f，k$互质，$\frac{e//b+a//f}{b//f}=\frac{ef+a}{b}$.这个分数需要再来一个约分，即$(ek+a)\equiv0\pmod{b})$，解完模方程组，我们发现这里$k$就是$d$了。 | + | 假如$b$是合数，为了方便后续约分，令$b=f*k$，其中$f，k$互质，$\frac{e*b+a*f}{b*f}=\frac{ef+a}{b}$.这个分数需要再来一个约分，即$(ek+a)\equiv0\pmod{b})$，解完模方程组，我们发现这里$k$就是$d$了。 |
| 假如$b$是合数，但是不存在$b=f*k$，其中$f，k$互质，即$b$是某个质数的整数次幂，则需要对模方程组进行同时约分。 | 假如$b$是合数，但是不存在$b=f*k$，其中$f，k$互质，即$b$是某个质数的整数次幂，则需要对模方程组进行同时约分。 | ||
| + | <hidden 代码> | ||
| <code cpp> | <code cpp> | ||
| #include<bits/stdc++.h> | #include<bits/stdc++.h> | ||
| 行 512: | 行 528: | ||
| } | } | ||
| </code> | </code> | ||
| + | </hidden> | ||
| + | |||
| ===== G.Operating on a Graph ===== | ===== G.Operating on a Graph ===== | ||
| 行 522: | 行 540: | ||
| 直接用并查集维护组，set记录组里的边，每次合并用启发式合并就可以过掉了 | 直接用并查集维护组，set记录组里的边，每次合并用启发式合并就可以过掉了 | ||
| + | <hidden 代码> | ||
| <code cpp> | <code cpp> | ||
| #include<iostream> | #include<iostream> | ||
| 行 608: | 行 627: | ||
| } | } | ||
| </code> | </code> | ||
| + | </hidden> | ||
| ===== L.Problem L is the Only Lovely Problem ===== | ===== L.Problem L is the Only Lovely Problem ===== | ||
| 行 644: | 行 664: | ||
| wxg:这场比赛题目写的多，但是速度还是不行，G和D很早就想出来怎么写，但因为觉得复杂迟迟没有开工，要锻炼一下写细节多的题。 | wxg:这场比赛题目写的多，但是速度还是不行，G和D很早就想出来怎么写，但因为觉得复杂迟迟没有开工，要锻炼一下写细节多的题。 | ||
| - | hxm:这场比赛在$$E$$题上拖延了很久,还好wxg及时得出dp的算法，$$F$$题思考上表现出对数论的熟练度还是比较低，同时需要准备充足的模板 | + | hxm:这场比赛在$E$题上拖延了很久,还好wxg及时得出dp的算法，$F$题思考上表现出对数论的熟练度还是比较低，同时需要准备充足的模板 |
| fyh:虽然过题数一样，但是相同题数罚时倒数第二，导致排名感人。我在写手性那题的时候交了一发wa就不知道哪里错了，开始看别的题，最后还是队友发现应该是eps开太小了，这既是审题的问题（题目说了六位有效数字）也是对eps理解的问题，应该好好研究一下eps的使用。还有A题二分条件不等号写错了，这些都导致了罚时的无意义增加（至少增加了1:30） | fyh:虽然过题数一样，但是相同题数罚时倒数第二，导致排名感人。我在写手性那题的时候交了一发wa就不知道哪里错了，开始看别的题，最后还是队友发现应该是eps开太小了，这既是审题的问题（题目说了六位有效数字）也是对eps理解的问题，应该好好研究一下eps的使用。还有A题二分条件不等号写错了，这些都导致了罚时的无意义增加（至少增加了1:30） | ||
2020-2021/teams/die_java/front_page_summertrain3.1595591809.txt.gz · 最后更改: 2020/07/24 19:56 由 fyhssgss
