maxn

用户名：maxn

访问量：8205

签　名：

等　　级
排　　名	7100
经　　验	1345
参赛次数	0
文章发表	5
年　　龄	0
在职情况	学生
学　　校	zut
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

蓝桥杯算法提高VIP-找素数-题解(C++代码)
浏览：1004

你可能喜欢

Day7 + Day8 + Day9题解

　　作者: maxn　　　　发表时间：2020-01-20 20:01:20 浏览：465　|　评论：0　

#### Day7
##### 问题 1548: [蓝桥杯][算法提高VIP]盾神与砝码称重
  刚开始用dp的方法，算出给出的最大的数的所使用的砝码的种数，提交之后未通过，才发现砝码是左右两边都可以放置。由于数据比较小，所以直接$$dfs$$即可。
```c
//dp未通过代码
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=1e6+10;
const int inf=0x3f3f3f3f;
int nw[maxn],mw[maxn];
int dp[maxn];

int main(){
	int mmax=0;
	int n,m; scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&nw[i]);
	for(int i=1;i<=m;i++){
		scanf("%d",&mw[i]);
		mmax=max(mmax,mw[i]);
	}
	memset(dp,0x3f,sizeof(dp));
	dp[0]=0;
	//cout<<mmax<<endl;
	for(int i=1;i<=n;i++){
		for(int j=mmax;j>=nw[i];j--){
			dp[j]=min(dp[j],dp[j-nw[i]]+1);
		}
	}
	//for(int i=1;i<=mmax;i++) cout<<dp[i]<<" "; cout<<endl;
	for(int i=1;i<=m;i++){
		if(dp[mw[i]]!=inf) puts("YES");
		else puts("NO");
	}
	return 0;
}
```
```c
//dfs通过代码
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=1e6+10;
const int inf=0x3f3f3f3f;
int nw[maxn],mw[maxn];
int n,m;

bool dfs(int l,int r,int cnt){
	if(cnt>n+1) return false;//全部选完为满足条件返回false
	else if(l==r) return true;//两边一样重返回true
	else{
		return dfs(l+nw[cnt],r,cnt+1)||dfs(l,r+nw[cnt],cnt+1)||dfs(l,r,cnt+1);
		//三种情况，砝码放左边，不放砝码和砝码放右边
	}
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&nw[i]);
	for(int i=1;i<=m;i++) scanf("%d",&mw[i]);
	for(int i=1;i<=m;i++){
		if(dfs(0,mw[i],1)) puts("YES");
		else puts("NO");
	}
	return 0;
```
##### 问题 1630: [蓝桥杯][算法训练VIP]摆动序列
  通过题目的描述我们可以发现，任意选择 2, 3, 4, ..., n-1, n 个数我们在选出的每一组数中我们都可以组成一组摆动数列，然后逆序就又是一组摆动数列。那么答案就是
  $$(C_{n}^{2}+C_{n}^{3}+C_{n}^{4}+.. .+C_{n}^{n-1}+C_{n}^{n})*2$$。

我们知道$$C_{n}^{0}+C_{n}^{1}+C_{n}^{2}+.. .+C_{n}^{n-1}+C_{n}^{n} = 2^{n}$$

那么就有$$(ans=2^{n}-1-n)*2$$
```c
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=1e5+10;

int main(){
	int k; scanf("%d",&k);
	ll ans=(1<<k)-k-1;
	printf("%lld\n",ans*2);
}
```
##### 问题 1923: [蓝桥杯][算法提高VIP]学霸的迷宫
  前面题解中有些过，不在叙述。直接bfs即可。
```c
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=1e3+10;
const int inf=0x3f3f3f3f;
string str[maxn];
bool vis[maxn][maxn];
int n,m;
//DLRU
int net[4][2]={{1,0},{0,-1},{0,1},{-1,0}};

struct Node{
	int x,y,step;
	string way="";
	Node(){}
	Node(int x,int y,int step,string way):x(x),y(y),step(step),way(way){}; 
};

struct Ans{
	int step=inf;
	string way="";
}ans;

bool check(int x,int y){
	if(x<0||x>=n||y<0||y>=m)
		return false;
	return true;
}

bool bfs(int x,int y){
	queue<Node>q; q.push(Node(x,y,0,""));
	vis[x][y]=true;
	while(!q.empty()){
		Node node=q.front();q.pop();
		if(node.x==n-1&&node.y==m-1){
			ans.step=node.step;
			ans.way+=node.way;
			return true;
		}
		for(int i=0;i<4;i++){
			int netx=node.x+net[i][0];
			int nety=node.y+net[i][1];
			if(check(netx,nety)&&str[netx][nety]=='0'&&!vis[netx][nety]){
				string str1=""; str1+=node.way; vis[netx][nety]=true;
				if(i==0) str1+="D";
				else if(i==1) str1+="L";
				else if(i==2) str1+="R";
				else str1+="U";
				q.push(Node(netx,nety,node.step+1,str1));
			}
		}
	}
	return false;
}

int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++) cin>>str[i];
	bool flag=bfs(0,0);
	if(flag) cout<<ans.step<<endl<<ans.way<<endl;
	else cout<<"0"<<endl; 
	return 0;
}
```
#### Day8
##### 问题 1188: 做幻方
  如图：
