参考书

《算法笔记》----胡凡，曾磊

B1001 害死人不偿命的(3n+1)猜想 (15分)

卡拉兹(Callatz)猜想：

对任何一个正整数 n，如果它是偶数，那么把它砍掉一半；如果它是奇数，那么把 (3n+1) 砍掉一半。这样一直反复砍下去，最后一定在某一步得到 n=1。卡拉兹在 1950 年的世界数学家大会上公布了这个猜想，传说当时耶鲁大学师生齐动员，拼命想证明这个貌似很傻很天真的命题，结果闹得学生们无心学业，一心只证 (3n+1)，以至于有人说这是一个阴谋，卡拉兹是在蓄意延缓美国数学界教学与科研的进展……

我们今天的题目不是证明卡拉兹猜想，而是对给定的任一不超过 1000 的正整数 n，简单地数一下，需要多少步（砍几下）才能得到 n=1？
输入格式：

每个测试输入包含 1 个测试用例，即给出正整数 n 的值。
输出格式：

输出从 n 计算到 1 需要的步数。
输入样例：
3
输出样例：
5
实现代码：

#include <iostream>
using namespace std;
int main()
{
    int i=0, set;
    cin >> i;
    for (set = 0;i != 1;set++)
    {
        if (i % 2 == 0)
        {
            i = i / 2;
        }
        else
        {
            i = (3 * i + 1) / 2;
        }
    }
    cout << set;
    system("pause");
    return 0;
}

B1002 写出这个数 (20分)

读入一个正整数 n，计算其各位数字之和，用汉语拼音写出和的每一位数字。

输入格式：
每个测试输入包含 1 个测试用例，即给出自然数 n 的值。这里保证 n 小于 10的100次方
输出格式：
在一行内输出 n 的各位数字之和的每一位，拼音数字间有 1 空格，但一行中最后一个拼音数字后没有空格。

输入样例：
1234567890987654321123456789
输出样例：
yi san wu
实现代码：

#include <iostream>
#include<string>
using namespace std;
int main()
{
    int sum = 0, sum_seperate[10], sum_num = 0;
    char  temp;
    //字符串string类型的使用和头文件
    string s_output[10] = { "ling","yi","er","san","si","wu","liu","qi","ba","jiu" };
    //检测回车键；char字符转化为int数值
    while ((temp = cin.get()) != '\n')
        sum += (temp - '0');
    //do...while语句格式
    while (sum)
    {
        sum_seperate[sum_num++] = sum % 10;
        sum /= 10;
    }

    while (1)
    {
        --sum_num;
        cout << s_output[sum_seperate[sum_num]];
        if (!sum_num)
            break;
        cout << ' ';
    }
    system("pause");
    return 0;
}

B1003 我要通过！ (20分)

“答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于 PAT 的“答案正确”大派送 —— 只要读入的字符串满足下列条件，系统就输出“答案正确”，否则输出“答案错误”。

得到“答案正确”的条件是：

字符串中必须仅有 P、 A、 T这三种字符，不可以包含其它字符；
任意形如 xPATx 的字符串都可以获得“答案正确”，其中 x 或者是空字符串，或者是仅由字母 A 组成的字符串；
如果 aPbTc 是正确的，那么 aPbATca 也是正确的，其中 a、 b、 c 均或者是空字符串，或者是仅由字母 A 组成的字符串。
现在就请你为 PAT 写一个自动裁判程序，判定哪些字符串是可以获得“答案正确”的。

输入格式：
每个测试输入包含 1 个测试用例。第 1 行给出一个正整数 n (<10)，是需要检测的字符串个数。接下来每个字符串占一行，字符串长度不超过 100，且不包含空格。

输出格式：
每个字符串的检测结果占一行，如果该字符串可以获得“答案正确”，则输出 YES，否则输出 NO。

