ACM新生赛题目解题报告2
Hosted by 计算机与信息科学系
解题报告
2012.5.19
12:00~17:00
本题册总共有10道题目，页数共有39页。
注意事项
1、比赛网址是：https://www.sodocs.net/doc/995643207.html,。
2、可以带一切纸质材料，严禁携带U盘等电子类产品。
3、杜绝网上搜索资料和互相抄袭，如有发现，上报学校处分。
4、本测试系统采用的是window平台的服务器，int类型为4
个字节，__int64为8个字节，8个字节的输出格式为
printf(“%I64d\n”,n);
5、有问题可以举手找志愿者。
6、比赛结束将分发答案参考程序。
1、Be Good at Guassing
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Problem Description
Give you many positive integer N (N<=23),for each N, just output N*(N+1)/2 integers in a single line, separated by space. (Don't ask me why.)For each N, the output line contains integers from 1 to N, and each just once. Again, do not ask me why, thank you. I'm so busy. But I can tell you a secret, the output has relationship with number triangle. As:(N=3)
1
2 6
3 4 5
See the sample for more information.
Input
Many lines, each line contains a positive integer N (N<=23).
3
4
2
6
Sample Output
1 2 6 3 4 5
1 2 9 3 10 8 4 5 6 7
1 2 3
1 2 15 3 16 14 4 17 21 13 5 18 19 20 12 6 7 8 9 10 11 解题代码
#include
using namespace std;
#include
#include
#include
#include
const int maxN = 24;
int tri[maxN][maxN];
int main()
{
int N,value,row,col,dir,i,j;
while(cin>>N)
{
memset(tri,0,sizeof(tri));
row=col=1;
for(value=1;value<=N;++value)
tri[row++][col]=value;
row=N,col=2;
for(value=N+1;value<=2*N-1;++value) tri[row][col++]=value;
row=N-1,col=N-1;
for(value=2*N;value<=3*N-3;++value) tri[row--][col--]=value;
row=2,col=2;
value=3*N-2;
dir=1;
while(value<=N*(N+1)/2)
{
if(1==dir)/*down one line*/
{
if((0==tri[row+1][col]))
tri[++row][col]=value;
else
{
dir=2;
tri[row][++col]=value;
}
}
else if(2==dir)/*right one line*/ {
if((0==tri[row][col+1]))
tri[row][++col]=value;
else
{
dir=3;
tri[--row][--col]=value;
}
}
else
{
if((0==tri[row-1][col-1]))
tri[--row][--col]=value;
else
{
dir=1;
tri[++row][col]=value;
}
}
++value;
}
for(row=1;row<=N;++row)
{
for(col=1;col<=row;++col)
{
cout< if(!(row==N&&col==row)) cout<<" "; } } cout< } return 0; } 2、工院宅男 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Problem Description 男女比例严重失调的工院向来不乏宅男，Jim做为茫茫一员，每天过着三点一线的生活，宿舍、饭店、教室。为了节省时间Jim觉得应该找一个离宿舍和教室最近的饭店，没必须浪费这么多时间在这条线上（神一般的宅男）。现在给你一张地图来帮Jim找出这个饭店，在这张地图中Jim可以往上、下、左、右四个方向走，且花费一个单位的时间。输入只包含一个宿舍、一个教室，饭店可以多个。 Input 第一行输入一个正整数T，表示共有T组测试项。 每组先输入两个整数n、m(2<=m、n<=200)表示地图的规模。 接下来是n行，每行m个字符： ‘S’ 表示宿舍 ‘F’ 饭店 ‘J’ 教室 ‘#’ 障碍 ‘.’ 路 Output 每一项输出Jim所要花的最少时间。结果保证可以找到一个饭店。 Sample Input 3 4 4 J.#F .... ..#S . F.. 4 4 J.#F .... .#.. F#.S 5 5 J..F. ..... .#... F..S. #.#.# Sample Output 7 8 6 解题报告 两遍广度优先搜索 #include int i,j; int time; }; int array[250][250]; int direction[4][2]={{0,-1},{0,1},{1,0},{-1,0}}; char map[250][250]; bool mark[250][250]; int n,m; void bfs(int x,int y){ queue node d,p; p.i=x; p.j=y; p.time=0; mark[x][y]=true; q.push(p); while(!q.empty()){ d=q.front(); q.pop(); if('F'==map[d.i][d.j]){ array[d.i][d.j]+=d.time; } for(int i=0;i<4;i++){ p.i=d.i+direction[i][0]; p.j=d.j+direction[i][1]; if( p.i>=0&&p.i &&false==mark[p.i][p.j] &&'#'!=map[p.i][p.j]){ mark[p.i][p.j]=true; p.time=d.time+1; q.push(p); } } } } int main(){ int T,m_i,m_j; int y_i,y_j; scanf("%d",&T); while(T--){ cin>>n>>m; for(int i=0;i for(int j=0;j cin>>map[i][j]; if('J'==map[i][j]){ y_i=i; y_j=j; } else if('S'==map[i][j]){ m_i=i; m_j=j; } } memset(array,0,sizeof(array)); memset(mark,false,sizeof(mark)); bfs(m_i,m_j); memset(mark,false,sizeof(mark)); bfs(y_i,y_j); int min=999999999; for(int i=0;i for(int j=0;j if(array[i][j]!=0&&min>array[i][j]){ min=array[i][j]; } }} cout< } return 0; } 3、Fantasy character game Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Problem Description A string and the string operations are given. Please deal with the string according to the operation orderly, and tell me what the final string is. Operations: Step 1: Reverse the order of the string from the first character to the last, such as change ABCDE into EDCBA. Step 2: Pick up the odd digit letters of the string together and put it in the front of the string, such as change ABCDE into ACEBD. Step 3: For each letter of the string, if the letter is in A-M plus 13, if not, minus 13, such as change A into N and O into B. Step 4: Map each character in the string, A-Z respectively corresponding to QWERTYUIOPASDFGHJKLZXCVBNM. Step 5: Split the string into two substrings, the length of the first half substring is L/2, and the second is (L+1)/2 long, then put the second substring before the first one, for example: make ABCDE into CDEAB or ABCDEF into DEFABC. Step 6: Split the string into two substrings, the length of the first half substring is L/2, and the second is (L+1)/2 long, then make each substring do Step 1 and then connect them up. such as make ABCDE into BAEDC or ABCDEF into CBAFED. Input An integer T means T cases. T<=100,The lenth of the string<=100。 Following T lines, each line contains one string, make up by character 'A' to 'Z'. The length of every string is less then 10086. Output Print one string to each case. Sample Input 2 ABCDE UPFSVVJT Sample Output Case 1: JFHKG Case 2: ILOVEYOU 解题报告 简单的字符串模拟题 #include #include char s1[10086]; char s2[10086]; char map[27]={'Q','W','E','R','T','Y','U','I','O','P','A','S','D','F','G','H','J','K','L','Z','X', 'C','V','B','N','M'}; int main() { int cas,CAS; int l,i; scanf("%d",&CAS);gets(s2); for(cas=1;cas<=CAS;cas++) { gets(s1); memset(s2,0,sizeof(s2)); l=strlen(s1); for(i=0;i s2[l-i-1]=s1[i]; for(i=0;i s1[i/2]=s2[i]; for(i=1;i s1[(l+i-1)/2+(l%2)]=s2[i]; for(i=0;i if(s1[i]>'M') s1[i]-=13; else s1[i]+=13; for(i=0;i s1[i]=map[s1[i]-'A']; if(l&1) { s2[l-1]=s1[l-1]; for(i=0;i s2[l-i-2]=s1[i]; } else { for(i=0;i s2[l-i-1]=s1[i]; } printf("Case %d:\n",cas); puts(s2); } return 0; } 4、环形渠道 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Problem Description 一个环形渠道，被n个挡板分为n块区域，每块区块含M1、M2、M3……Mn 大小的水量，现在要求拆掉最少的挡板使各个区域的水量相等。比如环形渠道被6块挡板分为10 、3、5、4、1、1的水量，那么只要拆除3块挡板即可（分别拆除3和5、1和1、1和10之间的挡板） Input 第一行输入一个正整数数T，表示共有T组测试数据。 接下来是T行 每行的第一个数为整数n，表示水池分为n块区块，之后输入n个正整数，分别表示每个区域的水量。 Output 输出每组数据至少要拆除要多少块挡板，每组一行。 Sample Input 3 6 10 3 5 4 1 1 4 4 4 3 3 8 2 1 1 2 2 1 1 6 Sample Output 3 2 5 解题报告 这题不要想太多，直接暴力两重循环，直到找到各个水池相等为止。#include #include #include #include #include #define eps 1e-8 using namespace std; int main() { int t; int n; int tank[210]; cin>>t; while (t--) { cin>>n; int i; double sum = 0; for (i = 0; i < n; i++) { cin>>tank[i]; sum += tank[i]; } double avg = sum/n; int mmin = n; int cnt = 0; double temp = 0; int t_min = 0; int j; for (i = 0; i < n; i++) { cnt = 1; temp = 0; t_min = 0; for (j = 0; j < n; j++) { temp += tank[(i + j) % n]; if (abs(temp / cnt - avg) < eps) { t_min += cnt - 1; temp = 0; cnt = 1;