![](/image_editor_upload/20200205054200_11881.png)
从图中即可看出规律，我们刚开始先把矩阵初始化为 0，然后从 1 开始赋值，直到矩阵中没有 0 即可，此题目输出时，每一个样例之后都空出来一行。
```c
#include<bits/stdc++.h>
using namespace std;

const int maxn=40;
int a[maxn][maxn];

int main(){
	int n; 
	while(scanf("%d",&n)&&n){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++) a[i][j]=0;
		}
		int cnt=0;
		a[n-1][n/2]=++cnt;
		int i=0,j=(n/2+1)%n;
		while(!a[i][j]){
			a[i][j]=++cnt;
			if(cnt%n==0){
				i=(i-1)%n;
				if(i==-1) i=n-1;
			}else{
				i=(i+1)%n;
				j=(j+1)%n;
			}
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(n*n<10) printf("%d",a[i][j]);
				else if(n*n<100) printf("%2d",a[i][j]);
				else if(n*n<1000) printf("%3d",a[i][j]);
				printf("%c",j==n-1?'\n':' ');
			}
		}
		puts("");
	}
	return 0;
}
```
##### 问题 1924: [蓝桥杯][算法提高VIP]01背包
  经典背包问题。直接给出优化算法，解释如下。
```
4 6
1 4
2 6
3 12
2 7
0 4 4 4  4  4  4       放入物品1的收益
0 4 6 10 10 10 10      放入物品2的收益
0 4 6 12 16 18 22      放入物品3的收益
0 4 7 12 16 19 23      放入物品4的收益

以前两行为例，处理dp[2][6]时，就是选择物品2是否要放入背包的过程，此时前面5种背包的状态还是未放入物品2的状态，所以它们此时都是表示上一行的状态。dpi[j]=max(dp[j],dp[j-c[i]]+v[i]);表示的就是dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+v[i]);如果是顺序的话，在计算dp[i][j]时，前面都是已经放过物品2的状态了，那么 dp[j]=max(dp[j],dp[j-c[i]]+v[i]);表示的就是dp[i][j]=max(dp[i][j],dp[i][j-c[i]]+v[i]);

```
```c
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=1e5+10;
const int maxm=1e6+10;
int w[maxn],v[maxn],dp[maxm];

int main(){
	int n,C; scanf("%d%d",&n,&C);
	for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&v[i]);
	for(int i=1;i<=n;i++){
		for(int j=C;j>=w[i];j--){
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	printf("%d\n",dp[C]);
	return 0;
}
```
##### 问题 1467: [蓝桥杯][基础练习VIP]完美的代价
  遍历字符串，找到与当前字符相同的第一个字符(从最后一个字符开始)，然后将该字符放到最后一个位置，此时将最后的这个位置前移，一直重复这样的操作，直到所有的字符都匹配完毕。如果某一字符没有找到与之对应的字符串，这样的字符如果超过两个那么一定无法完成匹配，或者字符串长度为偶数是出现这样的字符也无法完成匹配，此时输出"Impossible"即可。
```c
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=8e3+10;
char str[maxn];

int main(){
	int n; scanf("%d",&n);
	scanf("%s",str);
	int r=n-1; ll ans=0;
	bool flag=false;
	for(int i=0;i<=n/2;i++){//找到前面一半字符所对应的字符 
		for(int j=r;j>=i;j--){
			if(i==j){//未找到相同字母 
				if(n%2==0||flag){//偶数字符串和不是第一次找到这样的字母 
					puts("Impossible");
					return 0;
				}else{//奇数字符串，最后可以直接交换n/2-i次 
					ans+=(ll)n/2-(ll)i;
					flag=true;
					break;
				}
			}
			if(str[i]==str[j]){
				for(int k=j;k<r;k++) swap(str[k],str[k+1]); 
				ans+=(ll)r-(ll)j;
				r--;//最后一个字符位置对应 
				break;
			} 
		}
	}
	printf("%lld\n",ans);
	return 0;
}
```
#### Day9
##### 问题 1825: [蓝桥杯][2015年第六届真题]穿越雷区
  类似于学霸的迷宫，但是比学霸的迷宫简单。直接按照那种方法bfs即可。
