2023.5 NHOI 小学

A. 疯狂星期四（2023.5 NHOI 小学 1）

Description

小明非常喜欢吃KFC的炸鸡蛋挞。由于小明是个学生党，零花钱有限，每次都要隔一段时间才能去吃一次。已知KFC在每周四都会举行优惠活动，今天是星期一，还有n天小明才能去KFC吃东西，请你帮助小明算一下，他去的那天能不能赶上优惠活动！
输入格式
输入数据有一行，一行一个数n，代表小明在周一之后n天去KFC。
输出格式
输出数据有一行。
如果小明去的那天有优惠活动，输出 YES 。
如果小明去的那天没有优惠活动，输出 NO 。
输入/输出例子1
输入：
1
输出：
NO
输入/输出例子2
输入：
3
输出：
YES
样例解释
样例1，周一过了一天是周二，因此没有优惠活动。
样例2，周一过了三天是周四，因此有优惠活动。
【数据范围】
对于100%的数据，1<=n<=1000 .

题意

题目要求判断小明在n天后去KFC时，是否能够赶上每周四的优惠活动。输入为一个整数n，表示从星期一开始的天数。输出为"YES"表示那天是周四，有优惠活动；输出"NO"表示那天不是周四，没有优惠活动。

思路

关键在于理解一周有7天，并且通过计算n除以7的余数来确定星期几。如果余数是4，那么小明去的那天就是星期四，有优惠活动；否则，没有优惠活动。

参考代码

#include<bits/stdc++.h>
using namespace std;
int n;
int main() {cin>>n;n++;//n天后，需要加1n=n%7;//一周7天if(n==4)//如果是星期四 cout<<"YES";else cout<<"NO";return 0;
}

B. 默契测试（2023.5 NHOI 小学 2）

Description

小明突然有一天想和好朋友小军进行一次默契测试，小明思考出了一个默契测试方法。首先小明独自写下一个18位以内的数a ,然后小军也写下一个18位以内的数b，然后分别求出a的每一位数字之和x,以及b的每一位数字之和y。最终算出默契值x+y。

输入格式
输入数据有一行。以空格隔开的两个正整数a,b

输出格式
输出数据共一行。一个整数，表示x+y的和。

输入/输出例子1
输入：
10 25
输出：
8

【数据范围】
对于100%的数据，1<=a<10^18，1<=b<10^18 。

【样例解释】
10的每一位数字之和为1 。
25的每一位数字之和为7 。
最终为1+7=8 .

题意

要求计算两个18位以内的数a和b的每一位数字之和的总和

思路

分别求出两位数对应的数字之和，再累加即可，注意：定义 long long类型

参考代码

#include<bits/stdc++.h>
using namespace std;
long long x, y, a, b;
int main() {cin>>a>>b;while(a>0) {//求出每位数字之和 x+=a%10;a/=10;}while(b>0) {//求出每位数字之和y+=b%10;b/=10;}cout<<x+y;return 0;
}

C. X光线（2023.5 NHOI 小学 3）

Description

小明在玩一款热门游戏，游戏的地图是一个n×n的矩阵。在游戏地图当中存在着一定数量的小怪。现在小明的角色有一个技能：X光线，在地图的任意一个点释放技能，以该点的中心，分别在左上到右下对角线和左下到右上对角线上的小怪，都会被消灭。现在给出小明释放技能的位置，请你帮忙计算一共消灭了多少只小怪。

输入格式
第一行，三个整数：n、i、j，分别表示地图大小，技能释放的位置。
接下来n行，每行输入n个数，用来表示在当前位置是否有小怪，0表示没有小怪，1表示有一个小怪。

输出格式
共一行，X光线消灭小怪的数量。

输入/输出例子1
输入：
4 2 3
1 0 1 1
0 1 1 0
1 1 0 1
0 0 0 1
输出：
4

【数据范围】
对于100%数据，1<=n<=1000; 1<=i ,j <=n ;

题意

小明在玩一个游戏，地图是一个 $n\times n$ 的矩阵。他有一个技能“X光线”，可以在任意位置释放，消灭该位置为中心的两条对角线上的小怪。现在需要计算在特定位置释放技能时，一共消灭了多少只小怪。

思路

读取地图的大小 nn 和技能释放的位置 $(a,b)$ 。
嵌套循环读取整个 $n \times n$ 地图上每个位置的小怪信息，存储在二维数组 m 中。
使用三个独立的循环来计算两条对角线上的小怪数量：
- 第一个循环计算从技能释放点 $(a,b)$ 向左上角对角线方向的小怪数量。
- 第二个循环计算从技能释放点 $(a,b)$ 向左下到右上角对角线方向的小怪数量。
- 第三个循环计算从技能释放点 $(a,b)$ 向右下角对角线方向的小怪数量。
每个循环都会检查当前位置的小怪状态（1表示有小怪），并累加到总和 $sum$ 中。循环会在到达地图边界时停止。
如果技能释放点 $(a,b)$ 本身有小怪，则将其也加入到总和 $sum$ 中。
代码输出消灭的小怪总数 $sum$ 。

关键在于正确处理对角线方向的遍历，并在到达地图边界时停止循环。同时，它也考虑了技能释放点本身的小怪。

参考代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1005; 
long long n, a, b, m[N][N], sum;
int main() {cin>>n>>a>>b;for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) cin>>m[i][j];		for(int i=1; ;i++) {if(m[a-i][b-i]==1) sum++;if(a-i==0||b-i==0) break;}for(int i=1;; i++) {if(m[a-i][b+i]==1)sum++;if(a-i==0||b+i==n)break;}for(int i=1;; i++) {if(m[a+i][b-i]==1)sum++;if(a+i==n||b-i==0)break;}for(int i=1;; i++) {if(m[a+i][b+i]==1)sum++;if(a+i==n||b+i==n)break;}if(m[a][b]==1)sum++;cout<<sum;return 0;
}

