signed

QiShunwang

“诚信为本、客户至上”

2021.5.14 2022蓝桥杯练习赛2

2021/5/14 21:59:43   来源:

2021.5.14 2022蓝桥杯练习赛2

闲话:
1、就难度而言,练习赛2较练习赛1有了一定的提高,可能开始会有点不太自信,但这是属于正常现象,多练就会做了。
2、就体验而言,这场练习赛有一两个题需要认真读题,题目没有想的那么简单,还是有一定思考和有一点小坑的
3、没什么,昨天是2021年5月13号,需要记住的日子。

题目
1、试题 算法训练 筛选号码在这里插入图片描述
解析:本题真的是一道在经典不过的题目了,解题是应该要看一眼就知道这是裸的约瑟夫环问题,直接上公式就可以了。当然厉害一点的也可以去模拟这个过程,数据n<10000应该也是可以的。

公式:s=(s+m)%i; (s为值,初始为0,m表示每次从1开始的第m个人出去,记得输出答案是s+1,和for循环从i=2开始)

查漏补缺:约瑟夫环——公式法(递推公式)
推荐这篇博文,当时我也是看的这篇去理解的约瑟夫环问题

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,s=0;
	cin>>n;
	for(int i=2;i<=n;i++)
	{
		s=(s+3)%i;
	}
	cout<<s+1;
}

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

2、试题 算法训练 最大体积
在这里插入图片描述
解析:本题感觉跟完全背包有点像,但在完全背包的基础上有点改动,归结为完全背包的拓展+数学思维。本题虽然数据较小,但我觉得这题还是不能纯暴力乱搞,当然主要是我也不会。
思路:
1、首先我们应该考虑什么情况会使得有无限解。经过我非非非常认真的思考, 我发现,如果所有体积的gcd值为1的时候,我们可以组成无数多种情况,这样一直组成下去,总会存在比当前认为的最大值更大的数。所以此时就有无限解输出0。(可能是我的LJ编译器不支持gcd和__gcd(a,b)函数同时使用,不然会无法识别我的gcd什么的,所以代码中用变量t记录所有体积的gcd值
2、现在我们知道是有限解了,那么怎么求值可能又是大家遇到的第二个问题。
因为输出最大不可能值,没有其他限制条件,那么直接从大到小遍历vis数组找到第一个vis[i]==0就可以了,下标即答案。
3、怎么给vis数组赋值。这就是完全背包的问题了。上次发了背包九讲问题的学习链接,应该都会完全背包了,这里就不细说了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll n,t;
ll a[15];
bool vis[N];

bool check(){
    for(int i=1;i<=n;i++){
        t=__gcd(t,a[i]);
    }
    return t==1;
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        vis[a[i]]=1;
    }
    if(check()){
        for(int i=1;i<=n;i++){
            for(int j=a[i];j<N;j++){
                vis[j]|=vis[j-a[i]];
            }
        }
        for(int i=N-1;;i--){
            if(!vis[i]){
                cout<<i<<"\n";
                return 0;
            }
        }
    }
    else puts("0");
}

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

3、试题 算法提高 笨小猴
在这里插入图片描述
解析:这个题是我这次没有一发ac的题,但这个题是真的是个**题
可以使用map来记录’a’~~'z’中每个字符出现的次数。记得每个字符初始出现的此处都是0,且输入字符串没有某字符时,该字符对应的a[i]值也是0,这一点需要在求最小值的时候特别注意。其他的应该没什么,就是考对使用map的使用。

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
map<int,int>a;
string s;
int maxn=-inf,minn=inf,cha;
int main(){
    cin>>s;
    for(int i=0;i<s.length();i++){
        a[s[i]-'a']++;  //使mp中字符'a'对应数字0,字符'b'对应数字1....字符'z'对应数字25,这样后面遍历顺眼点
    }
    for(int i=0;i<26;i++){
        maxn=max(maxn,a[i]);
        if(a[i]!=0) minn=min(minn,a[i]);  //a[i]值等于0即代表没有出现过该字符,不予考虑
    }
    cha=maxn-minn;
    if(cha==1||cha==0){
        cout<<"No Answer\n"<<"0";
        return 0;       
    }
    for(int i=2;i<cha;i++){
        if(cha%i==0){
            cout<<"No Answer\n"<<"0";
            return 0;
        }
    }
    cout<<"Lucky Word\n"<<cha;
}

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

