CHD 2014迎新杯比赛题解

分析：高精度乘法或 JAVA大数类

很明显 10000 的阶乘已经远远超过 64 位数能表示的范围了。所以我们要用一个比较大的数组来存放这个数。那数组要开多少位合适呢？我们不妨计算一下 10000 个 10000 相乘有多少位，是一个 40000 位数。所以 40000 大小的数组肯定够了。接下来就是模拟一下乘法运算。因为数位太大不能直接相乘，所以我们就逐位相乘。相乘得到的数的个位是结果的对应位置的数字，然后除以 10 把进位保留下来，加到下一次乘法中。

在输出的时候注意忽略前导 0.

#include <cstdio>

#include <cstring>

int a[], n, t;

void solve( int n ){

    int id = , add;

    a[] = ;

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

        add = ;

        for( int j = ; j <= id; ++j ){

            a[j] = a[j] * i + add;

            add = a[j] / ;

            a[j] = a[j] % ;

        }

        while( add ){

            a[++id] = add % ;

            add /= ;

        }

    }

    for( int i = id; i >= ; --i ){

        printf( "%d",a[i] );

    }

    putchar( '\n' );

}

int main(){

    scanf( "%d", &t );

    while( t-- ){

        scanf( "%d", &n );

        solve(n);

    }

    return ;

}

import java.math.BigInteger;

import java.util.*;

import java.io.*;  

public class Main  {

    public static void main(String args[])  {

        Scanner in = new Scanner(System.in);

        int test = in.nextInt();

        while(test > 0)  {

            int n;

            n = in.nextInt();

            BigInteger ans = new BigInteger("1");

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

                ans = ans.multiply(BigInteger.valueOf(i));

            System.out.println(ans);

            test--;

        }

    }

}

JAVA代码

B.火影疾风传之旅

分析：简单模拟

题目给了游戏规则，只要你当前分数大于敌人的分数，你就可以获得他的％10 的分数(如果敌人是下忍，则直接把他干掉)。

用一个变量来记录当前分数，然后判断能否打败敌人，能的话继续打下一个，直到被打败或者打败所有敌人。

需要注意的地方是输入的是字母，需要转换成对应的分数，还有字母之间的空格间隔要忽略掉。

#include <cstdio>

int sco, n;

char ch;

int check( char ch ){

    if( ch == 'X' ) return ;

    else if( ch == 'Z' && sco >  ) return ;

    else if( ch == 'S' && sco >  ) return ;

    else if( ch == 'H' && sco >  ) return ;

    else return ;

}

int main(){

    int cas = ;

    while( ~scanf( "%d", &sco ) && sco ){

        scanf( "%d", &n );

        int flag = ;

        while( n-- ){

            getchar();

            ch = getchar();

            if( !flag ) continue;

            int add = check( ch );

            if(  add ){

                sco += add;

            }else{

                flag = ;

            }

        }

        printf( "Case #%d: %d\n", cas++, sco );

    }

    return ;

}

C.拯救拉面女神

分析：三维广搜

给出一个三维的迷宫，求从起点到终点的最短路的长度。

用一个结构体来表示点，成员变量有 x、y、z 坐标以及到起点的最短步数 step。在行进的过程中一共有上下左右前后 6 个方向，所以我们从起点开始拓展，如果没有出界或者遇到岩石，则向外走一步，同时步数加 1。把所有拓展出来的点放到一个队列里面。最开始队列里只有起点。从队首取点，如果该点就是终点，答案就是该点对应的 step，否则将所有可拓展的点入队，然后该点出队，直到到达终点或队列为空。

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cstring>

using namespace std;

#define N 52

int g[N][N][N];

int vis[N][N][N];

int dir[][]={,,,-,,,,,,,-,,,,,,,-};

int A,B,C,t;

struct node{

    int x,y,z,t;

};

int jud(int x,int y,int z){

    if(x>=&&x<A&&y>=&&y<B&&z>=&&z<C&&!g[x][y][z])return ;

    else return ;

}

int bfs(node st){

    queue<node>q;

    q.push(st);

    node u,v;

    while(!q.empty()){

        u=q.front();q.pop();

        if(u.x==A-&&u.y==B-&&u.z==C-&&u.t<=t)return u.t;

        for(int i=;i<;++i){

            v=u;

            v.x+=dir[i][];v.y+=dir[i][];v.z+=dir[i][];v.t++;

            if(jud(v.x,v.y,v.z)&&!vis[v.x][v.y][v.z]){

                q.push(v);vis[v.x][v.y][v.z]=;

            }

        }

    }

    return -;

}

