【题解】计蒜客 2020 蓝桥杯大学 B 组省赛模拟赛（一）

落日映苍穹つ 2023-07-01 03:24 8阅读 0赞

### 试题目录 ###

*  A. 结果填空：有趣的数字（签到）
 *  B. 结果填空：爬楼梯（dp）
 *  C. 结果填空：七巧板（数论）
 *  D. 结果填空：苹果（贪心）
 *  F. 程序设计：寻找重复项（HashMap）
 *  G. 程序设计：被袭击的村庄（模拟）
 *  H. 程序设计：字符串（模拟 + 取模）
 *  J. 程序设计：迷宫（bfs）

# A. 结果填空：有趣的数字（签到） #

> **原题链接：**[https://nanti.jisuanke.com/t/43115][https_nanti.jisuanke.com_t_43115]

*  **思路：** 签到题，直接暴力循环并判断每个数是否既为质数又含有5。

**Code：**

import java.util.*;
    import java.math.*;
    public class Main{ 
    	static boolean isprime(int n) { 
    		if(n==1 || n==0)	return false;
    		for(int i=2;i*i<=n;i++) { 
    			if(n%i==0)
    				return false;
    		}
    		return true;
    	}
    	static boolean check(int n) { 
    		while(n>0) { 
    			if(n%10==5)	return true;
    			n/=10;
    		}
    		return false;
    	}
        public static void main(String[] args){ 
        	int ans=0;
            for(int i=1;i<=100000;i++) { 
            	if(isprime(i) && check(i))
            		ans++;
            }
            System.out.println(ans);
        }
    }

# B. 结果填空：爬楼梯（dp） #

> **原题链接：**[https://nanti.jisuanke.com/t/43116][https_nanti.jisuanke.com_t_43116]

*  **思路：** 简单 dp

**Code：**

import java.util.*;
    import java.math.*;
    public class Main{ 
    	static int[] dp = new int[15];
        public static void main(String[] args){ 
        	dp[0]=1;	dp[1]=1;	
        	dp[2]=2;	dp[3]=4;
        	for(int i=4;i<=10;i++) { 
    			if(i==5 || i==7)	continue;
    			dp[i]=dp[i]+dp[i-1]+dp[i-2]+dp[i-3]+dp[i-4];
        	}
        	System.out.println(dp[10]);
        }
    }

# C. 结果填空：七巧板（数论） #

> **原题链接：**[https://nanti.jisuanke.com/t/43117][https_nanti.jisuanke.com_t_43117]

*  **思路：** 第一条直线最多可以划分出 6 个区域，以后每次划分比上次多划分一个区域出来，即 f\[i\] = f\[i-1\] + 1，故答案是47。

**Code：**

import java.util.*;
    import java.math.*;
    public class Main{ 
    	static int[] f = new int[10];
        public static void main(String[] args){ 
        	int ans=7;
        	f[1]=6;
        	ans+=f[1];
        	for(int i=2;i<=5;i++) { 
        		f[i]=f[i-1]+1;
        		ans+=f[i];
        	}
        	System.out.println(ans);
        }
    }

# D. 结果填空：苹果（贪心） #

> **原题链接：**[https://nanti.jisuanke.com/t/43118][https_nanti.jisuanke.com_t_43118]

*  **思路：** 有三种方法，分别是先取连续的三个 1，再取一个的 3 ；先取一个的 3 ，再取连续的三个 1；从左到右推过去，能取一个的 3 的就取，取完后再用后面两个篮子来凑连续的三个 1 ，答案分别是 58，57，62，故取最大的。下面只给出了第三种方案的代码。

**Code：**

import java.util.*;
    import java.math.*;
    public class Main{ 
    	static int[] a = new int[35];
        public static void main(String[] args){ 
        	Scanner cin = new Scanner(System.in);
        	int ans=0;
        	for(int i=1;i<=30;i++) 
        		a[i]=cin.nextInt();
        	for(int i=1;i<=30;i++) { 
        		ans+=a[i]/3;
        		a[i]%=3;
        		while(a[i]>0 && a[i+1]>0 && a[i+2]>0) { 
        			ans++;
        			a[i]--;a[i+1]--;a[i+2]--;
        		}
        	}
        	System.out.println(ans);
        }
    }

# F. 程序设计：寻找重复项（HashMap） #

> **原题链接：**[https://nanti.jisuanke.com/t/43120][https_nanti.jisuanke.com_t_43120]

*  **思路：** 这道题一开始直接模拟然后用数组标记一出现过的数值，但是只过了 6 个样例，因为数组一般只能定义到 1e7 的范围。所以用 HashMap 就不怕内存会超了。如果是用 C++ 的话，就得用 unorder\_map ，不然 AC 不了。还有 记得全部用 long 型，否则还是过不了一些样例。  
    \-感觉蓝桥杯好坑，又不能评测，又要在一次测试样例设坑！！！

**Code：**

import java.util.Scanner;
    import java.util.HashMap;
    public class Main{ 
    	static long[] f = new long[2000100];
        public static void main(String[] args){ 
        	Scanner cin = new Scanner(System.in);
        	HashMap<Long,Long> mp = new HashMap<Long,Long>();
        	long a = cin.nextLong(), b = cin.nextLong(), c = cin.nextLong();
        	f[0] = 1;
        	mp.put(f[0],(long)1);
        	for(int i=1;i<=2000000;i++) { 
        		f[i] = (f[i-1]*a+f[i-1]%b)%c;
        		if(mp.get(f[i])!=null) { 
        			System.out.println(i);
        			return;
        		}else	mp.put(f[i], (long)1);
        	}
        	System.out.println(-1);
        }
    }

# G. 程序设计：被袭击的村庄（模拟） #

> **原题链接：**[https://nanti.jisuanke.com/t/43121][https_nanti.jisuanke.com_t_43121]

*  **思路：** 这是一道差点要了我的命的模拟题。

1.  首先答案应该弄错了，这个出题人确实该喷，这套题已经好多道题目答案弄错了（C、D题比赛时的答案错的，已经改了，而这道答案错了，至今还没改）。输出的应该是道路、房屋、田地耐久度分别为 0 的数目，以及整个村庄受到的总伤害。而不是输出道路、房屋、田地分别受到的伤害以及村庄受到的总伤害。
2.  直接模拟，要注意的就是炸弹伤害那里的循环变量，要定义两个新的变量来表示炸弹范围里的坐标，而不是直接用地图的坐标。
3.  最后，一开始因为有个细节写错了，导致改了很久，找不出bug（哭了）。但是数据很水，这个错误后来没改过来居然还给我过了。
4.  直接用 C++ 吧，我累了，不想要再写一遍 Java 了。

**Code：**

#include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn=0x3f3f3f3f;
    const int pi=acos(-1.0);
    const int mod=1e9+7;
    int v[550][550],maps[550][550],life[550][550];
    ll sum=0,d_sum=0,f_sum=0,t_sum=0;
    int dx[8]={ -1,-1,-1,0,0,1,1,1},dy[8]={ 1,0,-1,1,-1,1,0,-1};
    int main(){ 
        ll n,m;    cin>>n>>m;
        ll a,b,c;  cin>>a>>b>>c;
        ll k,w; cin>>k>>w;
        for(int i=1;i<=k;i++)
            for(int j=1;j<=k;j++)
                cin>>v[i][j];
        for(int i=1;i<=n;i++){ 
            for(int j=1;j<=m;j++){ 
                cin>>maps[i][j];
                if(maps[i][j]==1)  life[i][j]=a;
                else if(maps[i][j]==2)  life[i][j]=b;
                else if(maps[i][j]==3)  life[i][j]=c;
            }
        }
        int q;  cin>>q;
        while(q--){ 
            int id,x,y;    cin>>id>>x>>y;
            if(id==1){ 
                for(int i=x-k/2,ii=1;i<=x+k/2,ii<=k;i++,ii++)
                    for(int j=y-k/2,jj=1;j<=y+k/2,jj<=k;j++,jj++){ 
                        if(i<=0 || i>n || j<=0 || j>m)    continue;
                        if(life[i][j]){ 
                            if(life[i][j]>v[ii][jj])    life[i][j]-=v[ii][jj];
                            else    life[i][j]=0;
                        }
                    }
            }
            else if(id==0){ 
                for(int i=x-k/2,ii=1;i<=x+k/2,ii<=k;i++,ii++)
                    for(int j=y-k/2,jj=1;j<=y+k/2,jj<=k;j++,jj++){ 
                        if(i<=0 || i>n || j<=0 || j>m)    continue;
                        if(life[i][j]){ 
                            if(life[i][j]>v[ii][jj])    life[i][j]-=v[ii][jj];
                            else    life[i][j]=0;
                        }
                        for(int d=0;d<8;d++){ 
                            int xx=dx[d]+i,yy=j+dy[d];
                            if(xx<=0||yy<=0||xx>n||yy>m) continue;
                            if(life[xx][yy]){ 
                                if(life[xx][yy]<=w) life[xx][yy]=0;
                                else life[xx][yy]-=w;
                        }
                    }
                    }
            }
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(maps[i][j]==1){ 
                     if(!life[i][j])    d_sum++;
                     sum+=(a-life[i][j]);
                }
                else if(maps[i][j]==2){ 
                     if(!life[i][j])    f_sum++;
                     sum+=(b-life[i][j]);
                }
                else if(maps[i][j]==3){ 
                     if(!life[i][j])    t_sum++;
                     sum+=(c-life[i][j]);
                }
        cout<<d_sum<<' '<<f_sum<<' '<<t_sum<<endl;
        cout<<sum<<endl;
        return 0;
    }

# H. 程序设计：字符串（模拟 + 取模） #

> **原题链接：**[https://nanti.jisuanke.com/t/43122][https_nanti.jisuanke.com_t_43122]

*  **思路：** 先把字符串转换为 26 进制，转换的过程要对 m 取模，然后双重循环暴力遍历，对任意两个字符进行转换，把转换后的字符串与原始字符串的差值加上原始字符串的值，再加上 m （为了防止出现负数的情况，但数据比较少，没考虑这种情况），判断是否为 m 的倍数。这道题的难点我觉得在于取模，每一步能取模的都要取模，不然只能通过 6 个样例。

**Code：**

import java.util.Scanner;
    public class Main{ 
    	static long m;
    	static long[] a = new long[2010];
    	static long change(String s) { 
    		long ans=0;
    		for(int i=0;i<s.length();i++)
    			ans=(ans*26+s.charAt(i)-'A')%m;
    		return ans;
    	}
        public static void main(String[] args){ 
        	Scanner cin = new Scanner(System.in);
        	String str = cin.next();
        	m = cin.nextInt();
        	int len = str.length();
        	a[len-1]=1;
        	for(int i=len-2;i>=0;i--)
        		a[i]=a[i+1]*26%m;
        	long ans = change(str);
        	if(ans==0) { 
        		System.out.println("0 0");
        		return;
        	}
        	for(int i=0;i<len;i++) { 
        		for(int j=i+1;j<len;j++) { 
        			long res = (str.charAt(j)-str.charAt(i))*a[i]+(str.charAt(i)-str.charAt(j))*a[j];
        			if((ans+res+m)%m==0) { 	//加上m防止出现负数
        				System.out.println(++i + " " + ++j);	//要用双引号
        				return;
        			}
        		}
        	}
        	System.out.println("-1 -1");
        }
    }

# J. 程序设计：迷宫（bfs） #

> **原题链接：**[https://nanti.jisuanke.com/t/43124][https_nanti.jisuanke.com_t_43124]

*  **思路：** 要求最少花费，可知是用 bfs ，因为到了传送门会立即传送，不可选择，所以对于队列里的点，要先判断是否为传送点，若是且传送终点符合条件就压入队列。如果不是传送点就判断四周的点是否符合条件。

**C++ Code：**

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    using namespace std;
    typedef long long ll;
    int n,m,ex,ey;
    int dir[4][2] = { { 1,0},{ -1,0},{ 0,1},{ 0,-1}};
    int vis[1010][1010],to[1010][1010];
    char maps[1010][1010];
    struct node{ 
        int x,y,v;
    };
    struct node1{ 
        int a,b,c,d;
    }door[1010];
    bool check(int x,int y){ 
        if(x<1 || x>n || y<1 || y>m || maps[x][y]=='*' || vis[x][y])
            return false;
        return true;
    }
    int bfs(){ 
        queue<node> q;
        node s;
        s.x=1,s.y=1,s.v=0;
        vis[1][1]=1;
        q.push(s);
        while(!q.empty()){ 
            node now = q.front();
            q.pop();
            int flag=0;
            if(to[now.x][now.y]){ 
                flag=1;
                int t = to[now.x][now.y];
                if(check(door[t].c,door[t].d)){ 
                    vis[door[t].c][door[t].d]=1;
                    node next;
                    next.x=door[t].c, next.y=door[t].d;
                    next.v=now.v;
                    if(next.x==ex && next.y==ey)	return next.v;
                    q.push(next);
                }
            }
            if(!flag){ 
                for(int i=0;i<4;i++){ 
                    int xx = now.x+dir[i][0];
                    int yy = now.y+dir[i][1];
                    if(check(xx,yy)){ 
                        vis[xx][yy]=1;
                        node next;
                        next.x=xx, next.y=yy, next.v=now.v+1;
                        if(xx==ex && yy==ey)    return next.v;
                        q.push(next);
                    }
                }
            }
        }
        return -1;
    }
    int main(){ 
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>maps[i][j];
        int q;  cin>>q;
        for(int i=1;i<=q;i++){ 
            cin>>door[i].a>>door[i].b>>door[i].c>>door[i].d;
            to[door[i].a][door[i].b]=i;
        }
        cin>>ex>>ey;
        int ans=bfs();
        if(ans==-1)   cout<<"No solution"<<endl;
        else    cout<<ans<<endl;
        return 0;
    }

**Java Code：**

import java.util.*;
    import java.math.*;
    class node{ 
    	int x,y,v;
    	public node(){ };
    	public node(int x,int y,int v) { 
    		this.x=x;
    		this.y=y;
    		this.v=v;
    	}
    }
    class node1{ 
    	int a,b,c,d;
    	public node1(){ };
    	public node1(int a,int b,int c,int d) { 
    		this.a=a;
    		this.b=b;
    		this.c=c;
    		this.d=d;
    	}
    }
    public class Main { 
    	static int n,m,ex,ey;
    	static int[][] dir = { { 1,0},{ -1,0},{ 0,1},{ 0,-1}};
    	static char[][] ch = new char[1010][1010];
    	static Queue<node> q = new LinkedList<node>();
    	static node1[] door = new node1[1010];
    	static int[][] to = new int[1010][1010];
    	static int[][] vis = new int[1010][1010];
    	static boolean check(int x,int y) { 
    		if(x<1 || x>n || y<1 || y>m || vis[x][y]==1 || ch[x][y]=='*')
    			return false;
    		return true;
    	}
    	static int bfs() { 
    		node s = new node(1,1,0);
    		vis[1][1]=1;
    		q.add(s);
    		while(!q.isEmpty()) { 
    			node now = q.poll();
    			int flag=0;
    			if(to[now.x][now.y]>0) { 
    				flag=1;
    				int t = to[now.x][now.y];
    				if(check(door[t].c,door[t].d)) { 
    					vis[door[t].c][door[t].d]=1;
    					node next = new node(door[t].c,door[t].d,now.v);
    					if(next.x==ex && next.y==ey)	return next.v;
    					q.add(next);
    				}
    			}
    			if(flag==0) { 
    				for(int i=0;i<4;i++) { 
    					int xx = now.x + dir[i][0];
    					int yy = now.y + dir[i][1];
    					if(check(xx,yy)) { 
    						vis[xx][yy] = 1;
    						node next = new node(xx,yy,now.v+1);
    						if(xx==ex && yy==ey)	return next.v;
    						q.add(next);
    					}
    				}
    			}
    		}
    		return -1;
    	}
    	public static void main(String[] args) { 
    		Scanner cin = new Scanner(System.in);
    		n = cin.nextInt(); m = cin.nextInt();
    		for(int i=1;i<=n;i++) { 
    			String str = cin.next();
    			for(int j=0;j<m;j++)
    				ch[i][j+1] = str.charAt(j);
    		}
    		int q = cin.nextInt();
    		new node();		//初始化类，不然会报空指针异常
    		for(int i=1;i<=q;i++)	//初始化类，不然会报空指针异常
    			door[i] = new node1();
    		for(int i=1;i<=q;i++) { 
    			door[i].a = cin.nextInt();
    			door[i].b = cin.nextInt();
    			door[i].c = cin.nextInt();
    			door[i].d = cin.nextInt();
    			to[door[i].a][door[i].b] = i;
    		}
    		ex = cin.nextInt();	ey = cin.nextInt();
    		int ans = bfs();
    		if(ans==-1)	System.out.println("No solution");
    		else	System.out.println(ans);
    	}
    }

[https_nanti.jisuanke.com_t_43115]: https://nanti.jisuanke.com/t/43115
[https_nanti.jisuanke.com_t_43116]: https://nanti.jisuanke.com/t/43116
[https_nanti.jisuanke.com_t_43117]: https://nanti.jisuanke.com/t/43117
[https_nanti.jisuanke.com_t_43118]: https://nanti.jisuanke.com/t/43118
[https_nanti.jisuanke.com_t_43120]: https://nanti.jisuanke.com/t/43120
[https_nanti.jisuanke.com_t_43121]: https://nanti.jisuanke.com/t/43121
[https_nanti.jisuanke.com_t_43122]: https://nanti.jisuanke.com/t/43122
[https_nanti.jisuanke.com_t_43124]: https://nanti.jisuanke.com/t/43124