Boleyn Su's Blog

求最大公约数。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-8-24

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using namespace std;

 

int main()

{

    int N,answer=0;

    cin>>N;

    for (int i=1;i<=N;i++)

    {

        int a=N,b=i,t;

        while (b) t=a,a=b,b=t%b;

        if (a==1) answer++;

    }

    cout<<answer<<endl;

}

 

欧拉路。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-8-24

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using namespace std;

 

const int MAXE=100*2;

const int MAXV=6–0+1;

typedef struct struct_edge* edge;

struct struct_edge{int v,id;char dir;edge n;};

struct_edge pool[MAXE];

edge top=pool;

edge adj[MAXV];

int degree[MAXV];

int used[MAXE/2];

int list[MAXE/2+1];

int listtop;

int size[MAXV][MAXV];

edge edges[MAXV][MAXV][MAXE];

int printed[MAXE/2];

void add_edge(int u,int v,int id)

{

     degree[u]++,edges[u][v][size[u][v]++]=top,

     top->v=v,top->id=id,top->dir=’+’,top->n=adj[u],adj[u]=top++;

     degree[v]++,edges[v][u][size[v][u]++]=top,

     top->v=u,top->id=id,top->dir=’-‘,top->n=adj[v],adj[v]=top++;

}

void find_circuit(int u)

{

     for (edge i=adj[u];i;i=i->n)

         if (!used[i->id])

         {

            used[i->id]=true;

            find_circuit(i->v);

         }

     list[listtop++]=u;

}

void print(int u,int v)

{

     for (int i=0;i<size[u][v];i++)

         if (!printed[edges[u][v][i]->id])

         {

            cout<<edges[u][v][i]->id+1<<” “<<edges[u][v][i]->dir<<endl;

            printed[edges[u][v][i]->id]=true;

            break;

         }

}

 

int main()

{

    int N,a,b;

    cin>>N;

    for (int i=0;i<N;i++)

        cin>>a>>b,add_edge(a,b,i);

    int odc=0;

    int S;

    for (int u=0;u<MAXV;u++)

        if (degree[u])

           S=u;

    #define odd(x) ((x)&1)

    for (int u=0;u<MAXV;u++)

        if (odd(degree[u]))

           odc++,S=u;

    if (odc==0||odc==2)

    {

       find_circuit(S);

       if (listtop==N+1)

          for (int i=1;i<listtop;i++)

              print(list[i-1],list[i]);

       else cout<<“No solution”<<endl;

    }

    else cout<<“No solution”<<endl;

}

 

经典题目。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-8-24

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

 

int main()

{

    int a,b;

    std::cin>>a>>b;

    std::cout<<a+b<<std::endl;

}

 

动态规划，斜率优化，具体见这里。

