临沂网站哪家好,苏州高端企业网站建设,哈市最新公告,互联网公司运营是做什么的文章目录 [蓝桥杯 2014 国 C] 拼接平方数[蓝桥杯 2019 国 B] 排列数 [蓝桥杯 2014 国 C] 拼接平方数
题目描述
小明发现 49 49 49 很有趣#xff0c;首先#xff0c;它是个平方数。它可以拆分为 4 4 4 和 9 9 9#xff0c;拆分出来的部分也是平方数。 169 169 169 也有… 文章目录 [蓝桥杯 2014 国 C] 拼接平方数[蓝桥杯 2019 国 B] 排列数 [蓝桥杯 2014 国 C] 拼接平方数
题目描述
小明发现 49 49 49 很有趣首先它是个平方数。它可以拆分为 4 4 4 和 9 9 9拆分出来的部分也是平方数。 169 169 169 也有这个性质我们权且称它们为拼接平方数。 100 100 100 可拆分 1 , 00 1,00 1,00这有点勉强我们规定 0 , 00 , 000 0,00,000 0,00,000 等都不算平方数。
小明想还有哪些数字是这样的呢
你的任务出现了找到某个区间的所有拼接平方数。
输入格式
两个正整数 a , b ( a b 1 0 6 ) a,b(ab10^6) a,b(ab106)。
输出格式
若干行每行一个正整数。表示所有的区间 [ a , b ] [a,b] [a,b] 中的拼接平方数从小到大输出。
样例 #1
样例输入 #1
169 10000样例输出 #1
169
361
1225
1444
1681
3249
4225
4900
9025提示
时限 1 秒, 256M。蓝桥杯 2014 年第五届国赛 解题思路
我们可以直接从 a a a 开始遍历到到 b b b 判断其是否是平方数在该数字是平方数的情况下将数字拆分去判断拆分出来的两部分数是否是平方数。
拆分数字可以将数字转成字符串使用 s u b s t r substr substr 来拆分数字再将得到的两个字符串用 s t o i stoi stoi 转成数字来判断是否是平方数。
include bits/stdc.h
using namespace std;//判断数字是否为平方数
//一个数的平方根减去其小数部分为0说明该数为平方数
bool check(int x)
{double dsqrt(x)-(int)sqrt(x);return d0.0;
}int main()
{int a,b;cinab;for(int ia;ib;i){//在数字为平方数的情况下再去拆分数字if(check(i)){string strto_string(i);for(int k1;kstr.size();k){string s1str.substr(0,k),s2str.substr(k);int p1stoi(s1),p2stoi(s2);//排除题目提及的0的特殊情况if(p2 0) break;//拆分出来的两个数也是平方数说明i是拼接平方数if(check(p1)check(p2)){coutiendl;break;}}}}return 0;
}[蓝桥杯 2019 国 B] 排列数
题目描述
在一个排列中一个折点是指排列中的一个元素它同时小于两边的元素或者同时大于两边的元素。
对于一个 1 ∼ n 1 ∼ n 1∼n 的排列如果可以将这个排列中包含 t t t 个折点则它称为一个 t 1 t 1 t1 单调排列。
例如排列 ( 1 , 4 , 2 , 3 ) (1, 4, 2, 3) (1,4,2,3) 是一个 3 3 3 单调排列其中 4 4 4 和 2 2 2 都是折点。
给定 n n n 和 k k k请问 1 ∼ n 1 ∼ n 1∼n 的所有排列中有多少个 k k k 单调排列
输入格式
输入一行包含两个整数 n n n, k k k。
输出格式
输出一个整数表示答案。答案可能很大你可需要输出满足条件的排列 数量除以 123456 123456 123456 的余数即可。
样例 #1
样例输入 #1
4 2样例输出 #1
12提示
对于 20 % 20 \% 20% 的评测用例, 1 ≤ k ≤ n ≤ 10 1 \leq k \leq n \leq 10 1≤k≤n≤10;
对于 40 % 40 \% 40% 的评测用例, 1 ≤ k ≤ n ≤ 20 1 \leq k \leq n \leq 20 1≤k≤n≤20; 对于 60 % 60 \% 60% 的评测用例, 1 ≤ k ≤ n ≤ 100 1 \leq k \leq n \leq 100 1≤k≤n≤100;
对于所有评测用例 1 ≤ k ≤ n ≤ 500 1 \leq k \leq n \leq 500 1≤k≤n≤500 。
蓝桥杯 2019 年国赛 B 组 G 题。 解题思路
注意到题目给定的数据范围是 n ≤ 500 n \leq 500 n≤500 所以不能用暴力解法很很明显我们要使用动态规划来解决这道问题。 d p [ i ] [ j ] dp[i][j] dp[i][j] 代表有 j j j 个节点的序列 1 ∼ i 1 ∼ i 1∼i 的排列个数。
接下来我们推状态转移方程
在序列 1 ∼ i 1 ∼ i 1∼i 中插入第 i 1 i 1 i1 个数这个数比原序列的所有数都要大并且这个数有 i 1 i 1 i1 个位置可以插入。 d p [ i 1 ] [ j ] dp[i 1][j] dp[i1][j] 表示插入第 i 1 i 1 i1 个节点后没有新增折点。
下面我们分情况讨论 峰谷 峰谷峰 所以我们其实可以推出折点数为 j j j 插入第 i 1 i 1 i1 个数后折点数不变的情况其实有 j 1 j 1 j1 种。谷峰谷、峰谷峰谷的情况都是这样
故递推公式 d p [ i 1 ] [ j ] d p [ i ] [ j ] × ( j 1 ) dp[i 1][j] dp[i][j] \times (j 1) dp[i1][j]dp[i][j]×(j1) d p [ i 1 ] [ j 1 ] dp[i 1][j 1] dp[i1][j1] 表示插入第 i 1 i 1 i1 个节点后新增1个折点。
新增一个节点的情况很简单只有序列两端是下降趋势且插入位置是序列前后端才能新增一个节点所以只有两种情况
故递归公式 d p [ i 1 ] [ j 1 ] d p [ i ] [ j ] × 2 dp[i 1][j 1] dp[i][j] \times 2 dp[i1][j1]dp[i][j]×2 d p [ i 1 ] [ j 2 ] dp[i 1][j 2] dp[i1][j2] 表示插入第 i 1 i 1 i1 个节点后新增2个折点。
插入第 i 1 i 1 i1 个数有 i 1 i 1 i1 个位置可以插入而增加折点的情况只有0个、1个、2个所以新增2个折点的情况数我们可以用总的可插入位置个数减去上面提到的新增0个和1个折点的情况就能得到。
新增两个折点有 i 1 − ( j 1 ) − 2 i − j − 2 i 1 - (j 1) - 2 i - j - 2 i1−(j1)−2i−j−2 种情况。
故递推公式 d p [ i 1 ] [ j 1 ] d p [ i ] [ j ] × ( i − j − 2 ) dp[i 1][j 1] dp[i][j] \times (i - j - 2) dp[i1][j1]dp[i][j]×(i−j−2)
初始情况 d p [ 1 ] [ 0 ] 0 dp[1][0] 0 dp[1][0]0 序列只有1个数0个折点的情况只有1种 d p [ i ] [ 0 ] 2 ( 2 ≤ i ≤ n ) dp[i][0] 2 (2 \leq i \leq n) dp[i][0]2(2≤i≤n) i i i 个数0个折点的情况是完全升序和完全降序两种情况。
最终答案为 d p [ n ] [ k − 1 ] dp[n][k - 1] dp[n][k−1] ( k − 1 k - 1 k−1个折点对应 k k k 单调序列)
#include bits/stdc.h
using namespace std;int dp[505][505];
int n,k;
//得到的个数可能过大需要取模处理
int mod(int x)
{return x%123456;
}int main()
{cinnk;dp[1][0]1;for(int i2;in;i){dp[i][0]2;for(int j0;ji;j){//取模处理dp[i1][j] mod(dp[i][j]*(j1));dp[i1][j1] mod(dp[i][j]*2);dp[i1][j2] mod(dp[i][j]*(i-j-2));}}coutdp[n][k-1]%123456endl;return 0;
}
