Boleyn Su's Blog

思考时间，答案在下面（字体是白色的）。
设一根棍与平行线成角(逆时针旋转角)，那么它与平行线相交的概率为 ，然后答案就是

这是2009年清华大学自主招生数学试题（理综）。

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

这道题其实考的是归并排序。

首先将马分为8组，每组排一下序，就比了8场。

然后再将这8组合并为4组，两两合并。

比如A和B组合并：

选A组的前4名和4个B组的前4名，比一场，如果从A中的选出的第4名比B中选出的第4名排名高，那么在A中的选出的第4名前和他自己一定是这些马中靠前的，于是把他们排到新的队中，其余马回到原来的位置；否则，同理分析。所以这样比一场可以确定至少4匹马在新的小组中的的位置。

接下来在剩下的马中继续这样做，直到所有马在新的小组中的位置都确定了。

由于每次都可以至少确定4匹马的位置，而且最后还剩8匹马时只需要比一次就可以确定8匹马的位置，所以两个8匹马的有序的小组合并为一个16匹马的有序小组只需要(16-8)/4+1=3次比赛。

所以8个8匹马的有序的小组合并为4个16匹马的有序小组需要4*3=12次比赛。

所以4个16匹马的有序的小组合并为2个32匹马的有序小组需要2*7=14次比赛。

所以2个32匹马的有序的小组合并为1个64匹马的有序小组需要1*15=15次比赛。

所以一共只需比49场就可以了。

这是2009年清华大学自主招生数学试题（理科）。

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

答案是3 11 19。

首先它是一个解，下面我们证明没有其它解。

设最小的一个数为X，那么数列为X,X+8,X+16。

然后

X mod 3 = X mod 3

X + 8 mod 3 = X+ 2 mod 3

X + 16 mod 3 =X + 1 mod 3

所以无论X为何值，这个数列中都有一个数是3的倍数，又它们都是质数，所以只可能是有一个数是3，那么显然这个问题解决了。

NOIP2010即将到来，这道题用来练练手感。

这道题的思路就是分解质因数。

首先，不难得到gcd(x/a1,a0/a1)=1以及gcd(b1/x,b1/b0)=1。

假设对于一个质因数y，a0含有a0c个y，a1含有a1c个y，b0含有b0c个y，b1含有b1c个y。

那么不难得到，如果a0c<a1c，那么就无解；如果a0c=a1c，那么x至少含有a1c个y；如果a0c>a1c，那么x只可能含有a1c个y。

同理，如果b1c<b0c，那么就无解；如果b1c=b0c，那么x至多含有b1c个y；如果b1c>b0c，那么x只可能含有b1c个y。

由此，可以求出对于每一个质数，x可能含有几个它，并求出一共有多少种选择方式。然后根据乘法原理，将每一个质数的选择方案数乘起来，就得到了答案。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-10-14

DESCRIPTION:

$DESCRIPTION

*/

#include <stdio.h>

 

const int MAXSIZE=5000;

int prime_table[MAXSIZE];

int prime_table_size;

void initialize_prime_table()

{

    prime_table_size=0;

    prime_table[prime_table_size++]=2;

    for (int i=3;prime_table_size<MAXSIZE;i++)

    {

        bool is_prime=true;

        for (int j=0;j<prime_table_size;j++)

            if (i%prime_table[j]==0)

            {

               is_prime=false;

               break;

            }

        if (is_prime) prime_table[prime_table_size++]=i;

    }

}

void calculate_one_step(int& a0,int& a1,int& b0,int& b1,int& result,int p)

{

     int a0c=0,a1c=0,b0c=0,b1c=0;

     while (a0%p==0) a0/=p,a0c++;

     while (a1%p==0) a1/=p,a1c++;

     while (b0%p==0) b0/=p,b0c++;

     while (b1%p==0) b1/=p,b1c++;

     if (a0c<a1c||b0c>b1c) result*=0;

     else if (a0c==a1c&&b0c==b1c)

     {

          if (a1c<=b1c) result*=b1c-a1c+1;

          else result*=0;

     }

     else if (a0c==a1c&&b0c<b1c)

     {

          if (a1c<=b1c) result*=1;

          else result*=0;

     }

     else if (a0c>a1c&&b0c==b1c)

     {

          if (a1c<=b1c) result*=1;

          else result*=0;

     }

     else //if (a0c>a1c&&b0c<b1c)

     {

          if (a1c==b1c) result*=1;

          else result*=0;

     }

}

