社区讨论

Just Shapes & Beats! 再度归来赛题解

WWen_kr
学术版参与者 25已保存回复 38

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
38 条
当前快照
1 份
快照标识符
@mi6zh8gr
此快照首次捕获于
2025/11/20 13:21
4 个月前
此快照最后确认于
2025/11/20 17:15
4 个月前
查看原帖

Just Shapes & Beats! 再度归来赛 题解

首先恭喜
@小粉兔 rank 1
ditolyrank 2
@star_city rank 3
(原rank 3 和 rank 5为验题人)
请私信我领取 20 rmb 奖励。
感谢 Harry_bhAn_Account@zhongyw 137_345_2814等验题人验题
感谢 Enzyme125An_Account137_345_2814等提供建议。
接着是题解：

T1 - Barracuda

Subtask -1

我会输出 illegal ，预期得分 10 Pts

Subtask 0

我会枚举，预计得分 30 ~ 50 Pts

Subtask 1

我会高斯消元，可是我判 illegal 的情况漏了一些，预计得分 30 ~ 60 Pts

Subtask 2

考虑枚举是哪一次称量结果有误，然后暴力跑高斯消元，按题意判无解。 时间复杂度 O(n4)O(n^4)

T2 - Lycanthropy

30 Pts

对于 30%30\% 的数据，考虑暴力模拟，最后输出。 时间复杂度 O(n2)O(n^2)

70Pts

考虑用线段树维护，时间复杂度 O(nlogn)​O(n log n)​。

100 Pts

考虑采用差分套差分，用差分维护差分数组即可。 时间复杂度 O(n)O(n)

T3 - Annihilate

30 Pts

把两两字符串拖出来跑 dp，时间复杂度 O(n3)O(n^3)。

60 Pts

考虑使用后缀自动机，因为毒瘤出题人卡内存，只有 60 Pts.

100 Pts

考虑把所有串连在一起，在中间加入分割符，使用后缀数组处理出 height 数组。
接着我们考虑设 ans[i][j]ans[i][j] 表示 第 ii 个串和第 jj 个串的最长公共字串。
设 pre[i] 表示从上一个属于第 i 个串的字符开头的 后缀 到当前位置的 height 数组的最小值，容易看出， pre[i] 就是从字符串 i 到当前后缀头字符所属的字符串的 lcp 长度
我们考虑按照 rank 从小到大枚举，对于一个后缀 p ，若它属于字符串 ii ，我们用 pre[j]pre[j] 更新 ans[i][j]和ans[j][i]ans[i][j] 和 ans[j][i]，最后输出答案即可。
时间复杂度 O(n∗∑len)O(n * \sum len)

T4 - T'ill It's Over

10 Pts

输出 0 或 n 都能得到十分。

0~20 Pts

CPP
rand()%2 == 1 output(1)
rand()%2 == 0 output(n)

20 Pts

n=1n = 1，考虑建出一张图，判断从 1 号点能否到 k 号点即可。

另外 10 Pts

使用网络流，暴力建图，op=1op = 1，建立一条从 aa 到 bb 的边，跑 EK 即可。

另外 20 Pts

考虑方案 2 和 3，建立两个虚拟节点，起点(可能有多个)向其中一个建立流量为无限大的边，另一个向终点(可能有多个)建立流量为无限大的边，然后从虚拟节点一个向另一个建立流量为这个方案使用次数限制的边。然后跑 EK 即可。

70 Pts

使用 Dinic(或其他更加优秀的网络流算法)，其他如另外 20 Pts 的建图方式。

100 Pts

考虑上一个连边方式的瓶颈，就是连接的节点数量为 nn 个，这不可以接受。
我们考虑使用线段树优化连边，这样连接的节点数量为 log(n)log(n) 个，由于数据随机，Dinic(或其他更加优秀的网络流算法) 可以轻松跑过。
以上
还麻烦我们辛勤的管理员将题目加入题库

回复

共 38 条回复，欢迎继续交流。

正在加载回复...