蓝桥杯补档

2013

省B

P8597 翻硬币 H

一排硬币给出初态和终态，每次只能翻转相邻的两枚，求最少多少次

用贪心，因为翻转两次相当于没翻，所以最优方案中同一组硬币肯定最多翻转一次，所以翻转顺序无后效性。从前往后翻，只要不一样就把它和它后面的硬币都翻转一次，计数器累加

2023

省A

P9230 有奖问答 B

P9231 平方差 C

给定 𝐿,𝑅问 𝐿≤𝑥≤𝑅中有多少个数 𝑥 满足存在整数 𝑦,𝑧使𝑥=𝑦²−𝑧²

注意到x=（y+z)(y-z)，两者同奇偶，也就是说x要么是奇数要么是4的倍数，那么4x+2是无法取到的，而奇数和4的倍数都是可以分解的

那只需要计算l到r之间有多少符合条件的数字即可，用前缀和计算

省B

P9240 冶炼金属 C

给出若干组a和b，a以固定比例v转换为b，求满足所有分组的v的最大和最小可能值。

对每一组，由[a/b]可以得到一个大概范围，考虑临界值

P9241 飞机降落 D

一开始想用贪心算法，看成区间安排问题。但是发现不好确定顺序，再看数据范围打暴力更方便呃呃呃直接dfs，记得打标记和去掉标记

P9242 接龙数列 E

计算去掉的数量不好算，可以先算出最长的接龙长度再与n相减，像这样就和最大不下降子序列差不多了。用dp计算。为了方便取头尾，用字符串存储

#include<bits/stdc++.h>
using namespace std;
int n,dp[10],maxn;
string a;//为了方便取头尾，可以以字符串形式存储
signed main(){cin>>n;for(int i=1;i<=n;i++){cin>>a;int ln=a.length();dp[a[ln-1]-'0']=max(dp[a[ln-1]-'0'],dp[a[0]-'0']+1);}for(int i=0;i<=9;i++) maxn=max(maxn,dp[i]);cout<<n-maxn;return 0;
}