高精度问题

Time Limit:1000MS  Memory Limit:65536K
Total Submit:381 Accepted:107

Description

相信经过暑假一个月的培训，大家应该已经掌握了高精度的算法了。但是往往比赛中涉及到高精度的问题并不多。而有些题目可能看起来需要高精度，而实际上并不需要。一个很好的例子就是3^p mod x, 初学者如果不知道同余的概念的话，可能会求出3^p先，然后再对x取余，然而这对p很大的时候是行不通的。。于是我们想到了边乘边取余，其基本的思想就是先把x的整数倍拿掉，因为他对最后的计算结果没有影响，但是这种算法对于p超过1000000的时候就会显得很慢了，你有没有想到更好的办法。
本题的任务就是给你一个p和x输出3^p mod x

Input

每行一个数据 p和x，2 < p, x ≤ 1000000000, 输入最后以0 0结束

Output

输出3^p mod x

Sample Input

10 7
0 0

Sample Output

4

         这个题目老师教了我好几遍我也没懂。。。悲剧！！！

代码如下：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
int modExp(int a, int b, int n)
{  
    __int64 t, y;
    t=1;y=a;
    while(b!=0)
    {
          if(b%2==1)
          {
              t=t*y%n;
          }
          y=y*y%n;
          b=b/2;
    }
      return t;
}


int main()
{
    int b,n;
    while(scanf("%d %d",&b,&n)!=EOF&&(b!=0&&n!=0))
    {
        printf("%d\n",modExp(3,b,n));
    }
    return 0;
}

Ignatius and the Princess III

Time Limit:1000MS  Memory Limit:65536K
Total Submit:86 Accepted:66

Description

"Well, it seems the first problem is too easy. I will let you know how foolish you are later." feng5166 says.

"The second problem is, given an positive integer N, we define an equation like this:
N=a[1]+a[2]+a[3]+...+a[m];
a[i]>0,1<=m<=N;
My question is how many different equations you can find for a given N.
For example, assume N is 4, we can find:
4 = 4;
4 = 3 + 1;
4 = 2 + 2;
4 = 2 + 1 + 1;
4 = 1 + 1 + 1 + 1;
so the result is 5 when N is 4. Note that "4 = 3 + 1" and "4 = 1 + 3" is the same in this problem. Now, you do it!"

Input

The input contains several test cases. Each test case contains a positive integer N(1<=N<=120) which is mentioned above. The input is terminated by the end of file.

Output

For each test case, you have to output a line contains an integer P which indicate the different equations you have found.

Sample Input

4
10
20

Sample Output

5
42
627
      就是这个题目上次我写整数划分的时候半天也没找到。。。直接用递归会超时！！
代买如下：
#include<cstdio>
int main()
{
    int i,j,n,c[121][121];
    for(i=1;i<121;i++)
        for(j=1;j<121;j++)
        {
            if(i==1||j==1)
                c[i][j]=1;
            else if(i<j)
                c[i][j]=c[i][i];
            else if(i==j)
                c[i][j]=c[i][j-1]+1;
            else
                c[i][j]=c[i][j-1]+c[i-j][j];
        }
    while(scanf("%d",&n)!=EOF)
    {
        printf("%d\n",c[n][n]);
    }
    return 0;
}

#include<stdio.h>
#include<string.h>
int m[10][10];//m[i][j]代表i个元素分成j个集合分法
int main()
{
    int i,j;
    memset(m,0,sizeof(m));
    for(i=1;i<10;i++)//初始化
    {
        m[i][1]=1;
        m[i][i]=1;
    }

    for(i=2;i<10;i++)//构造m解
    {
        for(j=2;j<i;j++)
        {
            m[i][j]=m[i-1][j]*j+m[i-1][j-1];
        }
    }

    for(i=1;i<10;i++)//输出结果
    {
        for(j=1;j<=i;j++)
            printf("%d ",m[i][j]);
        printf("\n");
    }
    return 0;
}

骑士问题

Time Limit:1000MS  Memory Limit:65536K
Total Submit:160 Accepted:71

Description

在一个标准8*8的国际象棋棋盘上，棋盘中有些格子可能是有障碍物的。已知骑士的初始位置和目标位置，你的任务是计算出骑士最少需要多少步可以从初始位置到达目标位置。
有障碍物的格子当然不可以到达。
标准的8*8的国际象棋棋盘中每个格子可以用唯一的编号确定。行用1~8这8个数字一次表示，列用a~h这8个字母依次表示如a4,b5等。骑士走日字型。

Input

