第十四届蓝桥杯c/c++B组 赛后复盘wa_蓝桥杯考试要禁用cincout输出流吗

 复盘反思：

  今天打完蓝桥杯，感觉自己被雷到了，简单题做不出，复杂题也只会暴力。感觉两个月的备赛就是场笑话，全程没有优美的算法可言，只有一层层堆砌的暴力循环。经过这场比赛，我明白了自己极其不扎实的技术功底以及缺乏参加大赛的经历。我在备战蓝桥杯的前期是使用acwing的，天天手抄y总代码以为自己有多牛b，最后到头来样样学不精。今年的自己确实令我失望，不过咱也不能气馁。从哪里跌倒，就要从哪里爬起来。趁着现在才大一，好好的沉淀一年，不要追求快速！不要自以为是！不要浮躁。明年，我还来捐300.不过那时候，我一定会拿回属于我的荣誉！！！

题目复盘

 试题A：日期统计

 【考试状态】：

  看到第一题名字的时候还以为又是什么签到题，毕竟以往几年的蓝桥杯的日期题我从来没有卡过。可是因为第一次参加比赛，我紧张得不得了，题都没读明白，后来明白了题意，判断的时候又总是不能完全不重不漏，写了半个小时的各种循环判断，最后还是选择手算。提交的答案是327，错大离谱了。

【题意分析】：

  其实，题目的思想本身不难，但是模拟很是复杂。而且现在其实我还是没有搞懂条件1

和条件2不是有冲突吗？子序列要为8，可是条件2又变相的告诉我子序列不一定为8，遇到单日期只需要补上前导0就行？？？？？？我就是这里好迷糊。算了，继续来分析。我们可以分单月单日期、单月双日期、双月单日期、双月双日期四个方式来做到不重不漏。然后借助dfs的来找到我们的答案。

这是考试时我的思路

 利用dfs算法思想 （学长给的代码，还没吃透hh）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
