3月15日 大学先修

2014Q1:细菌的战争

查看提交统计提问 总时间限制:  1000ms 内存限制:  65536kB 描述

有两种细菌，一种是有害菌，繁殖能力很强，每小时会繁殖一倍；另一种是有益菌，繁殖能力较弱，每小时能繁殖百分之五。但在单位体积内，当有害菌数量超过一 百万时，多出的细菌会因为密度太大而迅速死亡，直到细菌数量下降到一百万。已知每个有益菌每小时能消灭一个有害菌。给定单位体积内有害菌和有益菌的初始数 量，请问多少小时后，有害菌将被有益菌消灭干净？

输入 输入的第一行为一个整数n，表示后边有n组数据。 每组数据占一行，有两个整数，依次为有害菌和有益菌单位体积中的初始数量。整数之间用一个空格分隔。 输出 输出有n行，每行一个整数，为每组数据对应的有害菌将被有益菌消灭干净所用的小时数。 样例输入 4 364 78 289 48 952 40 966 23 样例输出 187 199 203 220 提示 1. 被消灭的有害菌不能繁殖； 2. 有害菌的总数最大为一百万。 查看   提交   统计   提问 简单模拟 #include<bits/stdc++.h>using namespace std;int n;int main(){ cin >> n; for(int i = 1;i <= n;i++) { int a,b; int hour = 0; scanf("%d %d",&a,&b); while(a > 0) { a -= b; a <<= 1; b *= 1.05; hour++; if(a > 1000000) a = 1000000; } printf("%d\n",hour); } return 0;} 

2014Q2:分数求和

查看提交统计提问 总时间限制:  1000ms 内存限制:  65536kB 描述

输入n个分数并对他们求和，并用最简形式表示。所谓最简形式是指：分子分母的最大公约数为1；若最终结果的分母为1，则直接用整数表示。

如：5/6、10/3均是最简形式，而3/6需要化简为1/2, 3/1需要化简为3。

分子和分母均不为0，也不为负数。

输入 第一行是一个整数n，表示分数个数，1 <= n <= 10； 接下来n行，每行一个分数，用"p/q"的形式表示，不含空格，p，q均不超过10。 输出 输出只有一行，即最终结果的最简形式。若为分数，用"p/q"的形式表示。 样例输入 2 1/2 1/3 样例输出 5/6 查看   提交   统计   提问 模拟模拟 代码： #include<bits/stdc++.h>using namespace std;int n;long long son,mom,sumson,summom;long long gcd(long long a,long long b){ return (b == 0 ? a : gcd(b,a % b)); } int main() { cin >> n; for(int i = 1;i <= n; i++) { char ch; if(i == 1) { scanf("%lld %c %lld",&sumson,&ch,&summom); continue; }  scanf("%lld %c %lld",&son,&ch,&mom); sumson = sumson * mom + son * summom; summom = summom * mom; } long long g = gcd(sumson,summom); if(g == 1) { if(summom == 1) printf("%lld",sumson); else{ printf("%lld/%lld",sumson,summom); } } else{ sumson /= g; summom /= g; if(summom == 1) printf("%lld",sumson); else{ printf("%lld/%lld",sumson,summom); } } return 0; }

2015Q1:流感传染

查看提交统计提问 总时间限制:  1000ms 内存限制:  65536kB 描述

有一批易感人群住在网格状的宿舍区内，宿舍区为n*n的矩阵，每个格点为一个房间，房间里可能住人，也可能空着。在第一天，有些房间里的人得了流感，以后每天，得流感的人会使其邻居传染上流感，（已经得病的不变），空房间不会传染。请输出第m天得流感的人数。

输入 第一行一个数字n，n不超过100，表示有n*n的宿舍房间。 接下来的n行，每行n个字符，’.’表示第一天该房间住着健康的人，’#’表示该房间空着，’@’表示第一天该房间住着得流感的人。 接下来的一行是一个整数m，m不超过100. 输出 输出第m天，得流感的人数 样例输入 5 ....# .#.@. .#@.. #.... ..... 4 样例输出 16 查看 提交 统计 提问 #include<bits/stdc++.h>using namespace std;const int MAXN = 105;int ans = 0;int k = 0;char Map[MAXN][MAXN];int n,m;int flag[MAXN][MAXN];int ganran[MAXN * MAXN];void search(int t){ while(t--) { k++; for(int i = 0;i < n;i++) { for(int j = 0;j < n;j++) { if(Map[i][j] == '@' && flag[i][j] == k - 1) { ans++; if(t == 0) goto on; if(i + 1 < n && Map[i + 1][j] == '.' && !flag[i + 1][j]) { Map[i + 1][j] = '@'; flag[i + 1][j] = k; } if(i - 1 >= 0 && Map[i - 1][j] == '.' && !flag[i - 1][j]) { Map[i - 1][j] = '@'; flag[i - 1][j] = k; } if(j + 1 < n && Map[i][j + 1] == '.' && !flag[i][j + 1]) { Map[i][j + 1] = '@'; flag[i][j + 1] = k; } if(j - 1 >= 0 && Map[i][j - 1] == '.' && !flag[i][j - 1]) { Map[i][j - 1] = '@'; flag[i][j - 1] = k; } } on : ; }  } } return;} int main(){ cin >> n; for(int i = 0;i < n;i++) { scanf("%s",Map[i]); } cin >> m; search(m); printf("%d",ans); return 0;}