int calculate(int a0,int a1,int b0,int b1)

{

    //gcd(x/a1,a0/a1)=1

    //gcd(b1/x,b1/b0)=1   

    if (a0%a1!=0||b1%b0!=0) return 0;

    int result=1;

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

        calculate_one_step(a0,a1,b0,b1,result,prime_table[i]);

    if (a0!=1) calculate_one_step(a0,a1,b0,b1,result,a0);

    else if (b1!=1&&b1!=a0) calculate_one_step(a0,a1,b0,b1,result,b1);

    return result;

}

 

int main()

{

    freopen(“son.in”,“r”,stdin);

    freopen(“son.out”,“w”,stdout);

    int n,a0,a1,b0,b1;

    initialize_prime_table();

    scanf(“%d”,&n);

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

    {

        scanf(“%d%d%d%d”,&a0,&a1,&b0,&b1);

        printf(“%d\n”,calculate(a0,a1,b0,b1));

    }

    return 0;

}

 

先离线处理出在[0,10^9)内中所有平方末尾数为987654321的数，然后显然应该写成下面那样。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-9-11

DESCRIPTION:

$DESCRIPTION

*/

#include <stdio.h>

 

int main()

{

    /*

    for (long long int i=0;i<1000000000;i++)

        if (i*i%1000000000==987654321) printf(“%d\n”,int(i));

    output:

    111111111

    119357639

    380642361

    388888889

    611111111

    619357639

    880642361

    888888889

    */

    int n;

    scanf(“%d”,&n);

    if (n<=8) printf(“%d\n”,0);

    else if (n==9) printf(“%d\n”,8);

    else

    {

        printf(“%d”,72);

        for (int i=10;i<n;i++) printf(“%d”,0);

        printf(“\n”);

    }

}

 

数学题。扩展欧几里得解模同余方程。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-8-26

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

#include <math.h>

using namespace std;

 

#define lli long long int

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

#define min(a,b) ((a)<(b)?(a):(b))

#define ceil_div(a,b) ceil(double(a)/double(b))

#define floor_div(a,b) floor(double(a)/double(b))

 

lli gcd(lli a,lli b,lli& x,lli& y)

{

    //ax+by=gcd(a,b)

    if (b==0)

    {

       x=1,y=0;

       return a;

    }

    else

    {

        lli g=gcd(b,a%b,y,x);

        //b*y+a%b*x=gcd(b,a%b)=gcd(a,b)

        // b*y+a%b*x

        //=b*y+(a-a/b*b)*x

        //=b*y-a/b*b*x+a*x

        //=a*x+b*(y-a/b*x)

        y-=a/b*x;

        return g;

    }

}

lli get_answer(lli a,lli b,lli c,lli x1,lli x2,lli y1,lli y2)

{

    //ax+by+c=0

    if (!(x1<=x2&&y1<=y2)) return 0;

    else if (a==0&&b==0)

         return (c==0)*(x2-x1+1)*(y2-y1+1);

    else if (a==0)

    {

         lli y=-c/b;

         return ((b*y+c==0)&&(y1<=y&&y<=y2))*(x2-x1+1);

    }

    else if (b==0)

    {

         lli x=-c/a;

         return ((a*x+c==0)&&(x1<=x&&x<=x2))*(y2-y1+1);

    }

    else

    {

        //a*x = c (mod b)

        lli x,y,g;

        g=gcd(a,b,x,y);//ax+by=g

        if (c%g==0)

        {

           a/=g,b/=g,c/=g;//ax+by=1

           x*=-c,y*=-c;//ax*(-c)+by*(-c)=-c          

           //set of root = {(x+b*k,y-a*k)}          

           lli rxa,rxb;

           if (b>0) rxa=ceil_div(x1-x,b),rxb=floor_div(x2-x,b);

           else rxa=ceil_div(x2-x,b),rxb=floor_div(x1-x,b);

           lli rya,ryb;

           if (a<0) rya=ceil_div(y-y1,a),ryb=floor_div(y-y2,a);

           else rya=ceil_div(y-y2,a),ryb=floor_div(y-y1,a);

           lli ra,rb;

           ra=max(rxa,rya);

           rb=min(rxb,ryb);

           if (ra<=rb) return (rb-ra+1);

           else return 0;

        }

        else return 0;

    }

}

 