CODE:

 /*

AUTHOR: Su Jiao

DATE: 2010-8-22

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using namespace std;

 

const long long int oo=0X19930309*19930309;

const int MAXN=500000+2;

int T;

int n,k;

long long int a[MAXN];

long long int s[MAXN];

long long int f[MAXN];

int q[MAXN];

int head,tail;

 

int main()

{

    ios::sync_with_stdio(false);

    cin>>T;

    for (int t=0;t<T;t++)

    {

        cin>>n>>k;

        for (int i=1;i<=n;i++) cin>>a[i];

        for (int i=1;i<=n;i++) s[i]=s[i-1]+a[i];

        f[0]=0;

        q[head=tail=0]=0;

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

        {

            #define value(i,j) ((i-j>=k)?(f[j]+s[i]-s[j]-(i-j)*a[j+1]):(oo))

            #define ky(j,k) (f[j]-f[k]+s[k]-s[j]+(j)*a[j+1]-(k)*a[k+1])

            #define kx(j,k) (a[j+1]-a[k+1])

            if (i-k>0)

            {

               while (head<tail

                      &&ky(q[tail-1],q[tail])*kx(q[tail],i-k)

                        >=kx(q[tail-1],q[tail])*ky(q[tail],i-k))

                     tail–;

               q[++tail]=i-k;

            }

            while (head<tail&&value(i,q[head])>value(i,q[head+1])) head++;

            f[i]=value(i,q[head]);

        }

        cout<<f[n]<<endl;

    }

}

 

更新：答案有误，因为答案只证明了当\(n \to \inf\)时，从\(1/n, 2/n, \dots, (n-1)/n\)中平均要取\(e\)个数才能让和超过一，而当\(n \to \inf\)时，\(1/n, 2/n, \dots, (n-1)/n\)并不能和\((0, 1)\)中的实数一一对应。写这个日志的时候才上高中，不知知道可数集不可数集的概念。而且即使把题目改为取有理数，我给出的答案也是不对了。献丑了，哈哈哈。

题目来自Matrix67.com，原文链接http://www.matrix67.com/blog/archives/3507。

Matrix67牛给出了一个用微积分做的解答，当我看到这个题目的时候，我想到了另一个方法。

思考时间，答案在下面（字体是白色的）。

首先，将题目转化为平均要取多少个1到n-1中的随机数才能让和超过n。显然当n趋于无穷大时，这两个问题是等效的。

然后，解：

设f(x)表示平均取多少次才能大于x.
显然 f(x)=0 x<0
     f(x)=1 x=0
对于x>0来说,设之前最后一次取得了i,那么i在1到n-1之间,且取到任意一个数的概率为1/(n-1).
所以 f(x)=sum{(1+f(x-i))/(n-1):1<=i<=n-1}
         =1+sum{f(x-i):1<=i<=n-1}/(n-1)
         =1+sum{f(t):0<=t<=x-1}/(n-1) (如果0<x<n)
         =1+sum{f(t):x-(n-1)<=t<=x-1}/(n-1) (如果x>=n)

对于0<x<n
    令 F(x)=sum{f(i):0<=i<=x}
    则 f(x)=1+F(x-1)/(n-1)     ......[1]
    所以 f(x-1)=1+F(x-2)/(n-1) ......[2]
    [1]式-[2]式得 f(x)-f(x-1)=(F(x-1)-F(x-2))/(n-1)
    所以 (f(x)-f(x-1))*(n-1)=f(x-1)
    所以 f(x)=f(x-1)*n/(n-1)
             =(n/(n-1))^x*f(0)
             =(n/(n-1))^x
所以 f(n)=1+sum{f(t):1<=t<=n-1}/(n-1)
         =1+sum{(n/(n-1))^t:1<=t<=n-1}/(n-1)
         =1+(n/(n-1))^n-n/(n-1)
         =(n/(n-1))^n-1/(n-1)

     lim(n->+oo) f(n)=(1+1/(n-1))^(n-1)*(1+1/(n-1))-1/(n-1)
                     =e*1-0
                     =e

后天就要启程去山东参加NOI了，感觉时间真的过的好快。从高一到现在，学信息学竞赛不知不觉已经两年了。从开始自以为是学C++就很了不起的我，变成知道原来算法比语言更美丽的我。对于NOI，之前根本就没有想过，我想的不过是有个NOIP一等奖就可以了。甚至连NOIP一等奖，我都感到畏惧。
高一的时候，第一次参加NOIP，抱着试一试的态度去的，不过路上我还是很自信的说我可能会拿一等奖。结果，最后失望而归。高二到了，我知道这是唯一一次机会了，我不敢松懈。NOIP前的一周，我跟LK,YWS一起向年级主任请假不上晚自习，一起到机房练题。VIJOS，那是一个有趣的题库。它让我明白，我还十分渺小。一次一次的WA，一次一次的提交。然而正因为这样，每一次的AC都让我兴奋，让我觉得满足。记得有一次，我一次提交就AC了一道动态规划的题目，当时我高兴死了，那是我第一次一次提交就AC。还有VIJOS的两场模拟赛，我记得我做得都很糟糕。说实话，我很担心NOIP会不会也那样挂掉。
2009年11月21日，我和同学们乘坐校车向重庆市巴蜀中学鲁能分校区进发。第二次进入那个考场，我只能拼了。最后220分。我是全市并列第五，我马上给我妈妈打电话，告诉她我一等奖拿定了。我高兴了整整一天！
之后，获奖名单出来了，我们学校高二这一届信息学竞赛的4名主力队员中3人获得一等奖。在这之后YWS和LK退出了，他们回到了正常的学习当中，剩下的就我跟WSC。WSC说，我可以冲一下省队，叫我做USACO Training。然后接下来的两个月，我疯狂的刷题。用两个月的时间做完USACO Training的97道题目。在这期间，WSC给了我很多帮助。说实话，要不是WSC，我可能就止步于NOIP。做完USACO Training后，我们一起做了几场USACO的月赛题目，那时都没资格做金组题目，不过正是由于不是金组吧，水题增强了我的自信。然后是一起去山东的NOI冬令营。听国家集训队的大牛们讲题，我感到自己学的真的还是太少了。
不管怎样，漫长而又短暂的时间很快过去。我和WSC就做了几套其它省的省选题和往届重庆的省选题，就去参加重庆市的代表队选拔赛了。这次，我考了全市第一。我知道这意味这什么，我可以去NOI了！WSC和RJ并列第七，最后WSC因为在APIO中发挥失误，只能进夏令营（正式选手名额只有7个，所以WSC和RJ凭APIO的分数来决定谁成为正式队员）。
然后是前不久的APIO，120分，国内银牌。有点失望，因为之前做了一场USACO金组的月赛（这是我做的唯一一场USACO金组月赛），而这次APIO的题目和那次月赛惊人的相似。
最近一两个月，重庆代表队的成员们常常聚到一起练题。我们一起做有道难题，一起做NOI往届的题目，一起交流各自的想法。我们的目标只有一个，在NOI上留下自己的印记！
NOI了，此刻依旧是我独自一人坐在空荡荡的机房，但我知道我不是一个人在战斗！

数据结构类题目，赤裸裸的平衡树。

然后我自己写了一个随机函数，经过我自己的测试，用这个函数连续输出10^6个数，其中只有10^3多一点点的数重复次数超过1，有0个数重复次数超过2。所以这是一个不错的随机函数。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-7-27

DESCRIPTION:

山东2008年省选 郁闷的小J

*/

