几道NOI题目

发表于 更新于 阅读次数：

都是普及T1题，有点复杂，但代码不多，较绕，体会到算法选手的天赋所在了（我爬了）

39:与7无关的数

总时间限制:  1000ms  内存限制:  65536kB

描述

一个正整数,如果它能被7整除,或者它的十进制表示法中某一位上的数字为7,则称其为与7相关的数.现求所有小于等于n(n < 100)的与7无关的正整数的平方和.

输入

输入为一行,正整数n(n < 100)

输出

输出一行，包含一个整数，即小于等于n的所有与7无关的正整数的平方和。

样例输入

21

样例输出

2336

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
源码

#include<stdio.h>
int main()
{
    int n,sum = 0,flag;
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
    {
        flag = 0;
        if(i % 7 == 0 || i % 10 == 7 || i / 10 == 7)
            flag = 1;
        if(!flag)
            sum += i * i;
    }
    printf("%d",sum);
    return 0;
}

79：开关灯

假设有 N 盏灯（N 为不大于 5000 的正整数），从 1 到 N 按顺序依次编号，初始时全部处于开启状态；有 M 个人（M 为不大于 N 的正整数）也从 1 到 M 依次编号。

第一个人（1号）将灯全部关闭，第二个人（2号）将编号为 2 的倍数的灯打开，第三个人（3 号）将编号为 3 的倍数的灯做相反处理（即，将打开的灯关闭，将关闭的灯打开）。依照编号递增顺序，以后的人都和 3 号一样，将凡是自己编号倍数的灯做相反处理。

请问：当第 M 个人操作之后，哪几盏灯是关闭的，按从小到大输出其编号，其间用逗号间隔。

输入格式

输入正整数 N 和 M，以单个空格隔开，M<=N。

输出格式

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

注：输出时每行末尾的多余空格，不影响答案正确性

样例输入

10 10

样例输出

1,4,9

题目分析：

M个人中一号人的唯一作用是把灯全部关闭，因此直接从二号开始思考；

这个题里面只有开关两种状态，在1号的作用下灯都关着，因此初状态全部为0；

把初状态数组规定成{0}，最后是0的都是被灭掉的

在每一个符合条件的人碰一次灯时，灯的状态改变一次

而此条件是人组成的数组中每个人自身编号的倍数，因此只需在人的数组循环中再嵌套一个倍数

循环进行乘积。

源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<stdio.h>
#include<math.h>
int main()
{
	int i,j,k,a[5000]={0},b[5000]={0},n;//a[i]这个数组为每个人附上编号
	int N,M;                            //b[i]则是灯的逻辑数组
	scanf("%d %d",&N,&M);
	for(i=2;i<=M;i++)//给人编号
	{
        a[1]=1;
		a[i]=a[i-1]+1;
        for(n=1;a[i]*n<=N;n++)//a[i]*n是每个人对应编号的倍数，即所需改变的灯的序号
        {
            j=a[i]*n;
            b[j]=!b[j];
        }
	}
	for(k=1;k<=N;k++)//找出还灭着的项，输出
	{
		if(b[k]==0)
        {
            if(k==1) 
            printf("1");//这块让结尾不出现逗号，虽然不知道最后一项筛选的是哪个数
            else 
            printf(",%d",k);//但是第一项一定是1，所以先输出逗号
        }
	}
    return 0;
}

84：雇佣兵

描述

雇佣兵的体力最大值为M，初始体力值为0、战斗力为N、拥有X个能量元素。

当雇佣兵的体力值恰好为M时，才可以参加一个为期M天的战斗期，战斗期结束体力值将为0。在同一个战斗期内，雇佣兵每连续战斗n天，战斗力就会上升1点，n为当前战斗期开始时的战斗力。

一个战斗期结束后，雇佣兵需要用若干个能量元素使其体力恢复到最大值M，从而参加下一个战斗期。每个能量元素恢复的体力值不超过当前的战斗力。每个能量元素只能使用一次。

请问：雇佣兵的战斗力最大可以到达多少。

输入

一行包括三个整数M、N、X，相邻两个整数之间用单个空格隔开。M、N、X均为不超过10000的正整数。

输出

输出一个整数，为雇佣兵的最大战斗力。

样例输入

1
5 2 10

样例输出
6

源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//c语言版
#include <stdio.h>

int main()
{
	int m,n,x;
	scanf("%d%d%d",&m,&n,&x);
	int M = 0;//初始体力值为0 
	for(int i=0;i<x;i++){//能量元素 恢复体力 
		M += n;//用能量元素恢复体力 
		if(M>=m){//恢复完毕 
			n+=m/n;/*雇佣兵每连续战斗n天，战斗力就会上升1点
			这里战斗天数为m*/ 
			M=0;//结束后体力为0 
		}
	}
	printf("%d",n);
}

其实雇佣兵这道题挺绕，但理解了代码反而不是很难，这种拿给我这种没基础的，简直要命（想半天），网上找了个思路解析，附上。

一，流程图

图片

二，提取关键点

1.不知道每个能量元素具体回复多少体力

2.雇佣兵初始体力值为0

3.雇佣兵通过战斗期来提升战斗力

4.当雇佣兵的体力值恰好为体力最大值时，才可以参加战斗期

三，解决关键点

1.不知道每个能量元素具体回复多少体力

因为求的是最大战斗力的情况，所以为了物尽其用，每个能量元素能回复的体力等于当前的战斗力。

2.雇佣兵初始体力值为0

在循环前就使用一次能量元素将体力恢复到最大值。

3.雇佣兵通过战斗期来提升战斗力

通过循环模拟战斗期，每次循环增加当前状况最多能增加的战斗力。

4.当雇佣兵的体力值恰好为体力最大值时，才可以参加战斗期

每次循环结束，使用一次能量元素将体力恢复到最大值。

如果能量元素不能将体力恢复到最大值，则跳出战斗期，并输出目前的战斗力。

=====注意=====

每次使用能量元素，需要将当前所拥有的能量元素数量减去使用的能量元素数量