【入门3】循环结构
虽然计算机可以在短时间批量处理成千上万条指令，但是不少问题中有许多规律性的重复操作，比如说计算几百个学生的平均分，或者对上万人的名单进行排序。仅使用顺序或者分支结构，对每一步操作都写出对应的语句是不可能的；但可以使用循环语句让计算机反复执行类似的任务。
本章将会介绍循环结构程序设计，同时前面的内容也会进一步的巩固。学完这一章，读者可以初步感受到计算机高效解决问题的能力。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7RjWTXd5-1680532688470)(2023-03-22-15-52-46.png)]
【深基4.例4】一尺之棰
# 【深基4.例4】一尺之棰
## 题目描述
《庄子》中说到，“一尺之棰，日取其半，万世不竭”。第一天有一根长度为 $a$ 的木棍，从第二天开始，每天都要将这根木棍锯掉一半（每次除 $2$，向下取整）。第几天的时候木棍的长度会变为 $1$？
## 输入格式
输入一个正整数 $a$，表示木棍长度。
## 输出格式
输出一个正整数，表示要第几天的时候木棍长度会变为 $1$。
## 样例 #1
### 样例输入 #1
```
100
```
### 样例输出 #1
```
7
```
## 提示
数据保证，$1 \le a\le 10^9$。\
while 循环，每次除以
2
2，如果到一了，退出循环。
code:
# include <iostream>
# include <stdio.h>
using namespace std;
int a, ans = 1;
int main () {
scanf ("%d", &a);
while (a > 1) {
ans++;
a /= 2;
}
cout << ans << endl;
return 0;
}
【深基4.例6】数字直角三角形
# 【深基4.例6】数字直角三角形
## 题目描述
给出 $n$，请输出一个直角边长度是 $n$ 的数字直角三角形。所有数字都是 $2$ 位组成的，如果没有 $2$ 位则加上前导 $0$。
## 输入格式
输入一个正整数 $n$。
## 输出格式
输出如题目要求的数字直角三角形。
## 样例 #1
### 样例输入 #1
```
5
```
### 样例输出 #1
```
0102030405
06070809
101112
1314
15
```
## 提示
数据保证，$1\le n\le13$。
这题还是有点技巧的
可以看出要输出
�
(
�
+
1
)
a(a+1)个数
每行输出a,a-1……，1个数
所以用i记录现在要输出什么
j记录在第几列
j>a之后就换行
输出是注意所有数字都是 2 位组成的即可
std:
#include <iostream>
#include <algorithm>
using namespace std;
int a,b;
int main()
{
int i,j,k;
cin>>a;
b=a;
a=a*(a+1)/2;
j=1;
i=1;
while(i<=a)
{
if(i<10)
{
cout<<0<<i;
}
else
{
cout<<i;
}
i++;
j++;
if(j>b)
{
b--;
j=1;
cout<<endl;
}
}
return 0;
}
解法2
这道题不坑,也不难
唯一不好解决的就是
所有数字都是 2 位组成的，如果没有 2 位则加上前导 0。
这里介绍一种巧妙又方便的方法:
printf("%02d",变量名);
下面上代码:
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,t=0,a;//t表示当前需要输出的数字
cin>>n;
a=n;//a控制列数
for(int i=0;i<n;i++){//n行
for(int j=0;j<a;j++){//每行a列
t++;//需要输出的数+1
//这里必须先加再输出,不然好像会出错
//因为这里先加再输出,所以t需要初始化为0
printf("%02d",t);//高级方法
}
a--;//每输出一行,减少一列
cout<<endl;//换行
}
return 0;//完美结束
}
[NOIP1998 普及组] 阶乘之和
# [NOIP1998 普及组] 阶乘之和
## 题目描述
用高精度计算出 $S = 1! + 2! + 3! + \cdots + n!$（$n \le 50$）。
其中 `!` 表示阶乘，定义为 $n!=n\times (n-1)\times (n-2)\times \cdots \times 1$。例如，$5! = 5 \times 4 \times 3 \times 2 \times 1=120$。
## 输入格式
一个正整数 $n$。
## 输出格式
一个正整数 $S$，表示计算结果。
## 样例 #1
### 样例输入 #1
```
3
```
### 样例输出 #1
```
9
```
## 提示
**【数据范围】**
对于 $100 \%$ 的数据，$1 \le n \le 50$。
**【其他说明】**
注，《深入浅出基础篇》中使用本题作为例题，但是其数据范围只有 $n \le 20$，使用书中的代码无法通过本题。
如果希望通过本题，请继续学习第八章高精度的知识。
C_Z_C
更新时间：2019-08-18 20:25:27
在 Ta 的博客查看
本蒟的第一篇题解，不要问我为什么要发这篇题解，昨天用了半天才写完了这篇橙题代码，大佬勿喷。
**本蒟的思路就是高精乘+高精加，就是把高精乘的模板套上去接着套高精加的模板，b=c=i的阶乘。**
话不多说，直接上代码：
#include<iostream>
#include<cstring>
using namespace std;
int n,a[90],b[90],c[90],f[90],d=0,len_a,len_b=1,len_c=1,len_ans,m=1;
string s;
int main(){
cin>>n;
b[0]=1; //初始化
for(int i=1;i<=n;i++){ //计算i的阶乘，已经算好了i-1的阶乘
len_a=0; //i的长度
int p=i;
while(p>0){ //把i存进a数组
a[len_a++]=p%10;
p/=10;
}
for(int j=0;j<len_a;j++) //计算a*b（i*（i-1）的阶乘），即i的阶乘，看不懂的网上查，我也不知道为什么
for(int k=0;k<=len_b;k++)
c[j+k]+=a[j]*b[k];
for(int j=0;j<len_c;j++) //需要进位的就进位
if(c[j]>9) c[j+1]+=c[j]/10,c[j]%=10;
if(c[len_c]) len_c++; //看最高位要不要进位
len_ans=len_b,len_b=len_c,m=max(m,len_c); //把len_b赋值给len_ans，修改len_b的值，m为i阶乘的长度，看有没有进位
for(int k=len_c-1;k>=0;k--) b[k]=c[k]; //把c存进b数组，即存进i的阶乘，下次循环b为i-1的阶乘
len_c=len_a+len_ans;
memset(c,0,sizeof(c)); //清零c数组，准备计算下个阶乘
for(int j=0;j<m;j++){ //高精加，直接套模板
f[j]+=b[j];
if(f[j]>9) f[j+1]+=f[j]/10,f[j]%=10; //进位，注意不要写成f[j+1]++，f[j]-=10;就因为这里wa了一个点
}
}
while(!f[m]&&m>0) m--; //去掉首导零
for(int i=m;i>=0;i--) cout<<f[i]; //倒序输出
return 0; //圆满结束
}
[NOIP2013 普及组] 计数问题
# [NOIP2013 普及组] 计数问题
## 题目描述
试计算在区间 $1$ 到 $n$ 的所有整数中，数字 $x$（$0\le x\le9$）共出现了多少次？例如，在 $1$ 到 $11$ 中，即在 $1,2,3,4,5,6,7,8,9,10,11$ 中，数字 $1$ 出现了 $4$ 次。
## 输入格式
$2$ 个整数 $n,x$，之间用一个空格隔开。
## 输出格式
$1$ 个整数，表示 $x$ 出现的次数。
## 样例 #1
### 样例输入 #1
```
11 1
```
### 样例输出 #1
```
4
```
## 提示
对于 $100\%$ 的数据，$1\le n\le 10^6$，$0\le x \le 9$。
#include<iostream>
using namespace std;
int main()
{
long long n,i,x,b,c,t=0;
cin>>n>>x;//输入范围与要查的数字；
for(i=1;i<=n;i++)//一到n进行循环；
{
b=i;//为了不改变i的值，就把i赋值给一个数；
while(b!=0)//如果b不等于0，继续循环；
{
c=b%10;//求是否是x，是的话计数器加一；
b=b/10;//求下一个数字是否为x；
if(c==x) t++;计数器加一；
}
}
cout<<t<<endl;//输出计数器的数字；
return 0;//结束
}
方法2
用的最笨的办法，一步一步的循环解的思路，希望有更优的解题思路，以供参考
#include <stdio.h>
int main(){
int a,b,j=0;
scanf("%d %d",&a,&b);
for(int i=1;i<=a;i++){
int d=i;
while(d>0){
int c=d%10;
d=d/10;
if(c==b){
j++;
}
}
}
printf("%d",j);
return 0;
}
方法3
John_Nash
更新时间：2016-02-08 20:39:46
在 Ta 的博客查看
这题是noip2013普及组第一题，难度肯定不大，nlog10n的算法不难想出，这里不再说明。
在真正的比赛中，只要想到能ac的算法就可以，但是在练习中还是要锻炼自己的思维，多想想更优的算法。
不难发现，即使不用计算机，答案也很容易求出，如：
n=728，x=7
可以按照这样的思路：
个位7:73个 7,17,...,727
十位7:70个 70~79,170~179,...,670~679
百位7:29个 700~728
答案是172
这样，就不难写出log10n的算法，这是一个巨大的改进！
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
int n,x,m=1,ans=0;
scanf("%d%d",&n,&x);
while(m<=n){
int a=n/(m*10),b=n/m%10,c=n%m; //a,b,c为n的三部分，求哪一位x的个数，b就为那一位数，a为b左边的数，c为b右边的数，如求1~728中十位7的个数，则a=7，b=2，c=8
if(x){
if(b>x) ans+=(a+1)*m; //如果b>x，说明有(a+1)*m个x（如求1~728中个位7的个数，则为（72+1）*1=73）
if(b==x) ans+=a*m+c+1; //如果b=x，说明有a*m+c+1个x（如求1~728中百位7的个数，则为0*100+28+1=29）
if(b<x) ans+=a*m; //如果b<x，说明有a*m个x（如求1~728中十位7的个数，则为7*10个）
}
else{ //x=0的情况和x！=0的情况有所不同
if(b) ans+=a*m;
else ans+=(a-1)*m+c+1;
}
m*=10;
}
printf("%d\n",ans);
return 0;
}
[NOIP2002 普及组] 级数求和
https://www.luogu.com.cn/problem/P1035
# [NOIP2002 普及组] 级数求和
## 题目描述
已知：$S_n= 1+\frac{1}{2}+\frac{1}{3}+…+\frac{1}{n}$。显然对于任意一个整数 $k$，当 $n$ 足够大的时候，$S_n>k$。
现给出一个整数 $k$，要求计算出一个最小的 $n$，使得 $S_n>k$。
## 输入格式
一个正整数 $k$。
## 输出格式
一个正整数 $n$。
## 样例 #1
### 样例输入 #1
```
1
```
### 样例输出 #1
```
2
```
## 提示
**【数据范围】**
对于 $100\%$ 的数据，$1\le k \le 15$。
**【题目来源】**
NOIP 2002 普及组第一题
https://www.luogu.com.cn/problem/solution/P1035
1.模拟
这种做法的思路是枚举
n从1开始，直到>
Sn>k结束，只需要一个循环即可实现。
代码：
#include<cstdio>
int main() {
int k,n=0;
scanf("%d",&k);
for(double Sn=0;Sn<=k;++n,Sn+=1.0/n);
printf("%d",n);
return 0;
}
2.数论（调和级数）
关于调和级数的姿势，点这里。
已知
�
�
=
1
+
1
/
2
+
1
/
3
+
.
.
.
+
1
/
�
=
∑
�
=
1
�
1
�
Sn=1+1/2+1/3+...+1/n=∑
k=1
n
k
1
。
明显地，
�
�
Sn为第
�
n个调和数。
欧拉推导过求调和级数有限多项和的表达式为
∑
�
=
1
�
1
�
=
ln
(
�
+
1
)
+
�
∑
k=1
n
k
1
=ln(n+1)+γ，我们拿过来用即可。（
�
γ约等于0.5772156649）
我们需要满足
�
�
>
�
Sn>k，即满足
ln
(
�
+
1
)
+
�
>
�
ln(n+1)+γ>k，化简得
�
>
�
�
−
�
−
1
n>e
k−γ
−1。
我们只需求满足上式的最小的
�
n，所以
�
=
�
�
−
�
+
0.5
n=e
k−γ
+0.5（四舍五入），即模拟做法的时间复杂度为
�
(
�
�
−
�
)
O(e
k−γ
)。
关于
�
γ（欧拉-马歇罗尼常数）的姿势，点这里。
代码：
#include<cstdio>
#include<cmath>
const double gamma=0.5772156649;
int main() {
int k,n;
scanf("%d",&k);
n=exp(k-gamma)+0.5;
printf("%d",n);
return 0;
}
P2669 [NOIP2015 普及组] 金币
# [NOIP2015 普及组] 金币
## 题目背景
NOIP2015 普及组 T1
## 题目描述
国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币……；这种工资发放模式会一直这样延续下去：当连续 $n$ 天每天收到 $n$ 枚金币后，骑士会在之后的连续 $n+1$ 天里，每天收到 $n+1$ 枚金币。
请计算在前 $k$ 天里，骑士一共获得了多少金币。
## 输入格式
一个正整数 $k$，表示发放金币的天数。
## 输出格式
一个正整数，即骑士收到的金币数。
## 样例 #1
### 样例输入 #1
```
6
```
### 样例输出 #1
```
14
```
## 样例 #2
### 样例输入 #2
```
1000
```
### 样例输出 #2
```
29820
```
## 提示
**【样例 1 说明】**
骑士第一天收到一枚金币；第二天和第三天，每天收到两枚金币；第四、五、六天，每天收到三枚金币。因此一共收到 $1+2+2+3+3+3=14$ 枚金币。
对于 $100\%$ 的数据，$1\le k\le 10^4$。
#include<iostream>
using namespace std;
int main()
{
int a,b=0,c=1,i;//a为天数，b为金币，c为每天比原来每天多获得的金币数
cin>>a;
for(i=1;i<=a;i++)
a-=i,b+=c*c,c++;//金币每天加上c的2次方，天数当然要减i了
cout<<b+a*c;//最后算上剩余的a乘加的最多一次的c
return 0;
}
#include<iostream>
using namespace std;
int main(){
int a,b=0,c=1,i;cin>>a;for(i=1;i<=a;i++)a-=i,b+=c*c,c++;cout<<b+a*c;//挤在了一行上
}
#include <iostream>
//反对万能头！
using namespace std;
int n,q,c,s;
//n是有多少天
//s是获得的金币总量
//c是每天能获得的金币数
//q表示往后数q天，获得的金币都是c个
int main()
{
cin>>n;
c=q=1; //第一天（往后的一天），获得1个金币
for(int i=1;i<=n;i++) //要发n天金币
{
s+=c; //累加
q--; //已经发了一天
if(q==0) //要更新数据
{
c++; //每天获得金币的数量+1
q=c; //根据题意，以后的c天都是c个金币，q就是c
}
}
cout<<s; //输出
return 0; //THE END
}
P3383 【模板】线性筛素数
# 【模板】线性筛素数
## 题目背景
本题已更新，从判断素数改为了查询第 $k$ 小的素数
提示：如果你使用 `cin` 来读入，建议使用 `std::ios::sync_with_stdio(0)` 来加速。
## 题目描述
如题，给定一个范围 $n$，有 $q$ 个询问，每次输出第 $k$ 小的素数。
## 输入格式
第一行包含两个正整数 $n,q$，分别表示查询的范围和查询的个数。
接下来 $q$ 行每行一个正整数 $k$，表示查询第 $k$ 小的素数。
## 输出格式
输出 $q$ 行，每行一个正整数表示答案。
## 样例 #1
### 样例输入 #1
```
100 5
1
2
3
4
5
```
### 样例输出 #1
```
2
3
5
7
11
```
## 提示
【数据范围】
对于 $100\%$ 的数据，$n = 10^8$，$1 \le q \le 10^6$，保证查询的素数不大于 $n$。
Data by NaCly\_Fish.
https://www.luogu.com.cn/problem/solution/P3383
网上有很多关于筛素数的帖子、博文，可以自学一下。
P1217 [USACO1.5]回文质数 Prime Palindromes
# [USACO1.5]回文质数 Prime Palindromes
## 题目描述
因为 $151$ 既是一个质数又是一个回文数（从左到右和从右到左是看一样的），所以 $151$ 是回文质数。
写一个程序来找出范围 $[a,b] (5 \le a < b \le 100,000,000)$（一亿）间的所有回文质数。
## 输入格式
第一行输入两个正整数 $a$ 和 $b$。
## 输出格式
输出一个回文质数的列表，一行一个。
## 样例 #1
### 样例输入 #1
```
5 500
```
### 样例输出 #1
```
5
7
11
101
131
151
181
191
313
353
373
383
```
## 提示
Hint 1: Generate the palindromes and see if they are prime.
提示 1: 找出所有的回文数再判断它们是不是质数（素数）.
Hint 2: Generate palindromes by combining digits properly. You might need more than one of the loops like below.
提示 2: 要产生正确的回文数，你可能需要几个像下面这样的循环。
题目翻译来自NOCOW。
USACO Training Section 1.5
产生长度为 $5$ 的回文数：
```cpp
for (d1 = 1; d1 <= 9; d1+=2) { // 只有奇数才会是素数
for (d2 = 0; d2 <= 9; d2++) {
for (d3 = 0; d3 <= 9; d3++) {
palindrome = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;//(处理回文数...)
}
}
}
```
方法1（打表）
打表
哈哈哈哈真爽
#include<cstdio>
#include<cstring>
using namespace std;
int a,b,db[800]={0,2,3,5,7,11,101,131,151,181,
191,313,353,373,383,727,757,787,797,
919,929,10301,10501,10601,11311,11411,12421,12721,
12821,13331,13831,13931,14341,14741,15451,15551,16061,
16361,16561,16661,17471,17971,18181,18481,19391,19891,
19991,30103,30203,30403,30703,30803,31013,31513,32323,
32423,33533,34543,34843,35053,35153,35353,35753,36263,
36563,37273,37573,38083,38183,38783,39293,70207,70507,
70607,71317,71917,72227,72727,73037,73237,73637,74047,
74747,75557,76367,76667,77377,77477,77977,78487,78787,
78887,79397,79697,79997,90709,91019,93139,93239,93739,
94049,94349,94649,94849,94949,95959,96269,96469,96769,
97379,97579,97879,98389,98689,1003001,1008001,1022201,1028201,
1035301,1043401,1055501,1062601,1065601,1074701,1082801,1085801,1092901,
1093901,1114111,1117111,1120211,1123211,1126211,1129211,1134311,1145411,
1150511,1153511,1160611,1163611,1175711,1177711,1178711,1180811,1183811,
1186811,1190911,1193911,1196911,1201021,1208021,1212121,1215121,1218121,
1221221,1235321,1242421,1243421,1245421,1250521,1253521,1257521,1262621,
1268621,1273721,1276721,1278721,1280821,1281821,1286821,1287821,1300031,
1303031,1311131,1317131,1327231,1328231,1333331,1335331,1338331,1343431,
1360631,1362631,1363631,1371731,1374731,1390931,1407041,1409041,1411141,
1412141,1422241,1437341,1444441,1447441,1452541,1456541,1461641,1463641,
1464641,1469641,1486841,1489841,1490941,1496941,1508051,1513151,1520251,
1532351,1535351,1542451,1548451,1550551,1551551,1556551,1557551,1565651,
1572751,1579751,1580851,1583851,1589851,1594951,1597951,1598951,1600061,
1609061,1611161,1616161,1628261,1630361,1633361,1640461,1643461,1646461,
1654561,1657561,1658561,1660661,1670761,1684861,1685861,1688861,1695961,
1703071,1707071,1712171,1714171,1730371,1734371,1737371,1748471,1755571,
1761671,1764671,1777771,1793971,1802081,1805081,1820281,1823281,1824281,
1826281,1829281,1831381,1832381,1842481,1851581,1853581,1856581,1865681,
1876781,1878781,1879781,1880881,1881881,1883881,1884881,1895981,1903091,
1908091,1909091,1917191,1924291,1930391,1936391,1941491,1951591,1952591,
1957591,1958591,1963691,1968691,1969691,1970791,1976791,1981891,1982891,
1984891,1987891,1988891,1993991,1995991,1998991,3001003,3002003,3007003,
3016103,3026203,3064603,3065603,3072703,3073703,3075703,3083803,3089803,
3091903,3095903,3103013,3106013,3127213,3135313,3140413,3155513,3158513,
3160613,3166613,3181813,3187813,3193913,3196913,3198913,3211123,3212123,
3218123,3222223,3223223,3228223,3233323,3236323,3241423,3245423,3252523,
3256523,3258523,3260623,3267623,3272723,3283823,3285823,3286823,3288823,
3291923,3293923,3304033,3305033,3307033,3310133,3315133,3319133,3321233,
3329233,3331333,3337333,3343433,3353533,3362633,3364633,3365633,3368633,
3380833,3391933,3392933,3400043,3411143,3417143,3424243,3425243,3427243,
3439343,3441443,3443443,3444443,3447443,3449443,3452543,3460643,3466643,
3470743,3479743,3485843,3487843,3503053,3515153,3517153,3528253,3541453,
3553553,3558553,3563653,3569653,3586853,3589853,3590953,3591953,3594953,
3601063,3607063,3618163,3621263,3627263,3635363,3643463,3646463,3670763,
3673763,3680863,3689863,3698963,3708073,3709073,3716173,3717173,3721273,
3722273,3728273,3732373,3743473,3746473,3762673,3763673,3765673,3768673,
3769673,3773773,3774773,3781873,3784873,3792973,3793973,3799973,3804083,
3806083,3812183,3814183,3826283,3829283,3836383,3842483,3853583,3858583,
3863683,3864683,3867683,3869683,3871783,3878783,3893983,3899983,3913193,
3916193,3918193,3924293,3927293,3931393,3938393,3942493,3946493,3948493,
3964693,3970793,3983893,3991993,3994993,3997993,3998993,7014107,7035307,
7036307,7041407,7046407,7057507,7065607,7069607,7073707,7079707,7082807,
7084807,7087807,7093907,7096907,7100017,7114117,7115117,7118117,7129217,
7134317,7136317,7141417,7145417,7155517,7156517,7158517,7159517,7177717,
7190917,7194917,7215127,7226227,7246427,7249427,7250527,7256527,7257527,
7261627,7267627,7276727,7278727,7291927,7300037,7302037,7310137,7314137,
7324237,7327237,7347437,7352537,7354537,7362637,7365637,7381837,7388837,
7392937,7401047,7403047,7409047,7415147,7434347,7436347,7439347,7452547,
7461647,7466647,7472747,7475747,7485847,7486847,7489847,7493947,7507057,
7508057,7518157,7519157,7521257,7527257,7540457,7562657,7564657,7576757,
7586857,7592957,7594957,7600067,7611167,7619167,7622267,7630367,7632367,
7644467,7654567,7662667,7665667,7666667,7668667,7669667,7674767,7681867,
7690967,7693967,7696967,7715177,7718177,7722277,7729277,7733377,7742477,
7747477,7750577,7758577,7764677,7772777,7774777,7778777,7782877,7783877,
7791977,7794977,7807087,7819187,7820287,7821287,7831387,7832387,7838387,
7843487,7850587,7856587,7865687,7867687,7868687,7873787,7884887,7891987,
7897987,7913197,7916197,7930397,7933397,7935397,7938397,7941497,7943497,
7949497,7957597,7958597,7960697,7977797,7984897,7985897,7987897,7996997,
9002009,9015109,9024209,9037309,9042409,9043409,9045409,9046409,9049409,
9067609,9073709,9076709,9078709,9091909,9095909,9103019,9109019,9110119,
9127219,9128219,9136319,9149419,9169619,9173719,9174719,9179719,9185819,
9196919,9199919,9200029,9209029,9212129,9217129,9222229,9223229,9230329,
9231329,9255529,9269629,9271729,9277729,9280829,9286829,9289829,9318139,
9320239,9324239,9329239,9332339,9338339,9351539,9357539,9375739,9384839,
9397939,9400049,9414149,9419149,9433349,9439349,9440449,9446449,9451549,
9470749,9477749,9492949,9493949,9495949,9504059,9514159,9526259,9529259,
9547459,9556559,9558559,9561659,9577759,9583859,9585859,9586859,9601069,
9602069,9604069,9610169,9620269,9624269,9626269,9632369,9634369,9645469,
9650569,9657569,9670769,9686869,9700079,9709079,9711179,9714179,9724279,
9727279,9732379,9733379,9743479,9749479,9752579,9754579,9758579,9762679,
9770779,9776779,9779779,9781879,9782879,9787879,9788879,9795979,9801089,
9807089,9809089,9817189,9818189,9820289,9822289,9836389,9837389,9845489,
9852589,9871789,9888889,9889889,9896989,9902099,9907099,9908099,9916199,
9918199,9919199,9921299,9923299,9926299,9927299,9931399,9932399,9935399,
9938399,9957599,9965699,9978799,9980899,9981899,9989899,
781};
int main()
{
scanf("%d %d",&a,&b);
for(int i=1;i<=781;i++)
if(db[i]>=a && db[i]<=b) printf("%d\n",db[i]);
return 0;
}
/*const int N=100000001;
int P[N],a,b,ans,sum;
bool Isp[N];
void Euler(int x){>//欧拉筛法
for(int i=2;i<=x;i++){
if(Isp[i]) P[++P[0]]=i;
for(int j=1;i*P[j]<=x && j<=P[0];j++){
Isp[i*P[j]]=false;
if(i%P[j]==0) break;
}
}
}
bool hw(int x)
{
int x2=x,y=0;
while (x2!=0)
{
y=y*10+x2%10;
x2/=10;
}
if (x==y) return true;
else return false;
}
int main()
{
memset(Isp,true,sizeof(Isp));Isp[1]=0;
scanf("%d %d",&a,&b);
Euler(b);
for(int i=a;i<=b;i++)
if(hw(i) && Isp[i]){
printf("%d,",i);
sum++;
if(sum%9==0) printf("\n");
}
printf("\n%d",sum);
return 0;
}*/
方法2（观察数据特征）
我用的不是制造回文数，是从a找到b。那怎么会不超时呢？
1、我从奇数开始找，每次+2；
2、我发现，没有偶数位的回文质数！省了一大把的时间啊！
虽说还是很慢，不过很好写就是了！哈哈。
下面列核心的三个判断：
bool ok(int k) //回文数
{
int a[10],i=0;
while (k>0){a[i]=k%10;k/=10;i++;}
for(int j=0;j<i;j++)if(a[j]!=a[i-j-1])return false;
return true;
}
bool ws(int k) //位数
{
if(k>=10 && k<100 && k!=11 || k>=1000 && k<10000)return false;
if(k>=100000 && k<1000000 || k>=10000000 && k<100000000)return false;
return true;
}
bool ss(int k) //素数
{
for(int i=3;i*i<=k;i+=2)if(k%i==0)return false;
return true;
}
更优的方法是制造回文数，这个我就不说了。给个赞吧！
P1720 月落乌啼算钱（斐波那契数列）
# 月落乌啼算钱（斐波那契数列）
## 题目背景
（本道题目木有隐藏歌曲……不用猜了……）
《爱与愁的故事第一弹·heartache》最终章。
吃完 pizza，月落乌啼知道超出自己的预算了。为了不在爱与愁大神面前献丑，只好还是硬着头皮去算钱……
## 题目描述
算完钱后，月落乌啼想着：“你 TMD 坑我，（以下用闽南语读）归粒靠杯靠亩诶，（以下用英读）是伊特游！”于是当爱与愁大神问多少钱时，月落乌啼说了一堆乱码。爱与愁大神说：“算了算了，我只问第 $n$ 样菜价格多少？”月落乌啼写出了：
$$F_n=\dfrac{(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n}{\sqrt{5}}$$
[]()
由于爱与愁大神学过编程，于是就用 $1$ 分钟的时间求出了 $F_n$ 的结果。月落乌啼为此大吃一惊。你能学学爱与愁大神求出 $F_n$ 的值吗？
## 输入格式
一行一个自然数 $n$。
## 输出格式
只有 $1$ 行一个实数 $F_n$，保留两位小数。
## 样例 #1
### 样例输入 #1
```
6
```
### 样例输出 #1
```
8.00
```
## 提示
对于所有数据：$0 \leq n\leq 48$。
警策看取
更新时间：2019-10-22 19:04:32
在 Ta 的博客查看
这题是一个求斐波那契数列的题。
提供5种解法。
解法1
递归。
代码
#include <bits/stdc++.h>
using namespace std;
long long f(int n) {
if(n == 1||n == 2)return 1;
return f(n - 1) + f(n - 2);
}
int main() {
int n;
cin >> n;
cout << f(n) <<".00"<< endl;
return 0;
}
可是，超时。
在洛谷，似乎没有无限栈，还爆空间了。
那么，有什么办法可以解决这个问题呢？
于是，就有了解法2.
解法2
可以记录已经算过的值，避免重复计算，大大提升效率。
代码
#include <bits/stdc++.h>
using namespace std;
long long fa[100] = { 0, 1, 1 };//前几个写进去
long long f(int n) {
if (!fa[n]) {//算过的直接返回，没算过的计算
fa[n] = f(n - 1) + f(n - 2);
}
return fa[n];
}
int main() {
int n;
cin >> n;
cout << f(n) <<".00"<< endl;
return 0;
}
但是，WA，80.
为什么呢？
问题出在if (!fa[n])这边。当输入是0时，
�
(
0
)
=
0
f(0)=0,因此会又递归，所以WA了。
那么，应该加个特判，或用其他方法解决问题，代码这里不贴了，大家自己想想吧。
但是，有没有更好理解的办法呢？
解法3
递推。
代码
#include <bits/stdc++.h>
using namespace std;
int f[50] = { 0, 1, 1 };
int main() {
int n;
cin >> n;
for (int i = 3; i <= n; ++i) {
f[i] = f[i - 1] + f[i - 2];//按照斐波那契的公式算。
}
cout << f[n] << ".00";
return 0;
}
额外提供两种解法。
解法4
三变量法。
#include<bits/stdc++.h>
using namespace std;
int main(){
long long a,b,c=0,num=0;
cin>>num;
a=b=1;//初始值为1
for(int i=3;i<=num;++i){
c=b+a;//算第个数
a=b;//b的值赋给a
b=c;//c的值赋给b
}
cout<<c<<".00";
return 0;
}
能理解的尽量理解吧。
解法5
公式法。
P5724 【深基4.习5】求极差 / 最大跨度值
# 【深基4.习5】求极差 / 最大跨度值
## 题目描述
给出 $n$ 和 $n$ 个整数 $a_i$，求这 $n$ 个整数中的极差是什么。极差的意思是一组数中的最大值减去最小值的差。
## 输入格式
第一行输入一个正整数 $n$，表示整数个数。
第二行输入 $n$ 个整数 $a_1,a_2 \dots a_n$，以空格隔开。
## 输出格式
输出一个整数，表示这 $n$ 个整数的极差。
## 样例 #1
### 样例输入 #1
```
6
1 1 4 5 1 4
```
### 样例输出 #1
```
4
```
## 提示
数据保证，$1 \leq n\leq 100$，$0\le a_i \le 1000$。
我的思路是将存在a数组里，然后sort一边，用a[n] 即最大- a[1] 即最小即可食用
#include<bits/stdc++.h>
using namespace std;
int a[100001];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
sort(a+1,a+n+1);
cout<<a[n]-a[1];
return 0;
}
P1075 [NOIP2012 普及组] 质因数分解
# [NOIP2012 普及组] 质因数分解
## 题目描述
已知正整数 $n$ 是两个不同的质数的乘积，试求出两者中较大的那个质数。
## 输入格式
输入一个正整数 $n$。
## 输出格式
输出一个正整数 $p$，即较大的那个质数。
## 样例 #1
### 样例输入 #1
```
21
```
### 样例输出 #1
```
7
```
## 提示
$1 \le n\le 2\times 10^9$
NOIP 2012 普及组 第一题
本题考数学。
首先要知道唯一分解定理:一个数能且只能分解为一组质数的乘积。可知，若输入的数满足题目条件，他就只能分解为两个质数的乘积。所以在比他小且大于1的自然数中，只有那两个数能整除它，之间不可能再有任何合数或质数能整除它了，因为最小的能整除它的合数已经是他本身了。
所以代码就很容易实现了
#include<cstdio>
int main()
{
int n;
scanf("%d",&n);
for(int i=2;i<=n;++i)
if(n%i==0)
{
printf("%d",n/i);
return 0;
}
}
P5725 【深基4.习8】求三角形
# 【深基4.习8】求三角形
## 题目描述
模仿例题，打印出不同方向的正方形，然后打印三角形矩阵。中间有个空行。
## 输入格式
输入矩阵的规模，不超过 $9$。
## 输出格式
输出矩形和正方形
## 样例 #1
### 样例输入 #1
```
4
```
### 样例输出 #1
```
01020304
05060708
09101112
13141516
01
0203
040506
07080910
```
luosw
更新时间：2020-03-17 09:10:08
在 Ta 的博客查看
愉快的模拟。
我们先来分析一下题意：
题意简述
模仿例题，打印出不同方向的正方形，然后打印三角形矩阵。中间有个空行。
只有这么多了，好，不说废话，开始分析。
题目分析
这道题我们可以采取这样的策略：
靠循环解决问题
我们需要两个大号的循环分别输出正方形和三角形。
正方形只要判断循环变量
�
≡
1
(
m
o
d
�
)
i≡1(modn) 我们就换行，如果小于
10
10就在前面补
0
0。
三角形则需要建立一个变量
�
�
�
cnt 来输出数字，用前面的空格数量
�
i 来作为 while 循环的条件。
好，分析结束，上代码。
代码
#include<bits/stdc++.h>
using namespace std;
int n,i,cnt;
int main(){
scanf("%d",&n);
for(i=1;i<=n*n;i++){
if(i%n==1&&i!=1){
printf("\n"); //如果到了边缘就换行
}
if(i<10){
printf("0"); //如果小于10就输出0
}
printf("%d",i); //输出数字
}
printf("\n\n"); //中间的空行和最后一行正方形的换行
i=2*n;
while(i>0){//按照剩余的空位判断
i-=2;
for(int j=0;j<i;j++){
printf(" ");
}
for(int j=0;j<(2*n-i)/2;j++){
cnt++;
if(cnt<10){
printf("0");
}
printf("%d",cnt);
}
printf("\n");
}
return 0;
}
P5726 【深基4.习9】打分
# 【深基4.习9】打分
## 题目描述
现在有 $n(n \le 1000)$ 位评委给选手打分，分值从 $0$ 到 $10$。需要去掉一个最高分，去掉一个最低分（如果有多个最高或者最低分，也只需要去掉一个），剩下的评分的平均数就是这位选手的得分。现在输入评委人数和他们的打分，请输出选手的最后得分，精确到 $2$ 位小数。
## 输入格式
第一行输入一个正整数 $n$，表示有 $n$ 个评委。
第二行输入 $n$ 个正整数，第 $i$ 个正整数表示第 $i$ 个评委打出的分值。
## 输出格式
输出一行一个两位小数，表示选手的最后得分。
## 样例 #1
### 样例输入 #1
```
5
9 5 6 8 9
```
### 样例输出 #1
```
7.67
```
## 提示
数据保证，$3 \leq n \leq 1000$，每个评委打出的分值为为 $0$ 到 $10$（含 $0$ 与 $10$）之间的整数。
#include<bits/stdc++.h>
using namespace std;
int n,a[10001];
double ans;
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
for(int i=2;i<=n-1;i++) ans+=a[i];
printf("%.2lf",ans/(n-2));
return 0;
}
P1089 [NOIP2004 提高组] 津津的储蓄计划
# [NOIP2004 提高组] 津津的储蓄计划
## 题目描述
津津的零花钱一直都是自己管理。每个月的月初妈妈给津津 $300$ 元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。
为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上 $20\%$ 还给津津。因此津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于 $100$ 元或恰好 $100$ 元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。
例如 $11$月初津津手中还有 $83$ 元，妈妈给了津津 $300$ 元。津津预计$11$月的花销是 $180$ 元，那么她就会在妈妈那里存 $200$ 元，自己留下 $183$ 元。到了 $11$ 月月末，津津手中会剩下 $3$ 元钱。
津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。
现在请你根据 $2004$ 年 $1$ 月到 $12$ 月每个月津津的预算，判断会不会出现这种情况。如果不会，计算到 $2004$ 年年末，妈妈将津津平常存的钱加上 $20\%$ 还给津津之后，津津手中会有多少钱。
## 输入格式
$12$ 行数据，每行包含一个小于 $350$ 的非负整数，分别表示 $1$ 月到 $12$ 月津津的预算。
## 输出格式
一个整数。如果储蓄计划实施过程中出现某个月钱不够用的情况，输出 $-X$，$X$ 表示出现这种情况的第一个月；否则输出到 $2004$ 年年末津津手中会有多少钱。
注意，洛谷不需要进行文件输入输出，而是标准输入输出。
## 样例 #1
### 样例输入 #1
```
290
230
280
200
300
170
340
50
90
80
200
60
```
### 样例输出 #1
```
-7
```
## 样例 #2
### 样例输入 #2
```
290
230
280
200
300
170
330
50
90
80
200
60
```
### 样例输出 #2
```
1580
```
#include<iostream>
using namespace std;
int money,cost,mama,flag=1,monthofdeath; //money代表在津津手里的钱，cost代表花费的钱，mama代表在妈妈手里的100元的张数，flag=1代表尚未透支，monthofdeath代表死亡月份
int main ()
{
for(int i=1;i<=12;i++)
{
money+=300; //每个月津津手里的钱都会增加300
cin>>cost; //输入这个月的花销
money-=cost; // 津津手里的钱减去这个月的花销等于剩余的钱
if(money<0) //若剩余的钱小于0,
{
flag=0; //旗帜倒下，即已经透支
monthofdeath=i; //输出死亡月份
break; //终止循环
}
mama+=money/100; //剩余的钱整除100即为在妈妈手里的100元的张数
money%=100; //用100去模剩余的钱即为月底幸存的钱
}
if(flag==1) //若旗帜未倒下，即坚持到年底还没有透支
{
money+=mama*120; //剩余的钱
cout<<money;
}
else
{
cout<<-monthofdeath;
}
return 0;
}
