刘汝佳《算法竞赛入门经典（第二版）》第三章习题（一）
习题
3-1
得分（
ACM/ICPC Seoul 2005
，
UVa1585
）
给出一个由
O
和
X
组成的串（长度为
1~80
），统计得分。每个
O
的得分为目前连续出现的
O
的个数，
X
的得分为
0
。例如：
OOXXOXXOOO
的得分为
1+2+0+0+1+0+0+1+2+3
。
解析
因为
X
的得分为
0
，所以只需要统计
O
的得分，另外需要注意的是每次遇到
X
，统计
O
得分的变量都要置
0
。
#include <iostream>
#include <cstdio>
using namespace std;
int main (void)
{
string s;
cin >> s;
int onum = 0,sum = 0;
for (int i = 0; i < s.size(); i++)
{
if (s[i] == 'O')
{
onum++;
sum += onum;
}
else if (s[i] == 'X')
onum = 0;
}
cout << sum << endl;
return 0;
}
习题
3-2
分子量（
ACM/ICPC Seoul 2007
，
UVa1586
）
给出一种物质的分子式（不带括号），求分子量。本题中的分子式只包含
4
种原子，分别为
C
，
H
，
O
，
N
，原子量分别为
12.01
，
1.008
，
16.00
，
14.01
（单位：
g/mol
）。例如：
C6H5OH
的分子量为
94.108g/mol
。
解析
这道题在
ACM/ICPC Seoul 2007
中需要输入的是
n
（
1≤n≤99
）个分子量（管他呢），而且并没有给出数据范围和运行时间限制，所以暂且当做标准限制来做吧（下面的题目除非书中注明，否则同样看待）。
因为分子式中数字对应的一定是其前面的分子，所以只需要判断分子是哪个，以及分子后面的分子数，再根据对应分子的分子量计算就好了。然而麻烦就麻烦在分子数并不一定是个位数，所以我们要怎么将代表分子数的字符串转换成数字呢？
c
标准库提供了
atoi
，
atof
，
atol
，
atoll
函数（需包含头文件
stdlib.h
或
cstdlib
）将字符串分别转换成
int
，
double
，
long
，
long long
型，我们将两个分子之间的数字存放在一个字符型数组，再调用
atof
函数转换即可。
说起来挺简单的，但实现起来需要考虑的东西还蛮多。
不废话，上代码：
#include <iostream>
#include <cstdlib>
#include <memory>
#include <cctype>
using namespace std;
const char name[] = "CHON";
const double fweight[] = {12.01,1.008,16.00,14.01};
int main (void)
{
char c[5];
string s;
cin >> s;
double sum = 0.0, weight = 0.0;
int num = 0;
for (int i = 0; i < s.size(); i++)//遍历字符串，找出分子
{
if (isalpha(s[i]))
{
for (int j = 0; j < 4; j++)//将分子对应的分子量赋给weight
if (s[i] == name[j])
{
weight = fweight[j];
break;
}
num = 0;//将用来移位的变量清零
if (isalpha(s[i+1]) || i+1 == s.size())//分子式后面若没有分子数则其分子数默认为1
sum += weight;
else
{
for (int k = i+1; k < s.size() && isdigit(s[k]); k++)//将表示分子数的字符串转换为double型数据
c[num++] = s[k];
sum += atof(c)*weight;//计算分子量
}
memset(c, '\0', sizeof(c));//将用于存放分子数的数组清空
}
else
continue;
}
cout << sum << "g/mol" << endl;
return 0;
}
习题
3-3
数数字（
ACM/ICPC Danang 2007
，
UVa1225
）
把前
n
（
n≤10000
）个整数顺次写在一起：
123456789101112…
数一数
0~9
各出现多少次（输出
10
个整数，分别是
0
，
1
，
…
，
9
出现的次数）。
解析
刚看到这道题的时候我一直以为这些数字的出现是有规律的，想了很久，然而
……
失败了（等我用暴搜写完后在网上找各路大神的解法才悲剧地发现：根本没有规律T.T）。数据范围不大，原题的时间限制为
3000ms
，所以直接暴搜吧。有两种思路，第一种是对
1~n
的整数分别进行数字统计，得出结果；第二种是将
1~n
的整数一个个转成字符串，然后统计，得出结果。
对于第一种思路，一般做法是直接一个
1~n
的大循环，对每个整数一步步拆分，统计数字出现次数，我就是这么写的。另外我在网上看到一种比较特别的做法：直接用
10000×10
的二维数组做成一个查询表，
再根据输入的值查询输出，下面
是
1~19
的查询表，帮助理解：
解法一
#include <cstdio>
#include <memory>
#include <cstdlib>
int main (void)
{
int a[10];
int n,num;
scanf ("%d",&n);
memset(a, 0, sizeof(a));
for (int i = 1; i <= n; i++)
{
int temp = i;
while (temp)//拆分整数
{
num = temp%10;
temp /= 10;
a[num]++;
}
}
for (int i = 0; i < 10; i++)
(i == 0)?printf ("%d",a[i]):printf (" %d",a[i]);
return 0;
}
解法二
#include <cstdio>
#include <memory>
#include <cstdlib>
int a[10000][10];
int main (void)
{
memset (a, 0, sizeof(a));
for (int i = 1; i < 10000; i++)
{
for (int j = 0; j < 10; j++)
a[i][j] = a[i-1][j];
for (int k = i; k; k /= 10)
a[i][k%10]++;
}
int n;
scanf ("%d",&n);
for (int j = 0; j < 9; j++)
(j)?printf (" %d",a[n][j]): printf ("%d",a[n][j]);
printf ("\n");
return 0;
}
在本题中解法二相对于解法一在速度上并没有什么优势，但这个制表查询的想法还是值得学习的（反正我想不到
– –
）。
对于第二种思路，用
sprintf
函数（虽然
itoa
也可以，但与
ANSI
标准不兼容，不建议使用）将每个整数转成字符串是关键，直接看代码就好了。
解法三
#include <cstdio>
#include <cstdlib>
#include <memory>
#include <cctype>
int main (void)
{
int num[10];
int n;
scanf ("%d",&n);
char c[10];
memset(num, 0, sizeof(num));//初始化存放统计数字的数组
for (int i = 1; i <= n; i++)//对1~n的数字逐一统计
{
memset(c, '\0', sizeof(c));//初始化存放转换结果的字符数组
sprintf(c, "%d", i);//将数字转换为字符存到数组c中
for (int j = 0; j < 10; j++)//对字符数组c进行扫描，对数字进行统计
if (isdigit(c[j]))
{
switch (c[j])
{
case'0':
num[0]++;
break;
case'1':
num[1]++;
break;
case'2':
num[2]++;
break;
case'3':
num[3]++;
break;
case'4':
num[4]++;
break;
case'5':
num[5]++;
break;
case'6':
num[6]++;
break;
case'7':
num[7]++;
break;
case'8':
num[8]++;
break;
case'9':
num[9]++;
break;
}
}
}
for (int i = 0; i < 10; i++)
(i == 0)?printf ("%d",num[i]):printf (" %d",num[i]);
return 0;
}
习题
3-4
周期串（
UVa 455
）
如果一个字符串可以由某个长度为
k
的字符串重复多次得到，则称该串以
k
为周期。例如，
abcabcabcabc
以
3
为周期（注意，它也以
6
和
12
为周期）。
输入一个长度不超过
80
的字符串，输出其最小周期。
解析
题目已经说得很清楚，做法也很简单，只需要从
1
开始假设周期，然后扫描字符串的一半，验证是否是这个周期，是则输出周期，否则假设的周期增
1
。
#include <cstdio>
#include <string>
#include <cstdlib>
int main (void)
{
string s;
int kase = 0,T = 0;//kase判断是否存在周期
cin >> s;
for (int i = 0; i < s.size()/2; i++)//扫描字符串的一半
{
T++;
if (s.size()%T == 0)
{
kase = 1;
for (int j = 0; j < T; j++)//验证假设的第一个周期是否成立
{
for (int k = 0; k+T < s.size(); k += T)
if (s[j] != s[k+j])
{
kase = 0;
break;
}
if (!kase)//一旦发现周期不成立即退出，减少不必要的时间消耗
break;
}
}
if (kase)//同上一个kase作用相同
break;
}
if (kase)
printf ("%d\n",T);
return 0;
}