C/C++蓝桥杯算法真题打卡(Day6)

news/2025/3/18 19:57:19/

一、P8615 [蓝桥杯 2014 国 C] 拼接平方数 - 洛谷

方法一:算法代码(字符串分割法)

#include<bits/stdc++.h>  // 包含标准库中的所有头文件,方便编程
using namespace std;     // 使用标准命名空间,避免每次调用标准库函数时都要加 std::bool f[1000005];         // 定义一个布尔数组 f,用于标记某个数是否是完全平方数
int l, r;                // 定义两个整数 l 和 r,表示查询的范围 [l, r]
string s;                // 定义一个字符串 s,用于存储数字的字符串形式// 判断一个数是否是完全平方数
bool pfs(int x) {return (int)sqrt(x) == sqrt(x);  // 如果 x 的平方根的整数部分等于其平方根,则 x 是完全平方数
}int main() {cin >> l >> r;  // 读取输入的 l 和 r,表示查询的范围 [l, r]// 预处理:标记 [1, r] 范围内的所有完全平方数for (int i = 1; i <= r; i++) {if (pfs(i))  // 如果 i 是完全平方数f[i] = 1;  // 将 f[i] 标记为 1(true)}// 遍历 [l, r] 范围内的所有数for (int i = l; i <= r; i++) {if (f[i]) {  // 如果 i 是完全平方数s = to_string(i);  // 将 i 转换为字符串 sint sl = s.size();  // 获取字符串 s 的长度// 尝试将 s 分成两部分,判断这两部分是否都是完全平方数for (int j = 1; j < sl; j++) {int x = stoi(s.substr(0, j));  // 提取 s 的前 j 位,转换为整数 xint y = stoi(s.substr(j));     // 提取 s 的剩余部分,转换为整数 y// 如果 x 和 y 都是完全平方数if (f[x] && f[y]) {printf("%d\n", i);  // 输出 ibreak;  // 跳出内层循环,继续检查下一个 i}}}}return 0;  // 程序正常结束
}

代码思路

  1. 预处理完全平方数

    • 使用数组 f 标记 [1, r] 范围内的所有完全平方数。

    • 通过 pfs 函数判断一个数是否是完全平方数。

  2. 遍历查询范围

    • 对于 [l, r] 范围内的每个数 i,如果它是完全平方数,则将其转换为字符串 s

    • 尝试将 s 分成两部分,判断这两部分是否都是完全平方数。

  3. 输出符合条件的数

    • 如果找到满足条件的数 i,则输出它。


关键点

  • 完全平方数判断

    • 使用 sqrt 函数判断一个数是否是完全平方数。

    • 如果 (int)sqrt(x) == sqrt(x),则 x 是完全平方数。

  • 字符串分割

    • 将数字转换为字符串后,尝试将其分成两部分。

    • 使用 substr 函数提取子串,并使用 stoi 函数将子串转换为整数。

  • 范围查询

    • 只处理 [l, r] 范围内的数,确保程序效率。


方法二:算法代码(取模分割法)

#include<bits/stdc++.h>  // 包含标准库中的所有头文件,方便编程
using namespace std;     // 使用标准命名空间,避免每次调用标准库函数时都要加 std::bool f[1000005];         // 定义一个布尔数组 f,用于标记某个数是否是完全平方数
int l, r;                // 定义两个整数 l 和 r,表示查询的范围 [l, r]
string s;                // 定义一个字符串 s,用于存储数字的字符串形式(虽然在这段代码中未使用)// 判断一个数是否是完全平方数
bool pfs(int x) {return (int)sqrt(x) == sqrt(x);  // 如果 x 的平方根的整数部分等于其平方根,则 x 是完全平方数
}int main() {cin >> l >> r;  // 读取输入的 l 和 r,表示查询的范围 [l, r]// 预处理:标记 [1, r] 范围内的所有完全平方数for (int i = 1; i <= r; i++) {if (pfs(i))  // 如果 i 是完全平方数f[i] = 1;  // 将 f[i] 标记为 1(true)}// 遍历 [l, r] 范围内的所有数for (int i = l; i <= r; i++) {if (f[i]) {  // 如果 i 是完全平方数int k = 10;  // 初始化 k 为 10,用于分割数字// 尝试将 i 分成两部分,判断这两部分是否都是完全平方数for (int j = 1; j <= 5; j++) {  // 最多尝试 5 次分割,因为a和b的范围为10的6次方int x = i % k;  // 提取 i 的最后 j 位数字int y = i / k;  // 提取 i 的前面部分数字k *= 10;  // 将 k 乘以 10,用于下一次分割// 如果 x 和 y 都是完全平方数if (f[x] && f[y]) {printf("%d\n", i);  // 输出 ibreak;  // 跳出内层循环,继续检查下一个 i}}}}return 0;  // 程序正常结束
}

代码思路

  1. 预处理完全平方数

    • 使用数组 f 标记 [1, r] 范围内的所有完全平方数。

    • 通过 pfs 函数判断一个数是否是完全平方数。

  2. 遍历查询范围

    • 对于 [l, r] 范围内的每个数 i,如果它是完全平方数,则尝试将其分成两部分。

    • 使用变量 k 从 10 开始,逐步尝试将 i 分成两部分:

      • x = i % k:提取 i 的最后 j 位数字。

      • y = i / k:提取 i 的前面部分数字。

    • 检查 x 和 y 是否都是完全平方数。

  3. 输出符合条件的数

    • 如果找到满足条件的数 i,则输出它。


