求助训练营D.石子游戏差分写法
我们每次操作区间
对差分数组而言,相当于是而
又因为,所以
操作简化为以下两种
当
,因为可以操作区间
当
而
,因为可以操作区间
那么是不是倒序扫描差分数组一遍就好了....但是一直
2021-02-23 09:34 江西师范大学 golang
关注
全部评论
Kur1su
北京师范大学 C++
issue yyds
我不会玩锐雯
吉首大学 Java
不是啊，看看代码。
我不会玩锐雯
吉首大学 Java
这样考虑，每次区间+1，对应差分数组a[i++]，a[i+k]--。 那么当a[i]<0时连一条i->i+k的边，当a[i]>0连一条i-k->i的边。 整个数组被拆分成若干条有向链或者环(两点配对了)，把数组变成全0(1和n+1位置除外)需要从每条链的起点开始处理，链中的点会受到前面点的影响。 可参考赛中代码(有点丑)：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=46825912
相关推荐