输入样例：
8
PAT
PAAT
AAPATAA
AAPAATAAAA
xPATx
PT
Whatever
APAAATAA
输出样例：
YES
YES
YES
YES
NO
NO
NO
NO
思路分析：
aPbTc 中a b c 段都只能包含“A"，其长度分别为len(a)、len(b)、len(c)，则其关系要求满足len(a)*len(b) = len(c)！
代码实现：

#include <iostream>
#include<string.h>
using namespace std;
int main()
{
	string s;
	int n, a, b, c, p, t, size;
	cin >> n;
	bool flag = true;
	while (n--)
	{
		flag = true;
		cin >> s;
		a = b = c = p = t = 0;
		size = s.size();
		if (size < 3)//长度小于3直接输出错误
		{
			flag = false;
			cout << "NO" << endl;
			continue;
		}
		for (int i = 0;i < size;i++)
		{
			if (s[i] == 'A')
			{
				if (p == 0) a++;//P前A的数量
				else if (p != 0 && t == 0) b++;//P与T中A的数量
				else if (p != 0 && t != 0) c++;//T后面的A的数量
			}
			else if (s[i] == 'P')
			{
				p++;
				if (p > 1)//有两个P，输出错误
				{
					flag = false;
					break;
				}
			}
			else if (s[i] == 'T')//有两个T，输出错误
			{
				t++;
				if (t > 1)
				{
					flag = false;
					break;
				}
			}
			else//有其他字符，输出错误
			{
				flag = false;
			}				
		}
		if (a * b != c || b == 0 || p == 0 || t == 0)
			//a * b != c输出错误
			//P与T间没有A，输出错误
			//没有P，输出错误
			//没有T，输出错误
		{
			flag = false;
		}
		if (flag)
		{
			cout << "YES" << endl;
		}
		else
		{
			cout << "NO" << endl;
		}

	}
	system("pause");
	return 0;
}

B1009 说反话 (20分)

给定一句英语，要求你编写程序，将句中所有单词的顺序颠倒输出。

输入格式：
测试输入包含一个测试用例，在一行内给出总长度不超过 80 的字符串。字符串由若干单词和若干空格组成，其中单词是由英文字母（大小写有区分）组成的字符串，单词之间用 1 个空格分开，输入保证句子末尾没有多余的空格。

输出格式：
每个测试用例的输出占一行，输出倒序后的句子。

输入样例：
Hello World Here I Come
输出样例：
Come I Here World Hello
实验代码：

#include <iostream>
#include <string.h>
using namespace std;
int main()
{
	char str[90];
	cin.getline(str,90);
	int len = strlen(str);
	int r = 0, h = 0;//r为行，h为列
	char ans[90][90];//ans[0]~ans[r]存放单词
	for (int i = 0;i < len;i++)
	{
		if (str[i] != ' ')//如果不是空格，则存放至ans[r][h],h++
		{
			ans[r][h++] = str[i];
		}
		else//如果是空格表示一个单词结束，行r增加1，列h恢复至0
		{
			r++;
			h = 0;
		}
	}
	for (int i = r;i >= 0;i--)
	{
		cout << ans[i];
		if (i > 0) cout << " ";
	}
	return 0;
}

笔记：

一。

C++中cin,cin.get()和cin.getline()的区别
cin：遇到空格，回车或者制表符就会结束输入，这样就导致了我们不能输入一个带有空格的字符串。
cin.get(),cin.getline() ：但是，很好，C++的这两个函数帮我们解决了这一问题，它们都表示每次读取一行字符串输入。
不过，这两个函数也有一些区别：
cin.getline()和cin.get()。这两个函数都读取一行输入，直到达到换行符。然而，随后cin.getline()将丢弃换行符，而cin.get()将换行符保留在输入序列中。

二。

使用strlen()，需要增加头文件#include<string.h>
还有：
strcmp(字符数组1，字符数组2)，返回两个字符串大小的比较结果
strcpy(字符数组1，字符数组2)，把字符串2复制给字符串1
strcat(字符数组1，字符数组2)，把一个字符串接到另一个字符串后面

三。

cin.getline()的使用方法：cin.getline(参数一，参数二)
第一个参数是用来储存输入行的数组名称，第二个参数是要读取的字符数