int main(){

    int K,i,j,k;

    scanf("%d",&K);

    while(K--){

        memset(vis,,sizeof(vis));

        scanf("%d%d%d%d",&A,&B,&C,&t);

        for(i=;i<A;++i){

            for(j=;j<B;++j){

                for(k=;k<C;++k)

                    scanf("%d",&g[i][j][k]);

            }

        }

        node s;

        s.x=,s.y=,s.z=,s.t=;

        vis[][][]=;

        printf("%d\n",bfs(s));

    }

    return ;

}

D.神奇彩带

分析：next数组性质

给出两个字符串，求最大长度的子串，使得该串是第一个串的前缀同时也是第二串的后缀。

朴素的算法应该是会超时的。这里其实是用到了 KMP 算法中 next 数组的性质，next[i]表示从最长子串，使得该串即是 next[0]到 next[i-1]的前缀也是后缀。所以将两个串并起来中间间隔一个不会出现的字符，比如’#’。所求的 next 最后一个值就是本题的答案。

#include<cstdio>

#include<cstring>

//#include<algorithm>

using namespace std;

#define N 50005

char p[*N],s[N];

int next[*N];

int plen;

void Next(){

    next[]=;

    plen=strlen(p);

    for(int i=,k=;i<plen;++i){

        while(k>&&p[k]!=p[i]) k=next[k-];

        if(p[k]==p[i]) k++;

        next[i]=k;

    }

}

int main(){

    while(~scanf("%s%s",p,s)){

        memset(next,,sizeof(next));

        strcat(p,"*");

        strcat(p,s);

        Next();

        printf("%d\n",next[plen-]);

    }

    return ;

}

E.草滩小王子的相反数

分析：位运算

本题中所谓的“相反数”就是把这个数的二进制左右翻转一下得到的数，注意题目中的输入输出都是十进制数。

最直接的想法就是把这个数转化成二进制，然后翻转数组，最后转化成十进制输出。

然而，最快的办法就是位运算，从最低位取 n 的二进制位，“相反数”则每次左移一位加上所取数字。

#include<cstdio>

int n, sum;

int main(){

    while( ~scanf( "%d", &n ) ){

        sum = ;

        while( n ){

            sum <<= ;

            sum += n & ;

            n >>= ;

        }

        printf( "%d\n", sum );

    }

    return ;

}

F.草滩小王子的锻炼

分析：费马小定理+快速幂取模

题目中已经很明确地说了结果会很大很大，一个变量甚至连指数都存不下。高精度也许是可以的，不过这里太麻烦了。因为 49999 是质数，我们用费马小定理来用指数对(49999 - 1)取模，将指数化简为一个很小的数(不过结果依然很大！)。所以在幂运算的过程中每次都要取模。

计算2的幂逐次乘2是很慢的，所以我们每次将2平方会得到 2²ⁱ，

再将指数写成二进制，如果对应位置是 1，就将结果乘上 2²ⁱ。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int M=;

const int M2=;

char c[];

int pow(int x,int y,int M){

    int t=,b=x%M;

    while(y){

        if(y&)t=(t*b)%M;

        b=(b*b)%M;

        y>>=;

    }

    return t;

}

int main(){

    int k,i,len;

    while(scanf("%s",c)==){

        len=strlen(c);

        for(k=,i=len-;i>=;i--){

            k=(k+(c[i]-'')*pow(,len--i,M2))%M2;

        }

        printf("%d\n",pow(,k,M));

    }

}

G.拉面女神的粉丝

分析：简单数学，质因数分解

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <cstring>

#include <algorithm>

using namespace std ;

#define LL long long

const int maxn = (<<) ;

LL pr[maxn+] ;

void getprime()

{

    memset(pr,,sizeof(pr)) ;

    for (int i =  ; i <= maxn ; ++ i) {

        if (!pr[i]) pr[++pr[]] = i ;

        for (int j =  ; j <= pr[] && i * pr[j] <= maxn ; ++ j) {

            pr[i*pr[j]] =  ;

            if (i%pr[j] == ) break ;

        }

    }

}

LL getans(LL x)

{

    if (x == ) return  ;

    if (x == ) return  ;

    LL cnt =  , ans =  ;

    for (int i =  ; pr[i]*pr[i] <= x ; ++ i) {

        if (x%pr[i] == ) {

            cnt =  ;

            while (x%pr[i] == ) {

                cnt ++ ;

                x /= pr[i] ;

            }

            ans *= (cnt + ) ;

        }

    }

    if (x > ) ans *=  ;

    return ans ;

}

