BestCoder Round #65 B C D || HDU 5591 5592 5593-白红宇

BestCoder Round #65 B C D || HDU 5591 5592 5593

阅读量：4632 次

发布时间：2019-06-09

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

B 题意：ZYB在远足中,和同学们玩了一个“数字炸弹”游戏：由主持人心里想一个在[1,N][1,N]中的数字XX，然后玩家们轮流猜一个数字，如果一个玩家恰好猜中XX则算负，否则主持人将告诉全场的人当前的数和XX比是偏大还是偏小，然后猜测的范围就会相应减小，一开始的范围是[1,N][1,N].每个玩家只能在合法的范围中猜测. 现在假设只有两个人在玩这个游戏,并且两个人都已经知道了最后的XX,若两个人都采取最优策略.求X \in [1,N]X∈[1,N]中是后手胜利的XX数量.

思路: 当n为奇数时，比如5： 1 2 3 4 5 。发现只有当X==3时先手必输(后手始终可以跟着先手关于3的对称点选) 那么X==2(先手猜4，后手只能猜1 || 3 都是输) || 4(雷同) || 1(先手直接猜2 后手输) || 5(雷同)

那么当n为偶数时，比如 4: 1 2 3 4 。当前 X== 1 || 4 时先手赢，当X==2时，先手猜4那么又变成奇数的情况了所以一直都是先手赢

代码略......

C 题意: ZYB有一个排列P,但他只记得P中每个前缀区间的逆序对数,现在他要求你还原这个排列.

(i,j)(i < j)(i,j)(i<j)被称为一对逆序对当且仅当Ai>Aj

给定的ai是前缀区间[1,i]里面的逆序对数直接说一组样例

下标 1 2 3 4 5 6

ai 0 1 1 4 8 10

全排列 5 3 6 2 1 4

很容易发现，ai从后往前，可以知道当前这个数在[1,i]区间有几个数比它大==a[i]-a[i-1];

10-8=2;当前[1,6]区间有2个数比它大，那么anw[6]=4;

8-4=4 ;当前[1,5]区间有四个数(6,5,3,2)比它大，4已经选了，那么anw[5]=1;

4-1=3;当前[1,4]区间有三个数(6,5,3)比它大，1,4已经选了，anw[4]=2;

1-1=0;当前[1,3]区间有0个数比它大，1,2,4已经选了，anw[3]=6;

1-0=1;当前[1,2]区间有1个数比它大，1,2,4,6已经选了,anw[2]=3;

1-0=0; 当前[1,1]区间有0个数比它大，1,2,3,4,6已经选了，anw[1]=5。

也就是用线段树或者树状数组维护第k小。k=i-(a[i]-a[i-1]);

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include 
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #define mst(ss,b) memset((ss),(b),sizeof(ss))#define maxn 0x3f3f3f3f///#pragma comment(linker, "/STACK:102400000,102400000")typedef long long ll;#define INF (1ll<<60)-1using namespace std;int n;int a[50010],tr[200010],anw[50010];void build(int root,int l,int r){ if(l==r){ tr[root]=1; return ; } int mid=(l+r)>>1; build(root*2,l,mid); build(root*2+1,mid+1,r); tr[root]=tr[root*2]+tr[root*2+1];}int query(int root,int l,int r,int k){ if(l==r){ return l; } int mid=(l+r)>>1; if(tr[root*2]>=k) return query(root*2,l,mid,k); else return query(root*2+1,mid+1,r,k-tr[root*2]);}void update(int pos,int v,int root,int l,int r){ if(l==r){ tr[root]=v; return ; } int mid=(l+r)>>1; if(pos>mid) update(pos,v,root*2+1,mid+1,r); else update(pos,v,root*2,l,mid); tr[root]=tr[root*2]+tr[root*2+1];}int main(){ int T; scanf("%d",&T); while(T--){ mst(a,0); mst(anw,0); scanf("%d",&n); build(1,1,n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=n;i>=1;i--){ int x=a[i]-a[i-1]; anw[i]=query(1,1,n,i-x); update(anw[i],0,1,1,n); } for(int i=1;i<=n;i++){ if(i==1) printf("%d",anw[i]); else printf(" %d",anw[i]); } printf("\n"); } return 0;}

D题意：ZYB有一颗N个节点的树,现在他希望你对于每一个点,求出离每个点距离不超过K的点的个数.

两个点(x,y)在树上的距离定义为两个点树上最短路径经过的边数,输出N个点的答案的xor和。

思路:第一遍DFS找当前节点向下走的长度<=k的num。第二遍DFS找当前节点向上走的长度<=k的num。

第一遍的时候直接搜就可以了，第二遍分两次取anw，令前节点为v,当前节点的父亲为x,仔细想一下，要寻找当前节点向上的num，是不是可以分成

1.找v的兄弟的num也就是父亲x的子节点 2.找父亲x的祖先到x长度<=k-1的num

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include 
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #define mst(ss,b) memset((ss),(b),sizeof(ss))#define inf 0x3f3f3f3f#define MAX 500010#pragma comment(linker, "/STACK:102400000,102400000")typedef long long ll;#define INF (1ll<<60)-1using namespace std;int n,k,A,B,tot;int head[MAX];struct node{ int to,next;}edge[MAX];void add(int u,int v){ edge[tot].to=v; /// 当前边 u->v edge[tot].next=head[u]; /// 连接 u 节点的上一条边 head[u]=tot++;}int son[MAX][15],pre[MAX][15],anw[MAX];void init(){ mst(head,-1); mst(son,0); mst(pre,0); mst(anw,0);tot=0;}void DFS(int x){ son[x][0]=1; for(int i=head[x];i!=-1;i=edge[i].next){ int v=edge[i].to; DFS(v); for(int j=1;j<=k;j++) son[x][j]+=son[v][j-1]; }}void DFS1(int x){ ///pre[x][0]=1; for(int i=0;i<=k;i++) anw[x]+=(son[x][i]+pre[x][i]); for(int i=head[x];i!=-1;i=edge[i].next){ int v=edge[i].to; for(int j=1;j<13;j++) pre[v][j]+=(pre[x][j-1]); pre[v][1]++; for(int j=2;j<13;j++) pre[v][j]+=(son[x][j-1]-son[v][j-2]); DFS1(v); }}int main(){ int T; scanf("%d",&T); while(T--){ init(); scanf("%d%d%d%d",&n,&k,&A,&B); for(int i=2;i<=n;i++){ ll w=((ll)A*i+B)%(i-1)+1; add((int)w,i); } DFS(1);DFS1(1); /*for(ll i=1;i<=n;i++) cout<
                 
                  <<" "; cout<

转载于:https://www.cnblogs.com/CrossCross/p/5029431.html

你可能感兴趣的文章