2022-2023:teams:loaf_on_contest:front_page:st3
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2022-2023:teams:loaf_on_contest:front_page:st3 [2022/08/31 12:28] toby-shi [F] |
2022-2023:teams:loaf_on_contest:front_page:st3 [2022/08/31 22:58] (当前版本) yuki |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| ====I==== | ====I==== | ||
| + | 由于long long的问题T了两次。 | ||
| + | 呜呜~ | ||
| ====B==== | ====B==== | ||
| 在经历了一堆错误的思考后，我发现只需要维护度为1的点或者子树就行了，这些树有两种状态，一种是根节点没有匹配，另一种是根节点已经被匹配，维护数量就可以了。 | 在经历了一堆错误的思考后，我发现只需要维护度为1的点或者子树就行了，这些树有两种状态，一种是根节点没有匹配，另一种是根节点已经被匹配，维护数量就可以了。 | ||
| 行 6: | 行 8: | ||
| WA是因为思路不对。 | WA是因为思路不对。 | ||
| ====H==== | ====H==== | ||
| + | 首先把 $a$ 数组排序，从小到大枚举 $a_i$。 | ||
| + | |||
| + | 首先考虑 $a_{i-1} - a_i$ 的右部点，再考虑 $a_i$ 对应的左部点。 | ||
| + | |||
| + | 需要统计的是 右 -> 左 -> 右 -> 左 ... -> 右 这样的链的数量为i时的情况数。 | ||
| + | |||
| + | 对于右部点，只会将链的数量+1（单独一个 右 ） add(f[k], f[k - 1]) | ||
| + | |||
| + | 对于 $a_i$ 对应的左部点 它和前面所有右部点都有连边，因此它可以把两个链连成一个 | ||
| + | |||
| + | 即：add(f[j - 1], (j - 1ll) * j % mod * f[j] % mod) | ||
| + | |||
| + | 每次枚举到i，相当于是枚举到了环的最后一个点，需要将当前的f[1]累加进答案，因为当前 $a_i$ 对应的左部点，一定可以把 "右 -> 左 -> 右 -> 左 ... -> 右 " 这样一个链的第一个和最后一个 右部点连起来。 | ||
| ====F==== | ====F==== | ||
| 行 12: | 行 27: | ||
| WA是因为longlong和整除的情况。 | WA是因为longlong和整除的情况。 | ||
| ====C==== | ====C==== | ||
| + | |||
| + | 做过一个有点类似的题，虽然事后怎么找都找不到qAq（一开始根本没看题，等到有队伍过了才发现QAQ，应该早点看到QAQ~ | ||
| + | |||
| + | 首先使用dp（或者说就是一个简单的标记数组）记录点1,1和n,m能到达的所有点。 | ||
| + | |||
| + | 由于每次往右或者往下所以 i+j 总是增加1，因此把所有点按 i+j 分类。只有一个点的类是不能删掉的。 | ||
| + | |||
| + | 对于多个点的类，不同类的第一个和最后一个点一定是联通的（这个不知道怎么证，但多举几个例子就会发现） | ||
| + | |||
| + | 然后根据这个性质枚举 i+j 对于每个 i+j 枚举其后面的对角线，在从两端往中间枚举 i 找到合适的点。 | ||
| + | |||
| + | |||
2022-2023/teams/loaf_on_contest/front_page/st3.1661920131.txt.gz · 最后更改: 2022/08/31 12:28 由 toby-shi