#include <stdio.h>

 

struct Treap

{

       static const int MAXNODE=1000000;

       struct struct_node{struct_node* c[1<<1];int p,s,k;};

       typedef struct_node* node;

       static struct_node pool[MAXNODE];

       static node top;

       node root,null;

       Treap()

       {

              null=top++;

              null->c[0]=null->c[1]=null;

              null->p=(~0u)>>1;

              null->s=0;

              null->k=0;

              root=null;

       }

       int rand()

       {

           const int a=0x19930309,b=19930309;

           static int c,d;

           c^=d;

           return d=(b*d)+(a^c);

       }

       void resize(node x)

       {

            if (x!=null) x->s=x->c[0]->s+x->c[1]->s+1;

       }

       void rotate(node& x,bool d)

       {

            node y=x->c[!d];

            x->c[!d]=y->c[d];

            y->c[d]=x;

            resize(x),resize(y);

            x=y;

       }

       void insert(node& x,int k)

       {

            if (x==null)

            {

               x=top++;

               x->c[0]=x->c[1]=null;

               x->p=rand();

               x->k=k;

               resize(x);

            }

            else

            {

                if (x->k==k) return;

                bool d=x->k<k;

                insert(x->c[d],k);

                if (x->c[d]->p<x->p) rotate(x,!d);

                else resize(x);

            }

       }

       void remove(node& x,int k)

       {

            if (x!=null)

            {

               if (x->k==k)

               {

                  if (x->c[0]==null&&x->c[1]==null) x=null;

                  else if (x->c[0]==null) x=x->c[1];

                  else if (x->c[1]==null) x=x->c[0];

                  else

                  {

                      bool d=x->c[0]->p<x->c[1]->p;

                      rotate(x,d);

                      remove(x->c[d],k);

                  }

               }

               else remove(x->c[x->k<k],k);

               resize(x);

            }

       }