```c
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=1e3+10;
char a[maxn][maxn];
int net[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int n,sx,sy;
bool vis[maxn][maxn];

struct Node{
	int x,y,step;
	Node(){}
	Node(int x,int y,int step):x(x),y(y),step(step){}
}node[maxn];

bool check(int x,int y){
	if(x<0||y<0||x>=n||y>=n)
		return false;
	return true;
}

int bfs(){
	queue<Node>q;
	for(int i=0;i<4;i++){
		int netx=sx+net[i][0];
		int nety=sy+net[i][1];
		if(check(netx,nety)){
			vis[netx][nety]=true;
			q.push(Node(netx,nety,1));
		}
	}
	while(!q.empty()){
		Node now=q.front();q.pop();
		if(a[now.x][now.y]=='-'){
			for(int i=0;i<4;i++){
				int netx=now.x+net[i][0];
				int nety=now.y+net[i][1];
				if(a[netx][nety]=='B') return now.step+1;
				if(!vis[netx][nety]&&a[netx][nety]=='+'&&check(netx,nety)){
					vis[netx][nety]=true;
					q.push(Node(netx,nety,now.step+1));
				}
			}
		}else if(a[now.x][now.y]=='+'){
			for(int i=0;i<4;i++){
				int netx=now.x+net[i][0];
				int nety=now.y+net[i][1];
				if(a[netx][nety]=='B') return now.step+1;
				if(!vis[netx][nety]&&a[netx][nety]=='-'&&check(netx,nety)){
					vis[netx][nety]=true;
					q.push(Node(netx,nety,now.step+1));
				}
			}
		}
	}
	return -1;
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			scanf(" %c",&a[i][j]);
			if(a[i][j]=='A'){
				sx=i; sy=j;
			}
		}
	}
	int ans=bfs();
	printf("%d",ans);
	return 0;
}
```
##### 问题 1604: [蓝桥杯][算法训练VIP]阶乘
  这个和前面的阶乘一样，直接模拟乘法，输出第一个不为0的数字即可。
```c
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=1e5+10;

struct BigNum{
	int s[maxn],l;
}ans[110];

BigNum operator *(BigNum a,int b){
	for(int i=0;i<a.l;i++) a.s[i]*=b;
	for(int i=0;i<a.l;i++){
		a.s[i+1]+=a.s[i]/10;
		a.s[i]%=10;
	}
	while(a.s[a.l]!=0){
		a.s[a.l+1]+=a.s[a.l]/10;
		a.s[a.l]%=10;
		a.l++;
	}
	return a;
}

int main(){
	ans[0].s[0]=1,ans[0].l=1;
	for(int i=1;i<=100;i++) ans[i]=ans[i-1]*i;
	int n; scanf("%d",&n);
	for(int i=0;i<ans[n].l;i++){
		if(ans[n].s[i]){
			printf("%d\n",ans[n].s[i]);
			break;
		}
	}
	return 0;
}
```
##### 问题 1609: [蓝桥杯][算法训练VIP]黑色星期五
  日期问题，我们先计算出从$$1998.1.1$$日起到给出年份的每个月$$13$$号都经过了多少天，然后用 mod 7方法判断这一天是否为星期五。
```c
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
int d[14]={0,31,28,31,30,31,30,31,31,30,31,30,31};//每个月天数
ll ans[13]={0,13};//记录1998.1.1到输入年份每个月的13号经过了多少天

bool isR(int y){//判断是否是闰年
	if((y%4==0&&y%100!=0)||y%400==0)
		return true;
	return false;
}

bool isFive(int days){//判断是否是星期五
	if(days%7==2)
		return true;
	return false;
}

int main(){
	int year; scanf("%d",&year);
	ll days=0;
	for(int i=1998;i<year;i++){
		if(isR(i)) days+=(ll)366;
		else days+=(ll)365;
	}
	if(isR(year)) d[2]=29;
	else d[2]=28;
	int cnt=0;
	for(int i=2;i<=12;i++) ans[i]=ans[i-1]+(ll)d[i-1];
	for(int i=1;i<=12;i++){
		ans[i]+=days;
		if(isFive(ans[i])) cnt++;
	}
	printf("%d\n",cnt);
	return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

maxn

TA的其他文章

你可能喜欢

C语言训练-大、小写问题（C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

用筛法求之N内的素数。（C语言代码）

上车人数（C语言代码）

Day7 + Day8 + Day9题解

评论区

精彩推荐

C二级辅导-统计字符（C语言代码）

C二级辅导-同因查找（C语言代码）

字符串的输入输出处理（C语言代码）

破解简单密码（C语言代码）

大神老白（C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

maxn

TA的其他文章

你可能喜欢

C语言训练-大、小写问题 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

用筛法求之N内的素数。 （C语言代码）

上车人数 （C语言代码）

Day7 + Day8 + Day9题解

评论区

精彩推荐

C二级辅导-统计字符 （C语言代码）

C二级辅导-同因查找 （C语言代码）

字符串的输入输出处理 （C语言代码）

破解简单密码 （C语言代码）

大神老白 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言训练-大、小写问题（C语言代码）

用筛法求之N内的素数。（C语言代码）

上车人数（C语言代码）

　　评论区

C二级辅导-统计字符（C语言代码）

C二级辅导-同因查找（C语言代码）

字符串的输入输出处理（C语言代码）

破解简单密码（C语言代码）

大神老白（C语言代码）