蓝桥杯集训第一周刷题笔记（1.17-1.21）

1.1题目描述

1.2输入输出样例

1.3解题思路
深度优先搜索，从最底层向上层搜索，每一层枚举可能的半径和高度，判断是否合法，合法则继续搜索上一层。
需要剪枝的情况：
上层最小体积+目前体积>目标体积
上层最小侧面积+目前面积>现有答案
剩下的侧面积+目前面积>现有答案

1.4源代码

#include
#define maxm 30
using namespace std;
int n,m,mins[maxm],minv[maxm],r[maxm],h[maxm],ans=(int)1e9;//mins,minv,r,h分别为各层的最小面积，最小高度，半径和高度
int s=0,v=0;
void dfs(int dep) {
	if(dep==0) {
		if(v==n) ans=min(ans,s);//搜索完毕，更新最小ans值
		return;
	}
	for(r[dep]=min(r[dep+1]-1,(int)sqrt(n-v)); r[dep]>=dep; r[dep]--) {
//sqrt(n-v)：剩余体积做成一层的半径，r[dep+1]-1:上一层至少比下一层小1，
//r[dep]>=dep：每一层半径需比本层层数大，否则一共不够m层
		for(h[dep]=min((int)((double)(n-v)/r[dep]/r[dep]),h[dep+1]-1); h[dep]>=dep; h[dep]--) { //剩余体积做成的一层高度，至少比下一层少1，保证能构成m层
			if(v+mins[dep-1]>n) continue;//上层最小体积+目前体积>目标体积
			if(s+mins[dep-1]>ans) continue;//上层最小面积+目前面积>现有答案，不是最优
			if(s+(double)2*(n-v)/r[dep]>ans) continue;//2*(n-v)/r[dep]:用体积确定剩下的侧面积+目前面积>现有答案，不是最优
			if(dep==m) s+=r[dep]*r[dep];//从下往上第一层加上上表面面积，其它层只需考虑侧面积
			v+=r[dep]*r[dep]*h[dep];
			s+=2*r[dep]*h[dep];
			dfs(dep-1);
			if(dep==m) s-=r[dep]*r[dep];//还原
			v-=r[dep]*r[dep]*h[dep];
			s-=2*r[dep]*h[dep];
		}
	}
}


int main() {
	cin>>n>>m;
	mins[0]=minv[0]=0;
	for(int i=1; i<=m; i++) { //每一层最小r、h均是层数，预处理算出每层最小s,v,逐个递增
		mins[i]=mins[i-1]+2*i*i;
		minv[i]=minv[i-1]+i*i*i;
	}
	h[m+1]=r[m+1]=(int)1e9;
	dfs(m);
	cout< 
2.头疼的数列（动态规划） 
2.1题目描述
 
 2.2输入输出样例
 
 2.3解题思路
 动态规划，定义状态dp[i][0]和dp[i][1]分别表示从开始到位置i把全部元素变成变成0或1的 *** 作数。题目转化为找出找出dp[i][0]与dp[i-1][0]和dp[i-1][1]的关系，求ap[n][0]。
 若a[i]=1，要使a[1-i]为0，要么使a[1-(i-1)]全为0、翻转a[i]，要么使a[1-(i-1)]全为1、翻转a[1-i]；要使a[1-i]为1，要么使a[1-(i-1)]全为1，要么使a[1-(i-1)]全为0、翻转a[1-(i-1)]。
 由此，得出状态转移方程：
 
 同理可以得出a[i]=0的递推式.
 2，4源代码
 
#include
using namespace std;
const int N=1e5+10;
int a[N],dp[N][2];
int main() {
	int n;
	scanf("%d",&n);
	for(int i=1; i<=n; i++) {
		scanf("%d",&a[i]);
	}
	if(a[1]==0) dp[1][0]=0,dp[1][1]=1;
	if(a[1]==1) dp[1][0]=1,dp[1][1]=0;
	for(int i=2; i<=n; i++) {
		if(a[i]==0) {
			dp[i][0]=min(dp[i-1][0],dp[i-1][1]+1);
			dp[i][1]=min(dp[i-1][0]+1,dp[i-1][1]+1);
		} else {
			dp[i][0]=min(dp[i-1][0]+1,dp[i-1][1]+1);
			dp[i][1]=min(dp[i-1][1],dp[i-1][0]+1);
		}
	}
	printf("%d",dp[n][0]);
}
 
3.进制转换（模拟） 
3.1题目描述
 
 3.2输入输出样例
 
 3.3解题思路
 先把n从p进制转换为十进制，再从十进制转换为q进制
 3.4源代码
 
#include
using namespace std;
stack ans;
int main() {
	string n;
	int p,q;
	cin>>p>>q>>n;
	if(n=="0") printf("0");
	int num=0;
	for(int i=0; i='0'&&n[i]<='9') num+=n[i]-'0';
		else num+=10+n[i]-'A';
	}
//cout<=0&&k<=9) ans.push('0'+k);
		else ans.push('A'+k-10);
	}
	while(!ans.empty()) {
		printf("%c",ans.top());
		ans.pop();
	}
}

 
4.数列的平方和（前缀和） 
4.1题目描述
 
 4.2输入输出样例
 
 4.3解题思路
 前缀和
 4.4源代码
 
#include
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll a[N];
int main() {
	int test;
	scanf("%d",&test);
	while(test--) {
		int n,m;
		scanf("%d%d",&n,&m);
		ll ans=0,tmp;
		for(int i=1; i<=n; i++) {
			scanf("%lld",&a[i]);
			a[i]=a[i]*a[i];
			if(i<=m) ans+=a[i],tmp=ans;
			else {
				tmp=tmp-a[i-m]+a[i];
				ans=min(tmp,ans);
			}
		}
		printf("%lldn",ans);
	}
}
 
5.骑士移动（BFS） 
5.1题目描述
 
 5.2输入输出样例
 
 
 5.3解题思路
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5711919.html