int main()

{

    lli a,b,c,x1,x2,y1,y2;

    cin>>a>>b>>c>>x1>>x2>>y1>>y2;

    cout<<get_answer(a,b,c,x1,x2,y1,y2)<<endl;

}

 

数学题。一个数能被3整除，当且仅当它的各位数的和能被3整除。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-8-26

DESCRIPTION:

$DESCRIPTION

*/

#include <stdio.h>

int main()

{

    int N;

    scanf(“%d”,&N);

    printf(“%d\n”,N/3*2+(N%3==2));

}

 

动态规划经典题目，据说是IOI上出现的首个动态规划题目。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-8-24

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using namespace std;

 

const int MAXF=100+2,MAXV=100+2;

const int oo=19930309;

int F,V;

int A[MAXF][MAXV];

int f[MAXF][MAXV];

 

void print(int v,int i)

{

     if (i)

     {

        int j;

        for (j=1;j<=V;j++)

            if (f[i][j]==v)

               break;

        print(v-A[i][j],i-1);

        cout<<j<<char(i==F?’\n’:’ ‘);

     }

}

 

int main()

{

    cin>>F>>V;

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

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

            cin>>A[i][j];

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

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

        for (int j=0;j<=V;j++)

        {

            f[i][j]=-oo;

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

                f[i][j]=max(f[i][j],f[i-1][k]+A[i][j]);

        }

    int answer=-oo;

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

        answer=max(answer,f[F][i]);

    cout<<answer<<endl;

    print(answer,F);

}

 

最短路。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-8-24

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using namespace std;

 

const int MAXE=14000*2;

const int MAXV=300+2;

typedef struct struct_edge* edge;

struct struct_edge{int v,d;edge n;};

struct node

{

       int c,r,t[2];

       int color(int timeline)

       {

           int alpha=timeline%(t[0]+t[1]);

           if (r<=alpha&&alpha<r+t[!c]) return !c;

           else return c;

       }

       int remain(int timeline)

       {

           int alpha=timeline%(t[0]+t[1]);

           if (alpha<r)

              return r-alpha;

           else if (alpha<r+t[!c])

                return r+t[!c]-alpha;

           else return t[0]+t[1]-alpha;

       }

};

struct_edge pool[MAXE];

edge top=pool;

int S,T;

int V,E;

node vertex[MAXV];

edge adj[MAXV];

const int oo=19930309;

int d[MAXV];

int visited[MAXV];

int pre[MAXV];

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

{

     top->v=v,top->d=d,top->n=adj[u],adj[u]=top++;

     top->v=u,top->d=d,top->n=adj[v],adj[v]=top++;

}

int min(int a,int b)

{

    return a<b?a:b;

}

int wait(int u,int v,int now=0,int change_times=0)

{

    if (change_times>3) return oo;

    if (vertex[u].color(now)==vertex[v].color(now)) return now;

    else

    {

        int wt=wait(u,v,now+min(vertex[u].remain(now),vertex[v].remain(now)),change_times+1);

        if (wt==oo) return oo;

        else return wt;

    }

}

void dijkstra()

{

     for (int u=1;u<=V;u++)

         d[u]=oo;

     d[S]=0;

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

     {

         int u,du=oo;

         for (int tu=1;tu<=V;tu++)

             if (!visited[tu]&&d[tu]<du)

                du=d[u=tu];

         visited[u]=true;

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

             if (!visited[i->v])

             {

                int tdv=wait(u,i->v,d[u])+i->d;

                if (d[i->v]>tdv)

                   d[i->v]=tdv,

                   pre[i->v]=u;

             }

     }

}

void print(int u)

{

     if (u!=S) print(pre[u]);

     cout<<u<<char(u==T?’\n’:’ ‘);

}

 

int main()

{

    ios::sync_with_stdio(false);

    cin>>S>>T;

    cin>>V>>E;

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

    {

        char color;

        cin>>color>>vertex[i].r>>vertex[i].t[0]>>vertex[i].t[1];

        vertex[i].c=(color==’P’);

    }

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

    {

        int a,b,d;

        cin>>a>>b>>d;

        add_edge(a,b,d);

    }

    dijkstra();

    if (d[T]==oo) cout<<0<<endl;

    else

    {

        cout<<d[T]<<endl;

        print(T);

    }

}

 

求最大公约数。

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;

}