T1 小w的进制转换
小w在将一个10进制数转换为二进制数的时候,不小心将“0”和“1”搞混了,也就是说本来该输出1的时候他输出了0,本来该输出0的时候他又输出了1。而他在输出答案的时候,又将输出的左右顺序搞混了。举个例子:小w将6转换为二进制,本来6的二进制表示为110,但是小w转换成了001,输出时又倒了过来变成100。现在假设评测姬中的评测数据是1,2,3,4,5,6…n也就是从1到n,问小w能AC其中的多少组测试案例?
这个东西是一个很纯的进制题,题目大意就是计数合法的串,满足各位异或1之后调转整个序列使得与原序列相同。也就是让你求“反对称01串”的个数。显然奇数长度的串是不会合法的,那么考虑偶数长度的串,推一推样例可以发现第N个符合长度的串就是N的二进制接上N的反对称串,熟悉位运算的话实际上就是一个模拟题,思维难度不大,就是看你能不能掌握位运算了。。。
1 |
|
T2 小doge的快乐阳光跑
每次开始阳光跑,会在n个点里随机生成好多点位,并且需要按照点位顺序跑.
当且仅当,阳光跑随机生成的点位序列(注意顺序)是你跑步序列的一个子序列时,你完成阳光跑。
某一个序列的子序列指的是,保留该序列的顺序并删除一些元素或者不进行删除后的结果。
小doge是一个乐于助人的好孩子,他常常帮助别人跑步。
这天,小doge想要完成自己的阳光跑并且顺便帮助小w一起完成即一个人完成两人的任务,并且两个人的任务是独立的,小doge有a个点位,小w有b个点位。小doge想要最效率的跑法,所以他想知道他最少要跑多远。小doge可以选择任何一个点出发。
对于阳光跑的要求,我们如下定义:有n个有顺序的点位a1到an,想要完成阳光跑,必须按照顺序依次经过每个点位,并且在到达前一个点位后到达下一个点位才有效。
搬过来的题解里面的题意简化:给一张图,求一个权值和路径最小的移动序列,使得移动序列包含两个给定的子序列。(早这样说多好
这题很显然你应该求一个最短路,想用Floyed的大可不必了,数据范围对于A和B来说只有100,所以我们可以直接对于每一个A和B中的点为起点跑一遍SPFA,时间上是没有问题的。现在有了D[i][j]之后我们就可以进行Dp了,设Dp[i][j][0/1],表示当前完成了A的第i位和B的第j位,然后0为停留在A路径上,1为停留在B路径上。转移方程还是需要推一推的。
1 | Dp[i][j][0] = min(Dp[i][j][0], Dp[i - 1][j][0] + D[La[i - 1]][La[i]]) ; |
看起来非常的整齐(嗯
1 |
|
T3 区间异或和异或区间最大值异或区间最小值
小w学会了RMQ算法,他现在可以求出一个给定数组某一段子区间的最大值,最小值。在这之前,他也学会了前缀和,并且他知道前缀和可以扩展到位运算求出区间异或和。 现在你给了他一个长度大小为n的数组,为了考察小w写RMQ以及前缀异或和的正确性,你要求他求出该数组的某一个子区间,记该子区间的异或和为xorsum,记该子区间的最大值为max,记该子区间的最小值为min,你要求使得xorsum⊕max⊕min最大。其中⊕为位运算异或操作。
看起来就是一道很毒瘤的数据结构题,(从题目名字就看得出来好嘛
先考虑考虑部分分吧。首先我们得知道一个原理A⊕B⊕B=A,相当于一个数两次异或另一个数答案是不变的。那么对于答案所求就是去掉最大值和最小值之后的区间异或和。对于区间最大值和区间最小值我们可以使用RMQ进行维护,对于Sumxor我们可以使用前缀和进行维护,于是对于确定区间的求值就只O(1)的,我们枚举区间的左右端点,时间复杂度就是O(N2)的。
但是出题人十分毒瘤,导致O(N2)只能过30%的点,这就有些不良心了。。
接下来想正解,发现这个序列实际上是可以用分治瞎搞进行维护的,对于该区间取中点Mid,然后考虑从左端点在Mid左侧,右端点在Mid右侧的所有子区间,它们有一个共性就是一定是由一个从Mid开始往左延伸的区间和从Mid开始往右延伸的区间拼接得到的(意会),对于这两个区间我们需要找到一个支持快速插入以及查询的数据结构来进行维护从Mid向左延伸的区间的贡献,之后再遍历往右的区间。
这样我们就处理完了所有左端点在Mid左侧,右端点在Mid右侧的子区间,那么之后直接递归计算[L,Mid]和[Mid+1,R]就可以了。
回想这个数据结构,我们发现字典树可以较好地解决这个问题,我们只需要将异或和放入字典树中,然后分类讨论:
- 左侧区间提供最大值最小值
- 右侧区间提供最大值最小值
- 左侧区间提供最大值,右侧区间提供最小值
- 左侧区间提供最小值,右侧区间提供最大值
并且,由于显而易见的是随着区间延伸最大值单调不减,最小值单调不升,所以我们枚举极值的时候有一个双单调性,因此可以考虑尺取法,之中对于以上四种情况分类讨论即可。
思维难度颇大,鄙人在考场上大致也只能想出来O(N2)暴力做法。(没准还可以水一水特殊数据点?
v1.5.2