22年贵工程程序设计团体赛

文章目录

• 7-1 成绩等级
• 7-2 h0001.Hello World! (5 分)
• 7-3 h0055. 长方体
• 7-4 Jack cheng的烦恼
• 7-5 毕业照
• 7-6 h0045. 限速
• 7-7 弄丢的直角三角形（题目存在一些问题）
• 7-8 自守数
• 7-9 h0039. 平方数
• 7-10 h0040. 丑数
• 7-11 阶乘末尾0的个数
• 7-12 2017Final 圆周率山
• 7-13 h0057. 平衡
• 7-14 机工士姆斯塔迪奥
• 7-15 扫描与筛选
• 7-16 插松枝

7-1 成绩等级

PAT考试每年举办三次，分为Top、Advanced和Basic三个级别。小明的公司正在招聘程序员，主要关注Basic这个等级成绩。很多应聘者提供了他们的Basic级别的PAT考试分数。
对2016年三次PAT考试的分数做了一番研究之后，小明的公司给出了一个规则把应聘者划分为A、B 2个等级：如果分数小于底线L，则为B级，否则就是A级。
请编写程序帮忙计算应聘者的等级。

输入格式:
在一行中给出2个整数L和G。0

输出格式:
在一行中输出应聘者的等级。

输入样例:

75 89

输出样例:

A

#include 

using namespace std;

int main()
{
    int a,b;
    cin >> a >> b;
    if(b < a) cout << "B";
    else cout << "A";
    
    return 0;
}

7-2 h0001.Hello World! (5 分)

本题要求编写程序，输出一个短句“Hello World!”。

输入格式:
本题目没有输入。

输出格式:
在一行中输出短句“Hello World!”。

输入样例:

无

输出样例:

Hello World!

#include 

using namespace std;

int main()
{
    cout << "Hello World!";
    return 0;
}

7-3 h0055. 长方体

给出共享长方体一个顶点的三个面的面积，求它十二条边的边长和。

输入格式:
每行三个整数a, b, c表示面积（1 <= a, b, c <= 10000)。

输出格式:
相应行一个整数表示边长和。

输入样例:

1 1 1
4 6 6

输出样例:

12
28

#include 

using namespace std;

int main()
{
    double a, b, c;
    while(cin >> a >> b >> c)
    {
        double x = sqrt(a * b / c);
        double y = sqrt(a * c / b);
        double z = sqrt(b * c / a);
        printf("%.0fn",4 * (x + y + z));
    }
    return 0;
}

7-4 Jack cheng的烦恼

Jack cheng 一出生就表现出非同一般的天赋 ， 异常的聪明，对于老师教授的知识他总是一点就会， 其中Jack cheng尤其擅长数学，喜欢计算机。课下之余他自己学习了一些编程知识，然而遗憾的是他并不能看懂Code。现在他遇到了一个问题，他想要编程一个进制转换的计算器，他需要我们这些专业人士帮忙。。。

简单点， 我们要帮Jackcheng 实现一个十进制和二进制互转的计算器。

输入格式:
输入n , m 。 n 代表要进行转换的数字(n>=0 && n <= 1000000) , m 代表需要转换成的进制。

输出格式:
将转换后的数据输出。

输入样例:

8 2

输出样例:

1000

#include 

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    if(m == 2) //  10转2
    {
        string s;
        while(n)
        {
            s += n % m + '0';
            n /= m;
        }
        for(int i = s.size() - 1; i >= 0; i -- )
            cout << s[i];
    }
    else //  2转10
    {
        int sum = 0, k = 0;
        while(n)
        {
            sum += n % 10 * pow(2, k);
            k ++ ;
            n /= 10;
        }
        cout << sum;
    }
    return 0;
}

7-5 毕业照

你拍了一张毕业生的毕业照。这幅图可以看作是n乘以n×n的矩阵a, a中的每个元素都是0或1，分别代表一个空白的背景或一个学生。