4、试题 算法提高 学霸的迷宫
在这里插入图片描述
解析:这类走迷宫问题,百分之九十九会用到bfs算法
这都不能说是算法了,在平常的算法比赛中bfs是一种必备的基础技能,需要掌握。这题是在问 走出迷宫的最短路径长度问题的基础上,加上输出最短路径,其他的都一模一样。
十分巧的是上学期我的一个课设题目就是迷宫问题,且要求跟这个题目大同小异,十分感谢涛哥当时教了我一手,所以这个题基本就被我水过去了。(加粗感谢涛哥)
思路:
1、跟普通的走迷宫问题一样,我利用队列queue的先进先出的特性,来遍历每个到达的点,因为每个节点的信息不只是x,y,还有一个走到的step需要记录,所以这里用pair是不太现实的了,不过没有关系,我可以用struct,这是没得丝毫影响的。当到了点(n,m)时,输出当前step的就是最小步数了。我们就成功解决了第一小问。
2、第二小问是输出路径。这个要求是如果有多条长度相同的最短路径,选择在此表示方法下字典序最小的一个。这个为难了我,平时写dx数组、dy数组的写法,不过这都问题不大,就是看着感觉别扭 。剩下的就是这for循环四个方向的时候,去记录一下该次操作是什么,我这里用cz数组记录的是第几种操作,开始用to数组打表相应操作,最后输出就可以了。

#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,m;
char mp[N][N];
bool vis[N][N];
int cz[N][N];
int dx[5]={1,0,0,-1};
int dy[5]={0,-1,1,0};
char to[5]={"DLRU"};
struct node{
    int x,y,step;
};
queue<node>q;

void bfs(){
    q.push({1,1,0});
    vis[1][1]=1;

    while(!q.empty()){
        node t=q.front();
        q.pop();
        if(t.x==n&&t.y==m){
            cout<<t.step<<"\n";
            return;
        }
        for(int i=0;i<4;i++){
            int nx=t.x+dx[i];
            int ny=t.y+dy[i];
            int nstep=t.step+1;
            if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&mp[nx][ny]=='0'&&!vis[nx][ny]){
                cz[nx][ny]=i;
                q.push({nx,ny,nstep});
                vis[nx][ny]=1;
            }
        }
    }
}

void Step(int n,int m){
    if(n==1&&m==1) return;
    Step(n-dx[cz[n][m]],m-dy[cz[n][m]]);
    cout<<to[cz[n][m]];
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>mp[i][j];
        }
    }
    bfs();
    Step(n,m);
}

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

5、试题 算法训练 友好数
在这里插入图片描述
解析:本题应该是本场最简单的题。没有小细节,也没有考算法,唯一考了就是C语言基础。用suma、sumb分别记录a、b除开自身的约数和。然后if(suma==b && sumb == a) 为真就输出yes,否则就输出no。 数据才10000,直接两次for循环解决。

#include<bits/stdc++.h>
using namespace std;
int a,b;
int suma,sumb;

int main(){
    cin>>a>>b;
    for(int i=1;i<a;i++){if(a%i==0) suma+=i;}
    for(int i=1;i<b;i++){if(b%i==0) sumb+=i;}
    if(suma==b&&sumb==a) puts("yes");
    else puts("no");
}

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

6、试题 算法提高 高精度乘法
在这里插入图片描述
解析:这个题是一个好题,反正我是不太会。
Python在这里插入图片描述
C++(龚神)
在这里插入图片描述
C++(自己)
在这里插入图片描述

Java(队友)
在这里插入图片描述
FFT学习链接
这类高精题我还是挺喜欢用Python的,根据代码长度占用空间来看,很明显的发现码量:Python(40B)<Java(367B)<C++(1.584KB)<C++(1.742KB)。
(龚神的代码还加了一些其他的东西,所以会比我的代码长些,但本质都一样,没有不同。)

可惜我Python学艺不精只a90分;
Java是队友以前帮我写的,就是用Java中的大数,然后就莫名其妙的ac了;
C++是龚神以前帮我写的,当时不会NTT,(现在也不怎么会,但也有了自己的NTT板子,跟巨佬差距还是挺大的)

思路:好好学习,去看看FFT或NTT。平时大家肯定主要都是用C++做题,而且在蓝桥的竞赛中,报名了C/C++组,中途是不能用Java或Python去解题的。所以最好还是要会用C++做题。

这里我仅贴出代码,有兴趣的同学可以课余自己去了解。

Java代码- - -队友的解法

import java.io.*;
import java.math.*;
import java.util.*;
import java.text.*;

public class Main {
	public static void main(String[] args) {
		  Scanner cin = new Scanner (new BufferedInputStream(System.in));
		  BigDecimal a=cin.nextBigDecimal();
		  BigDecimal b=cin.nextBigDecimal();
		  BigDecimal ans=a.multiply(b);
		  System.out.println(ans.toString());
	}

}

-----------------------------------------------------------------------------------------------
C++代码- - -龚神的模板

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+10, P = 998244353, G = 3, Gi = 332748118;

string s;
int cnta, cntb;
int limit = 1, L, rev[MAXN];
long long a[MAXN], b[MAXN];

int cs(long long *A) {
	for(int i = 0;i < s.length(); i++) A[i] = s[i]-'0';
	return (int)s.length();
}

inline long long fastpow(long long a, long long k) {
	long long base = 1;
	while(k) {
		if(k & 1) base = (base * a ) % P;
		a = (a * a) % P;
		k >>= 1;
	}
	return base % P;
}

