2015 年 JXNU_ACS 算法组寒假第二次周赛

浏览数：20 / 时间：2015年06月08日

2015 年 JXNU_ACS 算法组寒假第二次周赛

比赛链接:http://acm.hdu.edu.cn/diy/contest_show.php?cid=26246

Start Time : 2015-02-01 13:00:00

End Time : 2015-02-01 17:30:00

终榜:http://acm.hdu.edu.cn/diy/contest_ranklist.php?cid=26246&page=1

这次比赛考查的知识都很基础，甚至还有几道就是C语言基础(比如1006 但只有一个人A了)，总体难度不大。

高精度、深搜、广搜的题都是模板题，没有转一丁点儿弯的。

这些东西就不废话了，我想吐槽的是你们的编码风格！！！ 为毛我看到1001有人函数名取dfs....

随手Google了一篇博文:http://hustcs.is-programmer.com/posts/16567.html

两点建议吧:

1.函数取名要有一定意义

2.重复的代码最好写成函数形式

通过这次比赛我希望大家要注重基础，当然这里的基础也不仅仅是包括基础知识&基本算法——还有编码风格。

and 这次数据没出什么问题，比赛途中开溜了下~ 当然这得感谢@WX 的测题

【这次做题情况不好的同学也不要灰心~~ 对于新生来说，这才刚开始 你需要做的是投入更多的时间】

-----------------------------现在流行分割线-------------------我也来一条玩玩-----------------------

一、1001.Factorial

题意:题目虽是英文，不过学过E文的都不应该存在障碍。so 略。

考点: 大数乘小数大数加法
PS :很基础的模板题新生用C++ 15mins 也1AC了，@WX 用Java更是分分钟过了。

直接上代码,没过的看下面的代码。

参考代码

C++:

#include<iostream>
#include<cstring>
#include<string>
#include<fstream>
//#define cin fin
//#define cout fout
#define maxn 620
using namespace std;
//ifstream fin("1001.in");
//ofstream fout("1001.out");
int F1[maxn],F2[maxn],m,n,t;
string ToString(int x[]){
    string res="";
    int i=maxn-1;
    for(;i>0&&!x[i];)i--;
    for(;i>=0;i--)res+=x[i]+'0';
    return res;
}
string calc(int x[],int k){
    for(int i=1;i<=k;i++){
        for(int j=0;j<maxn;j++)
            x[j]*=i;
        for(int j=0;j<maxn;j++)
        {
            if(x[j]>9){
                x[j+1]+=x[j]/10;
                x[j]%=10;
            }
        }
    }
    return ToString(x);
}
string Add(){
    for(int i=0;i<maxn;i++){
         F1[i]+=F2[i];
         if(F1[i]>9){
            F1[i+1]+=F1[i]/10;
            F1[i]%=10;
         }
    }
   return ToString(F1);
}
int main()
{
    cin>>t;
    while(t--)
    cin.sync_with_stdio(false);
   while(cin>>m>>n)
    {
        memset(F1,0,sizeof(F1));
        memset(F2,0,sizeof(F2));
        F1[0]=F2[0]=1;
        calc(F1,m); calc(F2,n);
       cout<<Add()<<endl;
    }
    return 0;
}

Java:

import java.util.*;
import java.math.*;
import java.io.*;
public class Main {
    static Scanner cin=new Scanner(new BufferedInputStream(System.in));
    public static void main(String args[]){
        int n,m,t;
        t=cin.nextInt();
        while(cin.hasNext()){
            n=cin.nextInt();m=cin.nextInt();
            System.out.println(fac(n).add(fac(m)));
        }
    }
    static BigInteger fac(int n){
        BigInteger ans=BigInteger.ONE;
        for(int i=1;i<=n;i++) ans=ans.multiply(BigInteger.valueOf(i));
        return ans;
    }
}

二、1002.Fibonacci

题意:这题就是求斐波那契序列
PS：需要注意的是，要用long long ~~还有需要开一个数组，用"动态规划"
　　的思想避免重复计算——看看时限就知道了,250ms

参考代码：

