ZJT's Blog

大変に気分がいい~

[自选题 #154] 简单数据结构题

2017-11-3 0:512017-11-3 0:51
集训队作业自选题链表

传送门

是不是只有我这个傻逼全程没有想到trie,强行拿一堆双向循环链表做的啊。。。

首先我们可以$O(1)$的维护每个点当前的值,所以询问的时候就可以当父亲不存在了。接下来就只用维护每个点的所有儿子,支持某个点所有儿子整体+1,还要支持单个儿子+1。

考虑第$k$位为1的数$x$,肯定满足$(x\%2^{k+1})\geq2^k$。所以对每个$k$,如果在某一次+1时有某个数达到了$2^k$,就直接把$[0,2^{k+1})$中的每个取值看成一个节点,建一个双向循环链表,在每个点上维护有多少数模$2^{k+1}$后为这个值。同时,维护指向$0$号节点和$2^k$号节点的指针,以及$[2^k,2^{k+1})$之间有多少数。这样的话,整体+1就是整体循环右移一位,也相当于两个指针左移一位。为了支持单个儿子+1,我们还得维护每个儿子当前的指针。当某一步+1之后发现有数从$2^{k+1}-1$回到了$0$,就说明在更高的位上发生了进位,检查一下需不需要建$2^{k+1}$的链表就行了。

建链表的代价均摊下来是每次$O(1)$,然后每次建链表都要遍历一下儿子,而每个点最多只会建$O(\log q)$次链表,所以遍历儿子的代价是$O(n\log q)$的。总复杂度就是1个log啦。

#include <cstdio>
#include <cstring>
#define MAXN 1000010
#define LL long long

const LL P=1000000007;

int read(){
    char c;
    while((c=getchar())<'0' || c>'9');
    int res=c-'0';
    while((c=getchar())>='0' && c<='9') res=res*10+c-'0';
    return res;
}

struct edge{
    int to,next;
    edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[MAXN<<1];

int n,m;
int g[MAXN],nume;
int d1[MAXN],d2[MAXN];
int pre[MAXN];
int s[MAXN][21];

struct node{
    int s;
    node *prev,*next;
}*pt[500010][21];

struct List{
    node *h1,*h2;
}ls[500010][21];

void addEdge(int u,int v){
    e[nume]=edge(v,g[u]);
    g[u]=nume++;
}

void dfs(int x,int p){
    pre[x]=p;
    ls[x][0].h1=new node;
    ls[x][0].h1->s=0;
    ls[x][0].h2=new node;
    ls[x][0].h2->s=0;
    ls[x][0].h1->prev=ls[x][0].h1->next=ls[x][0].h2;
    ls[x][0].h2->prev=ls[x][0].h2->next=ls[x][0].h1;
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to^p){
            dfs(e[i].to,x);
            ls[x][0].h1->s++;
            pt[e[i].to][0]=ls[x][0].h1;
        }
}

int getV(int x){ return d2[x]+d1[pre[x]]; }

void build(int x,int i){
    int l=1<<i;
    static node* temp[MAXN];
    for(int j=0;j<l<<1;j++){
        temp[j]=new node;
        temp[j]->s=0;
    }
    for(int j=0;j<l<<1;j++){
        temp[j]->next=temp[(j+1)%(l<<1)];
        temp[j]->prev=temp[(j-1+(l<<1))%(l<<1)];
    }
    ls[x][i].h1=temp[0];
    ls[x][i].h2=temp[l];
    for(int j=g[x];~j;j=e[j].next)
        if(e[j].to^pre[x]){
            int v=getV(e[j].to);
            int b=v&((l<<1)-1);
            if(b>=l) s[x][i]++;
            temp[b]->s++;
            pt[e[j].to][i]=temp[b];
        }
}

void gao1(int x){
    if(!pre[x]) return;
    int v=getV(x);
    for(int i=0;i<=20;i++)
        if(ls[pre[x]][i].h1){
            pt[x][i]->s--;
            pt[x][i]=pt[x][i]->next;
            pt[x][i]->s++;
            if(pt[x][i]==ls[pre[x]][i].h1) s[pre[x]][i]--;
            if(pt[x][i]==ls[pre[x]][i].h2) s[pre[x]][i]++;
        }else if(pt[x][i-1]==ls[pre[x]][i-1].h1){
            build(pre[x],i);
        }else break;
}

void gao2(int x){
    for(int i=0;i<=20;i++)
        if(ls[x][i].h1){
            ls[x][i].h1=ls[x][i].h1->prev;
            ls[x][i].h2=ls[x][i].h2->prev;
            s[x][i]+=ls[x][i].h2->s-ls[x][i].h1->s;
        }else if(ls[x][i-1].h1->s){
            build(x,i);
        }else break;
}

int query(int x){
    int res=0;
    for(int i=0;i<=20;i++)
        if(s[x][i]&1)
            res^=1<<i;
    return res;
}

int gao(int x){
    if(pre[x]) d2[pre[x]]++;
    d1[x]++;
    gao1(pre[x]);
    gao2(x);
    int res=query(x)^getV(pre[x]);
    return res;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
#endif
    memset(g,-1,sizeof g);
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++){
        int u=read(),v=read();
        addEdge(u,v);
        addEdge(v,u);
    }
    dfs(1,0);
    LL ans=0;
    for(LL i=1;i<=m;i++){
        int x=read();
        LL temp=gao(x);
        ans=(ans+temp*(i*i%P+i))%P;
    }
    printf("%lld\n",ans);
    return 0;
}

