051017模拟 string&&big

发布于 2017-10-06  12.21k 次阅读


[toggle hide="yes" title="题目" color=""]
[ttl2v]
051017-problem
[/ttl2v]
[/toggle]

这套题又是画风不太正常的那种= =,到现在还差第二道没改过去,还没想明白。

 

string(T1)

这道题和HEOI2016那道排序有点相似,都是在字符集较小的情况下,通过线段树统计区间内各个字符出现次数,然后直接区间修改做到排序,思路非常简单,代码实现也不难。但是,分析一下复杂度,应该是O(26*mlogn),如果真的是按照出题人给的n、m<=1e5的话根本过不去,事实上数据最大也就只有1e5、5e4,这样才能勉强卡过去,即使这样,还是很容易被常数卡掉几个点,出题人不仅卡常,还不把数据范围清楚地给出,简直丧尽天良。。。

 

big(T3)

考虑转换一下设问。首先,那个奇奇怪怪的式子其实可以看成是“循环左移1位”,即如果原数的最高位是1的话,左移后就把最高位换到最低位。接着,如果对方在第i次操作后进行“循环左移”,则可以看成是将初始的数和数列中的前i项左移后在异或后面的项,也就是说,可以预处理出对方在m+1个位置异或后的结果。问题转化为,选出一个数,求这个数和m+1个数异或后的最小值的最大值。

考虑按位贪心。将m+1个数按照二进制从高位到低位加入trie树,如果一个节点,有0、1两个子节点,那么如果我选的数是1,那么对方一定也选1使异或后为0,反之亦然,所以这一位的贡献一定是0。如果只有0,那么我一定可以选1,使这一位产生贡献,反之亦然,所以这一位一定能够产生贡献。我们就从高位到低位在trie树上dfs,递归到最低位时更新答案,统计方案即可。

这道题思路非常好,很有启发。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974