B1013 数素数 (20分)

令 P
​i
​​ 表示第 i 个素数。现任给两个正整数 M≤N≤10
​4
​​ ，请输出 P
​M
​​ 到 P
​N
​​ 的所有素数。

输入格式：
输入在一行中给出 M 和 N，其间以空格分隔。

输出格式：
输出从 P
​M
​​ 到 P
​N
​​ 的所有素数，每 10 个数字占 1 行，其间以空格分隔，但行末不得有多余空格。

输入样例：
5 27
输出样例：
11 13 17 19 23 29 31 37 41 43
47 53 59 61 67 71 73 79 83 89
97 101 103
代码实现：

#include <iostream>
using namespace std;
const int maxn = 10000001;
int prime[maxn], num = 0;//prime数组存放所有素数，num为素数的个数
bool p[maxn] = { 0 };//如果i为素数，则p[i]为false，否则为ture
void Find_Prime(int n)
{
	for (int i = 2;i < maxn;i++)
	{
		if (p[i] == false)//如果i是素数
		{
			prime[num++] = i;//把素数i存到prime数组中
			if (num >= n) break;//只需要n个
			for (int j = i + i;j < maxn;j += i)//筛去所有i的倍数
			{
				p[j] = true;
			}
		}
	}
}
int main()
{

	int m, n, count = 0;
	cin >> m >> n;
	Find_Prime(n);
	for (int i = m;i <= n;i++)//输出第m个至第n个素数
	{
		cout << prime[i - 1];
		count++;
		if (count % 10 != 0 && i < n)
		{
			cout << " ";
		}
		else
		{
			cout << endl;
		}
	}
	system("pause");
	return 0;
}

笔记

用筛法计算100以内所有的素数

#include <iostream>
using namespace std;
const int maxn = 101;//求解100以内全部的素数
int prime[maxn], pNum = 0;//prime数组存放所有素数，pNum为素数的个数
bool p[maxn] = { 0 };//如果i为素数，则p[i]为false，否则为ture
void Find_Prime()
{
	for (int i = 2;i < maxn;i++)
	{
		if (p[i] == false)//如果i是素数
		{
			prime[pNum++] = i;//把素数i存到prime数组中

			for (int j = i + i;j < maxn;j += i)//筛去所有i的倍数
			{
				p[j] = true;
			}
		}
	}
}
int main()
{
	Find_Prime();
	for (int i = 0;i < pNum;i++)
	{
		cout << prime[i]<<endl;
	}
	cout << endl;
	system("pause");
	return 0;
}

B1019 数字黑洞 (20分)

给定任一个各位数字不完全相同的 4 位正整数，如果我们先把 4 个数字按非递增排序，再按非递减排序，然后用第 1 个数字减第 2 个数字，将得到一个新的数字。一直重复这样做，我们很快会停在有“数字黑洞”之称的 6174，这个神奇的数字也叫 Kaprekar 常数。

例如，我们从6767开始，将得到

7766 - 6677 = 1089
9810 - 0189 = 9621
9621 - 1269 = 8352
8532 - 2358 = 6174
7641 - 1467 = 6174
... ...
现给定任意 4 位正整数，请编写程序演示到达黑洞的过程。

输入格式：
输入给出一个 (0,10000) 区间内的正整数 N。

输出格式：
如果 N 的 4 位数字全相等，则在一行内输出 N - N = 0000；否则将计算的每一步在一行内输出，直到 6174 作为差出现，输出格式见样例。注意每个数字按 4 位数格式输出。

输入样例 1：
6767
输出样例 1：
7766 - 6677 = 1089
9810 - 0189 = 9621
9621 - 1269 = 8352
8532 - 2358 = 6174
输入样例 2：
2222
输出样例 2：
2222 - 2222 = 0000
代码实现：

