全国青少年信息学奥林匹克竞赛（信奥赛）备考实战之一维数组（应用技巧）
二、一维数组应用技巧2：打标记
实战训练1—开关灯
问题描述：
有 M 人从 1 到 M 按顺序编号参与一项游戏活动。共有 K 盏从 1 到 K 编号依次排列并亮着（其中 M 和 K 均为正整数，并且满足 M≤K≤5000）。系统会对该 K 盏灯光进行一系列的操作——熄灭与点亮动作。初始状态下所有灯均处于点亮状态；第一个参与者（编号为 1 的人）会将其余所有开关位置；第二个参与者（编号为 2 的人）会对所有标号是其倍数位置上的灯光进行反向操作；第三个参与者（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次操作后, 每次操作都将所有编号为其当前循环变量倍数的灯切换状态. 为了实现这一过程, 可以使用双层循环结构: 外层循环控制开关的操作次数, 内层循环遍历所有灯光并判断其是否符合切换条件. 最后统计熄灭状态的所有灯光并记录其信息. 在输出结果时需要注意除了最后一盏灯的状态不需要单独列出外, 其余灯光的状态之间需要用逗号分隔开. 具体实现代码如下所示:
#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之间的所有整数中，请问各位数字在整个范围内各自出现的总次数是多少？举个例子，在区间[...]中的整数如...统计结果表明：“0”总共出现了一次，“9”的情况也是如此……
输入格式：
输入共一行，包含两个整数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各数字出现的频率。具体操作方法是：初始化一个长度为10的数组，并将其中所有元素设置为零；然后利用循环变量i遍历该区间内的每一个整数值；每次循环时将当前整数值赋值给临时变量tmp；接着对tmp执行各位分离操作；最后将tmph各位上的数字对应到目标数组中的相应位置并累加计数值。值得注意的是，在程序运行过程中不允许直接对循环索引变量i执行各位分解操作；因为这会使得i失去其作为区间控制变量的作用而导致程序运行错误；因此在处理数据时必须先提取出待分解的具体数值存放在临时变量tmp中
#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;
}