D. 质量检测（2023.5 NHOI 小学 4）

Description

最近淄博烧烤非常火爆，原因就是当地的烧烤物美价廉，而且拒绝缺斤少两，诚信买卖。现在有一家工厂，由于设备缘故，在生产的一批从1开始的连续编号的产品中，每隔k个产品就有一个产品是不达标的，即k号、k+k号产品、k+k+k号产品……。现在工商局接到举报，前来进行n次质量检测，每次检测抽取编号l到r的连续编号产品。请帮忙算出每次检测，不达标产品有多少个？

输入格式

输入第一行，两个整数：n和k。

接下来n行，每行两个正整数l，r。

输出格式

输出n行，表示每次检测不合格数量。

输入/输出例子1

输入：

3 5

1 1

1 10

5 15

输出：

样例解释

【样例解释】

不合格的产品编号有5,10,15,20，……，区间[1,1]中没有不合格产品，[1,10]中有5和10，[5,15]中有5,10,15.

【数据范围】

对于30%的数据，1<=n<=10,1<=l<=r<=10, 1<=k<=10。

对于60%的数据，1<=n<=10000, 1<=l<=r<=10000, 1<=k<=10000。

对于100%的数据，1<=n<=100000, 1<=l<=r<=100000, 1<=k<=100000。

题意

本题描述了一个工厂生产的产品中，每隔 kk 个产品就有一个不达标的情况。现在需要对 nn 次质量检测进行分析，每次检测抽取编号从 l 到 r 的连续编号产品，并计算每次检测中不达标产品的数量。

思路

目的是计算每次质量检测中不达标产品的数量。

标准输入读取检测次数 n 和不达标产品的间隔 kk。
循环 n 次，每次读取两个正整数 l 和 r，分别表示检测的产品编号范围。
对于每次检测，计算不达标产品的数量：
- 计算 l 之前（包括 l）有多少个不达标的产品，即 $\left\lfloor \frac{l-1}{k} \right\rfloor + 1$
- 计算 r 之前（包括 r）有多少个不达标的产品，即 $\left\lfloor \frac{r}{k} \right\rfloor$ $+1$ 。
- 两者相减得到 l到 r 范围内不达标产品的数量。
输出每次检测中不达标产品的数量。

关键在于正确计算不达标产品的数量，通过计算区间 [l, r][l,r] 内不达标产品的个数，然后相减得到结果。这种方法简单且高效，适用于大规模的数据输入。

参考代码

#include<bits/stdc++.h>
using namespace std;
int n, k, l, r, x, y;
int main() {scanf("%d%d",&n,&k);while(n--) {scanf("%d%d",&l,&r);x=(l-1)/k+1, y=r/k+1;printf("%d\n",y-x);}return 0;
}

E. 寻宝达人（2023.5 NHOI 小学 5）

Description

小路从小就酷爱冒险寻宝，终于在某一天，小路进入了一个神秘山洞，这个山洞里面有很多关于宝藏的信息。小路通过超强的推理发现，这些信息中的有价值的信息，都暗藏一个字符串，例如，字符串为abc，那么abcefg，bbbabcddd，ertabc这些都是有价值的信息，而abderc这些就不是有价值的信息。

现在告诉你暗藏的字符串和一共有n条信息，请你帮忙小路计算一下，有多少条有价值的信息。

输入格式

输入数据有n+1行。

第一行输入一个正整数n和一个字符串，表示n条信息和暗藏的字符串。

接下来n行，每行一条信息字符串，表示一条信息。

输出格式

输出一行，一个整数，表示有价值的信息数量。

输入/输出例子1

输入：

4 abc

abcefg

bbbabcddd

ertabc

abderc

输出：

样例解释

【数据范围】

对于100%的数据，1<=n<=100，暗藏的字符串和信息字符串的长度小于等于100，并且只有小写字母组成。

题意

本题描述了小路在山洞中寻找宝藏信息的情景。小路发现有价值的信息都包含一个特定的暗藏字符串。现在需要计算在给定的 $n$ 条信息中，有多少条包含这个暗藏字符串。

