1 条题解
-
0
何老师 (root) LV 0 MOD @ 2024-09-13 11:58:43
标记数组的运用:
1、某个编号i,若它既不在a[1]..a[K]中,也不在b[1]..b[K]中,则为答案贡献1;
2、对于a[1]..a[K]和b[1]..b[K]构成的两个环,分两种情况:
1)直接统计既在a[1]..a[K]中,也在b[1]..b[K]的编号,算出他们的位置差,并用标记数组记录位置差的数量(delt[t]表示位置差为 t的编号数量),注意对于环的情况,若位置差小于0,则加K。
2)因为是环,所以把a[1]..a[K]翻转一下,重新统计每个元素的位置,再算位置差。
上面两种情况中delt[0]..delt[K-1]中最大的是对答案的贡献。
本题用到了5个标记数组:
cnta[i]和cntb[i] 都表示i分别在a[1]..a[K]和b[1]..b[K]中是否出现。
da[i]和db[i]表示i分别在a[1]..a[K]和b[1]..b[K]中的位置。
delt[i]表示i分别在a[1]..a[K]和b[1]..b[K]中的位置差。
- 1
信息
- ID
- 2936
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 2
- 已通过
- 1
- 通过率
- 50%
- 上传者