#include<iostream>
#define maxn 100
#define LL long long
#include<fstream>
//#define cin fin
//#define cout fout
using namespace std;
//ifstream fin("1002.in");
//ofstream fout("1002.out");
LL F[maxn],n,t;
struct Node{
    LL bit,r;
}res[maxn];
LL fib(int x){
    if(F[x])return F[x];
    F[x]=fib(x-2)+fib(x-1);
    return F[x];
}
void init(){
     for(int i=1;i<95;i++){
     LL temp=fib(i),sum=0,num;
     num=temp;
     while(temp){
        sum++; temp/=2;
     }
     res[i].bit=sum; res[i].r=num;
     }
}
int main()
{
    F[1]=F[2]=1;
    init();
    cin>>t;
    while(t--){
     cin>>n;
     cout<<res[n].bit<<" "<<res[n].r<<endl;
    }
    return 0;
}

三、1003.colors

题意:这题就是求组合数

题解;模板题——DFS之我在群里传的课件中有求组合的代码，我这里就是把 1 2 3..
换成了颜色而已，其实还是一样。还有数据量不大，500ms的时限也算是宽裕

参考代码;

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 100+5
#include<string>
#include<fstream>
//#define cin fin
//#define cout fout
using namespace std;
//ifstream fin("1003.in");
//ofstream fout("1003.out");
string foll[maxn];
int m,n,f[maxn],res[maxn],bz[maxn];
void print(){
    for(int i=1;i<n;i++)
    cout<<foll[res[i]]<<" ";
    cout<<foll[res[n]]<<endl;
}
void comb(int k){
    if(k==n){
        print();
        return ;
    }
    for(int i=k;i<=m;i++){
        if(!bz[i]&&res[k]<i){
            res[k+1]=i;
            bz[i]=1;
            comb(k+1);
            bz[i]=0;
        }
    }
}
int main()
{
    while(cin>>m>>n){
        memset(res,0,sizeof(res));
        memset(bz,0,sizeof(bz));
        for(int i=1;i<=m;i++)cin>>foll[i];
        comb(0);
    }
    return 0;
}

四、1004.Tank

题意:给定一个图，求Y到T的最短路径长度，其中R和S均为障碍物。

题解:这题也是由我传在群里一个课件中的例题改遍的。

题目改简单了，变成一道标标准准的BFS模板题——数据量虽然不大，

但是你想用DFS跑出来该是不行的——我出的数据都是卡DFS的。像这

种求一个图中两点间的最短路径一般都是用BFS，如果问是否有路则DFS。

纯模板，没有挖坑。

参考代码:

#include<iostream>
#include<cstring>
#include<fstream>
#define maxn 10000000
//#define cin fin
//#define cout fout
#define N 11
using namespace std;
//ifstream fin("tank.in");
//ofstream fout("tank.out");
int m, n, ex, ey, exdir, nodedir, flag;
char ch;
struct Node{
	int x, y, step;
	bool chess[N][N];
}stat[maxn], temp;
int dir[4][2] = {
	{ 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 }
};
bool check(Node x){
	for (int i = 0; i <= exdir; i++)
	for (int j = 0; j<m; j++)
	for (int k = 0; k<n; k++)
	if (stat[0].chess[j][k] != temp.chess[j][k])
		return true;
	return false;
}
bool End(Node x){
	if (x.x == ex&&x.y == ey)return true;
	return false;
}
int main()
{
    int sum=0;
    cin.sync_with_stdio(false);
	while (cin >> m >> n&&(m||n)){
            sum++;
		for (int i = 0; i<m; i++)
		for (int j = 0; j<n; j++){
			stat[0].chess[i][j] = true;
			cin >> ch;
			if (ch == 'R' || ch == 'S'){
				stat[0].chess[i][j] = false;
			}
			else if (ch == 'Y'){
				stat[0].x = i; stat[0].y = j;
				stat[0].chess[i][j] = false;
			}
			else if (ch == 'T'){
				ex = i; ey = j;
			}
		}
		stat[0].step = 0;
		exdir = nodedir = 0; flag = 1;
		while (nodedir <= exdir&&exdir<maxn&&flag){
			for (int i = 0; i<4; i++){
				temp = stat[nodedir];
				int dx = dir[i][0] + temp.x, dy = dir[i][1] + temp.y;
				if (dx >= 0 && dx<m&&dy >= 0 && dy<n&&temp.chess[dx][dy]){

					temp.x = dx; temp.y = dy;
					temp.chess[dx][dy] = false;
					temp.step++;
					if (End(temp)){
						cout << temp.step << endl;
						flag = 0;
						break;
					}
					if (check(temp)){
						//cout << dx << " " << dy << endl;
						stat[++exdir] = temp;
					}
				}
			}
			nodedir++;
		}
	}
	return 0;
}

五、1005.Tank

题意:略。

