当前位置：首页 > news >正文

洛谷-循环结构（1）

news 2025/7/4 8:37:00

洛谷-循环结构（1）

P5718 【深基4.例2】找最小值

题目描述

给出 $n$ 和 $n$ 个整数 $a_i$ ，求这 $n$ 个整数中最小值是什么。

ps:

1.不建议用数组结合冒泡排序（或者库函数的方法），因为事前不知道数组大小，可能要new出新空间或者使用vector，麻烦！
2.题目找最小值，通过min不断更新即可

代码：

#include<iostream>
using namespace std;
int main() {int n;cin >> n;int min;cin >> min;for (int i = 0; i < n - 1; i++) {int a;cin >> a;if (a < min)min = a;}cout << min;return 0;}

P5720 【深基4.例4】一尺之棰

题目描述

《庄子》中说到，“一尺之棰，日取其半，万世不竭”。第一天有一根长度为 $a$ 的木棍，从第二天开始，每天都要将这根木棍锯掉一半（每次除 $2$ ，向下取整）。第几天的时候木棍的长度会变为 $1$ ？

ps：

注意day从1开始（如果day初始为0，记得最后cout的时候+1）

代码：

#include<iostream>
using namespace std;
int main() {int a,day=1;cin >> a;while (a != 1) {a /= 2;day++;}cout << day;return 0;
}

（最重要）P1009 [NOIP 1998 普及组] 阶乘之和

题目描述

用高精度计算出 $\cdots + n!$ （ $\le 50$ ）。

其中 ! 表示阶乘，定义为 $n!=n\times (n-1)\times (n-2)\times \cdots \times 1$ 。例如， $\times 4 \times 3 \times 2 \times 1=120$ 。

ps：难点：

1.高精度乘法

高精度乘法是用vector（容器，简单理解为-可伸缩的数组）来存储每一位上面的数字，并通过编程的方法模拟竖式乘法的操作（1.留下个位（存到数组当中）2.进位（满十向前进位））。
编程实现过程中还要记得：1.反转输出 2.去除前导0
2.高精度加法

高进度加法相对简单些，原理和高进度乘法类似，也是模拟进位。
3.阶乘递进计算

借用上一次算好的阶乘而不是从头算一次阶乘
pps：这里的高进度乘法使用的是“大数”和小数相乘的写法

代码

#include<iostream>
#include<vector>
using namespace std;vector<int>add(const vector<int>& a, const vector<int>& b) {int carry = 0;//处理进位的情况int i = 0,j=0;// 记录位数vector<int>result;while (i < a.size() || j < b.size() || carry)//判断条件：每一位确保相加，处理好进位{/*a如果是123456789，那么vector<int>a就是9,8,7,6,5,4,3,2,1，对b同理*/int x = (i < a.size() ? a[i++] : 0);int y = (j < b.size() ? b[j++] : 0);int temp = x + y + carry;result.push_back(temp % 10);carry =temp/ 10;}//不用处理前导0（不会发生）return result;
}vector<int>multipy(const vector<int>& a, int b) {int carry = 0;vector<int>result;for (int i = 0; i < a.size() || carry; i++) {int temp = carry;/*temp += a[i] * b + carry;*//*写条件语句是为了处理i>size()但是carry的进位没有处理好的情况，此时还用a[i]就越界了*/if(i<a.size())temp += a[i] * b ;result.push_back(temp % 10);carry =temp/ 10;}// 去除前导0（例如b是0的时候，只用一个0就可以了）/*while (result[result.size() - 1] == 0) {result.pop_back();}*/while ( result.size()>1&&result.back() == 0 )result.pop_back();return result;
}void print(const vector<int>& result) {/*for (int i = 0; i < result.size(); i++) {cout << result[i];}*/for (int i = result.size() - 1; i >= 0; i--)cout << result[i];
}int main() {int n;cin >> n;vector<int>fac = { 1 }, sum = {0};for (int i = 1; i <= n; i++) {fac = multipy(fac, i);sum = add(sum, fac);}print(sum);return 0;
}

