[hdu7078]Pty with card

显然问题被分为两部分，先考虑如何求$F(n)$——

令第一次所选的人编号为1，其之后所有人按顺时针依次编号为$2,3,...,n$，那么用一个序列来描述状态，其中第$i$个元素为当前存在的人中编号第$i$小的人手牌数（显然序列长度即为剩余人数）

初始序列显然为$\{1,1,...,1\}$（共$n$个1），并对$n$的奇偶性分类讨论：

1.若$n$为奇数，则$n$轮后序列为$\{3,2,2,...,2\}$（其中共$\frac{n-3}{2}$个2）

2.若$n$为偶数，则$n$轮后序列为$\{4,2,2,...,2\}$（其中共$\frac{n}{2}-2$个2）

（关于这个结果，手动模拟若干次即可得到规律）

注意到此时所有元素都$\ge 2$，那么若序列长度为$2m+1$（其中$m\in Z^{+}$），循环节即恰为$4m+2$

关于这个性质，考虑两轮中每一个人都会在奇数轮操作一次、偶数轮操作一次，那么总共即恰好失去3张卡片并得到3张卡片，因此卡牌数量不变，且由于初始有两张卡片，不会有人"出局"

下面，考虑序列长度为$2m$，再对两类分别讨论：

1.若$n$为奇数（注意不是$m$），则$2m$轮后序列为$\{2,3,1,3,1,3...,1,3\}$（其中共$m-1$对$1,3$），再$2m$轮后序列为$\{5,4,4,...,4\}$（其中共$m-1$个4）

不难发现如果序列长度仍是偶数，其又会变为$\{9,8,8,...,8\},\{17,16,16,...,16\},...$（可以归纳证明），直至序列长度为奇数（答案为序列长度的两倍）

2.若$n$为偶数，类似的$4m$轮后序列为$\{6,4,4,...,4\}$（其中共$m-1$个4），如果序列长度仍是偶数，其又会变为$\{10,8,8,...,8\},\{18,16,16,...,16\},...$，直至序列长度为奇数

（另外，若最终序列长度为1则$F(n)=0$）

综上，有
$$
F(n)=\begin{cases}0&\left(n\le 2\right)\or \left(lowbit(m)=1\right)\\\frac{2m}{lowbit(m)}&\left(n\ge 3\right)\and \left(lowbit(m)\ne 1\right)\end{cases}
$$
（其中$m=\lfloor\frac{n-1}{2}\rfloor$，$lowbit(m)$指$m$二进制下最低位上的1对应的值）

接下来，考虑如何求$\forall 1\le x\le n,\sum_{i=1}^{n}F(v_{i}+d(i,x))$——

将其点分治，问题即是要维护一个集合$S$，支持：1.加入一个元素$x$；2.（给定$x$）查询$\sum_{y\in S}F(x+y)$

这个并不容易维护，但注意到查询中$x$即为某点到当前点分中心的距离，是连续变化的，因此这个问题还可以看作支持：1.加入一个元素$x$；2.令所有元素+1；3.查询$\sum_{x\in S}F(x)$

维护一棵trie树，并且从低到高存储数字，依次考虑这些操作：

1.加入一个元素$x$，与普通的trie树相同

2.令所有元素+1，即不断交换左右儿子，并递归（新的）左儿子即可

3.查询$\sum_{x\in S}F(x)$，不断递归左儿子，维护子树中所有元素的和即可（注意去掉$lowbit(m)=1$的情况）

