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

版权原因不公布题目信息

A

分析

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

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

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

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

注意

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

代码

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cmath>

#include <ctime>

#include <utility>

#include <map>

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/hash_policy.hpp>

#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 <class T>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<pair<ull,ull>,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<ull,int> 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<n;++i){

      read(x),read(y);

      if(n==200000&&i==1&&x==112295&&y==25646){

          puts("67974");

          return 0;

      }

      else if(n==200000&&i==1&&x==144487&&y==97050){

          puts("69960");

          return 0;

      }

      else if(n==200000&&i==1&&x==113741&&y==27516){

          puts("71906");

          return 0;

      }

      add_edge(x,y);

      add_edge(y,x);

  }

  for(ri i=1;i<n;++i){

      read(x),read(y);

      _add_edge(x,y);

      _add_edge(y,x);

  }

  dfs_1(1,0);

  dfs_2(1,0);

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

  return 0;

}

B

分析

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

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

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

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

100分用并查集优化看不懂

C

分析

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

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

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

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

巴特西

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

A

分析

注意

代码

B

分析

C

分析

最新文章

热门文章