作者存档：edward_mj

[SGU187 Twist and whirl – want to cheat]【Splay】

【题目大意】

给定一个1~n的排列，每次操作会将[l,r]这个区间上的数翻转。问到最后，整个排列变成个什么样？

【算法分析】

就是Splay加个翻转操作啦。。。非常easy。用来增加自信心。。。。

属于被秒杀题类型。。。

【时间复杂度】O(m lg n)

【空间复杂度】O(n)

【其它】1Y。

【CODE】

#include

[POJ3764 The xor-longest Path]【异或运算】【Trie树】

【题目大意】给定一棵树，然后一条树的路径的权和定义为路径上边权全部xor之后得出的值

【算法分析】树的话。设d[x]为从根到x这条路径的权。那么两点间的路径权就是d[x] xor d[y]。（LCA到根部分被两次xor抵消啦），然后就转化为给定n个数，求d[x]^d[y]最大。这个就和USACO第6章那个cowxor一模一样啦。利用Trie树求解。

【时间复杂度】O(30*N)

【空间复杂度】O(30*N)

【其它】1Y。在lcc大神空间看到有这题，然后一看题目。。。Orz，再次见面的题目就成水题啦。。。睡前一水。

【CODE】

#include #include #include const int N=100005; struct edge{int y,w;edge *next;}g[N*2],*ls[N]; int n,e,tot; int d[N],L[N],v[N],ch[N*32][2];
void addedge(int x,int y,int w){       g[++e].y=y; g[e].w=w; g[e].next=ls[x]; ls[x]=&g[e];       g[++e].y=x; g[e].w=w; g[e].next=ls[y]; ls[y]=&g[e]; }
void init(){      int i,x,y,w;      for (e=i=0;i     for (i=1;i          scanf("%d%d%d",&x,&y,&w);           addedge(x,y,w);       } }
void bfs(){      int i,head=-1,tail=0;      for (i=0;i      v[0]=1; L[0]=d[0]=0;      while (head!=tail){             head++;            for (edge *t=ls[L[head]];t;t=t->next)              if (!v[t->y]){                 d[t->y]=d[L[head]]^t->w;                 v[t->y]=1;                 L[++tail]=t->y;               }       } }
void Insert(int x){      int s,p,t;      for (p=1,s=30;s>=0;s--){         t=( (1<       if (!ch[p][t]){           ch[p][t]=++tot;           ch[tot][0]=ch[tot][1]=0;         }         p=ch[p][t];       } }
int Get(int x){     int res=0,s,p,t;     for (p=1,s=30;s>=0;s--){        t=( (1<      if (ch[p][!t]) {p=ch[p][!t]; res|=!t<                else {p=ch[p][t];   res|= t<     }     return res^x; }
void work(){       tot=1;       ch[1][0]=ch[1][1]=0;       Insert(d[0]);      int i,ans=0,now;      for (i=1;i          now=Get(d[i]);          if (now>ans) ans=now;           Insert(d[i]);       }       printf("%dn",ans); }
int main(){     while (scanf("%d",&n)!=EOF){            init();            bfs();            work();      } }

[HDOJ1423 Greatest Common Increasing Subsequence]【最长公共上升子序列】

【算法分析】裸的dp。时间复杂度 O(mn)。空间复杂度 O(m+n)。

【其它】今天有人问我。。。于是就做了。= =，我还恶趣味地把代码压短了。。。搞到434B。大家不要鄙视我。。。起码还是有层次感的。。。不是恶意压行那种。。。

【CODE】

#include using namespace std; int m,n,T,k,i,j,r,p,a[505],b[505],F[505]; int main(){      cin>>T;     for (k=1;k<=T;k++){       for (cin>>m,i=0;i      for (cin>>n,i=0;i      for (r=p=0,i=0;i        for (j=0;j           p>?=b[j]           F[j]>?=a[i]==b[j]?p+1:0;          }        cout<       k!=T?puts(""):0;      } }

[HDOJ3440 House Man]【差分约束系统】

【题目大意】有n栋楼和一个SuperMan，每个都拥有一个唯一的高度，然后SuperMan每次会从第i高的楼，跳到第i+1高的楼上去。这些楼被安排在一个一维坐标轴上，然后这些楼有一个初始顺序，你是不能改变的。这些楼必须在整点上，并且不允许重叠，然后你要帮SuperMan安排这些楼，使得最高的楼和最低的楼距离之差最大。如果没有可行解，输出-1.

【算法分析】差分约束典型题目。根据那两个条件建好边，以最低楼和最高楼中顺序靠前的做起点，搞单源最短路，有环判无解，否则输出最高楼和最低楼d值之差的绝对值即可。

【其它】1Y

【CODE】

#include const int N=1005;
const int E=500005;
const int INF=0x7FFFFFFF/2-22;
int n,e,D;
int d[N],a[N],zz[N];
struct edge{int x,y,w;}g[E];

int cmp(const void *A,const void *B){
    return a[*((int*)A)]-a[*((int*)B)];
}

void add(int x,int y,int w){
     g[++e].x=x; g[e].y=y; g[e].w=w;
}

void init(){
     int i;
     scanf("%d%d",&n,&D);
     for (i=1;i<=n;i++){
       scanf("%d",&a[i]); zz[i]=i; } qsort(zz+1,n,sizeof(int),cmp);
     e=0;
     for (i=1;i     for (i=1;i       if (zz[i]                     else add(zz[i+1],zz[i],D);
}

void Bellman_Ford(){
     int i,j;
     for (i=1;i<=n;i++) d[i]=INF;
     if (zz[1]                 else d[zz[n]]=0;
     bool flag;
     for (i=1;i<=n;i++){
         flag=false;
         for (j=1;j<=e;j++)
           if (d[g[j].x]+g[j].w             flag=true;
             d[g[j].y]=d[g[j].x]+g[j].w;
           }
         if (!flag) break;
     }
     if (flag) { puts("-1"); return; }
     else if (zz[1]                      else printf("%dn",d[zz[1]]-d[zz[n]]);
}

int main(){
    int i,Tc;
    scanf("%d",&Tc);
    for (i=1;i<=Tc;i++){
        printf("Case %d: ",i);
        e=0;
        init();
        Bellman_Ford();
    }
    return 0;
}

[HDOJ3436 Queue-jumpers]【Splay练手】

【题目大意】

一开始给定n个人，他们按编号1..n地排好了。

有3个操作。

分别是：

Top x：把编号为x个人放到a[1]。然后a[1..x-1]的数都向后移一位。

Query x：返回编号为x个人现在在哪里位置。

Rank x：返回排名在x的这个人是编号是多少？

【算法分析】

我采用的是Splay来离线解决。

由于n高达10^8。所以不能完全模拟。

首先是把询问都读进来，然后对于Top和Query碰到的编号，开一个List取出来，排序并去重。

然后开始构建Splay。

对于在List中的编号，我们把他构建成一个结点。

然后对于List[i]和List[i-1]之间的间隙结点，我把它们都压缩成一个结点。（当然Size的计算方法就有点不同了。）

然后这样，Splay上最多有2*Q个点了。

对于Top操作，我们就相当于删掉这个点，再插入一次这个点。

对于Query，我们可以直接把这个点Splay到根，然后算他的左子树的Size，+1就是答案。

对于Rank，我们就像找第k个元素那样，找到那个对应位置，输出就行了。（就是压缩块有点不同而已）

【其它】

2TLE。写惯了SBT。。。那个父亲的域老是忘了维护，导致死循环了。

【CODE】

#include

#include

#include #define update(p) (Tr[p].Size=Tr[ch[p][0]].Size+Tr[ch[p][1]].Size+Tr[p].weight)
const int N=305555;

struct Splay_t{
       int root,tot,Lasttop;
       int ch[N][2],pre[N];
       struct Node{int St,Size,weight;}Tr[N];
      
       void init(){
            root=tot=1;
            Lasttop=2;
            ch[1][0]=ch[1][1]=0;
            Tr[0].Size=0;
            pre[1]=0;
       }
      
       void rotate(int x,int T){
            int y=pre[x];
            if (T){
              ch[y][0]=ch[x][1];
              ch[x][1]=y;
              pre[ch[y][0]]=y;
              pre[x]=pre[y];
              pre[y]=x;
            }
            else{
              ch[y][1]=ch[x][0];
              ch[x][0]=y;
              pre[ch[y][1]]=y;
              pre[x]=pre[y];
              pre[y]=x;
            }
            if (ch[pre[x]][0]==y) ch[pre[x]][0]=x;
                             else ch[pre[x]][1]=x;
            update(y);
            update(x);
       }
      
       void Splay(int x,int cut){
            if (x==cut) return;
            int y,z;
            while (pre[x]!=cut){
                  y=pre[x]; z=pre[y];
                  if (z==cut) rotate(x,ch[y][0]==x);
                  else
                  if (ch[z][0]==y)
                    if (ch[y][0]==x) {rotate(y,1); rotate(x,1);}
                                else {rotate(x,0); rotate(x,1);}
                  else
                    if (ch[y][1]==x) {rotate(y,0); rotate(x,0);}
                                else {rotate(x,1); rotate(x,0);}
            }
       }
      
       void Ins(int St,int weight){
            tot++;
            ch[tot][0]=ch[tot][1]=0;
            Tr[tot].St=St;
            Tr[tot].weight=Tr[tot].Size=weight;
            if (tot==2){
              ch[root][0]=2;
              pre[2]=root;
            }
            else{
              Splay(tot-1,root);
              ch[tot-1][1]=tot;
              update(tot-1);
              pre[tot]=tot-1;
            }
            Splay(tot,root);
       }
      
       void Top(int x){
            if (Lasttop==x) return;
            Splay(x,root);
            int p,q;
            q=x; p=ch[x][1];
            while (p){
                  q=p;
                  p=ch[p][0];
            }
            if (q==x){
              ch[1][0]=ch[x][0];
              pre[ch[x][0]]=1;
            }
            else{
              Splay(q,x);
              ch[q][0]=ch[x][0];
              pre[q]=1;
              pre[ch[x][0]]=q;
              ch[1][0]=q;
              update(q);
            }
            Splay(Lasttop,root);
            ch[Lasttop][0]=x;
            pre[x]=Lasttop;
            ch[x][0]=ch[x][1]=0;
            update(x);
            update(Lasttop);
            Lasttop=x;
       }      
      
       int Query(int x){
           Splay(x,root);
           return Tr[ch[x][0]].Size+1;
       }
      
       int rank(int x){
           int p,done=0;
           p=ch[root][0];
           while (1){
                 if (x<=Tr[ch[p][0]].Size+done)
                   p=ch[p][0];
                 else
                 if (x>Tr[ch[p][0]].Size+done+Tr[p].weight){
                   done+=Tr[ch[p][0]].Size+Tr[p].weight;
                   p=ch[p][1];
                 }
                 else break;
           }
           Splay(p,root);
           return x-Tr[ch[p][0]].Size+Tr[p].St-1;
       }
      
}Splay;
int n,Q,Lt;
int op[N],a[N],List[N],pos[N];

int cmp(const void *A,const void *B){return *((int*)A) – *((int*)B);}
void init(){
     int i,cnt;
     Lt=List[0]=0;
     char Str[100];
     scanf("%d%d",&n,&Q);
     for (i=1;i<=Q;i++){
         scanf("%s%d",Str,&a[i]);
         switch (Str[0]){
                case ‘T’:op[i]=1; break;
                case ‘Q’:op[i]=2; break;
                case ‘R’:op[i]=3; break;
         }
         if (op[i]!=3) List[++Lt]=a[i];
     }
     qsort(List+1,Lt,sizeof(int),cmp);
     for (i=1,cnt=0;i<=Lt;i++){
         cnt+=(!cnt || List[i]!=List[cnt]);
         List[cnt]=List[i];
     }
     Lt=cnt;
}

void pre_Insert(){
     int i;
     Splay.init();
     for (List[0]=0,i=1;i<=Lt;i++){
         if (List[i]-List[i-1]>1)
           Splay.Ins(List[i-1]+1,List[i]-List[i-1]-1);
         Splay.Ins(List[i],1);
         pos[i]=Splay.tot;
     }
}

int Find(int x){
    int l=1,r=Lt,mid;
    while (l          mid=(l+r)/2;
          if (x>List[mid]) l=mid+1;
                      else r=mid;
    }
    return pos[l];
}

void solve(){
     int i;
     for (i=1;i<=Q;i++)
       switch (op[i]){
              case 1:Splay.Top(Find(a[i])); break;
              case 2:printf("%dn",Splay.Query(Find(a[i]))); break;
              case 3:
                   if (a[i]>List[Lt]) printf("%dn",a[i]);
                                 else printf("%dn",Splay.rank(a[i]));
                   break;
       }
}

int main(){
    int Tc,i;
    scanf("%d",&Tc);
    for (i=1;i<=Tc;i++){
        printf("Case %d:n",i);
        init();
        pre_Insert();
        solve();
    }
}