P1980 [NOIP 2013 普及组] 计数问题

题目背景

NOIP2013 普及组 T1

题目描述

试计算在区间 $1$ 到 $n$ 的所有整数中，数字 $x$ （ $0\le x\le9$ ）共出现了多少次？例如，在 $1$ 到 $11$ 中，即在 $1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11$ 中，数字 $1$ 出现了 $4$ 次。

PS:（小心思）每一位取模，条件判断

pps：虽然感觉字符串一个个读取会快一些，但是还不大会字符串。。。而且最多六位数，六次循环也很快的。。。

代码：

#include<iostream>using namespace std;
int main() {int n;int number;int count = 0;cin >> n >> number;for (int i = 1; i <= n; i++) {int _count = i;while (_count) {if (_count % 10 == number)count++;_count /=10;}}cout<<count;return 0;
}

P1035 [NOIP 2002 普及组] 级数求和

题目描述

已知： $S_n= 1+\dfrac{1}{2}+\dfrac{1}{3}+…+\dfrac{1}{n}$ 。显然对于任意一个整数 $k$ ，当 $n$ 足够大的时候， $S_n>k$ 。

现给出一个整数 $k$ ，要求计算出一个最小的 $n$ ，使得 $S_n>k$ 。

输入格式

一个正整数 $k$ 。

输出格式

一个正整数 $n$ 。

ps：注意for循环中的条件是<=（作者本人当初就是个写>的🤡）

代码

#include<iostream>
using namespace std;
int main() {double sum = 0;double k, count = 0;cin >> k;for (int i = 1; sum <= k; i++) {sum += 1.0 / i;count++;//cout << "i:" << sum << "count:" << count << endl;}cout << count;return 0;
}

P2669 [NOIP 2015 普及组] 金币

题目背景

NOIP2015 普及组 T1

题目描述

国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币……；这种工资发放模式会一直这样延续下去：当连续 $n$ 天每天收到 $n$ 枚金币后，骑士会在之后的连续 $n + 1$ 天里，每天收到 $n + 1$ 枚金币。

请计算在前 $k$ 天里，骑士一共获得了多少金币。

输入格式

一个正整数 $k$ ，表示发放金币的天数。

输出格式

一个正整数，即骑士收到的金币数。

PS:

1.可以发现i枚金币要发i天，也就是总共i*i，注意到day的重要性
2.循环中的sum += i * i;day += i;，计算过去了i天，所以day+=i，这样逻辑清晰，也跳步完成
3.关于day+i < k，是看下一个金币周期是否可以发完

代码

#include<iostream>
using namespace std;
int main() {int sum=0, k,day=0,i;cin >> k;for ( i = 1; day + i < k; ++i) {sum += i * i;day += i;}sum += i * (k - day);cout << sum;return 0;
}

（重要）P1217 [USACO1.5] 回文质数 Prime Palindromes

题目描述

因为 $151$ 既是一个质数又是一个回文数（从左到右和从右到左是看一样的），所以 $151$ 是回文质数。

写一个程序来找出范围 $\le a < b \le 100,000,000)$ （一亿）间的所有回文质数。

输入格式

第一行输入两个正整数 $a$ 和 $b$ 。

输出格式

输出一个回文质数的列表，一行一个。

输入输出样例 #1

输入 #1

5 500

输出 #1

说明/提示

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$ 的回文数：

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;//(处理回文数...)}}}

PS:

眼见这题只有伤心泪，好不容易写出判断回文数的函数，组装起来发现超时了（wc）。题解的逻辑是建立一个回文数表，之后判断是否是质数。
小心思：回文数的代码用count记录位数，可以减少遍历9次

代码（我的超时型代码）

