自动搬运

查看原文

来自洛谷，原作者为

	a___ 这个家伙很蒻，什么也没有留下qwq

搬运于2025-08-24 22:25:11，当前版本为作者最后更新于2021-02-19 16:45:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先按题意建出二叉搜索树，在按照每次是走向左儿子还是右儿子，可以将每个位置状压成唯一对应的数。然后哈希成 $\sin$ 和，最后输出不同 $\sin$ 和个数就好。

#include<cstdio>
#include<cmath>
#include<unordered_set>
const int N=22;
int q,n,son[N][2],val[N],cnt,rt,now;
std::unordered_set<long long>st;double sum;
void insert(int &rt,int x)
{
	if(!rt)return (void)(val[rt=++cnt]=x,son[rt][0]=son[rt][1]=0,sum+=sin(now));
	now<<=1;now|=x>=val[rt];insert(son[rt][x>=val[rt]],x);
}
int main()
{
	int i,x;scanf("%d%d",&q,&n);
	while(q--)
	{
		rt=cnt=sum=0;
		for(i=1;i<=n;i++)scanf("%d",&x),now=1,insert(rt,x);
		st.insert((long long)(sum*1e6));
	}
	printf("%d\n",st.size());
	return 0;
}