int main()

{

    LL x ;

    getprime() ;

    while (cin >> x) {

        cout << getans(x) << endl ;

    }

    return  ;

}

H.a wise choice!

分析：凸包

//#define LOCAL

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <vector>

using namespace std;

struct Point

{

    double x, y;

    Point(double x=, double y=):x(x), y(y) {}

};

typedef Point Vector;

Point operator + (Point A, Point B)

{

    return Point(A.x+B.x, A.y+B.y);

}

Point operator - (Point A, Point B)

{

    return Point(A.x-B.x, A.y-B.y);

}

bool operator < (const Point& A, const Point& B)

{

    return A.x < B.x || (A.x == B.x && A.y < B.y);

}

bool operator == (const Point& A, const Point& B)

{

    return A.x == B.x && A.y == B.y;

}

double Cross(Vector A, Vector B)

{

    return A.x*B.y - A.y*B.x;

}

vector<Point> ConvexHull(vector<Point> p) {

  // 预处理，删除重复点

  sort(p.begin(), p.end());

  p.erase(unique(p.begin(), p.end()), p.end());

  int n = p.size();

  int m = ;

  vector<Point> ch(n+);

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

    while(m >  && Cross(ch[m-]-ch[m-], p[i]-ch[m-]) <= ) m--;

    ch[m++] = p[i];

  }

  int k = m;

  for(int i = n-; i >= ; i--) {

    while(m > k && Cross(ch[m-]-ch[m-], p[i]-ch[m-]) <= ) m--;

    ch[m++] = p[i];

  }

  if(n > ) m--;

  //for(int i = 0; i < m; ++i) printf("%lf %lf\n", ch[i].x, ch[i].y);

  ch.resize(m);

  return ch;

}

double sumx, sumy;

double Dist(Point a, Point b, int m)

{

    double A = a.y-b.y, B = b.x-a.x, C = a.x*b.y - b.x*a.y;

    //printf("%lf %lf", fabs(A*sumx+B*sumy+C), sqrt(A*A+B*B));

    return (fabs(A*sumx+B*sumy+C*m) / sqrt(A*A+B*B));

}

int main(void)

{

    int T;

    scanf("%d", &T);

    for(int kase = ; kase <= T; ++kase)

    {

        int n;

        vector<Point> p;

        sumx = 0.0, sumy = 0.0;

        scanf("%d", &n);

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

        {

            double x, y;

            scanf("%lf%lf", &x, &y);

            p.push_back(Point(x, y));

            sumx += x;    sumy += y;

        }

        vector<Point> ch = ConvexHull(p);

        int m = ch.size();

        //for(int i = 0; i < m; ++i)    printf("%lf %lf\n", ch[i].x, ch[i].y);

        if(m <= )

        {

            printf("Case #%d: 0.000\n", kase);

            continue;

        }

        double ans = 1e10;

        for(int i = ; i < m; ++i)

            ans = min(ans, Dist(ch[i], ch[(i+)%m], n));

        printf("Case #%d: %.3lf\n", kase, ans/n);

    }

}

J.BirthDay Gift

分析：动态规划

CHD 2014迎新杯比赛题解

/* ***********************************************

MYID    : Chen Fan

LANG    : G++

PROG    : J_Std

************************************************ */

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int f[][];

int a[];

int main()

{

//    freopen("data.in","r",stdin);

    int t;

    scanf("%d",&t);

    for (int tt=;tt<=t;tt++)

    {

        printf("Case #%d: ",tt);

        int n,sum=;

        scanf("%d",&n);

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

        {

            scanf("%d",&a[i]);

            sum+=a[i];

        }

        sum/=;

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

        for (int j=;j<=;j++) f[i][j]=-;

        f[][]=;

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

        for (int j=sum;j>=;j--)

        if (j>=a[i]) f[i][j]=max(max(f[i-][j],f[i-][j+a[i]]),f[i-][j-a[i]]+a[i]);

        else f[i][j]=max(max(f[i-][j],f[i-][j+a[i]]),f[i-][a[i]-j]+j);

        if (f[n][]==) printf("Unhappy\n");

        else printf("Happy %d\n",f[n][]);

    }

    return ;

}

秒客网

CHD 2014迎新杯比赛题解

相关文章