2014年秋季大学先修课考试解题报告

A:细菌的战争

总时间限制:: 1000ms
内存限制:: 65536kB

描述

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

输入

输入的第一行为一个整数n，表示后边有n组数据。
每组数据占一行，有两个整数，依次为有害菌和有益菌单位体积中的初始数量。整数之间用一个空格分隔。

输出

输出有n行，每行一个整数，为每组数据对应的有害菌将被有益菌消灭干净所用的小时数。

样例输入

样例输出

提示

1. 被消灭的有害菌不能繁殖；

2. 有害菌的总数最大为一百万。

/*直接模拟*/
#include<iostream>
using namespace std;
#include<cstdio>
int n;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        int l=1;
        long long int a,b;
        cin>>a>>b;
        while(a>0)
        {
            a-=b;
            b+=0.05*b;
            a*=2;
            if(a>1000000)
            a=1000000;
            l++;
        }
        printf("%d
",l-1);
    }
    return 0;
}

View Code

B:分数求和

总时间限制:: 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<iostream>
using namespace std;
#define N 15
#include<cstdio>
struct Fsum{
    int fz,fm;
};
Fsum fsum[N],ans;
int n;
int search_gys(int a,int b)
{
    if(a<b)
    swap(a,b);
    while(b!=0)/*辗转相除法求最大公约数*/
    {
        int c=a-b;
        a=b;
        b=c;
        if(a<b) 
        swap(a,b);
    }
    return a;
}
int  search_gbs(int i)
{
    int k=search_gys(ans.fm,fsum[i].fm);/*a，b的最小公倍数=a*b/（a，b的最大公约数）*/
    return ans.fm*fsum[i].fm/k;
}
void add(int i)
{
    int k=search_gbs(i);/*相加的时候，先找分母最小公倍数，通分后相加*/
    ans.fz*=k/ans.fm;
    fsum[i].fz*=k/fsum[i].fm;
    ans.fm=k;
    ans.fz+=fsum[i].fz;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d/%d",&fsum[i].fz,&fsum[i].fm);
    }
    ans=fsum[1];
    for(int i=2;i<=n;++i)
        add(i);/* 把分数依次加起来*/
    int k=search_gys(ans.fz,ans.fm);/*把当前的分数约分，寻找最大公约数*/
    ans.fz/=k;ans.fm/=k;
    if(ans.fm==1)
    printf("%d
",ans.fz);
    else printf("%d/%d
",ans.fz,ans.fm);
    return 0;
}

View Code

C:啤酒厂选址

总时间限制:: 1000ms
内存限制:: 65536kB

描述

海上有一个岛，在环海边上建有一条环岛高速公路，沿着公路有n（5 < n < 10000）个居民点，假设每个居民点有一个编号，从0开始，按顺时针依次从小到大（即，0,1，…，n-1）编号。在岛上啤酒很受青睐。某啤酒企业计划在岛上投资建一个啤酒厂，并根据啤酒需求每天向居住点送啤酒。已知两个相邻的居民点的距离以及每个居住点每天的啤酒需求量（假设每个居住点每天不超过2000桶）。假定每单位长度的路程送一桶啤酒需要的费用恒定（为单位费用）。请问，选择哪一个居民点建啤酒厂，才能使每天送啤酒的费用最小（空车不计费用）。

输入

第一行：为居民点数目n
后面为n行，每行为一个居民点的啤酒需求量以及按顺时针离下一个居民点的距离（均为整数,空格间隔），从编号为0的开始，按单增顺次给出。

注意：后面第n行对应于居民点（n-1)的啤酒需求量以及到编号为0的居民点距离。

输出

啤酒厂所在的居民点编号以及每天的运输费用，其间以逗号间隔

样例输入

样例输出

0,94100

