2015 年 JXNU_ACS 算法组寒假第二次周赛
浏览数：20 /
时间：2015年06月08日
2015 年 JXNU_ACS 算法组寒假第二次周赛
Start Time : 2015-02-01 13:00:00
End Time : 2015-02-01 17:30:00
这次比赛考查的知识都很基础，甚至还有几道就是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;
}
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;
}
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
