[蓝桥杯 2014 国 C] 拼接平方数

题目描述

小明发现 $49$ 很有趣，首先，它是个平方数。它可以拆分为 $4$ 和 $9$，拆分出来的部分也是平方数。$169$ 也有这个性质，我们权且称它们为：拼接平方数。

$100$ 可拆分 $1,00$，这有点勉强，我们规定，$0,00,000$ 等都不算平方数。

小明想：还有哪些数字是这样的呢？

你的任务出现了：找到某个区间的所有拼接平方数。

输入格式

两个正整数 $a,b(a<b<10^6)$。

输出格式

若干行，每行一个正整数。表示所有的区间 $[a,b]$ 中的拼接平方数，从小到大输出。

样例 #1

样例输入 #1

169 10000

样例输出 #1

169
361
1225
1444
1681
3249
4225
4900
9025

提示

时限 1 秒, 256M。蓝桥杯 2014 年第五届国赛

---

解题思路

我们可以直接从 $a$ 开始遍历到到 $b$ ，判断其是否是平方数，在该数字是平方数的情况下，将数字拆分去判断拆分出来的两部分数是否是平方数。

拆分数字可以将数字转成字符串，使用 $substr$ 来拆分数字，再将得到的两个字符串用 $stoi$ 转成数字来判断是否是平方数。

include <bits/stdc++.h>
using namespace std;

//判断数字是否为平方数
//一个数的平方根减去其小数部分为0，说明该数为平方数
bool check(int x)
{
    double d=sqrt(x)-(int)sqrt(x);
    return d==0.0;
}

int main()
{
    int a,b;
    cin>>a>>b;
    for(int i=a;i<=b;++i)
    {
        //在数字为平方数的情况下再去拆分数字
        if(check(i))
        {
            string str=to_string(i);
            for(int k=1;k<str.size();++k)
            {
                string s1=str.substr(0,k),s2=str.substr(k);
                int p1=stoi(s1),p2=stoi(s2);
                //排除题目提及的0的特殊情况
                if(p2 == 0) break;
                //拆分出来的两个数也是平方数，说明i是拼接平方数
                if(check(p1)&&check(p2))
                {
                    cout<<i<<endl;
                    break;
                }
            }
        }
    }
    return 0;
}

---

[蓝桥杯 2019 国 B] 排列数

题目描述

在一个排列中，一个折点是指排列中的一个元素，它同时小于两边的元素，或者同时大于两边的元素。

对于一个 $1\sim n$ 的排列，如果可以将这个排列中包含 $t$ 个折点，则它称为一个 $t+1$ 单调排列。

例如，排列 $(1,4,2,3)$ 是一个 $3$ 单调排列，其中 $4$ 和 $2$ 都是折点。

给定 $n$ 和 $k$，请问 $1\sim n$ 的所有排列中有多少个 $k$ 单调排列？

输入格式

输入一行包含两个整数 $n$, $k$。

输出格式

输出一个整数，表示答案。答案可能很大，你可需要输出满足条件的排列
数量除以 $123456$ 的余数即可。

样例 #1

样例输入 #1

4 2

样例输出 #1

12

提示

对于 $20\%$ 的评测用例, $1\le k\le n\le 10$;

对于 $40\%$ 的评测用例, $1\le k\le n\le 20$; 对于 $60\%$ 的评测用例, $1\le k\le n\le 100$;

对于所有评测用例， $1\le k\le n\le 500$ 。

蓝桥杯 2019 年国赛 B 组 G 题。

---

解题思路

注意到题目给定的数据范围是 $n\le 500$ ，所以不能用暴力解法，很很明显我们要使用动态规划来解决这道问题。

$dp[i][j]$ 代表有 $j$ 个节点的序列 $1\sim i$ 的排列个数。

接下来我们推状态转移方程：

在序列 $1\sim i$ 中插入第 $i+1$ 个数，这个数比原序列的所有数都要大，并且这个数有 $i+1$ 个位置可以插入。

1. $dp[i+1][j]$ 表示插入第 $i+1$ 个节点后没有新增折点。

下面我们分情况讨论：
峰谷

峰谷峰

所以我们其实可以推出，折点数为 $j$ ，插入第 $i+1$ 个数后折点数不变的情况其实有 $j+1$ 种。（谷峰谷、峰谷峰谷的情况都是这样）

故递推公式 $dp[i+1][j]+=dp[i][j]\times (j+1)$

2. $dp[i+1][j+1]$ 表示插入第 $i+1$ 个节点后新增1个折点。

新增一个节点的情况很简单，只有序列两端是下降趋势，且插入位置是序列前后端才能新增一个节点，所以只有两种情况

故递归公式 $dp[i+1][j+1]+=dp[i][j]\times 2$

3. $dp[i+1][j+2]$ 表示插入第 $i+1$ 个节点后新增2个折点。

插入第 $i+1$ 个数有 $i+1$ 个位置可以插入，而增加折点的情况只有0个、1个、2个，所以新增2个折点的情况数我们可以用总的可插入位置个数减去上面提到的新增0个和1个折点的情况就能得到。

新增两个折点有 $i+1-(j+1)-2=i-j-2$ 种情况。

故递推公式 $dp[i+1][j+1]+=dp[i][j]\times (i-j-2)$

初始情况：$dp[1][0]=0$ ，序列只有1个数0个折点的情况只有1种

$dp[i][0]=2(2\le i\le n)$ ，$i$ 个数0个折点的情况是完全升序和完全降序两种情况。

最终答案为 $dp[n][k-1]$ ($k-1$个折点对应 $k$ 单调序列)

#include <bits/stdc++.h>
using namespace std;

int dp[505][505];
int n,k;
//得到的个数可能过大，需要取模处理
int mod(int x)
{
    return x%123456;
}

int main()
{
    cin>>n>>k;
    dp[1][0]=1;
    for(int i=2;i<=n;++i)
    {
        dp[i][0]=2;
        for(int j=0;j<=i;j++)
        {
            //取模处理
            dp[i+1][j] += mod(dp[i][j]*(j+1));
            dp[i+1][j+1] += mod(dp[i][j]*2);
            dp[i+1][j+2] += mod(dp[i][j]*(i-j-2));
        }
    }
    cout<<dp[n][k-1]%123456<<endl;
    return 0;
}