本文提供了第十一届湖南省大学生程序设计竞赛的部分题目解析，包括阶乘除法、实数比较、多边形公共部分判断、求解网格中最大和的算法分析以及图论问题的解答。每个题目详细描述了输入输出格式，并给出了样例输入输出。
阶乘除法
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 13 Solved: 7
[ Submit][ Status][ Web Board]
Description
输入两个正整数 n, m，输出 n!/m!，其中阶乘定义为 n!= 1*2*3*...*n (n>=1)。
比如，若 n=6, m=3，则 n!/m!=6!/3!=720/6=120。是不是很简单？现在让我们把问题反过来：输入 k=n!/m!，找到这样的整数二元组(n,m)(n>m>=1)。
如果答案不唯一， n 应该尽量小。比如，若 k=120，输出应该是 n=5， m=1，而不是 n=6，m=3，因为 5!/1!=6!/3!=120，而 5<6。
Input
输入包含不超过 100 组数据。每组数据包含一个整数 k (1<=k<=109)。
Output
对于每组数据，输出两个正整数 n 和 m。无解输出"Impossible"，多解时应让 n 尽量小。
Sample Input
120
1
210
Sample Output
Case 1: 5 1
Case 2: Impossible
Case 3: 7 4 找连续的数字乘积即可，用for循环或者尺取法
代码：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;
typedef long long LL;
int main()
{
LL k;
LL t = 1;
while(scanf("%lld",&k)!=EOF){
LL n = (LL)sqrt(k)+10;
LL l = 1,r =2,sum=1;
LL ans1=k-1,ans2=k;
bool flag = true;
while(l<n){
while(r<n&&sum<k){
sum*=r;
r++;
}
if(sum==k){
ans1 = l;
ans2 = r-1;
flag = false;
break;
}
sum=sum/l;
l++;
}
if(!flag){
if(ans1!=1) ans1--;
}
printf("Case %lld: ",t++);
if(k==1){
printf("Impossible\n");
}else{
printf("%lld %lld\n",ans2,ans1);
}
}
return 0;
}大还是小？
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 6 Solved: 4
[ Submit][ Status][ Web Board]
Description
输入两个实数，判断第一个数大，第二个数大还是一样大。每个数的格式为：
[整数部分].[小数部分]简单起见，整数部分和小数部分都保证非空，且整数部分不会有前导 0。 不过， 小数部分的最后可以有 0，因此 0.0 和 0.000 是一样大的
Input
输入包含不超过 20 组数据。每组数据包含一行，有两个实数（格式如前所述）。每个实数都
包含不超过 100 个字符。
Output
对于每组数据， 如果第一个数大， 输出"Bigger"。 如果第一个数小， 输出"Smaller"。 如果两个数相同， 输出"Same"。
Sample Input
<span class="sampledata" style="font-family: monospace; font-size: 18px; white-space: pre; background: none 0px 0px repeat scroll rgb(141, 184, 255);">1.0 2.0 0.00001 0.00000 0.0 0.000</span>
Sample Output
<span class="sampledata" style="font-family: monospace; font-size: 18px; white-space: pre; background: none 0px 0px repeat scroll rgb(141, 184, 255);">Case 1: Smaller Case 2: Bigger Case 3: Same</span>代码：
import java.math.BigDecimal;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = 1;
while(sc.hasNext()){
String str = sc.next();
String str1 = sc.next();
BigDecimal a = new BigDecimal(str);
BigDecimal b = new BigDecimal(str1);
System.out.print("Case "+(t++)+": ");
if(a.compareTo(b)==0){
System.out.println("Same");
}else if(a.compareTo(b)<0){
System.out.println("Smaller");
}else{
System.out.println("Bigger");
}
}
}
}多边形的公共部分
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 10 Solved: 6
[ Submit][ Status][ Web Board]
Description
给定两个简单多边形， 你的任务是判断二者是否有面积非空的公共部分。如下图， (a)中的两个
矩形只有一条公共线段，没有公共面积。
(a) (b)
在本题中，简单多边形是指不自交（也不会接触自身）、不含重复顶点并且相邻边不共线的多
边形。
注意： 本题并不复杂，但有很多看上去正确的算法实际上暗藏缺陷，请仔细考虑各种情况。
Input
输入包含不超过 100 组数据。每组数据包含两行，每个多边形占一行。多边形的格式是：第一
个整数 n 表示顶点的个数 (3<=n<=100)， 接下来是 n 对整数(x,y) (-1000<=x,y<=1000)， 即多边
形的各个顶点， 按照逆时针顺序排列。
Output
对于每组数据， 如果有非空的公共部分， 输出"Yes"， 否则输出"No"。
Sample Input
<span class="sampledata" style="font-family: monospace; font-size: 18px; white-space: pre; background: none 0px 0px repeat scroll rgb(141, 184, 255);">4 0 0 2 0 2 2 0 2 4 2 0 4 0 4 2 2 2 4 0 0 2 0 2 2 0 2 4 1 0 3 0 3 2 1 2</span>
Sample Output
<span class="sampledata" style="font-family: monospace; font-size: 18px; white-space: pre; background: none 0px 0px repeat scroll rgb(141, 184, 255);">Case 1: No Case 2: Yes</span>思路：去年比赛没做出来，今年一开始用计算几何去判点，线段，多边形的关系然后还是过不去。
最后求面积并才过去了
代码：#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int maxn = 300;
const double eps = 1e-8;
const double pi = acos(-1.0);
int dcmp(double x)
{
if(x > eps) return 1;
return x < -eps ? -1 : 0;
}
struct Point
{
double x, y;
};
double cross(Point a,Point b,Point c) ///叉积
{
return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
}
Point intersection(Point a,Point b,Point c,Point d)
{
Point p = a;
double t =((a.x-c.x)*(c.y-d.y)-(a.y-c.y)*(c.x-d.x))/((a.x-b.x)*(c.y-d.y)-(a.y-b.y)*(c.x-d.x));
p.x +=(b.x-a.x)*t;
p.y +=(b.y-a.y)*t;
return p;
}
double PolygonArea(Point p[], int n)
{
if(n < 3) return 0.0;
double s = p[0].y * (p[n - 1].x - p[1].x);
p[n] = p[0];
for(int i = 1; i < n; ++ i)
s += p[i].y * (p[i - 1].x - p[i + 1].x);
return fabs(s * 0.5);
}
double CPIA(Point a[], Point b[], int na, int nb)//ConvexPolygonIntersectArea
{
Point p[20], tmp[20];
int tn, sflag, eflag;
a[na] = a[0], b[nb] = b[0];
memcpy(p,b,sizeof(Point)*(nb + 1));
for(int i = 0; i < na && nb > 2; i++)
{
sflag = dcmp(cross(a[i + 1], p[0],a[i]));
for(int j = tn = 0; j < nb; j++, sflag = eflag)
{
if(sflag>=0) tmp[tn++] = p[j];
eflag = dcmp(cross(a[i + 1], p[j + 1],a[i]));
if((sflag ^ eflag) == -2)
tmp[tn++] = intersection(a[i], a[i + 1], p[j], p[j + 1]); ///求交点
}
memcpy(p, tmp, sizeof(Point) * tn);
nb = tn, p[nb] = p[0];
}
if(nb < 3) return 0.0;
return PolygonArea(p, nb);
}
double SPIA(Point a[], Point b[], int na, int nb)///SimplePolygonIntersectArea 调用此函数
{
int i, j;
Point t1[4], t2[4];
double res = 0, num1, num2;
a[na] = t1[0] = a[0], b[nb] = t2[0] = b[0];
for(i = 2; i < na; i++)
{
t1[1] = a[i-1], t1[2] = a[i];
num1 = dcmp(cross(t1[1], t1[2],t1[0]));
if(num1 < 0) swap(t1[1], t1[2]);
for(j = 2; j < nb; j++)
{
t2[1] = b[j - 1], t2[2] = b[j];
num2 = dcmp(cross(t2[1], t2[2],t2[0]));
if(num2 < 0) swap(t2[1], t2[2]);
res += CPIA(t1, t2, 3, 3) * num1 * num2;
}
}
return PolygonArea(a, na)+PolygonArea(b, nb) - res;
}
Point p1[maxn], p2[maxn];
int n1, n2;
int main()
{
int t = 1;
while(scanf("%d", &n1) != EOF)
{
for(int i = 0; i < n1; i++) scanf("%lf%lf", &p1[i].x, &p1[i].y);
scanf("%d",&n2);
for(int i = 0; i < n2; i++) scanf("%lf%lf", &p2[i].x, &p2[i].y);
double Area = SPIA(p1, p2, n1, n2);
double Area1 = PolygonArea(p1,n1)+PolygonArea(p2,n2);
if(Area==Area1) printf("Case %d: No\n",t++);
else printf("Case %d: Yes\n",t++);
}
return 0;
}错误的算法
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 13 Solved: 6
[ Submit][ Status][ Web Board]
Description
有道题目是这样的：
输入一个 n 行 m 列网格，找一个格子，使得它所在的行和列中所有格子的数之和最大。 如果答案不唯一，输出任意解即可。 比如， 在下面的例子中，最优解是(1,3)，即第一行和的三列的交点（行从上到下编号为 1~n，列从左到右编号为 1~m），所有 7 个数之和为 35。
快要比赛的时候， 有一个裁判想到了这样一个算法：首先找一行 r(1<=r<=n) 使得该行所有数之和最大， 然后找一列 c(1<=c<=m) 使得该列所有数之和最大，最后直接输出(r,c)。 如果有多个满足条件的 r，输出最小的r。对于 c 同样处理。
hint: 首先找一行 r(1<=r<=n) 使得该行所有数之和最大， 然后找一列(1<=c<=m) 使得该列所有数之和最大，最后直接输出(r,c)。 如果有多个满足条件的 r，输出最小的 r。对于 c 同样处理。
显然， 这个算法是错的， 但它竟然通过了大部分测试数据！你能找出那些让这个错误算法得到正确结果的“弱”数据，以便裁判们改进这些数据吗？
Input
输入包含不超过 100 组数据。每组数据第一行为两个整数 n, m (1<=n<=500, 1<=m<=500)， 即行数和列数。 以下 n 行每行包含 m 个 1~100 的整数。输入的总大小不超过 2MB。
Output
对于每组数据， 如果错误算法能得到正确结果， 输出"Weak"，否则输出"Strong"。
Sample Input
4 4
5 5 5 5
1 1 5 1
1 1 5 1
1 1 5 1
5 4
2 5 1 1
1 1 9 1
1 1 1 1
1 1 1 1
1 1 1 1
Sample Output
Case 1: Weak
Case 2: Strong 思路：注意只要比值不要比坐标
代码：
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int N = 550;
int rsum[N],csum[N];
int graph[N][N];
int n,m;
int main()
{
int t = 1;
while(scanf("%d%d",&n,&m)!=EOF){
memset(rsum,0,sizeof(rsum));
memset(csum,0,sizeof(csum));
int r1,c1,r2,c2,MAX1=-1,MAX2=-1,MAX3=-1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&graph[i][j]);
rsum[i] += graph[i][j];
csum[j] += graph[i][j];
}
}
for(int i=1;i<=n;i++){
if(MAX1<rsum[i]){
MAX1 = rsum[i];
r1 = i;
}
}
for(int i=1;i<=m;i++){
if(MAX2<csum[i]){
MAX2 = csum[i];
c1 = i;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(MAX3<rsum[i]+csum[j]-graph[i][j]){
MAX3 = rsum[i]+csum[j]-graph[i][j];
r2 = i,c2 = j;
}
}
}
printf("Case %d: ",t++);
if(r1==r2&&c1==c2){
printf("Weak\n");
}else{
printf("Strong\n");
}
}
return 0;
}简单的图论问题？
Time Limit: 5 Sec Memory Limit: 128 MBSubmit: 11 Solved: 5
[ Submit][ Status][ Web Board]
Description
给一个 n 行 m 列的迷宫，每个格子要么是障碍物要么是空地。每个空地里都有一个权值。你的任务是从找一条(r1,c1)到(r2,c2)的路径，使得经过的空地的权值之和最小。每一步可以往上下左右四个方向之一移动一格，但不能斜着移动，也不能移动到迷宫外面或者进入障碍物格子。
如下图，灰色格子代表障碍物。路径 A->B->D->F->E 的权值为 10+3+6+14+8=41，它是从 A 到E 的最优路径。 注意，如果同一个格子被经过两次，则权值也要加两次。
为了让题目更有趣（顺便增加一下难度），你还需要回答另外一个问题：如果你每次必须转弯（左转、右转或者后退，只要不是沿着上次的方向继续走即可），最小权值是多少？ 比如， 在上图中， 如果你刚刚从 A 走到 B，那么下一步你可以走到 D 或者 A，但不能走到 G。 在上图中， A 到 E 的最优路径是 A->B->D->H->D->F->E，权和为10+3+6+2+6+14+8=49。注意， D 经过了两次。
Input
输入包含不超过 10 组数据。每组数据第一行包含 6 个整数 n, m, r1, c1, r2, c2 (2<=n,m<=500,1<=r1,r2<=n, 1<=c1,c2<=m). 接下来的 n 行每行包含 m 个格子的描述。每个格子要么是一个1~100 的整数，要么是星号"*"（表示障碍物）。起点和终点保证不是障碍物。
Output
对于每组数据， 输出两个整数。 第一个整数是“ 正常问题” 的答案， 第二个整数是“ 有趣问题” 的答案。 如果每个问题的答案是“无解”，对应的答案应输出-1。
Sample Input
4 4 1 2 3 2
7 10 3 9
* 45 6 2
* 8 14 *
21 1 * *
2 4 1 1 1 4
1 2 3 4
9 * * 9
2 4 1 1 1 4
1 * 3 4
9 9 * 9
Sample Output
Case 1: 41 49
Case 2: 10 -1
Case 3: -1 -1
思路：多记录一个方向
代码：#include <iostream>
#include<cstdio>>
#include<cstring>
#include<queue>
using namespace std;
struct Node
{
int x,y,dir,w; //d表示方向
Node(){}
Node(int x,int y,int dir,int w)
{
this->x = x;
this->y = y;
this->dir = dir;
this->w = w;
}
bool operator < (const Node &rhs)const {
return w > rhs.w;
}
};
int n,m,r1,r2,c1,c2;
int map[505][505];
int dire[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
int getnum(char *str)
{
int len = strlen(str);
int ans = 0;
for(int i = 0; i < len; i++)
{
ans = ans * 10 + str[i] - '0';
}
return ans;
}
int bfs1(int x,int y)
{
priority_queue<Node> q;
bool vis[505][505] = {0};
vis[x][y] = true;
Node now;
now.x = x, now.y = y;
now.w = map[x][y];
q.push(now);
while(!q.empty())
{
now = q.top();
q.pop();
if(now.x == r2 && now.y == c2) return now.w;
for(int i = 0; i < 4; i++)
{
int newx = now.x + dire[i][0];
int newy = now.y + dire[i][1];
if(newx < 1 || newx > n || newy < 1 || newy > m) continue;
if(vis[newx][newy] || map[newx][newy] == -1) continue;
vis[newx][newy] = true;
Node next;
next.x = newx, next.y = newy, next.w = now.w + map[newx][newy];
q.push(next);
}
}
return -1;
}
int bfs2(int x,int y)
{
priority_queue<Node> q;
bool vis[505][505][4] = {0};
q.push(Node(x,y,-1,map[x][y]));
while(!q.empty())
{
Node now = q.top();
q.pop();
if(now.x == r2 && now.y == c2) return now.w;
for(int i = 0; i < 4; i++)
{
int newx = now.x + dire[i][0];
int newy = now.y + dire[i][1];
if(newx < 1 || newx > n || newy < 1 || newy > m) continue;
if(vis[newx][newy][i] || map[newx][newy] == -1) continue;
if(i == now.dir) continue;
vis[newx][newy][i] = true;
q.push(Node(newx,newy,i,now.w + map[newx][newy]));
}
}
return -1;
}
int main()
{
int cas = 1;
char str[10];
while(scanf("%d%d%d%d%d%d",&n,&m,&r1,&c1,&r2,&c2)!=EOF)
{
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
scanf("%s",str);
if(str[0] == '*')
map[i][j] = -1;
else map[i][j] = getnum(str);
}
}
int ans1 = bfs1(r1,c1);
int ans2 = bfs2(r1,c1);
printf("Case %d: %d %d\n",cas++,ans1,ans2);
}
return 0;
}又一道简单题
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 3 Solved: 3
[ Submit][ Status][ Web Board]
Description
输入一个四个数字组成的整数 n，你的任务是数一数有多少种方法，恰好修改一个数字，把它变成一个完全平方数（不能把首位修改成 0）。比如 n=7844，有两种方法： 3844=622和7744=882。
Input
输入第一行为整数 T (1<=T<=1000)，即测试数据的组数，以后每行包含一个整数 n(1000<=n<=9999)。
Output
对于每组数据， 输出恰好修改一个数字， 把 n 变成完全平方数的方案数。
Sample Input
2
7844
9121
Sample Output
Case 1: 2
Case 2: 0 思路：一位一位去改即可
代码：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;
int f[10000];
int d[4],vis[10000];
void init()
{
memset(f,0,sizeof(f));
for(int i=32;;i++)
{
if(i*i>9999) break;
f[i*i]=1;
}
}
int solve(int x)
{
int ans=0;
memset(vis,0,sizeof(vis));
int l=x,t=0;
while(l)
{
d[t++]=l%10;
l/=10;
}
vis[x]=1;
for(int i=0;i<10;i++)
{
if(i==d[0]) continue;
int m=d[3]*1000+d[2]*100+d[1]*10+i;
if(vis[m]) continue;
vis[m]=1;
if(f[m]) ans++;
}
for(int i=0;i<10;i++)
{
if(i==d[1]) continue;
int m=d[3]*1000+d[2]*100+i*10+d[0];
if(vis[m]) continue;
vis[m]=1;
if(f[m]) ans++;
}
for(int i=0;i<10;i++)
{
if(i==d[2]) continue;
int m=d[3]*1000+i*100+d[1]*10+d[0];
if(vis[m]) continue;
vis[m]=1;
if(f[m]) ans++;
}
for(int i=1;i<10;i++)
{
if(i==d[3]) continue;
int m=i*1000+d[2]*100+d[1]*10+d[0];
if(vis[m]) continue;
vis[m]=1;
if(f[m]) ans++;
}
return ans;
}
int main()
{
int T,n,tot=1;
init();
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
printf("Case %d: ",tot++);
printf("%d\n",solve(n));
}
return 0;
}
聊天止于呵呵
Time Limit: 5 Sec Memory Limit: 128 MBSubmit: 15 Solved: 2
[ Submit][ Status][ Web Board]
Description
（现代版） 俗话说： 流言止于智者，聊天止于呵呵。 输入一段聊天记录，你的任务是数一数有多少段对话“止于呵呵”，即对话的最后一句话包含单词 hehe 或者它的变形。具体来说， 我们首先提取出对话的最后一句话， 把所有非字母的字符替换成空格， 把所有字符替换成小写， 然后导出一个单词列表（ 由空格隔开） ，只要列表中的任何一个单词是hehe，这段对话就算作“止于呵呵” 。比如， "Hi! Are you OK?" 会变成四个单词： hi, are, you, ok。 注意，单词列表可以是空的（比如，这句话是： "?!?!!"）有些人喜欢使用 hehe 的变形，这些变形也应被视为“呵呵”。为了简单起见，本题只考虑由n(n>1)个 he 连接而成的单词，比如 hehehe 或者 hehehehe。注意，以 hehe 为连续子串的其他单词不应视为“呵呵”，比如 hehee，或者 ehehe。
每两个不同人之间的所有对话算作“一段对话”。
Input
输入仅包含一组数据， 每行是一句对话， 格式为人名 1->人名 2: 一句话.
每行最多包含 1000 个字符，最多 100 行。
Output
输出“ 止于呵呵” 的对话段落所占的百分比， 四舍五入到最近的整数。 输入数据保证答案不会同时和两个整数最近。
Sample Input
A->B: Hello!
A->C: Hi!
B->A: Hehe
B->D: Hei!
D->B: How are you?
A->C: Hi???
A->C: Are you there?
B->D: Hehehei!
D->B: What does hehehei mean?
F->E: I want to hehehehehe yah.
Sample Output
50%
HINT
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
int ma[101][101];
map<string,int>m;
int main()
{
char op[10],s[1100];
int cnt=0;
memset(ma,0,sizeof(ma));
while(scanf("%s",op)!=EOF)
{
gets(s);
int len=strlen(s);
for(int i=len-1; i>=0; i--)
{
if(s[i]>='A'&&s[i]<='Z')
s[i+1]=s[i]-'A'+'a';
else if(s[i]<'a'||s[i]>'z')
s[i+1]=' ';
else s[i+1]=s[i];
}
s[0]=' ';
int flag=-1;
for(int i=0; i<len; i++)
{
if(s[i]==' '&&s[i+1]=='h')
{
int t=1;
for(i=i+2; i<=len&&s[i]!=' '; i++)
{
if(s[i-1]=='h'&&s[i]!='e') break;
if(s[i-1]=='e'&&s[i]!='h') break;
t++;
}
if(t>=4&&(s[i]==' '||i>len)&&s[i-1]=='e')
{
flag=1;
break;
}
i--;
}
}
int q=0;
string a;
for(q=0; q<strlen(op); q++)
{
if(op[q]=='-') break;
a+=op[q];
}
if(m.find(a)==m.end())
m[a]=cnt++;
string b;
for(q=q+2; q<strlen(op)-1; q++)
b+=op[q];
if(m.find(b)==m.end())
m[b]=cnt++;
ma[m[a]][m[b]]=ma[m[b]][m[a]]=flag;
}
double qian=0,hou=0;
for(int i=0; i<=100; i++)
for(int j=i+1; j<=100; j++)
{
if(ma[i][j]==-1) hou+=1.0;
else if(ma[i][j]==1) qian+=1.0;
}
hou+=qian;
int ans=(int)(qian*100/hou+0.5);
printf("%d%%\n",ans);
return 0;
}
扫一扫
3497
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