查看详细内容

集训队作业之AGC002-E

2017-9-30 1:12017-11-27 19:20
集训队作业AtCoderDP链表博弈论

传送门

最后一步算输的话,似乎不能用SG函数。。?然而这题根本没有什么子游戏,直接按先手是否必胜dp就行了。

首先把$a_i$排好序。设$f[i][j]$表示前$i$堆,执行了$j$次2操作后是否先手必胜。为了方便,我们直接把所有不可到达的状态(即$j\geq\max_{k=1}^ia_k{}$)的dp值设为1。其余状态的转移是:$$f[i][j]=(!f[i-1][j])||(!f[i][j+1])$$

然而直接dp显然过不了,所以我们尝试用一些数据结构去维护这个dp值。注意到不可能出现$f[i][j]=f[i][j+1]=0$的情况,所以每一层的dp值都必定是一些形如$10101...101$的东西拼在一起。我们直接用链表维护每个$101...101$的右端点,然后每次根据$a_i$的位置进行处理就行了(细节看代码吧)。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <list>
#define MAXN 1000010
using namespace std;

namespace S{
    list<int> ls;
    int delta;

    void add_all(int v){
        delta+=v;
    }

    int front(){
        return (*ls.begin())+delta;
    }

    void pop_front(){
        ls.pop_front();
    }

    int back(){
        return (*(--ls.end()))+delta;
    }

    void pop_back(){
        ls.pop_back();
    }

    void push_back(int x){
        ls.push_back(x-delta);
    }

    bool empty(){
        return ls.empty();
    }
}

int n;
int a[MAXN];

int main(){
#ifdef DEBUG
    freopen("E.in","r",stdin);
#endif
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",a+i);
    sort(a+1,a+n+1);
    S::push_back(a[1]);
    for(int i=2;i<=n;i++)
        if(a[i]>S::back()){
            if((a[i]-S::back())&1) S::pop_back();
            S::add_all(-1);
            while(!S::empty() && S::front()<0) S::pop_front();
            S::push_back(a[i]);
        }else{
            S::add_all(-1);
            while(!S::empty() && S::front()<0) S::pop_front();
        }
    if(S::front()&1) puts("Second");
    else puts("First");
}

查看详细内容