       node search(node x,int k)

       {

            if (x==null) return null;

            if (x->k==k) return x;

            else return search(x->c[x->k<k],k);

       }

       node select(node x,int k)

       {

            if (x==null) return x;

            if (x->c[0]->s>=k) return select(x->c[0],k);

            k-=x->c[0]->s;

            if (k==1) return x;

            k-=1;

            return select(x->c[1],k);

       }

       int rank(node x,int k)

       {

           if (x==null) return 0;

           if (k<x->k) return rank(x->c[0],k);

           else if (k==x->k) return x->c[0]->s+1;

           else return x->c[0]->s+1+rank(x->c[1],k);

       }

       void for_each(node x,void (*function)(node))

       {

            if (x==null) return;

            for_each(x->c[0],function);

            function(x);

            for_each(x->c[1],function);

       }

       void insert(int k)

       {

            insert(root,k);

       }

       void remove(int k)

       {

            remove(root,k);

       }

       node search(int k)

       {

            return search(root,k);

       }

       node select(int k)

       {

            return select(root,k);

       }

       int rank(int k)

       {

           return rank(root,k);

       }

       void for_each(void (*function)(node))

       {

            for_each(root,function);

       }

};

Treap::struct_node Treap::pool[Treap::MAXNODE];

Treap::node Treap::top=Treap::pool;

 

const int MAXN=100000+2;

const int MAXM=100000;

typedef Treap::node node;

int N,M;

int a[MAXN];

char order[MAXM];

int A[MAXM],B[MAXM],K[MAXM],P[MAXM];

Treap book;

Treap position[MAXN+MAXM];

void get_id(node x)

{

     static int id;

     x->s=id++;

}

int main()

{

    scanf(“%d%d”,&N,&M);

    for (int i=1;i<=N;i++)

        scanf(“%d”,a+i);

    for (int i=0;i<M;i++)

    {

        scanf(“\n%c”,&order[i]);

        if (order[i]==’C’) scanf(“%d%d”,A+i,P+i);

        else scanf(“%d%d%d”,A+i,B+i,K+i);

    }

    for (int i=1;i<=N;i++)

        book.insert(a[i]);

    for (int i=0;i<M;i++)

        if (order[i]==’C’) book.insert(P[i]);

        else book.insert(K[i]);

    book.for_each(get_id);

    for (int i=1;i<=N;i++)

    {

        node x=book.search(a[i]);

        position[x->s].insert(i);

    }

    for (int i=0;i<M;i++)

    {

        if (order[i]==’C’)

        {

           node x=book.search(a[A[i]]);

           position[x->s].remove(A[i]);

           node y=book.search(P[i]);

           position[y->s].insert(A[i]);

           a[A[i]]=P[i];

        }

        else

        {

            node x=book.search(K[i]);

            printf(“%d\n”,position[x->s].rank(B[i])-position[x->s].rank(A[i]-1));

        }

    }

}

 

赤裸裸的后缀数组。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-7-27

DESCRIPTION:

山东2008年省选 Sandy的卡片

*/

#include <stdio.h>

 

#define max(a,b) ((a)>(b)?(a):(b))

const int MAXALPHABET=1000000;

const int MAXLENGTH=1000000;

typedef int string[MAXLENGTH];

typedef int* int_pointer;

int sort[max(MAXALPHABET,MAXLENGTH)];

int _SA[MAXLENGTH],_rank[MAXLENGTH],_TSA[MAXLENGTH],_Trank[MAXLENGTH];

int_pointer SA=_SA,rank=_rank,TSA=_TSA,Trank=_Trank;

void get_SA(string s,int length)