但是老师们太忙了，没有时间和学生们合影，只能自己拍了一张合影。这张照片可以看作矩阵B，其中每个元素为2，代表一个老师。

作为一名photoshop大师，你的工作是将照片B放入照片a中，并遵循以下约束条件:

不允许分割、旋转或缩放图片，只能进行平移。

矩阵B中的每个元素应该与A中的一个元素完全重叠，每个老师应该与空白背景重叠，而不是躲避学生。

请计算一下你可以将照片B放入照片A的可能方法。

输入描述:

第一行包含两个整数n,m表示照片A和B的大小。

在接下来的n行中，每一行包含n个’0’或’1’字符，代表矩阵A。

最后一行包含m个字符’2’，代表矩阵B。

输出描述:

在一行中输出一个整数，表示答案。

输入样例:
在这里给出一组输入。例如：

5 3
00000
01110
01110
01110
00000
222

输出样例:
在这里给出相应的输出。例如：

6

#include 

using namespace std;

const int N = 1010;

int main()
{
    int n,m;
    string f[N],s;
    cin >> n >> m;
    
    for(int i=0;i> f[i];
    for(int i=0;i> s;
    for(int i=0;i
        for(int j=0;j<=n-s.size();j++)
        {
            string ss = f[i].substr(j,s.size());
            if(ss == s) cnt ++;
        }
    }
    cout << cnt;
    
    return 0;
}

7-6 h0045. 限速

B和T踏上行程，但他们汽车的里程表坏了，因此他们不知道他们驾车走了多少英里。幸运的是，B有一个正在运行的跑表，可以记录他们的速度和驾驶了多少时间。然而，这个跑表的记录方式有些古怪，他们需要计算总的驾驶距离。请您编写一个程序完成这项计算。

输入格式:
输入由一个或多个测试用例组成。每个测试用例开始的第一行为一个整数n，1≤n≤10；后面是n对值，每对一行。每对的第一个值s是时速，第二个值t是总的耗费时间。s和t都是整数，1 ≤s≤90并且1≤t≤12。t的值总是增序。n的值取-1表示输入结束。

输出格式:
对于每一个测试用例，输出行驶距离，然后空格，输出单词"miles"。

输入样例:

3
20 2
30 6
10 7
2
60 1
30 5
4
15 1
25 2
30 3
10 5
−1

输出样例:

170 miles
180 miles
90 miles

#include 

using namespace std;

int main()
{
    int n;
    while(cin >> n && n != -1)
    {
        int sum = 0;
        int res, t = 0, s; // res表示中间值
        for(int i=0;i
            res = t;
            cin >> s >> t;
            sum += s * (t - res);
        }
        printf("%d milesn",sum);
    }
    return 0;
}

7-7 弄丢的直角三角形（题目存在一些问题） 7-8 自守数

数学的世界有很多很漂亮的数字或者数字集合，比如梅森数，哥德巴赫猜想，水仙花数，完全数，自守数。今天我们就一起来探究一下自守数。自守数是指一个数的平方的尾数等于该数自身的自然数。例如：25^2 = 625，76^2 = 5776，9376^2 = 87909376。请求出n以内的自守数的个数

输入格式:
第一行输入n,随后输入n个数m。

输出格式:
在一行中输出m以内自守数的个数，所有输出在一行内完成，末尾没有多余空格。

输入样例:

5
1
2
3
4
5

输出样例:

2 2 2 2 3

#include 

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

int f[N];

int main()
{
    f[0] = 1, f[1] = 2;
    for (int i = 2; i <= N; i ++ )
    {
        int x = i,cnt = 1;
        LL y = i * i;
        while (x)
        {
            if (y % 10 != x % 10)
            {
                cnt = 0;
                break;
            }
            x /= 10, y /= 10;
        }
        f[i] = f[i - 1] + cnt;
    }
    int n, x;
    cin >> n;
    for (int i = 0; i < n; i ++ )
    {
        if(i) cout << ' ';
        cin >> x;
        cout << f[x];
    }
    return 0;
}

7-9 h0039. 平方数

平方数是一个整数，它的平方根也是一个整数。例如1、4、81是
一些平方数。给定两个数字a和b，请你在a和b之间(包括a和b)找出有多少平方数?

输入格式:
输入文件最多包含201行输入。每一行包含两个整数a和b (0 b≤100000)。输入以包含两个零的行结束。这一行不用处理。

输出格式:
每一行输入产生一行输出。这一行包含一个表示在a和b之间有多少个平方数(包括a和b)。

输入样例:

1 4
1 10
0 0

输出样例:

2
3

方法一： 前缀和

#include
using namespace std;
const int N = 100100;
int check(int x)
{
    int r = pow(x,0.5);
    return r*r == x;
}
int a[N], l, r;
int main()
{
    for(int i=1; i<=100000; i++)
        if(check( i ))
            a[i] ++;
    for(int i=1; i<=100000; i++) a[i]+=a[i-1];
    while(cin>>l>>r && l!=0&&r!=0)
        cout< 
方法二： 朴素做法
 
#include 

using namespace std;

int main()
{
    int a,b;
    while(cin >> a >> b && a || b)
    {
        int cnt = 0;
        for(int i=a;i<=b;i++)
        {
            double x = sqrt(i);
            int y = (int)x * x;
            if(i == y) cnt ++;
        }
        cout << cnt << endl;
    }
    return 0;
}
 
7-10 h0040. 丑数 
丑陋数是指那些质因数只有2、3或5的数。序列
 1、2、3、4、5、6、8、9、10、12、15、……
 显示前11个丑陋的数字。按照惯例，包含1。
 输入的每一行给出一个正整数n(1≤n≤1500), 编写程序求第 n 个丑数的值。
 
输入格式:
 输入的每一行给出一个正整数n(1≤n≤1500), 以n=0为结束标志。
 
输出格式:
 对每一组输入，在一行中输出第 n 个丑数的值。
 
输入样例:
 
1
2
5
0
 
输出样例:
 
1
2
5
 
#include
using namespace std;
bool check( int x ) 
{
    while(x%2 == 0) x/=2; 
    while(x%3 == 0) x/=3; 
    while(x%5 == 0) x/=5; 
    return x == 1; 
}
vector res;
void find(int x) 
{
    int a2=0, a3=0, a5=0, r;
    while(res[a2]*2 <= x) a2++; 
    while(res[a3]*3 <= x) a3++; 
    while(res[a5]*5 <= x) a5++; 
    r = res[a2]*2
    for(int i=1; res.size()<=500; i++) 
        if( check( i ) ) 
            res.push_back(i);
    while(res.size() <= 1500) find( res.back() ); 
    while( cin>>n && n!=0)
        cout << res[n-1] << endl;
    return 0;
}

 
7-11 阶乘末尾0的个数 
从输入中读取一个数n，求出n！中末尾0的个数。
 
输入格式:
 输入有若干行。第一行上有一个整数m，指明接下来的数字的个数。然后是m行，每一行包含一个确定的正整数n，1<=n<=1000000000。
 
输出格式:
 对输入行中的每一个数据n，输出一行，其内容是n！中末尾0的个数。
 
输入样例:
 
3
3
100
1024
 
输出样例:
 
0
24
253
 
#include
using namespace std;
int T, n;
int main()
{
    cin >> T;
    while( T-- ) {
        int res=0;
        cin >> n;
        while(n/5){
            res+=n/5;
            n/=5;
        }
        cout << res << endl;
    }
    return 0;
}
 
7-12 2017Final 圆周率山 
为了参加学校的社团风采展，怡山小学数学组的同学们决定画一座圆周率山，以宣传圆周率。
 
已知圆周率为：3.
 
1415926535 8979323846 2643383279 5028841971 6939937510
 
5820974944 5923078164 0628620899 8628034825 3421170679
 
8214808651 3282306647 0938446095 5058223172 5359408128
 
4811174502 8410270193 8521105559 6446229489 5493038196
 
输入格式:
 输入山的高度，为一个不超过10的正整数。
 
输出格式:
 以上尖下宽，左右对称的三角形形式，给出圆周率的前若干位（不含小数点）。注意：每行均以数字结尾，即数字右边无空格。
 
输入样例1:
 
1
 
输出样例1:
 
3
 
输入样例2:
 
4
 
输出样例2:
 
   3
  141
 59265
3589793
 
#include

using namespace  std;

string s = {"314159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196"};

int n, k; 

int main()
{
    cin >> n;
    int l = (2 * n - 1) / 2; 
    for(int i = 1; i <= n; i ++ ) {
        for(int j = 1; j <= l + 1 - i; j ++ ) cout << " "; 
        for(int j = 1; j <= 2 * i - 1; j ++ ,k ++ ) cout << s[k]; 
        cout << endl; 
    }
    return 0;
}
 
7-13 h0057. 平衡 
Iyo Kiffa Australis 女士有一个天平，但只有两种砝码可以用来称量一剂药物。例如，用 300 毫克和 700 毫克的砝码来测量 200 毫克阿司匹林，她就要将 1 个 700 毫克的砝码和药物放在天平的一边，并将 3 个 300 毫克的砝码放在天平的另一边，如图 1 所示。虽然她也可以将 4 个 300 毫克的砝码放和药物放在天平的一边，两个 700 毫克的砝码放在天平的另一边，如图 2 所示，但她不会选择这个方案，因为使用更多的砝码不太方便。
 
 
请您帮助 Iyo Kiffa Australis 女士，帮她计算要用多少的砝码
 
输入格式:
 输入是一系列的测试用例。每个测试用例一行，给出 3 个用空格分隔的正整数 a, b 和 d ，并满足以下关系： a<=b ， a<=10000 ，b<=10000 ，而且 d<=50000 。本题设定，您可以使用 a 毫克和 b 毫克的砝码组合来称量 d 毫克；也就是说，您不需要考虑 “ 无解 ” 的情况。
 
输入结束由一行表示，该行给出 3 个由空格分隔的零。这一行不是测试用例。
 
输出格式:
 输出由一系列的行组成，每行对应一个测试用例 (a, b, d) 。一个输出行给出两个由空格分隔的非负整数 x 和 y ，且 x 和 y 要满足以下三个条件：
 
• 使用 x 个 a 毫克的砝码和 y 个 b 毫克的砝码可以称量 d 毫克。
 
• 在满足上述条件的非负整数对中，砝码总数 (x + y) 最小。
 
• 在满足前两个条件的非负整数对中，砝码的总的质量 (ax + by) 最小。
 
• 输出中不能出现额外的字符（例如，额外的空格）。
 
输入样例:
 
700 300 200
500 200 300
500 200 500
275 110 330
275 110 385
648 375 4002
3 1 10000
0 0 0
 
输出样例:
 
1 3
1 1
1 0
0 3
1 1
49 74
3333 1
 
#include 

using namespace std;

typedef long long LL;

LL a,b,d,x,y;

LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(b==0)
    {
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a%b, y, x);
    y -= a / b * x;
    return d;
}
int main()
{
    while (cin >> a >> b >> d && a || b || b)
    {
        LL gcd = exgcd(a,b,x,y);
        LL dx = b / gcd; //  当特解x>0时
        LL x1 = (x * d / gcd % dx + dx) % dx; // 将x降至最小且大于0
        LL y1 = abs(d - a * x1) / b;
        LL dy = a / gcd; //  当特解y>0时
        LL y2 = (y * d / gcd % dy + dy) % dy; //  将y降至最小且大于0
        LL x2=abs(d-b*y2)/a;
         //  只有这两种情况 |x|+|y| 是最小的，若相等再判断下乘积即可
        if(x1 + y1 > x2 + y2 ||
           (x1 + y1 == x2 + y2 &&
            a * x1 + b * y1 > a * x2 + b * y2))
        {      
            x1 = x2;
            y1 = y2;
        }
        cout << x1 << " " << y1 << endl;
    }
    return 0;
}
 
7-14 机工士姆斯塔迪奥 
在 MMORPG《最终幻想14》的副本“乐欲之所瓯博讷修道院”里，BOSS 机工士姆斯塔迪奥将会接受玩家的挑战。
 
你需要处理这个副本其中的一个机制：N×M 大小的地图被拆分为了 N×M 个 1×1 的格子，BOSS 会选择若干行或/及若干列释放技能，玩家不能站在释放技能的方格上，否则就会被击中而失败。
 
给定 BOSS 所有释放技能的行或列信息，请你计算出最后有多少个格子是安全的。
 
输入格式:
 输入第一行是三个整数 N,M,Q (1≤N×M≤105，0≤Q≤1000)，表示地图为 N 行 M 列大小以及选择的行/列数量。
 接下来 Q 行，每行两个数 Ti ,C i ，其中 Ti =0 表示 BOSS 选择的是一整行，Ti=1 表示选择的是一整列，Ci为选择的行号/列号。行和列的编号均从 1 开始。
 
输出格式:
 输出一个数，表示安全格子的数量。
 
输入样例:
 
5 5 3
0 2
0 4
1 3
 
输出样例:
 
12
 
#include 

using namespace std;

const int N = 1e5 + 10;

int f1[N],f2[N];

int main()
{
    int n,m,q;
    cin >> n >> m >> q;
    while(q -- )
    {
        int a,b;
        cin >> a >> b;
        if(a == 0) f1[b] = 1;
        else f2[b] = 1;
    }
    int res = 0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(!f1[i] && !f2[j]) res ++ ;
        }
    }
    cout << res;
    
    return 0;
}
 
