往年蓝桥杯赛题回顾

acm

2017官方模拟赛
2016年题解
2015年题解
明天就要蓝桥杯了,然而好久没敲代码了,争取能够免费北京游吧,看下往年情况做出7道题就差不多稳了.
主要看了14,15,16三年的题目,知识点主要集中在数学,暴力,dp,除了最后一题,其他的都可以争取做出来.
注意到蓝桥杯大题是分点给分的,不会做也可以尽量骗分.
同时要注意细心!中途没有测试的机会,只能自己多造样例,用心检查.

• 2016-4:快速排序填空题,理解快速排序的原理即可
  然而我已经快要忘了快排,还好代码可以copy到本地,输出中间变量看下原理,不断尝试总能够尝试出来.
  快速排序回顾
  简单的说就是找一个元素作为标尺,比它大的放右边,小的放左边,然后分治.
• 2016-9:回文串,dfs+dp,注意空间可以开short节省

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
char s[5005];
short dp[5005][5005],n;
int dfs(int l, int r){
    if(dp[l][r]) return dp[l][r];
    if(l >= r) return 0;
    if(s[l]==s[r]) return dp[l][r] = dfs(l+1,r-1);
    else return dp[l][r]=min(dfs(l+1,r), dfs(l,r-1))+1;
}
int main(){
    while(scanf("%d", &n)!= EOF){
        memset(dp,0,sizeof(dp));
        scanf("%s", s+1);
        dfs(1,n);
        cout <<dp[1][n]<<endl;
    }
}

• 2015-6 暴力dfs
  为了避免重复的情况,我们可以考虑给枚举定一个顺序,也就是先枚举小的,再枚举大的.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int knt = 0;
void dfs(int st, int sum, int cur){
    if(sum==13) {knt++; return;}
    if(st > 13) return;
    if(cur<4)dfs(st, sum+1, cur+1);
    dfs(st+1,sum,0);
}
int main(){
    dfs(1,0,0);
    cout<<knt<<endl;
    return 0;
}

• 2015-7 暴力+全排列+判重
  学会使用next_permutation

next_permutation(首地址,末地址);
把指定区域内的排列按照字典序变为下一个排列.
char s[100]="abcdefghijklmnopq";
next_permutation(s,s+17);
cout<<s<<endl;
输出为abcdefghijklmnoqp