CHD 2014迎新杯比赛题解

本文主要是介绍CHD 2014迎新杯比赛题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A. 草滩的魔法学校

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

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

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

#include <cstdio>
#include <cstring>
int a[9999], n, t;void solve( int n ){int id = 0, add;a[0] = 1;for( int i = 2; i <= n; ++i ){add = 0;for( int j = 0; j <= id; ++j ){a[j] = a[j] * i + add;add = a[j] / 10;a[j] = a[j] % 10;}while( add ){a[++id] = add % 10;add /= 10;}}for( int i = id; i >= 0; --i ){printf( "%d",a[i] );}putchar( '\n' );
}int main(){scanf( "%d", &t );while( t-- ){scanf( "%d", &n );solve(n);}return 0;
}

View Code

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 1;else if( ch == 'Z' && sco > 600 ) return 60;else if( ch == 'S' && sco > 700 ) return 70;else if( ch == 'H' && sco > 2000 ) return 200;else return 0;
}int main(){int cas = 1;while( ~scanf( "%d", &sco ) && sco ){scanf( "%d", &n );int flag = 1;while( n-- ){getchar();ch = getchar();if( !flag ) continue;int add = check( ch );if(  add ){sco += add;}else{flag = 0;}}printf( "Case #%d: %d\n", cas++, sco );}return 0;
}

View Code

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[][3]={1,0,0,-1,0,0,0,1,0,0,-1,0,0,0,1,0,0,-1};
int A,B,C,t;
struct node{int x,y,z,t;
};
int jud(int x,int y,int z){if(x>=0&&x<A&&y>=0&&y<B&&z>=0&&z<C&&!g[x][y][z])return 1;else return 0;
}
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-1&&u.y==B-1&&u.z==C-1&&u.t<=t)return u.t;for(int i=0;i<6;++i){v=u;v.x+=dir[i][0];v.y+=dir[i][1];v.z+=dir[i][2];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]=1;}}}return -1;
}
int main(){int K,i,j,k;scanf("%d",&K);while(K--){memset(vis,0,sizeof(vis));scanf("%d%d%d%d",&A,&B,&C,&t);for(i=0;i<A;++i){for(j=0;j<B;++j){for(k=0;k<C;++k)scanf("%d",&g[i][j][k]);}}node s;s.x=0,s.y=0,s.z=0,s.t=0;vis[0][0][0]=1;printf("%d\n",bfs(s));}return 0;
}

View Code

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[2*N],s[N];
int next[2*N];
int plen;
void Next(){next[0]=0;plen=strlen(p);for(int i=1,k=0;i<plen;++i){while(k>0&&p[k]!=p[i]) k=next[k-1];if(p[k]==p[i]) k++;next[i]=k;}
}
int main(){while(~scanf("%s%s",p,s)){memset(next,0,sizeof(next));strcat(p,"*");strcat(p,s);Next();printf("%d\n",next[plen-1]);}return 0;
}

View Code

E.草滩小王子的相反数

分析：位运算

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

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

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

#include<cstdio>
int n, sum;
int main(){while( ~scanf( "%d", &n ) ){sum = 0;while( n ){sum <<= 1;sum += n & 1;n >>= 1;}printf( "%d\n", sum );}return 0;
}

View Code

F.草滩小王子的锻炼

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

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

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

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

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=49999;
const int M2=49998;
char c[102];
int pow(int x,int y,int M){int t=1,b=x%M;while(y){if(y&1)t=(t*b)%M;b=(b*b)%M;y>>=1;}return t;
}
int main(){int k,i,len;while(scanf("%s",c)==1){len=strlen(c);for(k=0,i=len-1;i>=0;i--){k=(k+(c[i]-'0')*pow(10,len-1-i,M2))%M2;}printf("%d\n",pow(2,k,M));}
}

View Code

G.拉面女神的粉丝

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

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <cstring>
#include <algorithm>
using namespace std ;
#define LL long long
const int maxn = (1<<16) ;
LL pr[maxn+10] ;void getprime()
{memset(pr,0,sizeof(pr)) ;for (int i = 2 ; i <= maxn ; ++ i) {if (!pr[i]) pr[++pr[0]] = i ;for (int j = 1 ; j <= pr[0] && i * pr[j] <= maxn ; ++ j) {pr[i*pr[j]] = 1 ;if (i%pr[j] == 0) break ;}}
}LL getans(LL x)
{if (x == 1) return 1 ;if (x == 0) return 0 ;LL cnt = 0 , ans = 1 ;for (int i = 1 ; pr[i]*pr[i] <= x ; ++ i) {if (x%pr[i] == 0) {cnt = 0 ;while (x%pr[i] == 0) {cnt ++ ;x /= pr[i] ;}ans *= (cnt + 1) ;}}if (x > 1) ans *= 2 ;return ans ;
}int main()
{LL x ;getprime() ;while (cin >> x) {cout << getans(x) << endl ;}return 0 ;
}

View Code

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=0, double y=0):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 = 0;vector<Point> ch(n+1);for(int i = 0; i < n; i++) {while(m > 1 && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--;ch[m++] = p[i];}int k = m;for(int i = n-2; i >= 0; i--) {while(m > k && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--;ch[m++] = p[i];}if(n > 1) 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 = 1; kase <= T; ++kase){int n;vector<Point> p;sumx = 0.0, sumy = 0.0;scanf("%d", &n);for(int i = 0; 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 <= 2){printf("Case #%d: 0.000\n", kase);continue;}double ans = 1e10;for(int i = 0; i < m; ++i)ans = min(ans, Dist(ch[i], ch[(i+1)%m], n));printf("Case #%d: %.3lf\n", kase, ans/n);}
}

View Code

J.BirthDay Gift

分析：动态规划

/* ***********************************************
MYID    : Chen Fan
LANG    : G++
PROG    : J_Std
************************************************ */#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;int f[110][2010];
int a[110];int main()
{
//    freopen("data.in","r",stdin);int t;scanf("%d",&t);for (int tt=1;tt<=t;tt++){printf("Case #%d: ",tt);int n,sum=0;scanf("%d",&n);for (int i=1;i<=n;i++){scanf("%d",&a[i]);sum+=a[i];}sum/=2;for (int i=0;i<=n;i++)for (int j=0;j<=2000;j++) f[i][j]=-3000;f[0][0]=0;for (int i=1;i<=n;i++)for (int j=sum;j>=0;j--)if (j>=a[i]) f[i][j]=max(max(f[i-1][j],f[i-1][j+a[i]]),f[i-1][j-a[i]]+a[i]);else f[i][j]=max(max(f[i-1][j],f[i-1][j+a[i]]),f[i-1][a[i]-j]+j);if (f[n][0]==0) printf("Unhappy\n");else printf("Happy %d\n",f[n][0]);}return 0;
}