{

     for (int i=0;i<MAXALPHABET;i++) sort[i]=0;

     for (int i=1;i<=length;i++) sort[s[i]]++;

     for (int i=1;i<MAXALPHABET;i++) sort[i]+=sort[i-1];

     for (int i=1;i<=length;i++) SA[sort[s[i]]–]=i;

     rank[SA[1]]=1;

     for (int i=2;i<=length;i++)

         if (s[SA[i]]==s[SA[i-1]]) rank[SA[i]]=rank[SA[i-1]];

         else rank[SA[i]]=rank[SA[i-1]]+1;

     for (int block=1;block<length;block<<=1)

     {

         for (int i=1;i<=length;i++) sort[rank[SA[i]]]=i;

         for (int i=length;i>=1;i–)

             if (SA[i]-block>=1)

                TSA[sort[rank[SA[i]-block]]–]=SA[i]-block;

         for (int i=length-block+1;i<=length;i++)

             TSA[sort[rank[i]]–]=i;

         int_pointer swap;

         swap=SA,SA=TSA,TSA=swap;

         swap=rank,rank=Trank,Trank=swap;

         rank[SA[1]]=1;

         for (int i=2;i<=length;i++)

             if (Trank[SA[i]]==Trank[SA[i-1]]

                 &&Trank[SA[i]+block]==Trank[SA[i-1]+block])

                rank[SA[i]]=rank[SA[i-1]];

             else rank[SA[i]]=rank[SA[i-1]]+1;

     }

}

int height[MAXLENGTH];

void get_height(string s,int length)

{

     for (int i=1,h=0;i<=length;i++)

     {

         if (h) h–;

         if (rank[i]!=1)

         {

            int j=SA[rank[i]-1];

            while (s[i+h]==s[j+h]) h++;

         }

         height[rank[i]]=h;

     }

}

 

int N;

string s;

int length;

int id[MAXLENGTH];

int found_time;

int found[MAXLENGTH];

bool check(int value)

{

     int i=1;

     while (i<=length)

     {

           while (i<=length&&height[i]<value) i++;

           int found_counter=1;

           found[id[SA[i-1]]]=++found_time;

           while (i<=length&&height[i]>=value)

           {

                 if (found[id[SA[i]]]!=found_time)

                 {

                    found[id[SA[i]]]=found_time;

                    found_counter++;

                 }

                 i++;

           }

           if (found_counter==N) return true;

     }

     return false;

}

int main()

{

    scanf(“%d”,&N);

    for (int i=1;i<=N;i++)

    {

        int M,a,b;

        scanf(“%d%d”,&M,&b);

        for (int j=1;j<M;j++)

        {

            a=b;

            scanf(“%d”,&b);

            s[++length]=b-a+100000;

            id[length]=i;

        }

        s[++length]=i;

        id[length]=i;

    }

    get_SA(s,length);

    get_height(s,length);

    if (N==1) printf(“%d\n”,length-1);

    else

    {

        int L=0,R=length;

        while (L+1!=R)

        {

              int mid=(L+R)>>1;

              if (check(mid)) L=mid;

              else R=mid;

        }

        printf(“%d\n”,L+1);

    }

}

 

状态压缩DP。

f[i][STATE][BEFORE]表示i以前的都已经吃到饭了，然后STATE用二进制压缩表示后面8个人的吃饭情况，BEFORE表示最后一个吃饭的人是谁，可以用相对位置表示，于是-8<=BEFORE<=8。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-7-26

DESCRIPTION:

山东2009年省选 学校食堂

*/

#include <stdio.h>

#include <string.h>

 

const int oo=0x7f7f7f7f;

const int MAXN=1000+10;

const int MAXB=7+1;

const int MAXBEFORE=MAXB*2+1;

const int MAXSTATE=1<<(MAXB+1);

int C;

int N;

int t[MAXN],b[MAXN];

int f[MAXN][MAXSTATE][MAXBEFORE];

int BEFORE(int x)

{

    return x+MAXB;

}

int STATE(int x)

{

    return 1<<x;

}

int min(int a,int b)

{

    return a<b?a:b;

}

int cost(int a,int b)

{

    return a^b;

}

int get(int i,int before,int state,int ii,int bbefore,int sstate)