#include <iostream>
#include<algorithm>
#include<iomanip>
using namespace std;
bool cmp(int a, int b)//递减排序
{
	return a > b;
}
void to_array(int n, int num[])//将n的每一位存到num数组中
{
	for (int i = 0;i < 4;i++)
	{
		num[i] = n % 10;
		n /= 10;
	}
}
int to_number(int num[])//将num数组转换成数字
{
	int sum = 0;
	for (int i = 0;i < 4;i++)
	{
		sum = sum * 10 + num[i];
	}
	return sum;
}
int main()
{
	int n;
	int MAX;//递增排序后的最大值
	int MIN;//递减排序后的最小值
	cin >> n;
	int num[5];
	while (1)
	{
		to_array(n, num);
		sort(num, num + 4);
		MIN = to_number(num);
		sort(num, num + 4, cmp);
		MAX = to_number(num);
		n = MAX - MIN;
		cout << MAX << " - " << setw(4) << setfill('0') << MIN << " = " << setw(4) << setfill('0') << n << endl;
		//printf("%04d - %04d = %04d\n",MAX,MIN,n);
		if (n == 0 || n == 6174) break;
	}

	return 0;
}

笔记：

输出控制：<< setw(4) << setfill('0')
是结果为4位数，不足4位前面补0

B1020 月饼 (25分)

月饼是中国人在中秋佳节时吃的一种传统食品，不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量，请你计算可以获得的最大收益是多少。

注意：销售时允许取出一部分库存。样例给出的情形是这样的：假如我们有 3 种月饼，其库存量分别为 18、15、10 万吨，总售价分别为 75、72、45 亿元。如果市场的最大需求量只有 20 万吨，那么我们最大收益策略应该是卖出全部 15 万吨第 2 种月饼、以及 5 万吨第 3 种月饼，获得 72 + 45/2 = 94.5（亿元）。

输入格式：
每个输入包含一个测试用例。每个测试用例先给出一个不超过 1000 的正整数 N 表示月饼的种类数、以及不超过 500（以万吨为单位）的正整数 D 表示市场最大需求量。随后一行给出 N 个正数表示每种月饼的库存量（以万吨为单位）；最后一行给出 N 个正数表示每种月饼的总售价（以亿元为单位）。数字间以空格分隔。

输出格式：
对每组测试用例，在一行中输出最大收益，以亿元为单位并精确到小数点后 2 位。

输入样例：
3 20
18 15 10
75 72 45
输出样例：
94.50
代码实现：

#include <iostream>
#include <algorithm>

using namespace std;
struct mooncake
{
	double store; //库存量
	double A_sell;//总售价
	double O_sell;//单价
}arr_K[1010];
bool cmp(mooncake a, mooncake b)//按单价从高到底排序
{
	return a.O_sell > b.O_sell;
}

int main()
{
	int n;//月饼种类
	int d;//月饼的市场最大需求量
	cin >> n >> d;
	for (int i = 0;i < n;i++)
	{
		cin >> arr_K[i].store;
	}
	for (int i = 0;i < n;i++)
	{
		cin >> arr_K[i].A_sell;
		arr_K[i].O_sell = arr_K[i].A_sell / arr_K[i].store;
	}
	sort(arr_K, arr_K + n, cmp);//按单价从高到底排序

	double ans = 0;//收益

	for (int i = 0;i < n;i++)
	{
		if (d >= arr_K[i].store)//需求总量高于单价最高的月饼库存量
		{
			d -= arr_K->store;//单价最高的月饼全部卖出
			ans += arr_K[i].A_sell;//计算收益
		}
		else
		{
			ans += arr_K[i].O_sell * d;//卖出市场需求量单价最高的月饼
			break;
		}
	}
	//cout <<  ans << endl;
	printf("%.2f\n", ans);
	system("pause");
	return 0;
}

笔记：

sort()函数是C++一种排序方法之一，它使用的排序方法是类似于快排的方法（既有快速排序又有与其它排序方法的结合），时间复杂度为n*log2(n)，执行效率很高！我们主要是讲如何使用sort()函数，sort函数包含在头文件为 #include”algorithm” 。sort()函数为非稳定排序，稳定排序可以用stable_sort()函数。
sort(start,end,排序方法) ，排序对象
sort函数有三个参数：
1.第一个是要排序的起始地址。
2.第二个是要排序的结束地址。
3.第三个参数是排序的方法，默认的排序方法是从小到大排序。

