目录

2023 牛客暑期多校训练营 9

各题总结

29min | E

纯签到,white秒掉了

101min | I

给定n个区间对,从每对区间中选择一个,使得它们至少包含一个公共点,问方案数。 aytony用扫描线过了

200min | D

给定长度为 n 的排列,计算有多少个子区间满足子区间第 k 小的数不在子区间第 k 位。 aytony用双指针一发过了。

G(-40)

Alice 和 Bob 博弈。黑板上原有 n 个数 ai,每次当前行动方可以选择一对 (i, j),并在黑板上写上 ai ⊕ aj。先写下 k 的人胜利。问博弈结果,或者平局。 正解是分解成异或空间线性基判断该集合的线性基能表示出的元素是否严格等于xor意义下张成的向量空间蕴含的向量即可,但是大家都不熟所以开始坐牢。

总结

除了G之外dirt控制的较好,但是掌握的算法还是不够多