全国青少年信息学奥林匹克竞赛（信奥赛）备考实战之一维数组（应用技巧）

二、一维数组应用技巧2：打标记

实战训练1—开关灯

问题描述：

有 M个从1到M依次编号的人参加一项游戏。将K 盏从1到K依次编号的灯(K和M均为正整数，M≤K≤5000)进行一系列的熄灭与打开的操作，游戏开始时均处于亮灯的状态；第一个人(1号)将灯全部熄灭；第二个人(2号)将编号为2的倍数的灯做相反处理（即将打开的灯熄灭，将熄灭的灯打开）；第三个人( 3号)将编号为3的倍数的灯做相反处理；依照编号递增顺序，以后的人都和3号一样，将凡是自己编号倍数的灯做相反处理。请问：当第M个人操作之后，哪几盏灯是关闭的，按从小到大输出其编号，其间用逗号间隔。

输入格式：

输入共一行，包含两个正整数K和M，以单个空格隔开。

输出格式：

输出共一行，顺次输出关闭的灯的编号，其间用逗号间隔。

输入输出样例：

输入样例1	输出样例1
10 10	1,4,9
输入样例2	输出样例2
20 30	1,4,9,16

问题分析：

根据题意，可以采用打标记的思想来解决此问题，首先定义一个布尔类型数组，数组元素为0表示灯处于亮的状态，1为灯处于熄灭的状态，起始值都为0，这里需要注意由于灯的编号从1到k，所以数组元素在初始时，从下标为1开始；其次来模拟操作的过程，总共m次操作，每次操作将所有是编号倍数的灯执行相反操作，这里使用嵌套循环来实现，外层循环表示m次操作，内层循环遍历一遍灯，将编号是外层循环变量的倍数，则执行相反操作；最后对熄灭的灯进行统计并输出，需要注意除了最后一盏灯，其余灯之间需要用逗号隔开。具体代码如下所示：

#include<bits/stdc++.h>
using namespace std;
int main(){const int MAXLEN =5005;//定义常变量的值为5005 int k,m;//定义灯的数量变量k和操作数变量m scanf("%d%d",&k,&m);//输入k和m的值 bool a[MAXLEN];//定义长度为MAXLEN的布尔类型数组a memset(a+1,0,k*sizeof(bool));//将1到k的初始值设置为0，表示所有的灯都开着，1表示灯关闭 int sum=0;//记录关闭灯的数量和 for(int i=1;i<=m;i++){//进行m次操作 for(int j=1;j<=k;j++){//对于每次操作，依据人的编号，对编号的倍数执行相关的操作 if(j%i==0){//查看当前灯j是否为编号i的整数倍 a[j]=!a[j];//对灯执行相反操作 }}}for(int j=1;j<=k;j++){//依次遍历k盏灯 if(a[j]){//灯如果是熄灭的状态 sum++;//数量加1 }}//在输出时，灯编号需要用逗号隔开，最后一盏灯不需要逗号，所以使用一个临时变量tmpsum来记录输出了多少盏关闭的灯 int tmpsum=0;for(int j=1;j<=k;j++){if(a[j]){//灯关闭，则输出该盏灯 tmpsum++;printf("%d",j);//输出灯编号 if(tmpsum<sum){//如果没有达到sum，则不是最后一盏关闭的灯，输出逗号 printf(",");}}}return 0;
} 

三、循环应用技巧3：巧用数组下标，实现计数功能

实战训练2—数字统计

问题描述：

在[l,r]范围内的整数中，每个整数各个数位上每个数字一共出现过多少次?例如，129~137:129，130，131，132，133，134，135，136，137。统计后发现:“0”出现了1次，“1”出现了10次，“2”出现了2次，“3”出现了9次，“4”出现了1次，“5”出现了1次，“6”出现了1次，“7”出现了1次，“8”出现了0次，“9”出现了1次。

输入格式：

输入共一行，包含两个整数M和N，并用空格分隔开来。

输出格式：

输出共一行，包含十个整数并用空格分开，分别表示数码 0，1，2，… ，9 在序列中出现的次数。

输入输出样例：

输入样例1	输出样例1
101 120	11 32 3 2 2 2 2 2 2 2
输入样例2	输出样例2
219 225	1 2 14 1 1 1 0 0 0 1

问题分析：

根据题意，需要依次分离[l,r]范围内每个整数的各个数位，用数组统计分离出来的数字(0~9)的个数，数组的下标表示出现的数字，数组元素表示该数字出现的次数，即累计“数组下标对应的数字”出现的次数。需要注意对于[l,r]范围内的整数依次进行分离时，用循环变量i来表示这个整数，首先需要将i赋值给一个临时变量tmp，然后再对 tmp进行数位分离。程序中不能直接对数 i 进行数位分离。原因在于数 i 除了有表示区间数的意义外，还在循环控制中起到一定作用，如果直接对 i 进行数位分离，会使得 i 的值变为0，造成程序运行错误。所以枚举区间的数进行数位分离时，需要一个临时变量tmp，存储待分离的数。通过取模运算将得到数的个位，通过整除运算将该数的个位去掉，如此反复运算,直至该数变为0,数位分离结束。所有数字统计完毕后，循环输出0~9各个整数累计的个数。具体程序代码如下：

#include<bits/stdc++.h>
using namespace std;
int main(){int l,r,a[10];//定义整数的取值范围变量l和r，其次定义数字出现的数组a,长度为10的整型数组 memset(a,0,sizeof(a));//起始时，所有数字出现的次数为0，为数组元素全部赋值为0 scanf("%d%d",&l,&r);//输入l和r for(int i=l;i<=r;i++){//依次列举l和r范围内的所有整数 int tmp=i;//将整数i赋值给临时变量tmp while(tmp){//tmp不为0 a[tmp%10]++;//分离最后一个数位，并将该数位出现的次数加1 tmp=tmp/10;//移除最后一个数位 }}for(int i=0;i<10;i++){//依次输出每个数字出现的次数 printf("%d ",a[i]);}return 0;
}