too hard for me!(4)
QOJ6660. 택시 여행
题意
给定一棵
每一个点上有一个出租车,起步价是
你现在在
题解
考虑什么时候会在一个点换车坐,发现新换的车
也就是说,所有坐过的车,
设
那么
直接做就能
点分树套李超树优化一下,复杂度
提交记录。
QOJ6661. 야유회
题意
现在有
现在要进行三轮游戏,分别是早上、下午、晚上。
早上的时候,每个人能看见自己和右边一个人的数字,然后所有人会同时更改自己的数字。
下午和晚上的时候,每个人能看见自己和左右各一个人的数字,然后所有人会同时更改自己的数字。
构造一种策略,使得三轮游戏过后任意相邻两个人数字不同。
具体的,需要构造三个确定性函数,分别为早上、中午、晚上每一个人的策略。
如果交互库调用函数时发现相同传入返回了不同的结果,将会直接判错。
每一组数据包含多测,但你不知道有几组数据也不知道
题解
首先可以发现,下午和晚上其实可以分别拆成
考虑让每一次游戏过程之后,相邻两个人的数字都不相同(否则肯定不好搞)。
对于早上,也就是说我们要构造一个函数
一个可能的思路是使用二进制位相关的东西进行构造:
令
设
可以发现若
那么此时我们能做到的数字种类为
我们现在的值域要在
考虑为什么一定要带上一个
这样就可能会导致
那么考虑能不能令
显然也是不行的,因为有
这个时候就有一个神仙优化,考虑
那么我们先将一开始所有人身上的数字映射到,二进制下恰好有
那么这个时候
那么我们直接令
考虑当前数字种类为
但是此时后两轮没有对局面造成任何改变,也就是说,我们还有整个晚上没有用!
考虑单独对晚上进行操作,设晚上的时候,相邻三个数分别为
若
若
这样我们就能在晚上能让数字种类数从
提交记录。
QOJ6662. 기지 간소화
题意
现在有
定义
求
题解
线段树合并一下,计算每条边会被计算多少遍。
提交记录。
QOJ6664. 학생들
题意
现在有
学生们只知道补习团队个数
现在过去了若干天,每一天早上,若一个人推断出,存在一个补习团队,使得自己不在这个团队里,那么他会选择进行举报。
如果学生进行举报,之后所有补习活动立刻停止。若下一天补习活动照常进行,则学生们都会知道上一天没有人进行举报。
问举报发生在第几天,有哪些学生进行了举报。
题解
先推一下什么时候会发生举报。
如果存在一个人
初始时
如果存在两个人
那么在
那么如果
所以
那么我们可以推出,在第
满足不存在一个补习团队,同时包含这
那么首先来考虑第一次举报在第几天,这相当于问找出最少的人,使得没有一个集合包含他们。
题目中给的条件相当于是在说,一个补习团队的补集是一个区间。
那么这相当于选出最少的人,满足每一个区间都包含了至少一个选中的人。
如果只是求出最小的人数的话,可以看出来最后这步是一个普及组贪心。
直接把所有区间按照右端点从小到大的顺序排序,然后直接贪就好了。
考虑现在还需要判断每一个人是否会去投诉,那就考虑设
同理令
那么如果固定第
所以哪些人会去举报也是容易计算的。
复杂度
提交记录。
QOJ6663. 회의실 2
题意
现在有
称两个会议有关,当且仅当,这两个会议时间段有交,或者存在另外一场会议,和这两场会议都有关。
在一次开会的过程中,所有有关的会议可以在一个会议室中进行,一次开会的代价是需要的最小的会议室个数。
现在要开
求让总代价和最小的,删除会议的顺序方案数。
题解
首先可以发现两个会议有关相当于是两个会议在一个连通块里面。
先考虑如果初始的时候,所有会议在同一个连通块里面,怎么做。
不难发现此时一定存在一个方案,使得,每一次开会的时候代价都是
也就是说,我们现在需要计算的是,每一次删除区间之后,代价都是
正着不好想,考虑倒着做,考虑计算每一次加一个区间,使得代价一直保持
考虑加入一个区间之后,区间并变化的时刻。假设并一共变化了
考虑其他的区间可以在什么时候插入。
令
同时令
那么方案数可以表示为
这个时候就好做了,设
dp 的时候只对并变化的过程进行转移即可。这样就做好了。
最后考虑初始的时候不是所有连通块都有关的情况,可以发现一定是每一次盯着最小的连通块删。
提交记录。
QOJ6665. 팀 만들기
题意
现在有
每一个人均有一个代码能力和思维能力,男生的代码能力和思维能力分别用
已知对于任意
一个男生
现在有
题解
后续分析中默认
设现在有两个男生
考虑
因式分解一下,
所以可以知道
也就是说,这个矩阵是满足四边形不等式,这是一个完全单调矩阵。
这样如果是单组询问,就可以直接分治去做了,可以做到
但是现在有多组询问,考虑分块去做。
散块对散块,直接把散块薅出来暴力跑分治,复杂度
整块对散块,预处理男生的每一块,和每一个女生的最优取值。复杂度
询问的时候,男生这边的整块有
那么直接把这当成一个
散块对整块,和上面一样。
整块对整块,先预处理出男生每一个整块,和女生每一个整块的最优解,这部分可以和上面一起预处理。
还是和上面一样,男生女生整块数量都是
(其实这里也可以用 st 表)
所有最终复杂度是
若使用 SMAWK 算法代替分治,则可以做到
分治提交记录。(怎么喜提最劣解)