多组测试数据。
每个测试数据的第一行是一个整数b( -1 <= b <= 62)表示棋盘中有障碍物的格子的数目，当b=-1时表示输入结束。
第二行含b个不同的有障碍物的格子编号，用空格隔开，当b=0时，此行为空行。
第三行是骑士的初始格子和目标格子的编号，也用空格隔开。

Output

每组输出一行格式：
Board n: m moves
其中n表示数据的序号，m表示最少步数
如果骑士无法到达，则输出
Board n: not reachable

Sample Input

10
c1 d1 d5 c2 c3 c4 d2 d3 d4 c5
a1 f1
0
c1 b3
2
b3 c2
a1 b2
-1

Sample Output

Board 1: 7 moves
Board 2: 1 moves
Board 3: not reachable

      广度搜索！

代码如下：

#include<stdio.h>
#include<string.h>
int a[8]={-2,-2,-1,-1,1,1,2,2};
int b[8]={1,-1,2,-2,2,-2,1,-1};
int p[2][1000];
int s[9][9];
int head;
int tail;
int count;
int x3,y3;
int temp;
#define cr(x) memset(x,0,sizeof(x));
int fun(int x,int y)
{
    int x1,y1;
    int i;
    int x2,y2;
    while(head<tail)
    {
        x1=p[0][head];
        y1=p[1][head];
        for(i=0;i<8;i++)
        {
            x2=x1+a[i];
            y2=y1+b[i];
            if(x2==x3&&y2==y3)
            {
                return 1;
            }
            else    if(s[x2][y2]==0&&x2>0&&y2>0&&x2<9&&y2<9)
            {
                p[0][tail]=x2;
                p[1][tail]=y2;
                tail++;
                s[x2][y2]=1;
            }

        }

        if(head==temp)//统计步数
        {
            temp=tail-1;
            count++;
        }
        head++;    
    }
    return 0;
}
int main()
{
    int x,y;
    int i,j;
    int d;
    char c[2];
    int x1,y1;
    int z=0;
while(scanf("%d",&d)!=EOF&&d!=-1)
    {
        z++;
        for(i=1;i<9;i++)
            for(j=1;j<9;j++)
            {
                s[i][j]=0;
            }
        for(i=0;i<d;i++)
        {
            scanf("%s",c);
            x=c[1]-48;
            y=c[0]-96;
            s[x][y]=1;
        }
        scanf("%s",c);
        x1=c[1]-48;
        y1=c[0]-96;
        scanf("%s",c);
        x3=c[1]-48;
        y3=c[0]-96;
        p[0][0]=x1;
        p[1][0]=y1;
        s[x1][y1]=1;
        count=0;
        head=0;
        tail=1;
        temp=0;
        if(fun(x1,y1)==1)
        {
            printf("Board %d: %d moves\n",z,count+1);
        }
        else
        {
            printf("Board %d: not reachable\n",z);
        }
    }

    return 0;
}

马的走法

Time Limit:1000MS  Memory Limit:65536K
Total Submit:127 Accepted:80

Description

在一个4*5的棋盘上，输入马的起始位置坐标（纵、横），求马能返回初始位置的所有不同走法的总数（马走过的位置不能重复,马走“日”字）。

Input

多个测试数据。
每组2个数字

Output

输出不同走法的总数。

Sample Input

2 2

Sample Output

4596

               穷举法！也可以看做深搜！角度不同。。这与前面一题过河卒不同，在过河卒中如果用深搜的话会超时，我试过了。。。
代码如下：

#include<stdio.h>
#include<string.h>
int count;
int s[4][5];
int a[8]={-2,-2,-1,-1,1,1,2,2};
int b[8]={1,-1,2,-2,2,-2,1,-1};
int x1,y1;
void fun(int x,int y)
{
    int i;
    int x2,y2;
    for(i=0;i<8;i++)
    {
        x2=x+a[i];
        y2=y+b[i];
        if((x2>=0)&&(y2>=0)&&(y2<=4)&&(x2<=3)&&(s[x2][y2]==0))
        {
            s[x2][y2]=1;
            fun(x2,y2);
            s[x2][y2]=0;
        }
        else if((x2==x1)&&(y2==y1))
            count++;
    }
}
int main()
{

    while((scanf("%d %d",&x1,&y1)!=EOF))
    {
        count=0;
        if((x1<=4)&&(y1<=5)&&(y1>0)&&(x1>0))
        {
            x1=x1-1;
            y1=y1-1;
            memset(s,0,sizeof(s));
            s[x1][y1]=1;
            fun(x1,y1);
            printf("%d\n",count);
        }
        else
        {
            printf("%d\n",count);
        }
    }
    return 0;
}

过河卒

Time Limit:1000MS  Memory Limit:65536K
Total Submit:691 Accepted:155