7-15 扫描与筛选 
本题目要求编写程序，给出多个非空字符串，再给出一篇文章，统计每个字符串在文章中出现的次数（字母不分大小写）。然后按照字符串的出现次数降序输出，若字符串的出现次数相等，则按照字符串的字典序升序输出。所谓的“字符串”是指连续不含空格的非空字符串。
 
输入格式:
 第一行首先输入一个N(≤10⁴),即字符串的数量，紧接着输入N个字符串，随后每一行输入一串字符。当读到某一行只有一个英文句子.时，输入结束，此行不算在文章内。
 
输出格式:
 如果在文章当中没有出现任何一个给出的字符串输出“No string ever appeared”，否则每一行输出给出的字符串以及它出现的次数。
 
输入样例:
 在这里给出一组输入。例如：
 
4 A for like look
Can I buy you a drink?
Actually I’d rather have the money.
I’m a photographer. I’ve been look for a face like yours.
I’m a plastic surgeon. I’ve been looking for a face like yours.
 
.
 输出样例:
 在这里给出相应的输出。例如：
 
A 5
for 2
like 2
look 1
 
#include
using namespace std;
typedef pair PII;
bool cmp(PII x, PII y)
{
	if(x.second!=y.second) return x.second > y.second;
	else return x.first < y.first;
}
string zhuang( string s )
{
	for(int i=0; s[i]; i++)
		if(s[i]>='A' && s[i]<='Z')
			s[i] = s[i]-'A'+'a';
	return s;
}
map< string, string> id; 
map< string, int> q;
vector< PII > w;
string s;
int N, F;
int main()
{
	cin >> N;
	while( N-- ) {
		cin >> s;
		q[s] = 0;
		id[zhuang(s)] = s;
	}
	getchar();
	while(getline(cin,s) && s!=".") {
		s = zhuang( s );
		int l = s.size();
		for(int i=0; i
			while(i
				string r = s.substr( i, j-i);
				if(id.find(r)!=id.end()) q[id[r]] ++, F = 1;
			}
			i = j;
		}
	}
	for(auto i=q.begin(); i!=q.end(); i++)
		w.push_back({i->first,i->second});
	sort( w.begin(), w.end(), cmp);
	for(int i=0; i 
7-16 插松枝 
 
人造松枝加工场的工人需要将各种尺寸的塑料松针插到松枝干上，做成大大小小的松枝。他们的工作流程（并不）是这样的：
 
每人手边有一只小盒子，初始状态为空。
 每人面前有用不完的松枝干和一个推送器，每次推送一片随机型号的松针片。
 工人首先捡起一根空的松枝干，从小盒子里摸出最上面的一片松针 —— 如果小盒子是空的，就从推送器上取一片松针。将这片松针插到枝干的最下面。
 工人在插后面的松针时，需要保证，每一步插到一根非空松枝干上的松针片，不能比前一步插上的松针片大。如果小盒子中最上面的松针满足要求，就取之插好；否则去推送器上取一片。如果推送器上拿到的仍然不满足要求，就把拿到的这片堆放到小盒子里，继续去推送器上取下一片。注意这里假设小盒子里的松针片是按放入的顺序堆叠起来的，工人每次只能取出最上面（即最后放入）的一片。
 当下列三种情况之一发生时，工人会结束手里的松枝制作，开始做下一个：
 （1）小盒子已经满了，但推送器上取到的松针仍然不满足要求。此时将手中的松枝放到成品篮里，推送器上取到的松针压回推送器，开始下一根松枝的制作。
 
（2）小盒子中最上面的松针不满足要求，但推送器上已经没有松针了。此时将手中的松枝放到成品篮里，开始下一根松枝的制作。
 
（3）手中的松枝干上已经插满了松针，将之放到成品篮里，开始下一根松枝的制作。
 
现在给定推送器上顺序传过来的 N 片松针的大小，以及小盒子和松枝的容量，请你编写程序自动列出每根成品松枝的信息。
 
输入格式：
 输入在第一行中给出 3 个正整数：N（≤103 ），为推送器上松针片的数量；M（≤20）为小盒子能存放的松针片的最大数量；K（≤5）为一根松枝干上能插的松针片的最大数量。
 
随后一行给出 N 个不超过 100 的正整数，为推送器上顺序推出的松针片的大小。
 
输出格式：
 每支松枝成品的信息占一行，顺序给出自底向上每片松针的大小。数字间以 1 个空格分隔，行首尾不得有多余空格。
 
输入样例：
 
8 3 4
20 25 15 18 20 18 8 5
 
输出样例：
 
20 15
20 18 18 8
25 5
 
#include 

using namespace std;

stackS;
queueQ;
int n, m, k;
int cnt, res, t;

void init() // 初始化
{
    cnt = 0;
    res = 1010;
}

int main()
{
    cin >> n >> m >> k;
    init();
    while(n -- )
    {
        int x;
        cin >> x;
        Q.push(x);
    }
    while(Q.size() || S.size())
    {
        while(S.size() && cnt < k && S.top() <= res) // 栈不为空
        {
            res = S.top();
            S.pop();
            if(cnt ++ ) cout << ' ';
            cout << res;
        }
        if(Q.size() && cnt < k) //  不超过最大数量
        {
            if(Q.front() <= res) //  可以插入松针片
            {
                res = Q.front();
                Q.pop();
                if(cnt ++ ) cout << ' ';
                cout << res;
            }
            else
            {
                if(S.size() == m) init(); //  栈满，初始化
                else //  放入推送器
                {
                    S.push(Q.front());
                    Q.pop();
                }
            }
        }
        else init();
        if(cnt == k) init(); //  不能再插入了，初始化
        if(cnt == 0) cout << endl; 
    }
    return 0;
}