ZROI2018暑期集训B班训练赛#1解题报告-白红宇

ZROI2018暑期集训B班训练赛#1解题报告

阅读量：5102 次

发布时间：2019-06-13

本文共 3017 字，大约阅读时间需要 10 分钟。

版权原因不公布题目信息

A

分析

虽然前一天搞到比较晚，考场上还是比较快的想到了正解，可惜姿势水平低被卡到了64(进入高中不知道考过多少次64了...)

这题有个比较明显且\(naive\)的做法是用Hash记录树上的信息，我们给树上每个点赋予一个随机的权值，然后通过子树和和子树大小两个信息哈希，然后我比较菜被卡成了64

讲题时才知道树上哈希是很容易被卡的，所以就有一个船新操作:异或哈希。将子树权值异或和来蛤习,如果权值值域很大的话,被卡的可能性就非常小

当然还有另一种做法是用dfs序,因为是一段连续区间我们判断他们最小值最大值就好了

注意

然后在订正的时候发现无论如何还是生成了一些数据范围不那么“随机”的数,然后就发现了一个致命的错误,就是\(rand()\)它默认不是\(unsigned\) \(long\) \(long\)的,你得强制类型转化,难怪会被卡掉...

代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #define ull unsigned long long #define ll long long #define ri register int using namespace __gnu_pbds;using std::map;using std::pair;using std::make_pair;const int maxn=200005;const int inf=0x7fffffff;template 
              
               inline void read(T &x){ x=0;int ne=0;char c; while(!isdigit(c=getchar()))ne=c=='-'; x=c-48; while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48; x=ne?-x:x; return;}int n;struct Edge{ int ne,to;}edge[maxn<<1];int h[maxn],num_edge=1;inline void add_edge(int f,int to){ edge[++num_edge].ne=h[f]; edge[num_edge].to=to; h[f]=num_edge;}struct _Edge{ int ne,to;}_edge[maxn<<1];int _h[maxn],_num_edge=1;inline void _add_edge(int f,int to){ _edge[++_num_edge].ne=_h[f]; _edge[_num_edge].to=to; _h[f]=_num_edge;}//map
               
                
                 ,int>g;/*inline ull mk_hash(int x,ull y){ ull tmp=(x^(y<<1)>>3)+((x*33)>>1)-(x<<3)+y*13*(y-x)>>1; tmp+=tmp<<(x&15); tmp^=tmp>>6; if((y-x)&1)tmp^=(tmp<<7>>5); else tmp^=~(tmp<<11>>8); tmp+=tmp<<3; return tmp;}inline ull _mk_hash(int x,ull y){ ull tmp=((x<<5>>3)^(y<<2>>5)<<1)-(((x*y<<3>>1)-x)<<1+y-x)<<1; if((y-x)&1)tmp^=(tmp<<7>>5); else tmp^=~(tmp<<11>>7); tmp+=tmp<<3; return tmp;}*/gp_hash_table
                 
                   g;int size[maxn],_size[maxn];ull st[maxn],_st[maxn],tot=0;ull w[maxn];void dfs_1(int now,int fa){ int v;size[now]=1,w[now]=st[now]=(((ull)rand()<<15)|rand())*(((ull)rand()<<15)|rand()); //printf("%lu\n",w[now]); for(ri i=h[now];i;i=edge[i].ne){ v=edge[i].to; if(v==fa)continue; dfs_1(v,now); size[now]+=size[v]; st[now]=st[now]^st[v]; } if(now!=1){ //ull tmp1=mk_hash(n-size[now],st[now]); //ull tmp2=_mk_hash(n-size[now],st[now]); //printf("**%d %lld\n",now,tmp); //printf("%lld %lld\n",tmp1,tmp2); g[st[now]+size[now]]++; } return ;}ll ans=0;void dfs_2(int now,int fa){ int v;_size[now]=1,_st[now]=w[now]; for(ri i=_h[now];i;i=_edge[i].ne){ v=_edge[i].to; if(v==fa)continue; dfs_2(v,now); _size[now]+=_size[v]; _st[now]=_st[now]^_st[v]; } if(now!=1){ //ull tmp1=mk_hash(n-_size[now],_st[now]); //ull tmp2=_mk_hash(n-_size[now],_st[now]); //if(g[tmp]!=0)printf("%d %lld\n",now,tmp); ans+=g[_st[now]+_size[now]]; } return ;}int main(){ int x,y; srand(1926081764); read(n); for(ri i=1;i

B

分析

首先有个比较显然的是(样例比较良心还提示了)这个答案肯定在最小生成树上

所以5分做法就是枚举挖掉一个点的最小生成树,然而要\(long\) \(long\)就导致我爆零了

然后25分做法是枚举挖掉一个点x后形成du[x]个联通块,将这些联通块与x相邻的点做MST

60分做法就比较神,用可并堆维护当前联通块的返祖边的最小值然后不断合并统计答案，当然要考虑横插边的影响

100分用并查集优化看不懂

C

分析

随机化很好写,5分很好拿

然后面积因为是单位圆直接角度算不用叉积

本来想写个模拟退火但是想不出来怎么做

题解动规我的软肋听不懂，弃疗

转载于:https://www.cnblogs.com/Rye-Catcher/p/9393296.html

你可能感兴趣的文章