第十届蓝桥杯赛前自救

客官°小女子只卖身不卖艺 2022-03-02 05:54 201阅读 0赞

2019.3.29更新：蓝桥杯省赛结果出来了，省三emmmm，有点意料之中吧，其实本来还期待省二的，可能编程大题只是过了样例，编程基础还是差吧。希望自己这半年能好好补基础一点点追上去。嗯，不能逃避，这周末会把第十届蓝桥杯省赛B组C++的题目复盘一下，也订正一下，加油。

--------------------

2019.3.24 更新： 今天早上考完了，考了4小时，但是不觉得累，有好多套路就是昨天总结的！奈何我没弄懂，所以考场上有的题没写出来，大概做出来5题左右吧，也不知道提交的对不对，等结果出来了再更新呀，知识点还是要一点点补的！

--------------------

刷了几十道真题和解析，发现了一些常考的知识点，但是自己还是很多似懂非懂，所以在距本次蓝桥杯还剩0天的时候，临时抱一波佛脚，希望自救成功。

1.  斐波那契数列及其变体（主要学会递归）  
    这个博主总结得很好：[https://blog.csdn.net/u013049553/article/details/80265959][https_blog.csdn.net_u013049553_article_details_80265959]
2.  快速排序及其变体

void swap(int a[], int i, int j){
    	int t = a[i];
    	a[i] = a[j];
    	a[j] = t;
    } 
    
    int partition(int a[], int p, int r)//作用是找标尺{
        int i = p;
        int j = r + 1;
        int x = a[p];
        while(1){
            while(i<r && a[++i]<x);
            while(a[--j]>x);
            if(i>=j) break;
            swap(a,i,j);
        }
    	swap(a,p,j);//**所以p要和j交换
        return j;//返回标尺
    }
    
    void quicksort(int a[], int p, int r){
        if(p<r){
            int q = partition(a,p,r);
            quicksort(a,p,q-1);
            quicksort(a,q+1,r);
        }
    }

1.  处理字符串输入输出流模板？？

void i2s(int num,string &str){
    	stringstream ss;
    	ss<<num;
    	ss>>str;
    }

1.  字符串如何处理（常常和日期题一起考）

string in;
    	cin>>in;
    	int a=0,b=0,c=0;
    	a=(in[0]-'0')*10+(in[1]-'0');
    	b = (in[3] - '0') * 10 + (in[4] - '0');
        c = (in[6] - '0') * 10 + (in[7] - '0');

1.  动态规划 深搜dfs必须学会（最大最小的类型）

//7对数字
    int dfs(int n){
    	if(n==4) n++;
    	if(n>6) return 1;
    	for(int i=3;i<=14;i++){
    		if(i==7||i==9) continue;
    		if(i+n+1<=14&& a[i]==0 && a[i+n+1]==0){
    			a[i]=a[i+n+1]=n;
    			if(dfs(n+1)) return 1;//如果n+1可以继续深入的话就继续
    			a[i]=a[i+n+1]=0;//不然没在上一步出去就是此路不通 要回溯重置
    		}
    	}
    	return 0;
    }

1.  二维数组判断连通性