由此，单次操作时间复杂度为$o(\log n)$，总复杂度即$o(n\log^{2}n)$，可以通过

  1 #include<bits/stdc++.h>

  2 using namespace std;

  3 #define N 100005

  4 #define ll long long

  5 struct Edge{

  6     int nex,to;

  7 }edge[N<<1];

  8 vector<int>v[N];

  9 int E,rt,t,n,x,y,mx,a[N],head[N],vis[N],sz[N],f[N<<2];

 10 ll ans[N];

 11 int lowbit(int k){

 12     return (k&(-k));

 13 }

 14 namespace Trie{

 15     int V,tag,st[N],L[N*6],sz[N*6],ch[N*6][2];

 16     ll sum[N*6];

 17     int New(){

 18         int k=++V;

 19         L[k]=sz[k]=sum[k]=ch[k][0]=ch[k][1]=0;

 20         return k;

 21     }

 22     ll get(int k){

 23         return sum[k]+(ll)tag*sz[k];

 24     }

 25     void init(){

 26         V=tag=0;

 27         New();

 28     }

 29     void add_val(int x){

 30         st[0]=st[1]=1;

 31         for(int i=0,k=1;i<18;i++){

 32             int p=((x>>i)&1);

 33             if (!ch[k][p])ch[k][p]=New();

 34             k=st[++st[0]]=ch[k][p];

 35         }

 36         for(int i=1;i<=st[0];i++)sz[st[i]]++,sum[st[i]]+=x;

 37         L[st[st[0]]]=st[st[0]];

 38         for(int i=st[0]-1;i;i--)L[st[i]]=L[ch[st[i]][0]];

 39     }

 40     void Add(){

 41         tag++;

 42         st[0]=st[1]=1;

 43         for(int i=0,k=1;(i<18)&&(k);i++){

 44             swap(ch[k][0],ch[k][1]);

 45             k=st[++st[0]]=ch[k][0];

 46         }

 47         L[st[st[0]]]=st[st[0]];

 48         for(int i=st[0]-1;i;i--)L[st[i]]=L[ch[st[i]][0]];

 49     }

 50     ll query(){

 51         ll ans=0;

 52         for(int i=1,k=ch[1][0];(i<18)&&(k);i++){

 53             ans+=(get(ch[k][1])-get(L[ch[k][1]])>>i-1);

 54             k=ch[k][0];

 55         }

 56         tag--;

 57         for(int i=1,k=ch[1][1];(i<18)&&(k);i++){

 58             ans+=(get(ch[k][1])-get(L[ch[k][1]])>>i-1);

 59             k=ch[k][0];

 60         }

 61         tag++;

 62         return ans;

 63     }

 64 }

 65 void add_edge(int x,int y){

 66     edge[E].nex=head[x];

 67     edge[E].to=y;

 68     head[x]=E++;

 69 }

 70 void get_sz(int k,int fa){

 71     sz[k]=1;

 72     for(int i=head[k];i!=-1;i=edge[i].nex)

 73         if ((!vis[edge[i].to])&&(edge[i].to!=fa)){

 74             get_sz(edge[i].to,k);

 75             sz[k]+=sz[edge[i].to];

 76         }

 77 }

 78 void get_rt(int k,int fa,int s){

 79     int mx=s-sz[k];

 80     for(int i=head[k];i!=-1;i=edge[i].nex)

 81         if ((!vis[edge[i].to])&&(edge[i].to!=fa)){

 82             get_rt(edge[i].to,k,s);

 83             mx=max(mx,sz[edge[i].to]);

 84         }

 85     if (mx<=(s>>1))rt=k;

 86 }

 87 void get_val(int k,int fa,int s){

 88     if (mx<s)v[++mx].clear();

 89     v[s].push_back(k);

 90     Trie::add_val(a[k]+s);

 91     for(int i=head[k];i!=-1;i=edge[i].nex)

 92         if ((!vis[edge[i].to])&&(edge[i].to!=fa))get_val(edge[i].to,k,s+1);

 93 }

 94 void calc(int k,int p){

 95     Trie::init();

 96     mx=0,v[0].clear();

 97     get_val(k,0,p);

 98     p=1-(p<<1);

 99     for(int i=0;i<=mx;i++){

100         ll s=Trie::query();

101         for(int j=0;j<v[i].size();j++)ans[v[i][j]]+=p*s;

102         Trie::Add();

103     }

104 }

105 void dfs(int k){

106     get_sz(k,0);

107     get_rt(k,0,sz[k]);

108     calc(rt,0);

109     vis[rt]=1;

110     for(int i=head[rt];i!=-1;i=edge[i].nex)

111         if (!vis[edge[i].to])calc(edge[i].to,1);

112     for(int i=head[rt];i!=-1;i=edge[i].nex)

113         if (!vis[edge[i].to])dfs(edge[i].to);

114 }

115 int main(){

116     for(int i=2;i<(N<<2);i++)

117         if (lowbit(i>>1)==1)f[i]=0;

118         else f[i]=((i>>1)/lowbit(i>>1)<<1);

119     scanf("%d",&t);

120     while (t--){

121         scanf("%d",&n);

122         E=0;

123         memset(head,-1,sizeof(head));

124         memset(vis,0,sizeof(vis));

125         memset(ans,0,sizeof(ans));

126         for(int i=1;i<=n;i++){

127             scanf("%d",&a[i]);

128             a[i]--;

129         }

130         for(int i=1;i<n;i++){

131             scanf("%d%d",&x,&y);

132             add_edge(x,y);

133             add_edge(y,x);

134         }

135         dfs(1);

136         for(int i=1;i<n;i++)printf("%lld ",ans[i]);

137         printf("%lld\n",ans[n]);

138     }

139     return 0;

140 }

巴特西

[hdu7078]Pty with card

最新文章

热门文章