/*暴力解题法：把所有点作为起点的情况全部枚举一遍，找出最小值
数据没有你想象的那么强
注意点：用输入的数据生成前缀和
注意环形的处理
*/
#include<iostream>
using namespace std;
#include<cstdio>
#include<cstring>
#define N 10100
#include<cstdlib>
#define INF 1<<30
int n,p;
long long int ans=INF;
long long int a[N],dict[N],sum[N];
void input()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d",&sum[i],&a[i]);
        dict[i]=dict[i-1]+a[i-1];
    }
}
int qiu(int i,int k)//qiu i->k de fei xiao fei yong
{
    int ans1;
    if(i<k) ans1=(dict[k]-dict[i])*sum[i];
    else ans1=(dict[i]-dict[k])*sum[i];
    int ans2;
    if(i>k)
    ans2=(dict[n]-dict[i]+a[n]+dict[k])*sum[i];
    else ans2=(dict[n]-dict[k]+a[n]+dict[i])*sum[i];
    return min(ans1,ans2);
}
void chuli(int k)// k wei qi dian
{
    long long MAX=0;
    for(int i=1;i<=n;++i)
    {
        if(i==k) continue;
        MAX+=qiu(i,k);
    }
    if(ans>MAX)
    {
        ans=MAX;
        p=k;
    }
}
int main()
{
    input();
    for(int i=1;i<=n;++i)
    chuli(i);
    cout<<(p-1)<<","<<ans<<endl;
    return 0;
}

View Code

D:回文子串

总时间限制:: 1000ms
内存限制:: 65536kB

描述

给定一个字符串，输出所有回文子串。
回文子串即从左往右输出和从右往左输出结果是一样的字符串
比如： abba cccdeedccc都是回文字符串

我们要查找的子串长度应该大于等于2

输入

输入是一行，即可一个字符串。长度500以内
比如：
abcddcbaab

输出

输出所有的回文子串，一个满足条件的子串一行。
子串长度小的优先输出，出现在原始字符串靠左的子串优先输出。
比如对于abcddcbaab
输出：
dd
aa
cddc
baab
bcddcb
abcddcba

样例输入

123321125775165561

样例输出

33

11

77

55

2332

2112

5775

6556

123321

165561

#include<iostream>
using namespace std;
#include<cstdio>
#include<cstring>
char s[25015],lens;
bool judge(int l,int r)
{
    while(l<r)
    {
        if(s[l]!=s[r])
            return false;
        l++;
        r--;
    }
    return true;
}
int main()
{
    scanf("%s",s+1);
    lens=strlen(s+1);
    int k,i;
    int j;
    for(k=2;k<=lens;++k)
    {
        for(i=1;i<=lens;++i)
        {
            if(i+k-1>lens) break;
            if(judge(i,i+k-1))
            {
                for(j=i;j<=i+k-1;++j)
                {
                    printf("%c",s[j]);
                }
                printf("
");
            }
        }
    }
    //system("pause");
    return 0;
}

View Code

E:柱状图上的最大矩形

总时间限制:: 1000ms
内存限制:: 65536kB

描述

给定n个非负整数，代表柱状图上每个柱的高度（宽度均为1），求这个柱状图中最大的矩形面积。例如对于输入"2 1 5 6 2 3"，最大面积为10（见下图）

输入

第一行是一个整数n，代表有多少个柱形，n小于等于20000
第二行有n个整数，依次为每个柱形的高度

输出

一个数字，即这个柱状图中最大的矩形面积，面积最大不超过int的表示范围

样例输入

6
2 1 5 6 2 3

样例输出

10

/*这就是全0子矩阵的变式：一行数的做一遍扩展而已*/
#include<iostream>
using namespace std;
#include<cstdio>
int n;
#define N 20100
int h[N],l[N],r[N];
int ans=-N;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    scanf("%d",&h[i]);
    for(int j=1;j<=n;++j)
    {
        l[j]=j;/*扩展的过程：先初始化是自己*/
        while(l[j]>1&&h[j]<=h[l[j]-1])/*如果这一列可以扩展的左边界不到边界，并且还可以扩展，就扩展，这种定义左边界扩展的方式可以减少循环次数*/
        l[j]=l[l[j]-1];
    }
    for(int j=n;j>=1;--j)
    {
        r[j]=j;
        while(r[j]<n&&h[j]<=h[r[j]+1])
        r[j]=r[r[j]+1];
        ans=max(ans,(r[j]-l[j]+1)*h[j]);
    }
    cout<<ans<<endl;
    return 0;
}