set<string> st;
int mon[13] = { 31, 30, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
int a[110];
 
 
//s是日期，id是100位数组编号，u是枚举到第几位，v是s的每一位
void dfs(string s, int id, int u, char v)  
 {
	if (u == 9) {
		st.insert(s);
		//		cout << s << "\n";
		return;
	}
	if (id > 100) return;
	if (u == 1) {
		if (a[id] == 2) {
			dfs(s + '2', id + 1, u + 1, 2);
		}
	}
	else if (u == 2) {
		if (a[id] == 0) {
			dfs(s + '0', id + 1, u + 1, 0);
		}
	}
	else if (u == 3) {
		if (a[id] == 2) {
			dfs(s + '2', id + 1, u + 1, 2);
		}
	}
	else if (u == 4) {
		if (a[id] == 3) {
			dfs(s + '3', id + 1, u + 1, 3);
		}
	}
	else if (u == 5) {
		if (a[id] <= 1) {
			char c = '0' + a[id];
			dfs(s + c, id + 1, u + 1, a[id]);
		}
	}
	else if (u == 6) {
		if (v == 0 && a[id] == 0) {
 
		}
		else if (v == 0 && a[id] > 0) {
			char c = '0' + a[id];
			dfs(s + c, id + 1, u + 1, a[id]);
		}
		else if (v == 1 && a[id] <= 2) {
			char c = '0' + a[id];
			dfs(s + c, id + 1, u + 1, a[id]);
		}
	}
	else if (u == 7) {
		if (a[id] <= 3) {
			char c = '0' + a[id];
			dfs(s + c, id + 1, u + 1, a[id]);
		}
	}
	else if (u == 8) {
		if (v == 3) {
			int num = (s[4] - '0') * 10 + s[5] - '0';
			if (mon[num] == 31 && a[id] <= 1) {
				char c = '0' + a[id];
				dfs(s + c, id + 1, u + 1, a[id]);
			}
		}
		else if (v == 0 && a[id] == 0) {
 
		}
		else {
			char c = '0' + a[id];
			dfs(s + c, id + 1, u + 1, a[id]);
		}
	}
 
	char c = '0' + a[id];
	dfs(s, id + 1, u, v);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
 
	for (int i = 1; i <= 100; ++i) {
		cin >> a[i];
	}
	dfs("", 1, 1, 0);
	cout << st.size() << "\n";
	return 0;
}

 【复盘代码】

#include<bits/stdc++.h>
using namespace std;
int a[100],ans;
bool vis[20240000];
bool check(int date){           //判断日期合法性
	if(vis[date]) return false;
	vis[date]=true;
	int mm=date/100%100;
	int dd=date%100;
	if(mm<1||mm>12)return false;
	if(mm==1||mm==3||mm==5||mm==7||mm==8||mm==10||mm==12){
		if(dd>=1&&dd<=31) return true;
	}else if(mm==2){
		if(dd>=1&&dd<=28)return true;
	}else if(dd>=1&&dd<=30)return true;
	else return  false;
} 
 
void dfs(int x,int pos,int date){    //x是当前枚举的下标，pos是当前枚举的位数，date是当前组成的日期 
	if(x==100)return ;
	if(pos==8){
		if(check(date))++ans;
		return;
	}
	if((pos==0&&a[x]==2)||        //将每一位的合法情况进行判断
	   (pos==1&&a[x]==0)||
	   (pos==2&&a[x]==2)||
	   (pos==3&&a[x]==3)||
	   (pos==4&&a[x]>=0&&a[x]<=1)||
	   (pos==5&&a[x]>=0&&a[x]<=9)||
	   (pos==6&&a[x]>=0&&a[x]<=3)||
	   (pos==7&&a[x]>=0&&a[x]<=9))
		dfs(x+1,pos+1,date*10+a[x]);  //选择这个数 
	dfs(x+1,pos,date);  //不选这个数 
}
 
 
int main()
{
	ios::sync_with_stdio(0);cin.tie(0); //关闭流同步
	for(int i=0;i<100;i++)cin>>a[i]; 
	dfs(0,0,0);
	cout<<ans;
	
	
	return 0;
}

 答案：235

试题B：01串的熵

【题意分析】

   学会加工题目信息。如果有i个0，那么则有n-i个1.而且0必定比1出现少。所以枚举一半即可。然后可以化成

 填空题枚举就行了！

【复盘代码】

#include<bits/stdc++.h>
using namespace std;
typedef long double db;
const db ans = 11625907.5798,eps=1e-4;
const int N =23333333;
int main()
{
	for(int i=0;i<=N/2;i++)   //0的个数
	{
		int u = N-i;
		db res=-1.0*u*u/N*log2(1.0*u/N)-1.0*i*i/N*log2(1.0*i/N);
		if(fabs(res-ans)<eps){
			cout<<i;
			return 0;
		}	
	}
	return 0;
}

答案：11027421

试题C:冶炼金属

【考试状态】

  这题可能是我最有把握的题目了，一拿到题目，我就想到了逆向分析。然后明确了一个思路。拿一个MAXN数组和一个MINN数组分别保存取下界的值（然后再数组里找一个最小值），MINN数组保存上界值（然后取数组的最大值）。也不知道对不对，只去过了样例。

【考试代码】

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 10010;
int MAXN[N], MINN[N];
int n, k ;
int main()
{
   
    scanf("%d", &n);
    while (n--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        MAXN[k] = a / b;
        if ((a * 1.0 / (b + 1) > a / (b + 1)))MINN[k] = a / (b + 1) + 1;
        else MINN[k] = a / (b + 1);
        k++;
    }
    sort(MAXN, MAXN + k);
    sort(MINN, MINN + k);
    printf("%d %d", MINN[k - 1] ,MAXN[0]);
    return 0;
}

【复盘代码】二分法：

#include<bits/stdc++.h>
using namespace std;
const int MAX_N=1e4+1;
int N,A[MAX_N],B[MAX_N];
bool check_min(int V)
{
	for(int i=1;i<=N;i++)
		if(A[i]/V>B[i])return false;
	else return true;
}
 
bool check_max(int V)
{
	for(int i=1;i<=N;i++)
	if(A[i]/V<B[i])return false;
	return true;
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>N;
	for(int i=1;i<=N;i++)cin>>A[i]>>B[i];
	
	//二分答案过程
	int L=1,R=1000000000,V_min;
	while(L<=R)
	{
		int mid = (L+R)>>1;
		if(check_min(mid)){
			V_min=mid;
			R=mid-1;
		}else L=mid+1;		
	 } 
	 L=1,R=1000000000;int V_max;
	 while(L<=R)
	 {
	 	int mid=L+R>>1;
	 	if(check_max(mid)){
	 		V_max=mid;
	 		L=mid+1;
		 }else R=mid-1;
	 }
	 cout<<V_min<<' '<<V_max;
	 
	return 0;
	
}

试题D:飞机降落

 【题意分析】

  飞机降落问题，看到数据范围的时候，立马想到了贪心模型，想着用全排列的方式去做，数据规模大概在3*10^9，会超时，不过可以过大部分样例。思路是这样，但是考试真的不会写这种排列hh。现在我还记得考试前我复习到的一个全排列函数next_permutation。赛后听到大佬讲用dfs+剪枝的方法可以大大减小数据规模（如果前面某驾飞机已经判断不能降落了，那么就不用再向全排列一样继续枚举），然后跟着大佬去尝试写代码

【复盘代码】dfs+剪枝

#include<bits/stdc++.h>
using namespace std;
const int N = 11;
int T[N],D[N],L[N];
bool used[N],have_answer;    //是否尝试降落，是否有答案 
int n;
void dfs(int x,int tim){	//已经降落了几架，现在所用时间 
	if(have_answer) return; //找到答案，就跳出 
	if(x==n){				//如果降落n架，有解 
		have_answer=1;
		return;
	}
	for(int i=1;i<n;i++)
		if(!used[i]&&tim<T[i]+D[i]){  //没降落，而且现在花费的时间小于这架飞机的最大停留时间 
			used[i]=1;    			 //成功降落 
			dfs(x+1,max(T[i],tim)+L[i]);   //最早在T【i】时间降落，这里取个max值 
			if(have_answer)return;         //找到答案，跳出 
			used[i]=0;					//否则回复原样 
		}
} 
 
void solve(){
	have_answer=0;   		//开头默认没有解 
	cin>>n;
	for(int i=1;i<=N;i++){
		cin>>T[i]>>D[i]>>L[i];
		used[i]=0;
	}
	dfs(0,0);
	if(have_answer)cout<<"YES\n";
	else cout<<"NO\n";
}
 
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	int t;
	cin>>t;
	while(t--) solve();
	return 0;
}

试题E：接龙数列