[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\) 。
-
样例输入
1 2 3 4 5 6 |
3 0 1 4 3 2 7 3 3 1 4 |
-
样例输出
1 2 3 4 |
0 2 -1 4 |
-
数据范围与提示
对于 \(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)\) 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #define _max(_a_,_b_) ((_a_)>(_b_)?(_a_):(_b_)) #define _min(_a_,_b_) ((_a_)<(_b_)?(_a_):(_b_)) inline int getnum() { register char c=getchar(); while(!(c>='0' && c<='9')) c=getchar(); register int a=0; while(c>='0' && c<='9') a=a*10+c-'0',c=getchar(); return a; } int N,limxd; bool ad[1050505][32]; int cnt[32][2]; inline void FindX() { register int x=0; for(register int d=0;d<limxd;d++) if(cnt[d][1]) if(cnt[d][0]) { printf("%d\n",-1); return; } else x+=(1<<d); printf("%d\n",x); } inline void ReConstruct(const int&l,const int&r,const int&sgn=1) { for(register int i=l+1;i<=r;i++) { register int d=limxd-1; while(d>=0 && ad[i-1][d]==ad[i][d]) d--; if(d>=0) cnt[d][ad[i-1][d]]+=sgn; } } inline void DBinary(const int&p,register int a) { register int dig=0; while(a) ad[p][dig++]=a&1,a>>=1; for(register int i=dig;i<limxd;i++) ad[p][i]=0; limxd=_max(limxd,dig); } int main() { //freopen("sort.in","r",stdin);freopen("sort.out","w",stdout); N=getnum(); for(register int i=1;i<=N;i++) DBinary(i,getnum()); ReConstruct(1,N); FindX(); register int Q=getnum(); for(register int lp=1;lp<=Q;lp++) { register int x=getnum(),y=getnum(); ReConstruct(_max(1,x-1),_min(N,x+1),-1); DBinary(x,y); ReConstruct(_max(1,x-1),_min(N,x+1)); FindX(); } return 0; } |