《算法竞赛入门经典（第二版）》第三章

思考题
- 题目1 必要的存储量
- 题目2 统计字符1的个数
示例程序
- 程序3-1 逆序输出
- 程序3-2 开灯问题
- 程序3-3 蛇形填数
- 程序3-4 竖式问题
例题
- 例题3-1 Tex中的引号 (Tex Quotes, UVa 272)
- 例题3-2 WERTYU (WERTYU, UVa 10082)
- 例题3-3 回文词 (Pdlindromes, UVa 401)
- 例题3-4 猜数字游戏的提示 (Master-Mind Hints, UVa 340)
- 例题3-5 生成元 (Digit Generator, ACM/ICPC Seoul 2005, UVa 1583)
- 例题3-6 环状序列 (Circular Sequence, ACM/ICPC Seoul 2004, UVa 1584)

思考题

题目1 必要的存储量

数组可以用来保存很多数据，但在一些情况下，并不需要把数据保存下来。下面哪些题目可以不借助数组，哪些必须借助数组？请编程实现。假设输入只能读一遍。

输入一些数，统计个数。
输入一些数，求最大值、最小值和平均数。
输入一些数，哪两个数最接近。
输入一些数，求第二大的值。
输入一些数，求它们的方差。
输入一些数，统计不超过平均数的个数。

答案是2、5必须使用数组，代码如下：

#include <iostream>
using namespace std;const int maxn=105;
void first(){int num,count=0;while(cin>>num)count++;cout<<"You're inputted "<<count<<" numbers"<<endl;return ;
}
void second(){int num,count=0,total=0;int max,min,average;bool firstFlag=true;while(cin>>num){if(firstFlag){max=min=num;firstFlag=!firstFlag;}if(num>max)max=num;if(num<min)min=num;count++;total+=num;}average=double(total)/count;cout<<"max:"<<max<<endl;cout<<"min:"<<min<<endl;cout<<"average:"<<average<<endl;return ;
}
void third(){int nums[maxn]={},i=0;while(cin>>nums[i++]);int a=nums[0],b=nums[1],mindistance=abs(a-b);for(int j=0;j<i-1;j++)for(int k=j+1;k<i;k++)if(abs(nums[j]-nums[k])<mindistance){mindistance=abs(nums[j]-nums[k]);a=nums[j];b=nums[k];}cout<<"Two nearest numbers:"<<a<<" "<<b<<endl;return ;
}
void fourth(){int max,secmax,num;cin>>max>>secmax;int t1=max>secmax?max:secmax;int t2=max<secmax?max:secmax;max=t1;secmax=t2;while(cin>>num){if(num>max){secmax=max;max=num;continue;}else if(num>secmax&&num!=max)secmax=num;}cout<<"max:"<<max<<endl;cout<<"secmax:"<<secmax<<endl;return ;
}
void fifth(){int nums[maxn]={};int count=0,num;double average=0.0,total=0.0,sqrTotal=0.0,variance;while(cin>>num){nums[count++]=num;total+=num;}average=total/count;for(int i=0;i<count;i++)sqrTotal+=(nums[i]-average)*(nums[i]-average);variance=sqrTotal/count;cout<<"variance:"<<variance<<endl;return ;
}
void sixth(){int nums[maxn]={},num;int count=0,aimCount=0;double average=0.0,total=0.0;while(cin>>num){nums[count++]=num;total+=num;}average=total/count;for(int i=0;i<count;i++)if(nums[i]<average)aimCount++;cout<<"aimCount:"<<aimCount<<endl;return ;
}
int main(){//只有一个输入流//first();//second();//third();//fourth();//fifth();sixth();
}

题目2 统计字符1的个数

下面的程序意图在于统计字符串中字符1的个数，可惜有瑕疵：

#include <cstdio>
#define maxn 10000000+10
int main()
{char s[maxn];scanf("%s",s);int tot=0;for(int i=0;i<strlen(s);i++)if(s[i]==1) tot++;printf("%d\n",tot);
}