inline void NTT(long long *A, int type) {
	for(int i = 0; i < limit; i++) 
		if(i < rev[i]) swap(A[i], A[rev[i]]);
	for(int mid = 1; mid < limit; mid <<= 1) {
		long long Wn = fastpow( type == 1 ? G : Gi, (P - 1) / (mid << 1));
		for(int j = 0; j < limit; j += (mid << 1)) {
			long long w = 1;
			for(int k = 0; k < mid; k++, w = (w * Wn) % P) {
				int x = A[j + k], y = w * A[j + k + mid] % P;
				A[j + k] = (x + y) % P,
				A[j + k + mid] = (x - y + P) % P;
			}
		}
	}
}

void init() {
	for(int i = 0;i < MAXN; i++) {
		a[i] = 0; b[i] = 0;
	}
}

int main() {
	while(cin >> s) {
		init();
		cnta = cs(a);
		cin >> s;
		cntb = cs(b);
		
		while(limit <= cnta + cntb) limit <<= 1, L++;
		for(int i = 0; i < limit; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (L - 1));
		
		NTT(a, 1); NTT(b, 1);
		for(int i = 0;i < limit; i++) a[i] = (a[i]*b[i]) % P;
		NTT(a, -1);
		long long inv = fastpow(limit, P-2);
		
		for(int i = 0;i <= cnta+cntb; i++) a[i] = (a[i]*inv)%P;
		vector <int> res;
		int jin = 0;
		for(int i = cnta+cntb-2; i >= 0; i--) {
			int now = a[i];
			now += jin;
			jin = now/10;
			now %= 10;
			res.push_back(now);
		}
		while(jin) {
			res.push_back(jin%10);
			jin /= 10;
		}
		
		reverse(res.begin(), res.end());
		for(int i = 0;i < res.size(); i++) printf("%d", res[i]); puts("");
	}
}

-----------------------------------------------------------------------------------------------
C++代码- - -自己的模板

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define IOS ios::sync_with_stdio(0)
using namespace std;
typedef long long ll;
const ll N=5e6+5;
const double pi=acos(-1);
string s;
ll n,m,limit,c[N];


struct complex{
	double real,imag;
	complex(double X=0,double Y=0){real=X;imag=Y;}
}a[N],b[N];

inline complex operator +(complex a,complex b){return complex(a.real+b.real,a.imag+b.imag);}
inline complex operator -(complex a,complex b){return complex(a.real-b.real,a.imag-b.imag);}
inline complex operator *(complex a,complex b){return complex(a.real*b.real-a.imag*b.imag,a.real*b.imag+a.imag*b.real);}

void FFT(complex *a,ll op){
	for(ll i=0;i<limit;i++){if(i<c[i]) swap(a[i],a[c[i]]);}
	for(ll mid=1;mid<limit;mid<<=1){
		complex W(cos(pi/mid),op*sin(pi/mid));
		for(ll r=mid<<1,j=0;j<limit;j+=r){
			complex w(1,0);
			for(ll l=0;l<mid;l++,w=w*W){
				complex x=a[j+l],y=w*a[j+mid+l];
				a[j+l]=x+y; a[j+mid+l]=x-y;
			}
		}
	}
}

int main(){
	 IOS; 
	 cin>>s; n=s.size()-1;
	 for(ll i=0;i<=n;i++) a[n-i].real=s[i]-48;
	 cin>>s; m=s.size()-1;
	 for(ll i=0;i<=m;i++) b[m-i].real=s[i]-48;
	 limit=1;
	 
	 ll l=0;
	 while(limit<=n+m){
	 	limit<<=1;
	 	l++;
	 }
	 
	 for(ll i=0;i<limit;i++) c[i]=(c[i>>1]>>1)|((i&1)<<(l-1));
	 FFT(a,1);FFT(b,1);
	 for(ll i=0;i<=limit;i++) a[i]=a[i]*b[i];
	 FFT(a,-1);
	 
	 memset(c,0,sizeof(c));
	 for(ll i=0;i<=n+m+1;i++) c[i]=a[i].real/limit+0.5;
	 for(ll i=0;i<=n+m;i++){
	 	c[i+1]+=c[i]/10;
	 	c[i]%=10;
	 }
	 limit=n+m+1;
	 while(c[limit]){
	 	c[limit+1]+=c[limit]/10;
	 	c[limit]%=10;
	 	limit++;
	 }
	 
	 for(ll i=limit-1;i>=0;i--) cout<<c[i];
	 return 0;
}

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

总结

1、本次可能有那么几道有难度的题,千万别灰心,多问,多做题,多学算法。一段时间后编程水平会有显著提高的。只要认真学了,这是必然的。
2、还是要背一些通用模板的 ,大部分平时用的多模板是要知道的,多用可以加深印象,但最好是在理解的基础上多去码几遍模板。正式的蓝桥杯是不能带模板进去的,所以认为有用的模板最好记到脑子里。虽然我也不记得这里的fft模板。
3、学习虽然重要,但还是得加强身体锻炼。比赛长达4小时,有的长达5小时,这还真不是一件容易的事。加强锻炼,在比赛等其他方面才更有优势。