思路

目的是帮助小路计算出有多少条信息包含特定的暗藏字符串，即有价值的信息。

输入读取一个整数 $n$ 和一个字符串 $a$ ，分别表示信息的数量和暗藏的字符串。
初始化一个计数器 $sum$ 来记录包含暗藏字符串的信息数量。
进入一个循环，循环 $n$ 次，每次读取一条信息字符串 $s$ 。
对于每条信息字符串 $n$ ，代码使用 $find$ 函数来查找暗藏字符串 $a$ 是否存在于 $s$ 中。 $find$ 函数返回第一次出现的子串位置，如果未找到子串，则返回 -1。
如果 $find$ 函数返回的值不是 -1，说明暗藏字符串 $a$ 存在于信息字符串 $s$ 中，因此将计数器 $sum$ 加一。
循环结束后，输出计数器 $sum$ 的值，即包含暗藏字符串的信息数量。

关键在于使用 $find$ 函数来检查每条信息字符串中是否包含特定的暗藏字符串。这种方法简单且直接，适用于本题的数据范围。代码的效率取决于字符串的长度和信息的数量，但对于本题的数据范围（ $1\leq$ $n$ $\leq 100$ ，字符串长度 $\leq 100$ ），这种方法是可行的。

参考答案

#include<bits/stdc++.h>
using namespace std;
int n, sum;
string a, s;
int main() {cin>>n>>a;for(int i=0; i<n; i++) {cin>>s;if(s.find(a)!=-1)sum++;}cout<<sum;return 0;
}

F. 珍珠项链（2023.5 NHOI 小学 6）

Description

小明妈妈有一条用n颗大小不同的珍珠串成的项链。有一天项链不幸断了，小明突发奇想，现在只能从项链的左端或者右端取走一颗珍珠并必须马上把这颗珍珠串入一个新的单向链中，他想知道他如果想串出从小到大的一条单向链，最多能取走多少颗珍珠？

输入格式

分两行输入。

第一行，一个整数n。

第二行，n个整数，空格分开，第i个整数表示a[i]，a[i]表示这颗珍珠在所有珍珠中的大小排名，例如a[i]=6，说明第i颗珍珠是所有珍珠第六小的那颗。

输出格式

一个整数，表示答案。

输入/输出例子1

输入：

1 2 3 4 5

输出：

输入/输出例子2

输入：

1 3 2 4

输出：

样例解释

【样例解释1】

每次拿最左边的珍珠，串成的长度为5.

【数据范围】

对于30%的数据， 1<=n<=20。

对于100%的数据，1<=n<=100000，1<=a[i]<=n，且保证n个数中没有相同的数据。

题意

本题描述了小明妈妈有一条由 $n$ 颗大小不同的珍珠组成的项链。小明想从项链的左端或右端取走一颗珍珠，并将其串入一个新的单向链中，使得这个新的链中的珍珠从小到大排列。小明想知道他最多能取走多少颗珍珠。

思路

这段C++代码的目的是计算小明最多能取走多少颗珍珠，以串成一条从小到大的单向链。代码的逻辑如下：

输入读取一个整数 $n$ ，表示珍珠的数量。
读取 $n$ 个整数，表示每颗珍珠的大小排名，并将它们存储在数组 $a$ 中。
初始化两个指针 $i$ 和 j，分别指向数组 a 的左端和右端，以及一个变量 x 来存储当前链中最大的珍珠排名。
进入一个循环，循环直到 i和 j 相遇或交叉。在每次迭代中，代码比较 a[i] 和 a[j] 的值：
- 如果a[i]≤a[j] 且a[i]>x，则将a[i] 添加到链中，并将 i 向右移动一位。
- 如果 a[i] > a[j] 且 a[j] > x，则将 a[j]添加到链中，并将 jj 向左移动一位。
- 如果 a[i] > x，则将 a[i]添加到链中，并将 i 向右移动一位。
- 如果 a[j] > x，则将 a[j]添加到链中，并将 j 向左移动一位。
- 如果 a[i] 和 a[j] 都不大于 x，则退出循环。
每次将珍珠添加到链中时，代码将计数器 ans 加一。
最后，输出计数器 ans 的值，即小明最多能取走的珍珠数量。

关键在于通过比较 a[i]和 a[j] 的值来决定从哪端取珍珠，以及如何更新链中最大的珍珠排名 x。这种方法确保了链中的珍珠始终从小到大排列，并且可以处理大量数据。

参考代码

#include<bits/stdc++.h>
using namespace std;
int n, a[100005], x, ans;
int main() {cin>>n;for(int i=0; i<n; i++) cin>>a[i];for(int i=0,j=n-1; i<=j;) {if(a[i]<=a[j]&&a[i]>x) {x=a[i++];ans++;} else if(a[i]>a[j]&&a[j]>x) {x=a[j--];ans++;} else if(a[i]>x) {x=a[i++];ans++;} else if(a[j]>x) {x=a[j--];ans++;} else {break;}}cout<<ans;return 0;
}