第十一届湖南省大学生程度设计竞赛部分题解

    xiaoxiao2023-09-19  0

    阶乘除法

    Time Limit: 1 Sec   Memory Limit: 128 MB Submit: 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)。 如果答案不唯一, 应该尽量小。比如,若 k=120,输出应该是 n=5, m=1,而不是 n=6m=3,因为 5!/1!=6!/3!=120,而 5<6  

    Input

    输入包含不超过 100 组数据。每组数据包含一个整数 k (1<=k<=109)  

    Output

    对于每组数据,输出两个正整数 和 m。无解输出"Impossible",多解时应让 尽量小。  

    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 MB Submit: 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 MB Submit: 10   Solved: 6 [ Submit][ Status][ Web Board]

    Description

    给定两个简单多边形, 你的任务是判断二者是否有面积非空的公共部分。如下图, (a)中的两个 矩形只有一条公共线段,没有公共面积。 (a) (b) 在本题中,简单多边形是指不自交(也不会接触自身)、不含重复顶点并且相邻边不共线的多 边形。 注意: 本题并不复杂,但有很多看上去正确的算法实际上暗藏缺陷,请仔细考虑各种情况。  

    Input

    输入包含不超过 100 组数据。每组数据包含两行,每个多边形占一行。多边形的格式是:第一 个整数 表示顶点的个数 (3<=n<=100), 接下来是 对整数(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 MB Submit: 13   Solved: 6 [ Submit][ Status][ Web Board]

    Description

    有道题目是这样的: 输入一个 行 列网格,找一个格子,使得它所在的行和列中所有格子的数之和最大。 如果答案不唯一,输出任意解即可。 比如, 在下面的例子中,最优解是(1,3),即第一行和的三列的交点(行从上到下编号为 1~n,列从左到右编号为 1~m),所有 个数之和为 35 快要比赛的时候, 有一个裁判想到了这样一个算法:首先找一行 r(1<=r<=n) 使得该行所有数之和最大, 然后找一列 c(1<=c<=m) 使得该列所有数之和最大,最后直接输出(r,c)。 如果有多个满足条件的 r,输出最小的r。对于 同样处理。

    hint:     首先找一行 r(1<=r<=n) 使得该行所有数之和最大, 然后找一列(1<=c<=m) 使得该列所有数之和最大,最后直接输出(r,c)。 如果有多个满足条件的 r,输出最小的 r。对于 c 同样处理。      

    显然, 这个算法是错的, 但它竟然通过了大部分测试数据!你能找出那些让这个错误算法得到正确结果的“弱”数据,以便裁判们改进这些数据吗?  

    Input

    输入包含不超过 100 组数据。每组数据第一行为两个整数 n, m (1<=n<=500, 1<=m<=500), 即行数和列数。 以下 行每行包含 个 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 MB Submit: 11   Solved: 5 [ Submit][ Status][ Web Board]

    Description

    给一个 行 列的迷宫,每个格子要么是障碍物要么是空地。每个空地里都有一个权值。你的任务是从找一条(r1,c1)(r2,c2)的路径,使得经过的空地的权值之和最小。每一步可以往上下左右四个方向之一移动一格,但不能斜着移动,也不能移动到迷宫外面或者进入障碍物格子。 如下图,灰色格子代表障碍物。路径 A->B->D->F->E 的权值为 10+3+6+14+8=41,它是从 的最优路径。 注意,如果同一个格子被经过两次,则权值也要加两次。  

    为了让题目更有趣(顺便增加一下难度),你还需要回答另外一个问题:如果你每次必须转弯(左转、右转或者后退,只要不是沿着上次的方向继续走即可),最小权值是多少? 比如, 在上图中, 如果你刚刚从 走到 B,那么下一步你可以走到 或者 A,但不能走到 G。 在上图中, 到 的最优路径是 A->B->D->H->D->F->E,权和为10+3+6+2+6+14+8=49。注意, 经过了两次。  

    Input

    输入包含不超过 10 组数据。每组数据第一行包含 个整数 n, m, r1, c1, r2, c2 (2<=n,m<=500,1<=r1,r2<=n, 1<=c1,c2<=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 MB Submit: 3   Solved: 3 [ Submit][ Status][ Web Board]

    Description

    输入一个四个数字组成的整数 n,你的任务是数一数有多少种方法,恰好修改一个数字,把它变成一个完全平方数(不能把首位修改成 0)。比如 n=7844,有两种方法: 3844=6227744=882  

    Input

    输入第一行为整数 T (1<=T<=1000),即测试数据的组数,以后每行包含一个整数 n(1000<=n<=9999)  

    Output

    对于每组数据, 输出恰好修改一个数字, 把 变成完全平方数的方案数。  

    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 MB Submit: 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

    A 和 B 之间的最后一句话是"Hehe". A 和 C 之间的最后一句话是"Are you there?". B 和 D 之间的最后一句话是"What does hehehei mean?". E 和 F 之间的最后一句话是"I want to hehehehehe yah". 最后第一段和最后一段话是“止于呵呵”的(注意最后一段对话是以呵呵的变种结束),因此 比例是 50%。 思路:对每一段话进行判断有没有一个段落是由n个hehe组成的即可,注意边界条件

    代码:

    #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; }

    转载请注明原文地址: https://ju.6miu.com/read-1279080.html
    最新回复(0)