该程序至少有3个问题，其中一个导致程序无法运行，另一个导致结果不正确，还有一个导致效率低下。你能找到它们并改正吗？
程序无法运行：strlen(s)需要#include <cstring>
结果不正确：if(s[i]==1)改为if(s[i]=='1')
效率低下：这是将输入存入数组并循环导致的，可改为下面的形式。

#include <cstdio>
int main(){char ch;int tot=0;while((ch=getchar())!=EOF)//while((ch=getchar())!='\n')if(ch=='1')tot++;printf("%d\n",tot);

EOF为End Of File的缩写，是文件结束标志，手动输入时需要用Ctrl+Z键入结束符，然后按Enter将其输入，while(cin>>ch)同理。

示例程序

程序3-1 逆序输出

读入一些整数，逆序输出到一行中

#include <cstdio>
#define maxn 1000010//大数组只能放在主函数外，分配于静态存储区
int a[maxn];
int main()
{int x,n=0;while(scanf("%d",&x)==1)a[n++]=x;for(int i=n-1;i>=1;i--)printf("%d ",a[i]);printf("%d\n",a[0]);return 0;
}

程序3-2 开灯问题

有n盏灯，编号为1～n。第1个人把所有灯打开，第2个人按下所有编号为2的倍数的开关（这些灯将被关掉），第3个人按下所有编号为3的倍数的开关（其中关掉的灯被打开，开着灯将被关闭），依此类推。一共有k个人，问最后有哪些灯开着？输入n和k，输出开着的灯编号。k≤n≤1000。

样例输入：

7  3

样例输出：

1 5 6 7

#include <cstdio>
#include <cstring>
#define maxn 1010
int a[maxn];//int a[maxn]={0};
int main()
{int n,k,first=1;memset(a,0,sizeof(a));scanf("%d%d",&n,&k);for(int i=1;i<=k;i++)for(int j=1;j<=n;j++)if(j%i==0)a[j]=!a[j];for(int i=1;i<=n;i++)if(a[i]){//在变量左边填充，第一个跳过if(first)first=0;elseprintf("*");printf("%d",i);}printf("\n");return 0;
}

程序3-3 蛇形填数

在 $n * n$ 方阵里填入1,2,…,n*n，要求填成蛇形。例如n=4时方阵为

 10 11 12  19 16 13  28 15 14  37  6  5  4

上面的方阵中，多余的空格只是为了便于观察规律，不必严格输出。n≤8。

#include <cstdio>
#include <cstring>
#define maxn 10
int a[maxn][maxn];
int main()
{int n,x,y;scanf("%d",&n);memset(a,0,sizeof(a));int tot=a[x=0][y=n-1]=1;while(tot<n*n){while(x+1<n&&a[x+1][y]==0) a[++x][y]=++tot;//可下移且未写过while(y-1>=0&&a[x][y-1]==0) a[x][--y]=++tot;//可左移且未写过while(x-1>=0&&a[x-1][y]==0) a[--x][y]=++tot;//可上移且未写过while(y+1<n&&a[x][y+1]==0) a[x][++y]=++tot;//可右移且未写过}for(x=0;x<n;x++){for(y=0;y<n;y++)printf("%3d",a[x][y]);printf("\n");}return 0;
}

程序3-4 竖式问题

找出形如 abc*de （三位数乘以两位数）的算式，使得在完整的竖式中，所有数字属于一个特定的数字集合。输入数字集合（相邻数字之间没有空格），输出所有竖式。每个竖式前应有编号，之后应有一个空行。最后输出解的总数。

样例输入：

样例输出：

<1>
..775
X..33
-----
.2325
2325.
-----
25575The number of solusions = 1

#include <iostream>
#include <iomanip>
#include <cstring>
#include <sstream>
using namespace std;string s,buf;
stringstream ss;
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int count=0;cin>>s;for(int abc=111;abc<=999;abc++)for(int de=11;de<=99;de++){int x=abc*(de%10),y=abc*(de/10),z=abc*de;ss.str("");ss.clear();ss<<abc<<de<<x<<y<<z;ss>>buf;bool flag=true;for(int i=0;i<int(buf.length());i++)if(s.find(buf[i])==s.npos)flag=false;if(flag){cout<<"<"<<++count<<">"<<endl;cout<<setw(5)<<abc<<endl<<"X"<<setw(4)<<de<<endl<<"-----"<<endl<<setw(5)<<x<<endl<<setw(4)<<y<<endl<<"-----"<<endl<<setw(5)<<z<<endl<<endl;}}cout<<"The number of solusions = "<<count<<endl;return 0;
}

例题

例题3-1 Tex中的引号 (Tex Quotes, UVa 272)

#include<iostream>
using namespace std;int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);//ios(basic_ios)是父类，ios_base是ios的子类，ios可以访问到ios_base的所有成员char c;bool q=true;while(cin>>c){if(c=='"'){cout<<(q?"``":"''");q=!q;}else{cout<<c;}}return 0;
}

