2020-2021:teams:legal_string:jxm2001:other:错题集_4
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:jxm2001:other:错题集_4 [2021/02/14 17:59] jxm2001 |
2020-2021:teams:legal_string:jxm2001:other:错题集_4 [2021/02/28 19:08] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 517: | 行 517: | ||
| } | } | ||
| } | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ===== 7、Make Them Similar ===== | ||
| + | |||
| + | [[https://codeforces.com/problemset/problem/1257/F|链接]] | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定一个长度为 $n$ 的序列 $a_1,a_2\cdots a_n$，要求找到 $x$ 使得 $a_1\oplus x,a_2\oplus x\cdots a_n\oplus x$ 中的二进制表示的 $1$ 一样多。 | ||
| + | |||
| + | 其中 $n\le 100,a_i\lt 2^{30}$。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 暴力枚举 $x$ 的低 $15$ 位和高 $15$ 位。假设当前枚举低 $15$ 位，且当前枚举的数为 $v$，记 $b_i$ 为 $a_i\oplus v$ 的二进制表示中的 $1$ 的个数。 | ||
| + | |||
| + | 将 $b_2-b_1,b_3-b_1\cdots b_n-b_1$ 所代表的序列插入字典树。然后枚举高位时查看有无刚好可以构成相反数的序列即可。 | ||
| + | |||
| + | 时间复杂度 $O(n\sqrt v)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=105,MAXL=15,MAXV=1<<MAXL,MAXS=MAXN*MAXV; | ||
| + | int n,a[MAXN],b[MAXN]; | ||
| + | int cal(int v){ | ||
| + | int cnt=0; | ||
| + | while(v){ | ||
| + | cnt+=v&1; | ||
| + | v>>=1; | ||
| + | } | ||
| + | return cnt; | ||
| + | } | ||
| + | int ch[MAXS][MAXL<<1|1],val[MAXS],cnt; | ||
| + | void Insert(int v){ | ||
| + | int pos=0; | ||
| + | _for(i,1,n){ | ||
| + | if(!ch[pos][b[i]]) | ||
| + | ch[pos][b[i]]=++cnt; | ||
| + | pos=ch[pos][b[i]]; | ||
| + | } | ||
| + | val[pos]=v; | ||
| + | } | ||
| + | void query(int v){ | ||
| + | int pos=0; | ||
| + | _for(i,1,n){ | ||
| + | if(!ch[pos][b[i]])return; | ||
| + | pos=ch[pos][b[i]]; | ||
| + | } | ||
| + | enter((v<<15)|val[pos]); | ||
| + | exit(0); | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | n=read_int(); | ||
| + | _for(i,0,n)a[i]=read_int(); | ||
| + | _for(i,0,MAXV){ | ||
| + | _for(j,0,n) | ||
| + | b[j]=cal((a[j]&(MAXV-1))^i); | ||
| + | _for(j,1,n) | ||
| + | b[j]=b[j]-b[0]+MAXL; | ||
| + | Insert(i); | ||
| + | } | ||
| + | _for(i,0,MAXV){ | ||
| + | _for(j,0,n) | ||
| + | b[j]=cal((a[j]>>15)^i); | ||
| + | _for(j,1,n) | ||
| + | b[j]=b[0]-b[j]+MAXL; | ||
| + | query(i); | ||
| + | } | ||
| + | puts("-1"); | ||
| return 0; | return 0; | ||
| } | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/other/错题集_4.1613296764.txt.gz · 最后更改: 2021/02/14 17:59 由 jxm2001
