[FJWC2019 Day3] 签到题

[FJWC2019 Day3] 签到题

时间限制: 1000ms               内存限制:256MB

难度: \(4.5\)

  • 题目描述

作为一道签到题,自然只能包含最基本的算法。本题的任务很简单,给定一个长度为 \(n\) 的序列 \(a\),你要将其排序。

由于出题人很菜,不会排序算法,他决定自己编一个。他想找到一个数 \(x\),使得序列中的所有数字都异或上 \(x\) 后序列恰好按从小到大排列。

顺带,这个序列会被进行若干次修改,每次修改后你需要回答当前是否存在一个 \(x\) 满足序列中数字异或上 \(x\) 后按从小到大排列,如果有,请你给出最小的 \(x\) 。

  • 输入格式

第一行一个正整数 \(n\) 。

第二行 \(n\) 个非负整数,表示序列 \(a\) 。

第三行一个非负整数 \(q\) ,表示修改次数。

接下来 \(q\) 行,每行一个正整数 \(x\) 和一个非负整数 \(y\),表示将序列中第 \(x\) 个元素修改为 \(y\) 。

  • 输出格式

输出 \(q+1\) 行,每行一个整数,第一行表示一开始最小的合法 \(x\) ,之后 \(q\) 行依次表示每次修改后最小的合法 \(x\),如果不存在则这一行输出 \(-1\) 。

  • 样例输入

  • 样例输出

  • 数据范围与提示

对于 \(20\%\) 的数据,\(n,m \le 500\),所有数字不超过 \(2^9\) ​​。

对于 \(50\%\) 的数据,\(n,m \le 1000\) 。

对于 \(100\%\) 的数据,\(n,m \le {10}^6\)​​,所有数字不超过 \(2^{30}\) ​​。

 

 

YZOJ P4263


 

 

 

作为一道合格的签到题,很懊悔没有在考场上切掉它。明明已经想到了正解

直接暴力 \(20pts\) 不用多说。

对于这类问题,最常见的方法就是把这些数二进制分解,然后讨论每一位上的情况。要使整串序列非严格单调递增,就是要让 \(\forall i \in [1,n-1], a_i \leq a_{i+1}\) 。

对于本题,很显然的一个贪心就是:从高位到低位找到相邻两个数 \(i\) 和 \(i+1\) 的第一个不同的二进制位设为 \(d\),如果 \(d_{i}=0, d_{i+1}=1\) 那么选择 \(0\) 不反转,如果 \(d_{i}=1, d_{i+1}=0\) 那么选择 \(1\) 反转。同时相等的位选什么都可以,但是为了使 \(x\) 最小应优先选 \(0\) 。

所以对于每个二进制位统计一下有几对相邻的 \(a\) 必须选 \(0\) 或 \(1\),那么修改就是 \(O(loga)\) 的。对于每个询问都 \(O(loga)\) 统计一下哪些位必须选 \(1\) ,并加入 \(x\) 中,注意如果出现必须同时选 \(0\) 和 \(1\) 的情况那就是无解了。

时间复杂度 \(O((n+q)loga)\) 。

 

 

 

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注