不算前言的前言：去年年底斥巨资报考了蓝桥杯，其实本人考完csp后完全疲惫变懒了…但想到花出的钱！…觉得这两周还是得练一下之前的真题，咱就是说也不能完全打水漂对吧…
OK让咱们先从最近的一次考试开始！！
贴出一个真题网址：蓝桥杯真题
平方差
给定 L,R，问 L ≤ x ≤ R中有多少个数 x满足存在整数 y,z使得 x = y2−z2。
输入格式
输入一行包含两个整数 L,R，用一个空格分隔。
输出格式
输出一行包含一个整数满足题目给定条件的 x 的数量。
数据范围
对于 40%的评测用例，1 ≤ L,R ≤ 5000；
对于所有评测用例，1 ≤ L ≤ R ≤ 109。
输入样例：
1 5
输出样例：
4
样例解释
1=12−02；
3=22−12；
4=22−02；
5=32−22。
这一题很明显遍历是会超时的；而且很明显这种题目的捷径好像和代码逻辑上的优化没太大关系…主要从数学的原理上下手；
代码撰写参考了这份博客：AcWing 4996. 🌟详解+O(1)简洁写法（附证明）
主要涉及数学原理上，我应该怎么来找到这样的平方差数（这样的平方差数有什么数学特性，可以让我在遍历的时候直接根据这个简化的特性大大减少搜索难度，减少时间的开销）
根据平方差公式，若有：x = y2 - z2，则 x = (y + z) * (y - z)
令A = (y + z) ，B = (y - z) ，则有 A - B = 2 * z； 也就是说 A, B两数之差为偶数，则A, B 的组合只能是同为奇数或者同为偶数
转化为 x 的性质：x 可以看作两个奇数的乘积或者是两个偶数的乘积；继续变抽象为具象，这样的转化可以具体化为 x 的怎样的性质。接下来我们分情况讨论，在这两种情况下，可以得到的最大共性是什么
如果一个数字是两个奇数的乘积：因为1本身为奇数，所以所有的奇数都可以写作 奇数 * 1；也就是所有的奇数都可以表示成为两个奇数的乘积。此时找到最大的共性特质。
如果一个数字是两个偶数的乘积：则这个数字必然是4的倍数。此时找到最大的共性特质
整理来说，x 如果是奇数，或者是4的倍数，那么这个数字必然可以写作平方差的形式
下面写给出一种超时写法：洛谷上过了，但是C语言网和acwing都超时了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll l, r; cin >> l >> r;
int cnt = 0;
for(int i = l; i <= r; i ++){
if(i & 1 || i % 4 == 0) cnt ++;
}
cout << cnt;
return 0;
}
此时这个写法还是在遍历，只是在判断数字是否符合条件的时候将时间复杂度下降到了O（1）但是搜索遍历的数量级还是到了1e9级别；所以此时涉及优化。其实也很简单，就是求一个区间内奇数的个数和4的倍数的个数
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//返回0 - x 之内的奇数个数加上4的倍数的个数
int fun(ll x)
{
//下面两种写法都可以
//return x / 4 + (x + 1) / 2;
return (x / 4 + ceil(x / double(2)));
}
int main()
{
ll l, r; cin >> l >> r;
cout << fun(r) - fun(l - 1);
return 0;
}
更小的数
小蓝有一个长度均为 n 且仅由数字字符 0∼9组成的字符串，下标从 0 到 n−1，你可以将其视作是一个具有 n位的十进制数字 num，小蓝可以从 num中选出一段连续的子串并将子串进行反转，最多反转一次。
小蓝想要将选出的子串进行反转后再放入原位置处得到的新的数字 numnew
满足条件 numnew<num，请你帮他计算下一共有多少种不同的子串选择方案，只要两个子串在 num
中的位置不完全相同我们就视作是不同的方案。
注意，我们允许前导零的存在，即数字的最高位可以是 0，这是合法的。
输入格式
输入一行包含一个长度为 n 的字符串表示 num（仅包含数字字符 0∼9），从左至右下标依次为 0∼n−1。
输出格式
输出一行包含一个整数表示答案。
数据范围
对于 20% 的评测用例，1≤n≤100；
对于 40% 的评测用例，1≤n≤1000；
对于所有评测用例，1≤n≤5000。
输入样例：
210102
输出样例：
8
样例解释
一共有 8种不同的方案：
所选择的子串下标为 0∼1，反转后的 numnew=120102<210102；
所选择的子串下标为 0∼2，反转后的 numnew=012102<210102；
所选择的子串下标为 0∼3，反转后的 numnew=101202<210102；
所选择的子串下标为 0∼4，反转后的 numnew=010122<210102；
所选择的子串下标为 0∼5，反转后的 numnew=201012<210102；
所选择的子串下标为 1∼2，反转后的 numnew~=201102<210102；
所选择的子串下标为 1∼4，反转后的 numnew=201012<210102；
所选择的子串下标为 3∼4，反转后的 numnew=210012<210102；
该题涉及的是字符串问题，就是找回文字符串；很明显死办法肯定会超时，想到了回文串是动态规划里面的一个经典问题。
果不其然要用dp，however我真的很久没有写过dp了orz
本题考察的是区间dp，也就是在区间上用动态规划。其中区间的范围要从小到大
比方说我的第一想法是：跑两个循环找区间，提取出这个区间的字符子串，然后从两端开始向内判断，其实也就是做比较，比方说我的初始代码如下：
void handle(string str)
{
int i = 0, j = str.size();
bool flag = false;
while(i < j){
if(str[i] == str[j]) {i ++; j --;}
else if(str[j] > str[i]) {break;}
else {flag = true; break;}
}
if(flag) cnt ++;
}
为什么会TLE，如何简化？其实跟引入动态规划的初衷一样，在上面的做法中我重复比较了；
比如说比较区间[0, 5]，[1, 4], [2, 3]，按照上面的做法，[2, 3]这个区间因为作为子区间，其实会被同样的方法比较多次！如果区间很大的话，会出现做重复工作的情况！！
这就说明，我应该是先比较小的区间，再看大的区间；大的区间在小的区间上逐步扩大，此时只需要比较引进来的端点的大小即可，其他的直接取用已经计算过的小区间结果
下面贴上AC代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 5e3 + 10;
int dp[N][N]; //dp[i][j]表示扭转i - j 位置的字串时符合题意
int main()
{
string number; cin >> number;
int n = number.size();
int cnt = 0;
for(int len = 2; len <= n;len ++){ //区间长度从小到大, 从长度为2的字串到长度为n的字串
for(int l = 0; l + len - 1 < n; l ++){ //遍历左端点
int r = l + len - 1;
if(number[r] < number[l]) { //右端点小于左端点，直接符合答案
cnt ++;
dp[l][r] = 1; //符合答案
}
else if(number[l] == number[r]){ //需要比较子串, 相当于原来代码的l ++, r --;比较一个更小的区间
cnt += dp[l + 1][r - 1];
dp[l][r] = dp[l + 1][r - 1]; //如果子串符合的话, 此时l - r也符合
}
}
}
cout << cnt;
return 0;
}
持续更新ing…