题解:根据计算规则——利用"高斯公式"就可以推出来公式了。不过long long

型还是必须的——看了下一些WA的代码，达到了我预期的效果。不少同学

以为只要把存放结果的变量定义为long long就可以，其实如果两个int型

变量相乘，如果结果超过了int型，那么返回的结果也会是错的。
知道了这点，然后就是几行代码的事了

参考代码:

#include<iostream>
#include<fstream>
#include<cstdio>
#define LL double
//#define cin fin
//#define cout fout
using namespace std;
//ofstream fout("1007.out");
//ifstream fin("1007.in");
LL m,n,t,sum;
int main()
{
  // freopen("1007.out", "w", stdout);
    cin>>t;
    while(t--){
        cin>>n>>m;
         cout<<((m-n)*45+(n+m-1)*(m-n)*5+m)<<endl;
    }
   return 0;
}

六、1006、好大的数

题意：这个题目名，很负责人的告诉大家，我是故意的.... (逃...

题解:这个看着像是大数，其实用double型就可以了——说过要考C语言基础的
利用pow函数开方表示成 1/n就可以了 pow(p,1/n);另外要注意的是精度

问题，不能讲结果强转成int。这里提供两种解决方法:
1.用printf控制小数位输出。
2.直接用C++中的cout

参考代码:

#include <iostream>
#include<cstdio>
#include <math.h>
using namespace std;
int main()
{
   // freopen("1005.in", "r", stdin);
    //freopen("1005.out", "w", stdout);
    double n, p;
    while (scanf("%lf %lf", &n, &p) !=EOF)
    {
        printf("%0.0lf\n", pow(p, 1/n));
    }
    return 0;
}

七、1007.YouKnow

题意:前面一堆废话(介绍UNO)的——我就是故意的~_~ 因为，我也被酱紫坑过，这种情况是会出现的【具体参考2014年ＡＣＭ－ＩＣＰＣ西安邀请赛＆考2014年ＡＣＭ－ＩＣＰＣ西安现场赛　第一题！！！你们不用自己找，我给链接：http://codeforces.com/gym/100548/attachments】
这题的题意就是叫你找规律，难点也在于在规律。
S(1)=0,
S(2)=10,
S(3)=1110,
...
规律就是——S(n)是对S(n-1)的一个描述。
例如求S(2)，因为S(1)是一个0 ，所以S(2)=10
然后S(3)，因为S(2)=10，是一个1和一个0，
所以S(3)=1110
就酱紫~~
接下来就是构造了

参考代码：

#include<iostream>
#include<fstream>
#include<string>
#define maxn 51
using namespace std;
//ifstream fin("1007.in");
//ofstream fout("1007.out");
string F[maxn];
//#define cin fin
//#define cout fout
int n;
void calc(int x){
    string temp=F[x-1],res="";
    int len=temp.size(),num=1;
    char ch=temp[0];
    for(int i=1;i<len;i++){
        if(ch!=temp[i]){
            res+=num+'0';
            res+=ch;
            num=1;
            ch=temp[i];
        }
        else num++;
    }
    res+=num+'0';
    res+=ch;
    F[x]=res;
}
int main()
{
    F[1]="0";
    for(int i=2;i<maxn;i++){
        F[i]="";
        calc(i);
    }
   while(cin>>n&&n)
        cout<<F[n]<<endl;
    return 0;
}

八、1008.又是汉诺塔

题解: 绝对值排序+贪心
在第一次新生训练赛的时候出了一道绝对值排序的题，这里稍微改了下。
这里就是每次找出最小的数，贪心的思想，具体看代码即可。

参考代码:

#include<iostream>
#include<fstream>
#include<algorithm>
#define LL long long
#define maxn 100+5
//#define cin fin
//#define cout fout
using namespace std;
//ifstream fin("1008.in");
//ofstream fout("1008.out");
LL num[maxn],t,n,sum;
LL F(LL x){
    if(x<0)return -x;
    return x;
}
bool cmp(LL x,LL y){
    return F(x)<F(y);
}
int main()
{
    cin.sync_with_stdio(false);
    while(cin>>n){
        sum=0;
        for(int i=0;i<n;i++) cin>>num[i];
        sort(num,num+n,cmp);
        LL temp=num[0]; sum=1;
        for(int i=1;i<n;i++){
            if(temp*num[i]<0){
                temp=num[i];
                sum++;
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

2015 年 JXNU_ACS 算法组寒假第二次周赛