随着蓝桥杯不断地推进，期间也要多加练习才能有所收获，对于这份去年的试卷，个人感觉有些难度，具体体现在数字大、状态方程难想，对于后四题编程都有所难度，本人也只能通过40%-60%的样例，下面针对下面10个题进行系统讲解，部分代码与思路源于网上，力求使用最简单的方法帮助你来理解，同时有任何疑问，可以留言，大家一起进步。
同时你的三连就是我创作的最大动力！！！
前言：本次题目还是有一定的难度，不少题目用到了dp，题目是比之前越来越高了，当然厉害的人也是越来越多了（不过我本人实在是太弱了）感觉去年的题目做对3道填空是不成问题的，再在大题混点分，省一还是有点希望的，不过A组竞争会更大一点。其实纵观题目有点难度，但是填空题还是可以在能力范围之内的，只要用心，稍微用一点技巧还是没有问题的，当然大题可以使用暴力，例如打表等方法进行求解。
如果还有什么更好的方法和解析，欢迎留下你的评论！
本次答题正确答案参考了以下的博客讲解：
2021蓝桥杯题解1
2021蓝桥杯题解2
讲解：此题难度简单，看来也是给我增强信心用的了！这个题目考查对计算机内存的理解：32位二进制是4个字节（8位一个字节），那么25610241024=268435456字节，用总字节除以4=67108864.
故答案是67108864！
这个题怎么想呢？其实这个题有个技巧，那就是一定是1最快结束，所以我们只要考虑1什么减少到0。那么这个题关键就是求每个位的数字，一般来说，可以使用循环迭代求出各个位，当然也可以使用整数转换为字符串然后直接进行判断，不过我个人推进循环迭代求出就好了。当然也很容易发现，肯定在千位就结束了，因为光是1000-2000就有1k+个了，所以，最后循环跳出的temp肯定使用break出来的，所以直接对他进行判断，如果是while出来的那必定是0了。
答案：3181
#include <iostream>
using namespace std;
int main(){
int a[10]={0};
for(int i=1;;i++){
int temp=i;
while(temp){
int n=temp%10;
if(n==1) a[1]++;
if(a[1]==2021) break;
temp/=10;
}
if(temp){
cout<<i<<endl;
break;
}
}
return 0;
}
乍一眼看到这个题就会感觉数字很大，但冷静分析一下，其实就是找不同的直线。注意，不同的直线，那肯定要使用set或map来进行存储了，但是我们也发现一条直线参数有k,b。根据高中数学知识可以得到下面一个直线方程：
y
=
y
1
−
y
2
x
1
−
x
2
x
+
b
y=\frac{y1-y2}{x1-x2}x+b
y=x1−x2y1−y2x+b
其中x前面的系数就是我们所要的k，那么b怎么得到呢，见下式，直接代入(x1,y1)就好：
b
=
y
1
−
y
1
−
y
2
x
1
−
x
2
x
1
b=y1-\frac{y1-y2}{x1-x2}x1
b=y1−x1−x2y1−y2x1
然后将k,b代入set里面就好，关键是set怎么处理？这有2个参数，那么当然是使用pair<>了，最好不要自己定义结构体放入set中，因为还需要重载排序方法。
这个题还有一个坑点就是double类型的炸精度，所以要将分母全部写上，如果使用我公式的求法会导致漏解，因为我定义y1是int型。
当然还要注意斜率不存在和直线平行x轴的情况哦！
答案：40257
下面是代码：
#include <iostream>
#include <set>
using namespace std;
int main(){
set<pair<double,double> > a;
for(int x1=0;x1<20;x1++){
for(int y1=0;y1<21;y1++){
for(int x2=0;x2<20;x2++){
for(int y2=0;y2<21;y2++){
if((x1!=x2)&&(y1!=y2)){
double k=(y1-y2)*1.0/(x1-x2);
double b=(y1*(x1-x2)-(y1-y2)*x1)*1.0/(x1-x2);
a.insert(pair<double,double>(k,b));
}
}
}
}
}
cout<<a.size()+21+20<<endl;
return 0;
}
拿到这个题目很容易发现，这类似于把一个数拆分3个进行乘积，我一开始想暴力解决，直接找出n的全部因数，然后通过打表进行三重循环求解，但发现运算的时候实在太大了，这里使用c++根本都运行不出来，使用java会运行到12位后就很慢了，所以纯粹的暴力解决是解决不了问题。那么只能换个思路了。我突然就想到了质因数分解了，什么意思呢？任何一个数都可以拆分成质因数来进行求解。例如：36=2233。那么把这个质因数找到了，就相当于高中数学排列组合一样，把这几个数放在3个空一样，而且每个空必须有数字，当然了可以是1，这很关键。OK，那么当务之急就是寻找质因数了，这个不难，可以看我下面代码，通过运算得出
2021041820210418
=
2
∗
3
3
∗
17
∗
131
∗
2857
∗
5882353
2021041820210418=2*3^3*17*131*2857*5882353
2021041820210418=2∗33∗17∗131∗2857∗5882353
问题就很显然了，首先考虑2,17,131,2857,5882353这5个数，相当于把这五个数放进3个空里面，那么每一个数就是有3种选择，即3^5=243。
最后考虑3的排列，有3个3，这3个三相当于给这5个数进行分配，不要考虑将其放在3个空中，举个例子，33就是一个数了9（9也是一种情况），我们已经将上面5个数进行放口了，现在就是对这5个数进行分配3的位置，就相当于5个里面选3个，即C(3,5)=10.
所以总数就是2430，很多人会问那11n的情况呢？注意到我前面说的，每个数都有3种选择，那么就存在一个空或2个空没有数来放，那么就是用1来进行补充，这一点很关键！
下面附质因数分解，比较简单的方法。
#include <iostream>
using namespace std;
long long n=2021041820210418;
long long a[]={1,2,3,3,3,17,131,2857,5882353,2021041820210418};
int main(){
//寻找质因数
/*for(int i=2;i<=n;i++){
if(n%i==0) {
cout<<i;
n/=i;
if(n!=1) cout<<",";
i=1;
}
}*/
cout<<pow(3,5)*10<<endl;
return 0;
}
拿到这个题目，心里还是比较开心的，这不就是最短路径的题目吗？心里还是比较开心的。当然前面的信息也不要大意，首先是最小公倍数怎么求，这里还是使用最常规的辗转相除法，先求出公因数，然后根据公式求出最小公倍数。接下来的事就是交给了图。首先对于图，不要忘记对角线a[i][i]=0，当然了不存在的路就是无穷大了。关键还得是怎么求图的最短路径，这里为了方便还是使用Floyd算法吧，比较简单，就是三个循环的事了。关于Floyd和Dijkstra的算法可以看我之前的博客此处链接
下面是解法代码（不过需要等待一会），答案是10266837
#include <iostream>
using namespace std;
int gcd(int m,int n){
return m%n==0?n:gcd(n,m%n);
}
long long a[2022][2022];
const long long maxm=2147483647;
int main(){
for(int i=1;i<=2021;i++){
for(int j=1;j<=2021;j++){
if((i-j>21)||(i-j<-21)){
a[i][j]=a[j][i]=maxm;
}
else if(i==j) a[i][j]=a[j][i]=0;
else{
int ix=max(i,j);
int jx=min(i,j);
a[i][j]=a[j][i]=i*j/gcd(ix,jx);
}
}
}
//floyd
for(int i=1;i<=2021;i++){
for(int j=1;j<=2021;j++){
for(int k=1;k<=2021;k++){
if(a[j][k]>a[j][i]+a[i][k]){
a[j][k]=a[j][i]+a[i][k];
}
}
}
}
cout<<a[1][2021]<<endl;
return 0;
}
这个别的不说，签到题。思路就是毫秒不用去管，然后根据时间运算来进行取舍，当然了同时也考了格式化输出的方法，注意到如何显示0和不显示，这个还是一个基本功，临近竞赛抽时间来整理一下。
#include <iostream>
using namespace std;
long long n,s,hour,mins,sec;
int main(){
cin>>n;
s=n/1000;
hour=s/(60*60);
mins=(s-hour*3600)/60;
sec=s-hour*3600-mins*60;
printf("%02lld:%02lld:%02lld\n",hour%24,mins%60,sec%60);
return 0;
}
其实拿到这道题我是比较难受的，一看就知道要用到dp，然后并没有掌握得太好。这其实就是类似于整数拆分的问题，通过实现拆分来达到目的。我这个自己的做法也只能通过40%的数据，大概思路就是dfs了，（深搜yyds)整体思路就是通过在sum加减数字来达到目的。话说也可能有同学不太理解dfs，这里就做简单的回答：在这个题目面，先进行sum+a[i]，等待此时i达到N时就出来，比较类似于栈一样进行回溯，然后再进入下一个阶段。
通过40%简单理解的代码：
#include <iostream>
using namespace std;
const int maxn=1e6;
int N;
long long a[maxn];
int vis[maxn];
void dfs(int sum,int i){
if(i==N){
if(sum>0){
vis[sum]=1;
}
return;
}
dfs(sum+a[i],i+1);
dfs(sum,i+1);
dfs(sum-a[i],i+1);
}
int main(){
int cnt=0;
cin>>N;
for(int i=0;i<N;i++){
cin>>a[i];
}
dfs(0,0);
for(int i=1;i<=maxn;i++){
if(vis[i]==1){
cnt++;
}
}
cout<<cnt<<endl;
return 0;
}
正确代码：关键就是状态方程。（考试能写出40%也是很不错了）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int dp[102][100002];
int main()
{
int n;
scanf("%d",&n);
int w[n+1];
ll sum=0;
for(int i=1;i<=n;i++){
scanf("%d",&w[i]);
sum+=w[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=sum;j++){
dp[i][j]=dp[i-1][j];
if(dp[i][j]==0){
if(w[i]>j)dp[i][j]=dp[i-1][w[i]-j];
if(w[i]==j)dp[i][j]=1;
if(w[i]<j)dp[i][j]=dp[i-1][j-w[i]];
}
}
}
ll ans=0;
for(int i=1;i<=sum;i++){
if(dp[n][i])ans++;
}
printf("%lld",ans);
return 0;
}
本题我也没什么好的思路，对于这个题我的最开始的思路偏向于大表，肯定是过不了全部用例，至少还是能混点一半分的，挂网测大概40%通过。这里的思路首先构造c[i][j]，对此进行赋值，不过建立起map关系，将出现的数字和位置放在map中，这样就很快查询了，比一般的查询要快不少，但还是暴力打表求解，不过打表法yyds!
附通过40%的样例代码：
#include <iostream>
#include <map>
#include <cstring>
using namespace std;
const int maxn=1000;
long long c[maxn][maxn];
int N;
map<long long,long long> a;
int main(){
memset(c,0,sizeof(c));
for(int i=0;i<maxn;i++) c[i][0]=1;
for(int i=0;i<maxn;i++) c[i][i]=1;
for(int i=2;i<maxn;i++){
for(int j=1;j<i;j++) c[i][j]=c[i-1][j]+c[i-1][j-1];
}
int sum=0;
for(int i=0;i<maxn;i++){
for(int j=0;j<=i;j++){
if(c[i][j]!=0){
sum++;
if(a.find(c[i][j])==a.end()){
a.insert(pair<long long,long long>(c[i][j],sum));
}
}
}
}
cin>>N;
map<long long,long long>::iterator it;
it=a.find(N);
cout<<it->second<<endl;
return 0;
}
下面是正确的答案：这个题正确解法偏向于二分求解。
#include <bits/stdc++.h>
using namespace std;
// 打印杨辉三角前x行，帮助直观感受
void Print(int x) {
long long int c[100][100];
for (int i = 1; i <= x; i++) {
c[i][0] = 1;
printf("%lld\t", c[i][0]);
for (int j = 1; j < i; j++) {
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
printf("%lld\t", c[i][j]);
}
printf("\n");
}
}
// 二分方法
long long int n;
long long int C(long long int a, long long int b) {
long long int ret = 1;
for (long long int i = a, j = 1; j <= b; i--, j++) {
ret = ret * i / j;
if (ret > n) {
return n + 1;
}
}
return ret;
}
long long int GetAns(int col) {
long long int l = col, r = max(n, (long long int)col);
while (l < r) {
long long int mid = (l + r) / 2;
if (C(mid, col) >= n)
r = mid;
else
l = mid + 1;
}
if (C(r, col) != n) { // 没有出现则返回出现位置无限大
return 4e18;
} else {
return r * (r + 1) / 2 + col + 1;
}
}
int main() {
scanf("%lld", &n);
long long int ans = 4e18;
for (int i = 0; i < 20; i++) { // 枚举前20列，记录最早出现位置
long long int cur = GetAns(i);
ans = min(ans, cur);
}
printf("%lld\n", ans);
return 0;
}
这个题目我是没啥思路，照样使用sort函数走天下！比较sort函数会采用最好的方法来选择。这个题目理解了意思就不觉得困难了。关键在于p=1和p=0的情况，当然也要注意，题目要求是对a1,a2…进行排序，也就是说你换了顺序以后，你的数组编号也要跟着改变，理解了这个意思就会觉得比较简单了！
通过60%评测的代码：
#include <iostream>
#include <algorithm>
using namespace std;
int n,m;
bool cmp(int a,int b){
return a>b;
}
int main(){
cin>>n>>m;
int a[n+1];
for(int i=0;i<=n;i++) a[i]=i;
while(m--){
int p,q;
cin>>p>>q;
if(p==0){
sort(a+1,a+q+1,cmp);
}else{
sort(a+q,a+1+n);
}
}
for(int i=1;i<=n;i++) cout<<a[i]<<" ";
cout<<endl;
return 0;
}
贴一波正确代码：
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
int n,m;
scanf("%d%d",&n,&m);
int sta[m];//栈数组
int cnt=0;//栈的长度
while(m-->0)
{
int op;
int mid;
scanf("%d %d",&op,&mid);
if(op==0){
if(cnt%2!=op)
{
if(cnt-1>=0&&sta[cnt-1]<=mid)cnt--;
else continue;
}
while(cnt-2>=0&&sta[cnt-2]<=mid){
cnt-=2;
}
}else{
if(cnt%2!=op)
{
if(cnt-1>=0&&sta[cnt-1]>=mid)cnt--;
else continue;
}
while(cnt-2>=0&&sta[cnt-2]>=mid){
cnt-=2;
}
}
sta[cnt++]=mid;
}
int l=1;
int r=n;
int ans[n+1];//答案数组
int x=n;
for(int i=0;i<cnt;i++){
int mid=sta[i];
if(i%2==1){
mid=min(r, mid);
while(l<mid)ans[l++]=x--;
}
else {
mid=max(l, mid);
while(r>mid)ans[r--]=x--;
}
if(r-l<1)break;
}
if(l<=r)
if(cnt%2==1) {
while(l<=r)ans[l++]=x--;
}else {
while(l<=r)ans[r--]=x--;
}
printf("%d",ans[1]);
for(int i=2;i<=n;i++)
{
printf(" %d",ans[i]);
}
printf("\n");
}
本题我觉得是最难的一道题，没什么特别好的思路，参考了一个博主的想法，写下了这段代码，主要是通过dfs方法来进行，这样每一次插入set中判断是否重复过。
#include <iostream>
#include <stack>
#include <string>
#include <cstring>
#include <set>
#include <cmath>
#include <algorithm>
using namespace std;
string m;
const int mod=1e9+7;
int f;
char c;
set<string> a;
//判断括号是否匹配
bool isok()
{
stack<char> sta;
for(int i=0;i<m.size();i++){
if(m[i]=='('){
sta.push(m[i]);
}else{
if(sta.empty()||sta.top()!='(')return false;
else sta.pop();
}
}
if(sta.empty())return true;
else return false;
}
//dfs，把每一种情况都进行判断
void dfs(int depth){
if(depth==f){
if(isok()){
a.insert(m);
}
}else{
for(int i=0;i<m.size();i++){
m.insert(m.begin()+i,c);
dfs(depth+1);
m.erase(m.begin()+i,m.begin()+i+1);
}
}
}
int main(){
cin>>m;
int left=0,right=0;
for(int i=0;i<m.size();i++){
if(m[i]=='('){
left++;
}else{
right++;
}
}
int flag=0;
left>right?flag=0:flag=1;
left>right?c=')':c='(';
f=abs(left-right);
dfs(0);
cout<<a.size()<<endl;
return 0;
}
贴一波正确代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5052;
const long long int MOD = 1e9 + 7;
int dp[maxn][maxn];
bool vis[maxn][maxn];
char str[maxn];
int n;
long long int mod(long long int x) { return x % MOD; }
long long int GetAns() {
memset(dp, 0, sizeof dp);
memset(vis, 0, sizeof vis);
dp[0][0] = 1;
vis[0][0] = true;
for (int i = 1; i <= n; i++) {
if (str[i - 1] == '(') {
for (int j = 1; j <= n; j++) {
dp[i][j] = dp[i - 1][j - 1];
vis[i][j] = vis[i - 1][j - 1];
}
} else {
dp[i][0] = mod(dp[i - 1][0] + dp[i - 1][1]);
vis[i][0] = vis[i-1][0] | vis[i-1][1];
for (int j = 1; j <= n; j++) {
dp[i][j] = mod(dp[i - 1][j + 1] + dp[i][j - 1]);
vis[i][j] = vis[i - 1][j + 1] | vis[i][j - 1];
}
}
}
for (int i = 0; i <= n; i++) {
if (vis[n][i] != 0) {
return dp[n][i];
}
}
return -1;
}
int main() {
scanf("%s", str);
n = strlen(str);
long long int ansL = GetAns();
reverse(str, str + n);
for (int i = 0; i < n; i++) {
if (str[i] == ')') {
str[i] = '(';
} else {
str[i] = ')';
}
}
long long int ansR = GetAns();
printf("%lld\n", mod(ansL * ansR));
return 0;
}