{

    int& A=f[i][state][BEFORE(before)];

    int B=f[ii][sstate][BEFORE(bbefore)];

    A=min(A,B+cost(t[ii+bbefore],t[i+before]));

}

int main()

{

    scanf(“%d”,&C);

    for (int c=0;c<C;c++)

    {

        scanf(“%d”,&N);

        for (int i=1;i<=N;i++)

            scanf(“%d%d”,t+i,b+i);

        memset(f,oo,sizeof(f));

        for (int before=0;before<=MAXB;before++)

        {

            bool can_get=true;

            for (int k=0;k<MAXB;k++)

                if ((1+before)-(1+k)>b[1+k])

                {

                   can_get=false;

                   break;

                }

            if (can_get) f[1][STATE(before)][BEFORE(before)]=0;

        }

        for (int ii=1;ii<=N+1;ii++)

            for (int sstate=0;sstate<MAXSTATE;sstate++)

                for (int bbefore=-MAXB;bbefore<=MAXB;bbefore++)

                    if (f[ii][sstate][BEFORE(bbefore)]!=oo)

                       for (int todo=0;todo<=b[ii];todo++)

                       {

                           int i=ii,before=todo,state=sstate|STATE(todo);

                           bool can_get=true;

                           for (int k=0;k<MAXB;k++)

                               if (!(state&STATE(k))&&((i+todo)-(i+k))>b[i+k])

                               {

                                  can_get=false;

                                  break;

                               }

                           if (can_get)

                           {

                              int di=0;

                              while (di<=MAXB&&(state&STATE(di))) di++;

                              i+=di,before-=di,state>>=di;

                              get(i,before,state,ii,bbefore,sstate);

                           }

                       }

        int answer=oo;

        for (int before=-MAXB;before<=0;before++)

            if (answer>f[N+1][0][BEFORE(before)])

               answer=f[N+1][0][BEFORE(before)];

        printf(“%d\n”,answer);

    }

}

 

树状数组。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-7-26

DESCRIPTION:

山东2009年省选 HH的项链

*/

#include <stdio.h>

#include <string.h>

 

const int MAXN=50000+2;

const int MAXM=200000+2;

const int MAXKIND=1000000+2;

typedef struct struct_query* query;

struct struct_query{int R,i;query n;};

typedef struct struct_kind* kind;

struct struct_kind{int p;kind n;};

struct_query pool[MAXM];

query top=pool;

struct_kind kind_pool[MAXKIND];

kind kind_top=kind_pool;

int N,M,L,R;

int necklace[MAXN];

query Q[MAXN];

kind k[MAXKIND];

int st[MAXN];

int answer[MAXM];

void add_query(int L,int R,int i)

{

     top->R=R,top->i=i,top->n=Q[L],Q[L]=top++;

}

void add_kind(int x,int p)

{

     kind_top->p=p,kind_top->n=k[x],k[x]=kind_top++;

}

void inc(int x,int value)

{

     for (;x<=N;x+=(x)&(-x)) st[x]+=value;

}

void sum(int x,int& value)

{

     for (;x;x-=(x)&(-x)) value+=st[x];

}

int main()

{

    scanf(“%d”,&N);

    for (int i=1;i<=N;i++) scanf(“%d”,necklace+i);

    scanf(“%d”,&M);

    for (int i=0;i<M;i++)

        scanf(“%d%d”,&L,&R),add_query(L,R,i);

    for (int i=N;i>=1;i–)

        add_kind(necklace[i],i);

    for (int i=0;i<MAXKIND;i++)

        if (k[i]) inc(k[i]->p,1);

    for (int L=1;L<=N;L++)

    {

        for (query q=Q[L];q;q=q->n)

            sum(q->R,answer[q->i]);

        inc(k[necklace[L]]->p,-1);

        if (k[necklace[L]]=k[necklace[L]]->n) inc(k[necklace[L]]->p,1);

    }

    for (int i=0;i<M;i++) printf(“%d\n”,answer[i]);

}