View Code

F:有花费的商务活动

总时间限制:: 1000ms
内存限制:: 65536kB

描述

一个商务人员要参加一个非常重要的商务活动，途中需要穿过一个 N*N 的正方形的网格。从正方形的一个角进入，相对着的另一个角出去（假定从左上角进，右下角出，N 不大于50 ）。每穿越中间1个小方格，都需要缴纳一定的过路费，同时参加这一活动也需要购买入场票。但这个人所带的费用有限。请根据这个人所带的费用，入场费以及穿越网格的费用，帮忙判断这个人能否参加这场商务活动。若能够，则输出YES，否则，输出NO

注意：不能对角穿越各个小方格（即，只能行号或列号之一增减1）。

输入

输入格式如下：
第1行：要穿越的方阵大小N，所带的总费用，入场费用，三者之间以空格间隔
后面 N 行 N 列，穿越各个小方格所需的费用。

例如

如：
5 129 20
1 4 6 8 10
2 5 7 15 17
6 8 9 18 20
10 11 12 19 21
20 23 25 29 33

输出

如果可以正常参加，则输出
YES

如果不能正常参加，则输出
NO

如，上述例子中：
穿越方阵的最小值为 109 = 1 + 2 + 5 + 7 + 9 + 12 + 19 + 21 + 33
同时，入场费为 20，而 20+109 =129 不高于所带的总费用 129，因此，可以参加。
应该输出：

YES

但是，如果所带费用少于129，或者入场费超过20，则无法参加。

样例输入

5 129 20
1  4  6  8  10 
2  5  7  15 17 
6  8  9  18 20 
10 11 12 19 21 
20 23 25 29 33

样例输出

YES

这个题目必须必须用最小费用最大流来能解决

其实这道题目的原题是这个样子的：

/*

7614:最低通行费

总时间限制:: 1000ms
内存限制:: 65536kB

描述

一个商人穿过一个 N*N 的正方形的网格，去参加一个非常重要的商务活动。他要从网格的左上角进，右下角出。每穿越中间1个小方格，都要花费1个单位时间。商人必须在(2N-1)个单位时间穿越出去。而在经过中间的每个小方格时，都需要缴纳一定的费用。

这个商人期望在规定时间内用最少费用穿越出去。请问至少需要多少费用？

注意：不能对角穿越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）。

输入

第一行是一个整数，表示正方形的宽度N (1 <= N < 100)；
后面 N 行，每行 N 个不大于 100 的整数，为网格上每个小方格的费用。

输出

至少需要的费用。

样例输入

5
1 4 6 8 10 
2 5 7 15 17 
6 8 9 18 20 
10 11 12 19 21 
20 23 25 29 33

样例输出

提示

样例中，最小值为109=1+2+5+7+9+12+19+21+33。

因为题目中规定了时间小于2*n-1，那么只能向右走或者向下走，向左或者向上走一步都是到不了的，所以这个题目用递推方程就可以解决了

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <memory.h>
#include <math.h>
using namespace std;
int i,j,n;
int f[1005][1005],a[1005][1005];
int main(){
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            scanf("%d",&a[i][j]);
    for(i=1;i<=n;i++){
        f[i][1]=a[i][1]+f[i-1][1];
        f[1][i]=a[1][i]+f[1][i-1];
    }
    for(i=2;i<=n;i++)
        for(j=2;j<=n;j++)
            f[i][j]=min(f[i-1][j],f[i][j-1])+a[i][j];
    printf("%d
",f[n][n]);
    return 0;
}

View Code

*/