[LOJ6469]Magic

题目大意：

有\(n(n\le10^5)\)个物品，每个物品有一个权值\(w_i(w_i\le10^{18})\)。求所有\(n\choose 2\)对物品\((i,j)\)对应\(\lfloor\log_{10}(w_i\oplus w_j)\rfloor+1\)之和。

思路：

相当于枚举\(10\)的若干次方\(m\)，然后在字典树上查找\(\ge m\)的数对的个数。

源代码：

#include<cstdio>

#include<cctype>

typedef long long int64;

inline int64 getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int64 x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

const int N=1e5+1,B=59;

const int64 A=1e18;

int64 ans=0;

class Trie {

	private:

		int val[N*B],ch[N*B][2],sz;

	public:

		void insert(const int64 &x) {

			for(register int i=B,p=0;i>=0;i--) {

				const bool b=(x>>i)&1;

				if(!ch[p][b]) ch[p][b]=++sz;

				p=ch[p][b];

				val[p]++;

			}

		}

		void query(const int &p,const int &q,const int64 &x,const int &d) {

			if(d==-1||(1llu<<(d+1))<=(unsigned long long)x) return;

			if((1ll<<d)>=x) {

				ans+=1ll*val[ch[p][0]]*val[ch[q][1]];

				ans+=1ll*val[ch[p][1]]*val[ch[q][0]];

				if(ch[p][0]&&ch[q][0]) query(ch[p][0],ch[q][0],x,d-1);

				if(ch[p][1]&&ch[q][1]) query(ch[p][1],ch[q][1],x,d-1);

			} else {

				if(ch[p][0]&&ch[q][1]) query(ch[p][0],ch[q][1],x-(1ll<<d),d-1);

				if(ch[p][1]&&ch[q][0]) query(ch[p][1],ch[q][0],x-(1ll<<d),d-1);

			}

		}

};

Trie t;

int main() {

	const int n=getint();

	for(register int i=0;i<n;i++) {

		t.insert(getint());

	}

	for(register int64 i=1;i<=A;i*=10) {

		t.query(0,0,i,B);

	}

	ans/=2;

	printf("%lld\n",ans);

	return 0;

}

巴特西

[LOJ6469]Magic

[LOJ6469]Magic

题目大意：

思路：

源代码：

最新文章

热门文章