题解 big

传送门

题面里那个式子

考场上我推了半天那个式子代表什么意思，但就是没想到位运算

\(\lfloor \frac{2x}{2x^n} \rfloor \iff x\gg(n-1)\)，即将x的第n位移至最低位

\(2*x\%2^n \iff (x\ll 1)\%2^n\)，即将x左移一位并舍弃n+1及更高位

所以这两个操作等价于将x循环左移一位，最高位补至最低位

显然那一大串异或操作可以搞个前缀和

然后考虑何时取最大值

先说一个错误的思路我考场上打的暴力就是这么挂的

令\(sum[i]\)为前i次操作的异或和

\(x \in [0, 2^n)\)可以取遍二进制位的所有情况，

所以 \(x \oplus sum[i] \in [0, 2^n)\)

那么x异或上前i个数就等价于没异或，题目就转化为求这i个数异或后缀和的最大值

然后你会在测样例的时候面对着一个执着的3一筹莫展

这个做法错误的原因是没有满足「你的对手会使 x 最后尽量小」

也就是说，你的对手会在你确定x后找到会使一个最小的位置下手

而我们先固定下手位置，再确定x的做法就显然不对了

再说正解：

令\(suf[i]\)为异或后缀和（suf为suffix缩写）

因为异或时各位互不影响的特性，x异或上前i个数等价于循环移位后的x异或上前i个数循环移位后的结果

那么令\(sum[i]\)为前i个数循环移位后的异或前缀和

题面就转化为求一个\(x\)使\(x \oplus sum[i] \oplus suf[i+1]\)最大

就珂以扔到一棵trie树上跑了

p.s. 这题还有一个坑点是求「得到最大值的初值数量」，实际上指的是有多少个不同的x能取到这个最大值，而不是指有多少个位置i能取到最大值. 哦这就是我一调一小时的原因

Code:

#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define N 100010

#define ll long long

#define ld long double

#define usd unsigned

#define ull unsigned long long

//#define int long long 

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)

char buf[1<<21], *p1=buf, *p2=buf;

inline int read() {

	int ans=0, f=1; char c=getchar();

	while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}

	while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}

	return ans*f;

}

int n, m;

int a[N], sum[N], suf[N], size;

struct trie{

	int son[2], cnt;

	#define t(p) tree[p]

}tree[N*25];

void upd(int u) {

	int p=0, t, t2;

	for (int i=30; i>=0; --i) {

		t2 = (u&(1<<i))?1:0;

		t = t(p).son[t2];

		if (!t) {t(p).son[t2]=++size; t=size;}

		p = t;

	}

	t(p).cnt = 1;

}

int query(int dep, int p) {

	if (dep<0) return 0;

	if (t(p).son[0] && t(p).son[1]) {

		int t1=query(dep-1, t(p).son[0]), t2=query(dep-1, t(p).son[1]);

		if (t1==t2) t(p).cnt = t(t(p).son[0]).cnt+t(t(p).son[1]).cnt;

		else t(p).cnt += t1>t2?t(t(p).son[0]).cnt:t(t(p).son[1]).cnt;

		return max(t1, t2);

	}

	else {

		if (t(p).son[0]) {

			int t=query(dep-1, t(p).son[0])|((dep<n)?(1<<dep):0);

			t(p).cnt += t(t(p).son[0]).cnt;

			return t;

		}

		else {

			int t=query(dep-1, t(p).son[1])|((dep<n)?(1<<dep):0);

			t(p).cnt += t(t(p).son[1]).cnt;

			return t;

		}

	}

}

int query_cnt(int u) {

	int p=0;

	for (int i=30; i; --i)

		p = (u&(1<<i))?t(p).son[1]:t(p).son[0];

	//cout<<p<<endl;

	return t(p).cnt;

}

signed main()

{

	#ifdef DEBUG

	freopen("1.in", "r", stdin);

	#endif

	n=read(); m=read();

	for (int i=1; i<=m; ++i) a[i]=read(), sum[i]=sum[i-1]^(((a[i]>>(n-1))+(a[i]<<1))%(1<<n));

	//for (int i=1; i<=m; ++i) a[i]=read(), sum[i]=sum[i-1]^((a[i]<<1)%(1<<(n-1)));

	for (int i=m; i; --i) suf[i] = suf[i+1]^a[i];

	for (int i=0; i<=m; ++i) upd(sum[i]^suf[i+1]); //, cout<<"upd "<<(sum[i]^suf[i+1])<<endl;

	int t=query(30, 0);

	printf("%d\n%d\n", t, t(0).cnt);

	return 0;

}

巴特西

题解 big

最新文章

热门文章