bool cmp(mooncake a, mooncake b)//按单价从高到底排序
{
	return a.O_sell > b.O_sell;
}
----------------------------------------
sort(arr_K, arr_K + n, cmp);//按单价从高到底排序

B1022 D进制的A+B (20分)

输入两个非负 10 进制整数 A 和 B (≤2
​30
​​ −1)，输出 A+B 的 D (1<D≤10)进制数。

输入格式：
输入在一行中依次给出 3 个整数 A、B 和 D。

输出格式：
输出 A+B 的 D 进制数。

输入样例：
123 456 8
输出样例：
1103
实现代码：

#include <iostream>
using namespace std;



int main()
{
	int A, B, D;
	cin >> A >> B >> D;
	int sum = A + B;

	int ans[31], num = 0;//ans存放D进制的每一位

	do//进制转换
	{
		ans[num++] = sum % D;
		sum = sum / D;
	} while (sum != 0);
	for (int i = num - 1;i >= 0;i--)//从高位到低位输出
	{
		cout << ans[i];
	}
	cout << endl;
	system("pause");
	return 0;
}

B1023 组个最小数 (20分)

给定数字 0-9 各若干个。你可以以任意顺序排列这些数字，但必须全部使用。目标是使得最后得到的数尽可能小（注意 0 不能做首位）。例如：给定两个 0，两个 1，三个 5，一个 8，我们得到的最小的数就是 10015558。

现给定数字，请编写程序输出能够组成的最小的数。

输入格式：
输入在一行中给出 10 个非负整数，顺序表示我们拥有数字 0、数字 1、……数字 9 的个数。整数间用一个空格分隔。10 个数字的总个数不超过 50，且至少拥有 1 个非 0 的数字。

输出格式：
在一行中输出能够组成的最小的数。

输入样例：
2 2 0 0 0 3 0 0 1 0
输出样例：
10015558
实现代码：

#include <iostream>

using namespace std;
int main()
{
	int count[10];
	for (int i = 0;i < 10;i++)
	{
		cin >> count[i];
	}
	for (int i = 1;i < 10;i++)
	{
		if (count[i] > 0)
		{
			cout << i;
			count[i]--;
			break;
		}
	}
	for (int i = 0;i < 10;i++)
	{
		for (int j = 0;j < count[i];j++)
		{
			cout << i;
		}
	}
	system("pause");
	return 0;

}

B1032 挖掘机技术哪家强 (20分)

为了用事实说明挖掘机技术到底哪家强，PAT 组织了一场挖掘机技能大赛。现请你根据比赛结果统计出技术最强的那个学校。

输入格式：
输入在第 1 行给出不超过 10000 的正整数 N，即参赛人数。随后 N 行，每行给出一位参赛者的信息和成绩，包括其所代表的学校的编号（从 1 开始连续编号）、及其比赛成绩（百分制），中间以空格分隔。

输出格式：
在一行中给出总得分最高的学校的编号、及其总分，中间以空格分隔。题目保证答案唯一，没有并列。

输入样例：
6
3 65
2 80
1 100
2 70
3 40
3 0
输出样例：
2 150
实现代码：

#include <iostream>
using namespace std;
#define N 100000
int school[N] = { 0 };//记录每个学校的总分
int main()
{
	int n, schId, score;
	cin >> n;
	for (int i = 0;i < n;i++)
	{
		cin >> schId >> score;//学校ID 和 分数
		school[schId] += score;//学校schID的总分加score
	}
	int k = 1, MAX = -1;//最高分的学校ID以及其总分
	for (int i = 1;i <= n;i++)//选出最高分
	{
		if (school[i] > MAX)
		{
			MAX = school[i];
			k = i;
		}
	}
	cout << k <<" "<< MAX;


	system("pause");
	return 0;
}