例题3-2 WERTYU (WERTYU, UVa 10082)

把手放在键盘上时，稍不注意就会往右错一位。这样，输入Q会变成输入W，输入J会变成输入K等。输入一个错位敲出的字符串（所有字母均大写），输出打字员本来想打出的句子。输入保证合法，即一定是错位之后的字符串。例如输入中不会出现大写字母A。

样例输入：

 O S,GOMR YPFSU/

样例输出：

I AMFINE TODAY.

#include <iostream>
using namespace std;char s[]="`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./";//其余内存全为空
int main(){char c;int i;while(c=getchar()){for(i=1;s[i]&&s[i]!=c;i++)//s[i]防止查找溢出;if(s[i])putchar(s[i-1]);elseputchar(c);}return 0;
}

例题3-3 回文词 (Pdlindromes, UVa 401)

输入一个字符串，判断它是否为回文串以及镜像串。输入字符串保证不含数字0。所谓回文串，就是反转以后与原串相同，如abba和madam。所谓镜像串，就是左右镜像之后和原串相同，如2S和3AIAE。注意，并不是每个字符在镜像之后都能得到一个合法字符。（空白项表示该字符镜像后不能得到一个合法字符。）

Character Reverse Character Reverse Character ReverseA        A        M        M        Y        YB                 N                 Z        5C                 O        O        1        1D                 P                 2        SE        3        Q                 3        EF                 R                 4        G                 S        2        5        ZH        H        T        T        6        I        I        U        U        7        J        L        V        V        8        8K                 W        W        9        L        J        X        X

输入的每行包含一个字符串，（保证只有上述字符。不含空白字符），判断它是否为回文串和镜像串（共四种组合）。每组数据之后输出一个空行。
样例输入：

NOTAPALINDROME
ISAPALINILAPASI
2A3MEAS
ATOYOTA

样例输出：

NOTAPALINDROME – is not a palindrome.ISAPALINILAPASI – is a regular palindrome.2A3MEAS – is a mirrored string.ATOYOTA – is a mirrored palindrome.

#include <iostream>
#include <cstring>
#include <cctype>
using namespace std;const string rev="A   3  HIL JM O   2TUVWXY51SE Z  8 ";
const string msg[]={"not a palindrome",
"a regular palindrome",
"a mirrored string",
"a mirrored palindrome"};
char r(char ch);
int main(){ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);string s;while(cin>>s){int len=s.length();int p=1,m=1;for(int i=0;i<(len+1)/2;i++){if(s[i]!=s[len-i-1])//表项转下标p=0;if(r(s[i])!=s[len-i-1])m=0;}cout<<s<<" -- is "<<msg[m*2+p]<<'.'<<endl<<endl;//nb!!}return 0;
}
char r(char ch){if(isalpha(ch))return rev[ch-'A'];//前26（字母）return rev[ch-'0'+25];//后10（数字）
}

例题3-4 猜数字游戏的提示 (Master-Mind Hints, UVa 340)

实现一个经典"猜数字"游戏。给定答案序列和用户猜的序列，统计有多少数字位置正确（A），有多少数字在两个序列都出现过但位置不对（B）。

输入包含多组数据。每组输入第一行为序列长度n，第二行是答案序列，接下来是若干猜测序列。猜测序列全0时该组数据结束。n=0时输入结束。

样例输入

4
1 3 5 5
1 1 2 3
4 3 3 5
6 5 5 1
6 1 3 5
1 3 5 5
0 0 0 0
10
1 2 2 2 4 5 6 6 6 9
1 2 3 4 5 6 7 8 9 1
1 1 2 2 3 3 4 4 5 5
1 2 1 3 1 5 1 6 1 9
1 2 2 5 5 5 6 6 6 7
0 0 0 0 0 0 0 0 0 0
0

样例输出

Game 1:(1,1)(2,0)(1,2)(1,2)(4,0)
Game 2:(2,4)(3,2)(5,0)(7,0)

#include <iostream>
using namespace std;const int maxn=1010;
int main(){ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);int n,a[maxn],b[maxn];int kase=0;while(cin>>n&&n){cout<<"Game "<<++kase<<":"<<endl;for(int i=0;i<n;i++)cin>>a[i];while(true){int A=0,B=0;for(int i=0;i<n;i++){cin>>b[i];if(a[i]==b[i])A++;}//A为同时出现且位置正确if(b[0]==0)break;for(int d=1;d<9;d++){int c1=0,c2=0;for(int i=0;i<n;i++){if(a[i]==d)c1++;if(b[i]==d)c2++;}B+=c1<c2?c1:c2;}//B为同时出现且位置任意B-=A;//B为同时出现且位置不定cout<<"    ("<<A<<","<<B<<")"<<endl;}}return 0;
}

例题3-5 生成元 (Digit Generator, ACM/ICPC Seoul 2005, UVa 1583)

如果x加上x的各个数字之和得到y，就说x是y的生成元。给出n（1≤n≤100000），求最小生成元。无解输出0。例如，n=216，121，2005时的解分别为198，0，1979。

#include <iostream>
//#include <cstring>
using namespace std;const int maxn=10005;
int ans[maxn]={};//未显式赋值即为0，该语法糖实为自动调用memset(,0,)
int main(){ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);int T,n;//memset(ans,0,sizeof(ans));for(int m=1;m<maxn;m++){int x=m,y=m;while(x>0){y+=x%10;x/=10;}if(ans[y]==0||m<ans[y])ans[y]=m;}cin>>T;while(T--){cin>>n;cout<<ans[n]<<endl;}return 0;
}

例题3-6 环状序列 (Circular Sequence, ACM/ICPC Seoul 2004, UVa 1584)

长度为n的环状串有n种表示法，分别为某个位置开始顺时针得到。例如，图中的环状串有10种表示：CGAGTCAGCT,GAGTCAGCTC,AGTCAGCTCG等。在这些表示法中，字典序最小的称为“最小表示”。
在这里插入图片描述

输入一个长度为n（n<=100）的环状DNA串（只包含A、C、G、T这4种字符）的一种表示法，你的任务是输出该环状串的最小表示。例如，CTCC的最小表示是CCCT,CGAGTCAGCT的最小表示为AGCTCGAGTC.

#include <iostream>
#include <cstring>
using namespace std;const int maxn=105;
bool isLess(const char* s,int p,int q);
int main(){int T;char s[maxn];cin>>T;while(T--){cin>>s;int ans=0;int n=strlen(s);for(int i=1;i<n;i++)//记录最小起点if(isLess(s,i,ans))ans=i;for(int i=0;i<n;i++)cout<<s[(ans+i)%n];cout<<endl;}return 0;
}
bool isLess(const char* s,int p,int q){int n=strlen(s);for(int i=0;i<n;i++)if(s[(p+i)%n]!=s[(q+i)%n])return s[(p+i)%n]<s[(q+i)%n];return false;
}