Description

棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点，如图中的C点和P1，……，P8，卒不能通过对方马的控制点。棋盘用坐标表示，A点(0,0)、B点(n, m) (n,m为不超过20的整数),同样马的位置坐标是需要给出的，C≠A且C≠B。现在要求你计算出卒从A点能够到达B点的路径的条数。

           1   2   3   4   5   6   7    8

     A +---+---+---o---+---o---+---+----+--------->Y

       |   |   |   |   |   |   |   |    |

     1 +---+---o---+---+---+---o---+----+

       |   |   |   |   |   |   |   |    |

     2 +---+---+---+---C---+---+---+----+

       |   |   |   |   |   |   |   |    |

     3 +---+---o---+---+---+---o---+----+

       |   |   |   |   |   |   |   |    |

     4 +---+---+---o---+---o---+---+----+ B(4,8)

       |

       |

       V



       X

Input

多个测试案例，每个案例一行，处理到文件末尾
B点坐标（n,m）以及对马的坐标（X,Y）{不用判错}

Output

一个整数(路径的条数)

Sample Input

6 6 3 2 

Sample Output

17

         这个题目还是不错的。。。

代码如下：

#include<stdio.h>


int s[21][21];
__int64 c[21][21];


int a0[8]={-2,-2,-1,-1,1,1,2,2};
int b0[8]={1,-1,2,-2,2,-2,1,-1};

int x1,y1;
int x3,y3;

int main()
{
    int x2,y2;
    int i,j;
    int test;
    while((scanf("%d %d %d %d",&x1,&y1,&x3,&y3)!=EOF))
    {

        for(i=0;i<21;i++)
            for(j=0;j<21;j++)
            {
                s[i][j]=1;
                c[i][j]=0;
            }
        s[x3][y3]=0;
        for(i=0;i<8;i++)//计算受马控制的点
        {
            x2=x3+a0[i];
            y2=y3+b0[i];
            if((x2>=0)&&(y2>=0)&&(y2<=20)&&(x2<=20))
            {
                s[x2][y2]=0;
            }
        }


        test=1;
        for(j=0;j<21;j++)//初始化边上的走法
        {
            if(test)
            {
                if(s[0][j]==0)
                {
                    test=0;
                }
                else
                {
                    c[0][j]=1;
                }
            }

        }
        test=1;
        for(j=0;j<21;j++)
        {
            if(test)
            {
                if(s[j][0]==0)
                {
                    test=0;
                }
                else
                {
                    c[j][0]=1;
                }
            }
        }


        for(i=1;i<21;i++)//计算一个点上的走法，上方点的走法数+左方点的走法数
            for(j=1;j<21;j++)
            {
                if(s[i][j])
                {
                    
                    c[i][j]=c[i-1][j]*s[i-1][j]+c[i][j-1]*s[i][j-1];
                }
            }
        

            printf("%I64d\n",c[x1][y1]); 
    }
    return 0;
}

最少硬币问题

设有n 种不同面值的硬币，各硬币的面值存于数组T［1:n］中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins［1:n］中。
对任意钱数0≤m≤20001，设计一个用最少硬币找钱m的方法。

编程任务：
对于给定的1≤n≤10，硬币面值数组T和可以使用的各种面值的硬币个数数组Coins，以及钱数m，0≤m≤20001，编程计算找钱m的最少硬币数。

Input

输入包括多组测试数据，每组输入的第一行中只有1 个整数给出n的值,第2 行起每
行2 个数，分别是T[j]和Coins[j]。每组输入最后1 行是要找的钱数m。

Output

Sample Input

3
1 3
2 3
5 3
18

Sample Output

5

         动态规划题。

代码如下：

#include<cstdio>
int main()
{
    int t[11],coins[11],c[11][20002];//c[i][j]前i种硬币找j块钱最少硬币数
    int i,j,n,m,k;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=1;i<=n;i++)
        {
            scanf("%d %d",&t[i],&coins[i]);
        }
        scanf("%d",&m);
        for(i=1;i<=n;i++)        //初始化
            for(j=0;j<=m;j++)
            {
                if(j==0)
                    c[i][j]=0;
                else if(i==1)  
                    if(j%t[i]==0&&j/t[i]<=coins[i])
                        c[1][j]=j/t[i];
                    else
                        c[1][j]=1000000;
                else
                    c[i][j]=1000000;
            }

        for(i=2;i<=n;i++)        //构造c数组
            for(j=1;j<=m;j++)
                for(k=0;k<=coins[i];k++)
                {
                    if(c[i][j]>(c[i-1][j-k*t[i]]+k)&&(j-k*t[i])>=0)
                            c[i][j]=c[i-1][j-k*t[i]]+k;
                }
        if(c[n][m]!=1000000)
        {
            printf("%d\n",c[n][m]);
        }
        else
            printf("-1\n");
    }
    return 0;
}

