题解 P6919 [ICPC2016 WF]Ceiling Function

a___ · 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;
}