专栏文章

2025.9.17 敬爱的金正恩

jjjy412467作弊者
个人记录参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minvbb5j
此快照首次捕获于
2025/12/02 08:56
3 个月前
此快照最后确认于
2025/12/02 08:56
3 个月前
查看原文
三天了我蒸鱼过了
ai,j≤ai+1,(j+1) mod ma_{i,j} \le a_{i+1,(j+1) \bmod m}
一个观察是若 i<ji < j，令 si=∑ai,js_i = \sum a_{i,j}，则 si≤sjs_i \le s_j
若 si=sjs_i = s_j，则限制可缩紧为 ai,j=ai+1,(j+1) mod ma_{i,j} = a_{i+1,(j+1) \bmod m}
所以重心就是处理 si=sjs_i = s_j 的情况
我们觉察到 si=Ss_i = S 的一个 groupgroup 内部，{ai}\{a_i\} 序列具有周期性
{ai}\{a_i\} 序列在其后会进行循环移位，直到转回它自己
这个循环节长度可以发现是 {ai}\{a_i\} 序列最小表示的循环节长度
那我们就可以 si=Ss_i=S 的一个 groupgroup 内按照循环移位 did_i 分组
记 tonjton_j 为循环移位为 jj 的 did_i 的数量
可以注意到当存在 i≠j,toni≠tonji \ne j,ton_i \ne ton_j 时
要么不存在解，要么可以确定起点和终点的位置
而在 ∀i,j,toni=tonj\forall i , j , ton_i = ton_j 时，似乎比较复杂，无法直接确定
我们考虑做一个 end_posend\_pos 的 DPDP
其它的都好说
只有连续两个的无法确定起点终点的位置复杂度无法接受
注意到因为循环的性质，本质上只有循环节 T1T_1 种比较
可以预处理一下 O(T1T2)O(T_1T_2)，后面查表 O(T1T2)O(T_1T_2)
这个复杂度乍一看不怎么对
但其实 ∑T1≤n\sum T_1 \le n ，又有 T2≤mT_2 \le m，总复杂度 O(nm)O(nm)
代码巨难调，前天写的代码实在调不下去了
昨天重新写了一遍才过写完整个人都升华了

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...