2015Q3:实数加法

查看提交统计提问 总时间限制:  1000ms 内存限制:  65536kB 描述

求2个实数相加的和。

输入输出中出现的实数都有如下的形式： P₁P₂...P_i.Q₁Q₂...Q_j。对于整数部分，P₁P₂...P_i是一个非负整数；对于小数部分，至少有一位且最后一位Q_j不等于0。

输入 2行，分别是两个加数。每个加数不超过100个字符。 输出 一行输出是相应的和。数据保证一定是一个小数部分不为0的实数。 样例输入 0.111111111111111111111111111111 0.111111111111111111111111111111 样例输出 0.222222222222222222222222222222 查看 提交 统计 提问 #include<bits/stdc++.h>const int MAXN = 1005;using namespace std;char x;string s1 = "",s2,s3 = "",s4;int a[MAXN],b[MAXN],c[MAXN],len;main(){ int i,j; while(cin >> x, x != '.') { s1 = x + s1; } cin >> s2; while(cin >> x, x != '.') { s3 = x + s3; } cin >> s4; if(s1.size() < s3.size()) swap(s1,s3); for(i = 0;i < s3.size();i++) { a[i] += s1[i] + s3[i] - 2*'0'; if(a[i] >= 10) { a[i + 1] += a[i]/10; a[i] %= 10; } } for(;i < s1.size();i++) { a[i] += s1[i] - '0'; if(a[i] >= 10) { a[i + 1] += a[i]/10; a[i] %= 10; } } if(a[i]) len = i; else len = i - 1; if(s2.size() < s4.size()) swap(s2,s4); for(i = 0; i < s4.size();i++) b[i] = s2[i] + s4[i] - 2*'0'; for(;i < s2.size();i++) b[i] = s2[i] - '0'; for(i = s2.size() - 1;i >= 0;i--) { if(i == 0 && b[i] >= 10) { a[0]++; b[0] -= 10; } else if(b[i] >= 10) { b[i - 1]++; b[i] -= 10; } } i = 0; while(a[i] >= 10) { a[i + 1]++; a[i] -= 10; i++; } len = max(len,i); for(j = len;j >= 0;j--) printf("%d",a[j]); cout << '.'; for(j = s2.size() - 1;j >= 0;j--) if(b[j]) break; for(i = 0;i <= j;i++) printf("%d",b[i]); return 0;}

2015Q4:还是采药问题

查看提交统计提问 总时间限制:  1000ms 内存限制:  65536kB 描述 辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。” 如果你是辰辰，你能完成这个任务吗？  输入 输入第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。 输出 输出包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。 样例输入 70 3 71 100 69 1 1 2 样例输出 3 来源 计算概论化学学院期末考试 查看 提交 统计 提问 #include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#include<iostream>using namespace std;int t,m;int f[10000][10000];int w[10000],c[10000];int main(){ cin>>t>>m; for(int i = 1;i <= m; i++) { cin>>w[i]>>c[i]; } for(int i = 1; i <= m; i++) { for(int j = 0; j <= t ;j++) { f[i][j] = (i == 1 ? 0 : f[i-1][j]); if(j >= w[i]) f[i][j] = max(f[i][j],f[i-1][j-w[i]]+c[i]); } } cout << f[m][t]; return 0;}

2015Q2:字符串最大跨距

查看提交统计提问 总时间限制:  1000ms 内存限制:  65536kB 描述

有三个字符串S,S1,S2，其中，S长度不超过300，S1和S2的长度不超过10。想检测S1和S2是否同时在S中出现，且S1位于S2的左边，并在S中互不交叉（即，S1的右边界点在S2的左边界点的左侧）。计算满足上述条件的最大跨距（即，最大间隔距离：最右边的S2的起始点与最左边的S1的终止点之间的字符数目）。如果没有满足条件的S1，S2存在，则输出-1。 例如，S = "abcd123ab888efghij45ef67kl", S1="ab", S2="ef"，其中，S1在S中出现了2次，S2也在S中出现了2次，最大跨距为：18。

输入 三个串：S1, S2, S3，其间以逗号间隔（注意，S1, S2, S3中均不含逗号和空格）； 输出 S1和S2在S最大跨距；若在S中没有满足条件的S1和S2，则输出-1。 样例输入 abcd123ab888efghij45ef67kl,ab,ef 样例输出 18 查看 提交 统计 提问 #include<bits/stdc++.h>using namespace std;char s1[15],s2[15],s3[305];int lens1 = 0,lens2 = 0,lens3 = 0;int k = 0;int l,r;int main(){ char c; while((c = getchar()) && c != ',') s3[lens3++] = c; while((c = getchar()) && c != ',') s1[lens1++] = c; while((c = getchar()) && c != EOF) s2[lens2++] = c; for(int i = 0;i < lens3;i++) { if(s3[i] == s1[k]) k++; else k = 0; if(k == lens1) { l = i + 1; break; } } int ss2 = lens2 - 2; for(int i = lens3 - 1;i >= 0;i--) { if(s3[i] == s2[ss2]) ss2--; else ss2 = lens2 - 2; if(ss2 == 0) { r = i - 1; break; } } int ans = r - l; if(ans >= 0) printf("%d",ans); else  cout << -1;  return 0;}