题目地址：http://acm.nankai.edu.cn/p1132.html

	我们学校的ACM网站进不去了。。。

 	滑雪，这个题目是稍微复杂一些的动态规划题，基本思路是先求的一个点上，上下左右上的最优值，然后再做判断。。该题一定要抓住这种思想，不然会很迷惑。

在代码实现的时候，用了一个中间值temp，用来存贮最优解。。。

代码如下：

#include<stdio.h>
#include<string.h>
int s[101][101],map[101][101];
int d[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
int n,m;
int dfs(int x,int y)            //计算x,y点上的最大深度，事实上它可以计算出所有他可以到达点上的最优值
{
    int sum=0;
    int temp=0;
    int i,x0,y0;
    if(s[x][y]!=0)
        return s[x][y];
    for(i=0;i<4;i++)        //从上下左右四个最优值中选择
    {
        x0=d[i][0]+x;
        y0=d[i][1]+y;
        temp=1;                //最小深度为1。。
        if((map[x0][y0]<map[x][y])&&x0>=0&&y0>=0&&x0<n&&y0<m)//满足条件的点，重置temp
        {
            temp=dfs(x0,y0)+1;
        }
        if(temp>sum)                //更新最大深度
        {
            sum=temp;
        }
    }
    s[x][y]=sum;                //置最优值
    return sum;                    //返回最优值
}
int main()
{
    int sum,i,j;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        memset(s,0,sizeof(s));
        sum=0;
        for(i=0;i<n;i++)
            for(j=0;j<m;j++)
                scanf("%d",&map[i][j]);
        for(i=0;i<n;i++)
            for(j=0;j<m;j++)
            {
                dfs(i,j);
            }
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                if(s[i][j]>sum)
                    sum=s[i][j];
                //printf("%d ",s[i][j]);
            }
        //    printf("\n");
        }
        printf("%d\n",sum);
    }
    return 0;
}


      这段代码可能是我自己写的，我记得当时我不理解这个，网上找了很多代码来看，结果还是看不懂。。。现在我看着这段代码还是觉得虚，虽然我理解他的意思。。。总结经验我觉得以前没有好好理解这个题目，然后盲目的看代码，结果毁了这个题目！！！以后一定要抓住思路再写代码！！！其实这个题目可以看做是最长不下降子序列扩展到二维的情况！！可能这也是我解决不了这个题目的一个因素，除了思路不清晰外，在写代码的时候直接用最优数组去迭代是不能成功的！！要用到中间变量！！最后总结为：1、盲目看\写代码。。2、经验主义。。

最长不下降序列

Time Limit:1000MS  Memory Limit:65536K
Total Submit:488 Accepted:197

Description

有由n个不相同的整数组成的数列，记为a(1)、a(2)、...a(n),当i!=j时，a(i)!=a(j)。若存在i1 < i2 < i3 < ... < ie,且有a(i1) < a(i2) < ... < a(ie), 则称为长度为e的不下降序列。
如 3，18，7，14，10，12，23，41，16，24
则有3，18，23，24是一个长度为4的不下降子序列
3，7，10，12，23，24是长度为6的不下降子序列。
现要求你求最长的不下降子序列。

Input

多组测试数据
每组一行，先输入一个数列长度n （1 <= n <= 1000),然后是n个整数
处理到文件末尾

Output

输出最长不下降子序列的长度

Sample Input

10 3 18 7 14 10 12 23 41 16 24

Sample Output

6

         简单动态规划题，给予我们一种思想！！

代码如下：

#include<stdio.h>
int Longest_Increasing(int num[],int List[],int n)//List[i]为包含i项在内的最长不下降子序列
{
    int i,j;
    for(i=1;i<n;i++)
    {
        for(j=0;j<i;j++)
        {
            if(num[i]>num[j]&&List[i]<List[j]+1)
                    List[i]=List[j]+1;
        }
    }
    return 0;
}

int main()
{
    int n,i,ans;
    int num[1001],List[1001];
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;i++)
        {
            List[i]=1;
            scanf("%d",&num[i]);
        }

        Longest_Increasing(num,List,n);
        
/**//*        printf("最优解：\n");
        for(i=0;i<n;i++)
            printf("%d ",List[i]);
        printf("\n");*/

        ans=0;
        for(i=0;i<n;i++)
            if(List[i]>ans)
                ans=List[i];

        printf("%d\n",ans);
    }
    return 0;
}