for(int i=0;i<3;++i){
    		for(int j=0;j<4;++j){
    			if(g[i][j]==1)
    				dfs(g,i,j);
    			cnt++;
    		}
    		
    	void dfs(int g[3][4],int i,int j){
    	g[i][j]=0;
    	//一个格子的四个方向
    	if(i-1>=0&&g[i-1][j]==1)dfs(g,i-1,j);
    	if(i+1<=2&&g[i+1][j]==1)dfs(g,i+1,j);//时刻注意下标与实际差1
    	if(j-1>=0&&g[i][j-1]==1)dfs(g,i,j-1);
    	if(j+1<=3&&g[i][j+1]==1)dfs(g,i,j+1);}

1.  全排列问题  
    前几天整理过了：[https://mp.csdn.net/mdeditor/88697133\#][https_mp.csdn.net_mdeditor_88697133]
2.  最大公共字串的模板 经典dp

#define N 256
    int f(const char*s1,const char *s2){
    	int a[N][N];
    	int len1=strlen(s1);
    	int len2=strlen(s2);
    	int i,j;
    memset(a,0,sizeof(int)*N*N);
    int max=0;
    for(i=1;i<len1;i++){
    	for(int j=1;j<len2;j++){
    		if(a1[i-1]==s2[j-1]) a[i][j]=a[i-1][j-1]+1;
    		if(a[i][j]>max) max=a[i][j];
        }
    }
    return max;
    }

1.  最大公约数模板

int gcd(int a,int b){
    	if(b==0) return a;
    	return gcd(b,a%b);
    }

1.  二分法left right mid 二分枚举 模板

while(l<=r){
    	int mid=(l+r)/2;
    	int cnt=0;
    	for(int i=0;i<n;i++){
    	/*根据题目写内容 例如*/
    	cnt+=(h[i]/mid)*(w[i]/mid);
    	}
    	if(cnt>=k){
    		l=mid+1;
    		ans=mid;//某题中答案就是要找最大的点
    		}else{
    		r=mid-1;
    		} 
    	cout<<ans<<endl;
    	return 0;
    }

1.  ij之间的区间和

for(int i=1;i<=n;i++){
    		cin>>a[i];
    		s[i]=s[i-1]+a[i];
    	}
    	long long ans=0;
    	for(int i=1;i<=n;i++){
    		for(int j=i;j<=n;j++){
    			//ij之间的区间和=s[j]-s[i-1]
    			if((s[j]-s[i-1])%k==0)
    				ans++;
    		}
    	}

1.  10进制转k进制

string toKbit(ull num, int k){
    	if(num==0)
    		return "0";
    	int i=0;
    	char buffer[66];
    	while (num!=0){
    		int bit=num%k;
    		if(bit >=10){
    			buffer[i++]='A'+bit -10;//???
    		}else{
    			buffer[i++]='0'+bit;
    		}
    		num/=k;
    	}
    	buffer[i]='\0';
    	string res(buffer);//吧字符串数组改成字符串
    	reverse(res.begin(),res.end());
    	return res;
    }

1.  k进制转10进制

ull kbitto10(const string& num, int k){
    	ull res=0,p=1;
    	for(int i=num.size()-1;i>=0;--i,p*=k){
    		int bit;
    		if(num[i]>='A'&& num[i]<='Z'){
    			bit=num[i]-'A'+10;
    		}else
    		{bit=num[i]-'0';}
    		res+=(p*bit);
    	}
    	return res;
    }

1.  哈希表怎么用
2.  迭代器怎么用

for(set<string>::iterator iter=ans.begin();iter!=ans.end();iter++){
    			cout<<*iter<<endl;
    	}

1.  set怎么用
2.  map怎么用
3.  数组初始化为0/清0

memset(g, 0, sizeof(g));

1.  求素数

bool iss(LL k){
    	int ans=0;
    	for(int i=1;i<=k/2;i++){
    		if(k%i==0)return false;//你更笨不需要算完啊 只要出现了就不是ans++;
    	}
    		return true;
    
    }

冷门的一些知识点：  
考察printf中“\*”的作用 是宽度的意思  
printf(“%\*s\\n”,5,”1”); -> 4个空格+1

注意事项：

*  题目要看清楚，比如是问某一层还是所有层
 *  记得考虑数字类型范围，不要int到底！
 *  找规律演算！
 *  正向做不出来就反向求
 *  暴力要注意范围！脑子要清晰！
 *  考虑问题要全面，比如骰子上下不动时，前后左右四个面都可以转的！
 *  遇到除法 记得变成乘法
 *  注意输出要求  
    • “%d”表示按十进制整型输出；  
    • “%ld”表示按十进制长整型输出；  
    • “%c”表示按字符型输出等。
 *  代码填空先把代码复制出来跑一下
 *  打印图形的题目不要忘记数空格
 *  想把编程学好，必须学好数学！补！
 *  做不出来就凑啊！蒙啊！19年就蒙19啊！
 *  不要犯低级错误，比如填空多写了“；”之类
 *  大题就算做不出来也要暴力出来至少能拿一部分分
 *  输出/保留x位小数：printf("%.xf",m);

(里面好多依然模糊，祝自己某题好运吧。。。)

[https_blog.csdn.net_u013049553_article_details_80265959]: https://blog.csdn.net/u013049553/article/details/80265959
[https_mp.csdn.net_mdeditor_88697133]: https://mp.csdn.net/mdeditor/88697133#