关键点

  • 完全平方数判断

    • 使用 sqrt 函数判断一个数是否是完全平方数。

    • 如果 (int)sqrt(x) == sqrt(x),则 x 是完全平方数。

  • 数字分割

    • 使用取模运算 % 和除法运算 / 将数字分成两部分。

    • 通过逐步增加 k 的值(10, 100, 1000, ...),尝试不同的分割方式。

  • 范围查询

    • 只处理 [l, r] 范围内的数,确保程序效率。

 

二、P8699 [蓝桥杯 2019 国 B] 排列数 - 洛谷(国赛题难啊qwq,已放弃ing)

大佬的算法代码: 

#include <bits/stdc++.h>  // 包含标准库中的所有头文件,方便编程
#define ll long long      // 定义宏 ll 表示 long long 类型
#define setp setprecision // 定义宏 setp 表示 setprecision 函数
#define mem(a, m) memset(a, m, sizeof(a))  // 定义宏 mem 表示 memset 函数
using namespace std;const int MOD = 123456;  // 定义常量 MOD,表示取模的值
int n, k;                // 定义两个整数 n 和 k,分别表示排列的长度和单调排列的折点数
int dp[505][505];        // 定义二维数组 dp,用于动态规划// 自定义取模函数
int mod(int a) {return a % MOD;  // 返回 a 对 MOD 取模的结果
}int main() {ios::sync_with_stdio(false);  // 关闭同步流,提高输入输出效率cin >> n >> k;  // 读取输入的 n 和 kdp[1][0] = 1;  // 初始化 dp[1][0] = 1,表示长度为 1 的排列有 1 种情况// 动态规划填充 dp 数组for(int i = 2; i < n; i++) {  // 遍历排列的长度从 2 到 n-1dp[i][0] = 2;  // 初始化 dp[i][0] = 2,表示长度为 i 的排列有 2 种单调排列for(int j = 0; j <= i; j++) {  // 遍历可能的折点数// 更新 dp[i+1][j],表示在长度为 i+1 的排列中,折点数为 j 的情况dp[i+1][j] += mod(dp[i][j] * (j + 1));// 更新 dp[i+1][j+1],表示在长度为 i+1 的排列中,折点数为 j+1 的情况dp[i+1][j+1] += mod(dp[i][j] * 2);// 更新 dp[i+1][j+2],表示在长度为 i+1 的排列中,折点数为 j+2 的情况dp[i+1][j+2] += mod(dp[i][j] * (i - j - 2));}}cout << dp[n][k-1] % MOD;  // 输出长度为 n 的排列中,折点数为 k-1 的情况数,并对 MOD 取模return 0;  // 程序正常结束
}

大佬的思路(牛牛牛):


http://www.ppmy.cn/news/1580146.html

相关文章

Microsoft Outlook 2024 LTSC for Mac v16.95 电子邮件和日历 支持M、Intel芯片

应用介绍 Microsoft Outlook 2024 LTSC for Mac 是微软为Mac用户推出的一款电子邮件管理和日历应用&#xff0c;属于长期服务通道&#xff08;LTSC&#xff09;版本&#xff0c;适合需要稳定性和长期支持的企业用户。它提供了强大的邮件管理功能、日历功能以及团队协作工具&am…

深度学习 Deep Learning 第1章 深度学习简介

第1章 深度学习简介 概述 本章介绍人工智能&#xff08;AI&#xff09;和深度学习领域&#xff0c;讨论其历史发展、关键概念和应用。解释深度学习如何从早期的AI和机器学习方法演变而来&#xff0c;以及如何有效解决之前方法无法应对的挑战。 关键概念 1. 人工智能的演变 …

【最佳实践】Go 状态模式

设计思路 状态模式的核心在于将对象的行为封装在特定的状态类中&#xff0c;使得对象在不同的状态下表现出不同的行为。每个状态实现同一个接口&#xff0c;允许对象在运行时通过改变其内部状态对象来改变其行为。状态模式使得状态转换更加明确&#xff0c;并且易于扩展新的状…

coding ability 展开第四幕(滑动指针——巩固篇)超详细!!!!

文章目录 前言水果成篮思路 找到字符串中所有字母异位词思路 串联所有单词的子串思路 最小覆盖子串思路 总结 前言 本专栏上一篇博客&#xff0c;带着大家从认识滑动窗口到慢慢熟悉 相信大家对滑动窗口已经有了大概的认识 其实主要就是抓住——一段连续的区间 今天来学习一些滑…

GaussDB备份数据常用命令

1、常用备份命令gs_dump 说明&#xff1a;是一个服务器端工具&#xff0c;可以在线导出数据库的数据&#xff0c;这些数据包含整个数据库或数据库中指定的对象&#xff08;如&#xff1a;模式&#xff0c;表&#xff0c;视图等&#xff09;&#xff0c;并且支持导出完整一致的数…

物联网(IoT)平台层中 大数据处理过程

在物联网(IoT)平台层中,大数据处理是一个核心环节,它负责对海量设备数据进行采集、存储、处理和分析,以提取有价值的信息并支持上层应用。以下是物联网平台层中大数据处理的技术实现、架构设计和解决方案。 大数据处理的主要流程 物联网中的大数据处理通常包括以下几个阶…

LeetCode 1005. K 次取反后最大化的数组和 java题解

https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/ 看着简单但是写si人的一题。 class Solution {public int largestSumAfterKNegations(int[] nums, int k) {Arrays.sort(nums);//排序int last_negative-1,first_positive-1;//最后一个负…