一、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; // 程序正常結束
}代碼思路
-
預處理完全平方數：
-
使用數組?
f?標記?[1, r]?范圍內的所有完全平方數。 -
通過?
pfs?函數判斷一個數是否是完全平方數。
-
-
遍歷查詢范圍：
-
對于?
[l, r]?范圍內的每個數?i，如果它是完全平方數，則將其轉換為字符串?s。 -
嘗試將?
s?分成兩部分，判斷這兩部分是否都是完全平方數。
-
-
輸出符合條件的數：
-
如果找到滿足條件的數?
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; // 程序正常結束
}代碼思路
-
預處理完全平方數：
-
使用數組?
f?標記?[1, r]?范圍內的所有完全平方數。 -
通過?
pfs?函數判斷一個數是否是完全平方數。
-
-
遍歷查詢范圍：
-
對于?
[l, r]?范圍內的每個數?i，如果它是完全平方數，則嘗試將其分成兩部分。 -
使用變量?
k?從 10 開始，逐步嘗試將?i?分成兩部分：-
x = i % k：提取?i?的最后?j?位數字。 -
y = i / k：提取?i?的前面部分數字。
-
-
檢查?
x?和?y?是否都是完全平方數。
-
-
輸出符合條件的數：
-
如果找到滿足條件的數?
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; // 程序正常結束
}大佬的思路（牛牛牛）：