B1036 跟奥巴马一起编程 (15分)

美国总统奥巴马不仅呼吁所有人都学习编程，甚至以身作则编写代码，成为美国历史上首位编写计算机代码的总统。2014 年底，为庆祝“计算机科学教育周”正式启动，奥巴马编写了很简单的计算机代码：在屏幕上画一个正方形。现在你也跟他一起画吧！

输入格式：
输入在一行中给出正方形边长 N（3≤N≤20）和组成正方形边的某种字符 C，间隔一个空格。

输出格式：
输出由给定字符 C 画出的正方形。但是注意到行间距比列间距大，所以为了让结果看上去更像正方形，我们输出的行数实际上是列数的 50%（四舍五入取整）。

输入样例：
10 a
输出样例：
aaaaaaaaaa
a a
a a
a a
aaaaaaaaaa
代码实现：

#include <iostream>
using namespace std;
#define N_MAX 20
int N = 0;//正方形边长
char C = 'a';//字符C
int main()
{
	cin >> N >> C;
	for (int i = 0;i < N;i++)//输出最上面的一条边
	{
		cout << C;
	}
	cout << endl;
	if (N % 2 == 0)//N为偶数
	{
		for (int i = 0;i < N / 2 - 2;i++)
		{
			cout << C;
			for (int i = 0;i < N - 2;i++)
			{
				cout << " ";
			}
			cout << C;
			cout << endl;
		}
	}
	else//N为奇数,加1使其为偶数
	{
		for (int i = 0;i < (N+1) / 2 - 2;i++)
		{
			cout << C;
			for (int i = 0;i < N - 2;i++)
			{
				cout << " ";
			}
			cout << C;
			cout << endl;
		}
	}


	for (int i = 0;i < N;i++)//输出最下面的一条边
	{
		cout << C;
	}
	cout << endl;
	system("pause");
	return 0;
}

B1040 有几个PAT (25分)

字符串 APPAPT 中包含了两个单词 PAT，其中第一个 PAT 是第 2 位(P)，第 4 位(A)，第 6 位(T)；第二个 PAT 是第 3 位(P)，第 4 位(A)，第 6 位(T)。

现给定字符串，问一共可以形成多少个 PAT？

输入格式：
输入只有一行，包含一个字符串，长度不超过10
​5
​​ ，只包含 P、A、T 三种字母。

输出格式：
在一行中输出给定字符串中包含多少个 PAT。由于结果可能比较大，只输出对 1000000007 取余数的结果。

输入样例：
APPAPT
输出样例：
2
思路：

对于一个确定位置的A,以它形成的PAT的个数等于它左边P个个数乘以它右边P的个数
这个问题就转换为，对字符串中的每个A，计算它左边P的个数与它右边T的个数的乘积，然后把所有A的这个乘积相加就是答案

代码实现：

#include <iostream>
#include<string.h>
using namespace std;
const int MAXN = 100010;
const int MOD = 1000000007;
char str[MAXN];//字符串
int leftNumP[MAXN] = { 0 };//每一位左边（含）P的个数

int main()
{
	cin.getline(str, MAXN);
	int len = strlen(str);
	for (int i = 0;i < len;i++)//从左到右遍历字符串
	{
		if (i > 0)//如果不是0号位，继承上一位的结果
		{
			leftNumP[i] = leftNumP[i - 1];
		}
		if (str[i] == 'P')//当前位是P，leftNumP加1
		{
			leftNumP[i]++;
		}
	}
	int ans = 0;//ans为答案
	int rightNumT = 0;//记录右边T的个数
	for (int i = len - 1;i >= 0;i--)//从右到左遍历字符串
	{
		if (str[i] == 'T')//
		{
			rightNumT++;
		}
		else if(str[i]=='A')
		{
			ans = (ans + leftNumP[i] * rightNumT) % MOD;//累计乘积
		}
	}
	cout << ans << endl;
	system("pause");
	return 0;
}