#include<iostream>
#include<cmath>
using namespace std;bool is_zhi_shu(int i) {if (i == 1||(i%2==0&&i!=2))return false;else if (i == 2)return true;else {//原先写成<=sqrt(i)+1导致9也放进去了for (int j = 3; j <=sqrt(i); j++) {if (i%j == 0) {return false;break;}}return true;}
}bool is_hui_wen(int *a) {int orignal[9] = { 0 }, back[9] = { 0 };int remember=*a;int count = 0;//记录有几位for (int i = 0; remember != 0; i++) {orignal[i] = remember % 10;//cout << "orignal:" << orignal[i] << ' ';back[8 - i] = remember % 10;//cout << " back:" << back[8 - i];remember /=10;count++;//cout <<" count:"<<count<< " remember:" << remember << endl;}for (int i = 0; i < count; i++) {if (orignal[i] != back[9-count+ i])return false;}return true;
}bool is_hui_zhi(int *a) {//没放参数还可以不报错？return (is_hui_wen(a) && is_zhi_shu(*a));
}int main() {int a,b;cin >> a>>b;/*for (int i = a; i <= b; i++) {if (is_hui_zhi(i))cout << i << endl;}*/for (int i = a; i <= b; i++) {if (is_hui_wen(&i)) {if (is_zhi_shu(i)){cout << i << endl;}}else continue;}return 0;}

AC代码

#include <iostream>
#include <vector>
using namespace std;// 优化的质数判断
bool isPrime(int n) {if (n <= 1) return false;if (n == 2) return true;if (n % 2 == 0) return false;if (n == 3) return true;if (n % 3 == 0) return false;for (int i = 5; i * i <= n; i += 6) {if (n % i == 0 || n % (i + 2) == 0) {return false;}}return true;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int a, b;cin >> a >> b;vector<int> result;// 预计算所有可能的回文质数（数量很少）// 实际上在1亿范围内，回文质数数量极少// 1位数回文质数if (a <= 2 && b >= 2) result.push_back(2);if (a <= 3 && b >= 3) result.push_back(3);if (a <= 5 && b >= 5) result.push_back(5);if (a <= 7 && b >= 7) result.push_back(7);// 2位数回文数：11, 22, 33, ..., 99// 只有11是质数if (a <= 11 && b >= 11) result.push_back(11);// 3位数回文数for (int d1 = 1; d1 <= 9; d1++) {for (int d2 = 0; d2 <= 9; d2++) {int palindrome = 100 * d1 + 10 * d2 + d1;if (palindrome >= a && palindrome <= b && isPrime(palindrome)) {result.push_back(palindrome);}if (palindrome > b) break;}if (100 * d1 > b) break;}// 4位数回文数：所有4位回文数都是11的倍数，所以除了1111都不是质数// 1111 = 11 * 101，不是质数，所以4位数没有回文质数// 5位数回文数for (int d1 = 1; d1 <= 9; d1 += 2) { // 只考虑奇数if (10000 * d1 > b) break;for (int d2 = 0; d2 <= 9; d2++) {if (10000 * d1 + 1000 * d2 > b) break;for (int d3 = 0; d3 <= 9; d3++) {int palindrome = 10000 * d1 + 1000 * d2 + 100 * d3 + 10 * d2 + d1;if (palindrome > b) break;if (palindrome >= a && isPrime(palindrome)) {result.push_back(palindrome);}}}}// 6位数回文数：所有6位回文数都能被11整除，所以都不是质数// 7位数回文数for (int d1 = 1; d1 <= 9; d1 += 2) { // 只考虑奇数if (1000000 * d1 > b) break;for (int d2 = 0; d2 <= 9; d2++) {if (1000000 * d1 + 100000 * d2 > b) break;for (int d3 = 0; d3 <= 9; d3++) {if (1000000 * d1 + 100000 * d2 + 10000 * d3 > b) break;for (int d4 = 0; d4 <= 9; d4++) {int palindrome = 1000000 * d1 + 100000 * d2 + 10000 * d3 + 1000 * d4 + 100 * d3 + 10 * d2 + d1;if (palindrome > b) break;if (palindrome >= a && isPrime(palindrome)) {result.push_back(palindrome);}}}}}// 8位数回文数：所有8位回文数都能被11整除，所以都不是质数// 输出结果for (int prime : result) {cout << prime << '\n';}return 0;
}