蓝桥杯官网历年真题(51 - 55)

PREV55 小计算器

题目描述

问题描述
  模拟程序型计算器,依次输入指令,可能包含的指令有

1. 数字:'NUM X',X为一个只包含大写字母和数字的字符串,表示一个当前进制的数
  2. 运算指令:'ADD','SUB','MUL','DIV','MOD',分别表示加减乘,除法取商,除法取余
  3. 进制转换指令:'CHANGE K',将当前进制转换为K进制(2≤K≤36)
  4. 输出指令:'EQUAL',以当前进制输出结果
  5. 重置指令:'CLEAR',清除当前数字

指令按照以下规则给出:
  数字,运算指令不会连续给出,进制转换指令,输出指令,重置指令有可能连续给出
  运算指令后出现的第一个数字,表示参与运算的数字。且在该运算指令和该数字中间不会出现运算指令和输出指令
  重置指令后出现的第一个数字,表示基础值。且在重置指令和第一个数字中间不会出现运算指令和输出指令
  进制转换指令可能出现在任何地方

运算过程中中间变量均为非负整数,且小于2^63。
  以大写的'A''Z'表示1035
输入格式
  第1行:1个n,表示指令数量
  第2..n+1行:每行给出一条指令。指令序列一定以'CLEAR'作为开始,并且满足指令规则
输出格式
  依次给出每一次'EQUAL'得到的结果
样例输入
7
CLEAR
NUM 1024
CHANGE 2
ADD
NUM 100000
CHANGE 8
EQUAL
样例输出
2040

算法分析

这里主要用到的核心语法是

  • 1、10进制转r进制 Integer.toString(int x,int r)10进制的x转化为r进制,并返回字符串,若x过大,可以写成Long.toString(int x,int r)
  • 2、r进制转10进制 Integer.parseInt(String s,int r)r进制的s转化为10进制,并返回一个数字类型,若返回值过大,可以写成Long.parseLong(String s,int r)
    注意:
  • 10进制转r进制,若有字母,转出来的是小写
  • r进制转10进制,无论x里面包含小写还是大写,出来的数字都是一样的
public class Main {
    //10进制转r进制
    static String ten_to_r(long x,int r)
    {
        return Long.toString(x,r);
    }
    //r进制转10进制
    static long r_to_ten(String s,int r)
    {
        return Long.parseLong(s,r);
    }
    public static void main(String[] args){
        System.out.println(ten_to_r(1000,11)); // 答案:82a
        System.out.println(r_to_ten("82A",11));// 答案:1000
        System.out.println(r_to_ten("82a",11));// 答案:1000
    }
}

模拟
ans记录的是当前10进制的结果(统一记录成10进制),op代表当前的操作数,r表示当前数的进制,输出的时候再从10进制转化为当前进制数

时间复杂度

不清楚

Java 代码

import java.util.Scanner;

public class Main {
    static long ans = -1;//永远记录10进制的答案
    static String op = "#";
    static int r = 10;
    //10进制转r进制
    static String ten_to_r(long x,int r)
    {
        return Long.toString(x,r);
    }
    //r进制转10进制
    static long r_to_ten(String s,int r)
    {
        return Long.parseLong(s,r);
    }
    //ans通过op操作更新答案
    static void update_ans(String op,String x)
    {
        long t = r_to_ten(x,r);//将x变为10进制
        if(op.equals("ADD"))
        {
            ans += t;
        }
        else if(op.equals("SUB"))
        {
            ans -= t;
        }
        else if(op.equals("MUL"))
        {
            ans *= t;
        }
        else if(op.equals("DIV"))
        {
            ans /= t;
        }
        else if(op.equals("MOD"))
        {
            ans %= t;
        }
        
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        while(n -- > 0)
        {
            String t = scan.next();
            if(t.equals("CLEAR"))
            {
                ans = -1;
            }
            else if(t.equals("NUM"))
            {
                String x = scan.next();
                if(ans == -1) ans = r_to_ten(x,r);
                else update_ans(op,x);
            }
            else if(t.equals("CHANGE"))
            {
                r = Integer.parseInt(scan.next());
            }
            else if(t.equals("ADD"))
            {
                op = "ADD";
            }
            else if(t.equals("SUB"))
            {
                op = "SUB";
            }
            else if(t.equals("MUL"))
            {
                op = "MUL";
            }
            else if(t.equals("DIV"))
            {
                op = "DIV";
            }
            else if(t.equals("MOD"))
            {
                op = "MOD";
            }
            else 
            {
                String temp = ten_to_r(ans,r);
                for(int i = 0;i < temp.length();i ++)
                {
                    if(temp.charAt(i) >= 'a' && temp.charAt(i) <= 'z')
                        System.out.print((char)(temp.charAt(i) - ('a' - 'A')));
                    else System.out.print(temp.charAt(i));
                }
                System.out.println();
            }
        }
    }
}

PREV54 合根植物

题目描述

资源限制
时间限制:2.0s 内存限制:256.0MB
问题描述
  w星球的一个种植园,被分成 m * n 个小格子(东西方向m行,南北方向n列)。每个格子里种了一株合根植物。
  这种植物有个特点,它的根可能会沿着南北或东西方向伸展,从而与另一个格子的植物合成为一体。

如果我们告诉你哪些小格子间出现了连根现象,你能说出这个园中一共有多少株合根植物吗?
输入格式
  第一行,两个整数m,n,用空格分开,表示格子的行数、列数(1<m,n<1000)。
  接下来一行,一个整数k,表示下面还有k行数据(0<k<100000)
  接下来k行,第行两个整数a,b,表示编号为a的小格子和编号为b的小格子合根了。

格子的编号一行一行,从上到下,从左到右编号。
  比如:5 * 4 的小格子,编号:
  1 2 3 4
  5 6 7 8
  9 10 11 12
  13 14 15 16
  17 18 19 20
样例输入
5 4
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17
样例输出
5


image.png

算法分析

并查集
将所有能连通的点合并到一个集合,求集合的个数,从1枚举到n * m,将所有点对应的集合根结点放进set中进行判重,输出set的大小即可

时间复杂度 O(n^2)

并查集操作接近O(1)

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

public class Main {
    static int N = 1000010;
    static int n,m;
    static int[] p = new int[N];
    static Set<Integer> set = new HashSet<Integer>();
    static int find(int x)
    {
        if(p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        int k = Integer.parseInt(br.readLine());
        for(int i = 1;i <= n * m;i ++) p[i] = i;
        while(k -- > 0)
        {
            String[] s2 = br.readLine().split(" ");
            int a = Integer.parseInt(s2[0]);
            int b = Integer.parseInt(s2[1]);
            a = find(a);
            b = find(b);
            p[a] = b;
        }
        for(int i = 1;i <= n * m;i ++) set.add(find(i));
        System.out.println(set.size());
            
    }
}

PREV53 分考场

题目描述

资源限制
时间限制:1.0s 内存限制:256.0MB
问题描述
  n个人参加某项特殊考试。
  为了公平,要求任何两个认识的人不能分在同一个考场。
  求是少需要分几个考场才能满足条件。
输入格式
  第一行,一个整数n(1<n<100),表示参加考试的人数。
  第二行,一个整数m,表示接下来有m行数据
  以下m行每行的格式为:两个整数a,b,用空格分开 (1<=a,b<=n) 表示第a个人与第b个人认识。
输出格式
  一行一个整数,表示最少分几个考场。
样例输入
5
8
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5
样例输出
4
样例输入
5
10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
样例输出
5

算法分析

经验:在蓝桥杯中,如果数据范围是100,用爆搜 + 各种剪枝还是可以通过的
此题没有什么思路,可以只用dfs做
dfs(int x,int nums)表示当前枚举到底x个人,nums表示目前开了多少个考场
g[i][j]数组记录的是第i个人是否和第j个人认识
dfs的过程,依次枚举所有的人往现有的nums考场上放,枚举所有情况
x个人往第1个考场放
x个人往第2个考场放
...
x个人往第nums个考场放
新开一个考场,第x个人往第nums + 1个考场放
优化:
最优性剪枝:若当前考场数量比ans大,则退出
可行性剪枝,若当前考场有当前这个人x认识的,则continue

时间复杂度

具有剪枝,不好分析

Java 代码

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    static int N = 110;
    static int n,m;
    static boolean[][] g = new boolean[N][N];
    static LinkedList[] list = new LinkedList[N];
    static int ans = Integer.MAX_VALUE;
    static boolean check(int x,int u)
    {
        for(int i = 0;i < list[u].size();i ++)
        {
            int t = (int)list[u].get(i);
            if(g[x][t]) return false;
        }
        return true;
    }
    static void dfs(int x,int nums)
    {
        if(nums >= ans) return; //最优性剪枝
        if(x == n + 1)
        {
            ans = Math.min(ans, nums);
            return;
        }
        //能否放在本来有的考场
        for(int i = 1;i <= nums;i ++)
        {
            if(!check(x,i)) continue;
            list[i].add(x);
            dfs(x + 1,nums);
            list[i].remove(list[i].size() - 1);
        }
        //新开一个
        list[nums + 1].add(x);
        dfs(x + 1,nums + 1);
        list[nums + 1].remove(list[nums + 1].size() - 1);
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        while(m -- > 0)
        {
            int a = scan.nextInt();
            int b = scan.nextInt();
            g[a][b] = g[b][a] = true;
        }
        for(int i = 1;i <= n;i ++) list[i] = new LinkedList<Integer>();
        dfs(1,0);
        System.out.println(ans);
    }
}

资源限制
时间限制:1.0s 内存限制:256.0MB
问题描述
  我们知道,整数做除法时,有时得到有限小数,有时得到无限循环小数。
  如果我们把有限小数的末尾加上无限多个0,它们就有了统一的形式。

本题的任务是:在上面的约定下,求整数除法小数点后的第n位开始的3位数。
输入格式
  一行三个整数:a b n,用空格分开。a是被除数,b是除数,n是所求的小数后位置(0<a,b,n<1000000000)
输出格式
  一行3位数字,表示:a除以b,小数后第n位开始的3位数字。
样例输入
1 8 1
样例输出
125
样例输入
1 8 3
样例输出
500
样例输入
282866 999000 6
样例输出
914

Java代码

PREV52 小数第n位

资源限制
时间限制:1.0s 内存限制:256.0MB
问题描述
  我们知道,整数做除法时,有时得到有限小数,有时得到无限循环小数。
  如果我们把有限小数的末尾加上无限多个0,它们就有了统一的形式。

本题的任务是:在上面的约定下,求整数除法小数点后的第n位开始的3位数。
输入格式
  一行三个整数:a b n,用空格分开。a是被除数,b是除数,n是所求的小数后位置(0<a,b,n<1000000000)
输出格式
  一行3位数字,表示:a除以b,小数后第n位开始的3位数字。
样例输入
1 8 1
样例输出
125
样例输入
1 8 3
样例输出
500
样例输入
282866 999000 6
样例输出
914

算法分析

这里主要的公式可以列出来


image.png

10^{n + 2}用快速幂求,时间复杂度O(logn)

时间复杂度 O(logn)

Java 代码

import java.util.Scanner;

public class Main {
    static long qmi(int a,int k,int p)
    {
        long res = 1 % p;
        long t = a;
        while(k > 0)
        {
            if((k & 1) == 1) res = res * t % p;
            k >>= 1;
            t = t * t % p;
        }
        return res ;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();
        int n = scan.nextInt();
        int p = b * 1000;
        System.out.println(((a * qmi(10,n + 2,p)) % p) / b);
    }
}

PREV51 观光铁路

资源限制
时间限制:2.0s 内存限制:256.0MB
问题描述
  跳蚤国正在大力发展旅游业,每个城市都被打造成了旅游景点。
  许多跳蚤想去其他城市旅游,但是由于跳得比较慢,它们的愿望难以实现。这时,小C听说有一种叫做火车的交通工具,在铁路上跑得很快,便抓住了商机,创立了一家铁路公司,向跳蚤国王请示在每两个城市之间都修建铁路。
  然而,由于小C不会扳道岔,火车到一个城市以后只能保证不原路返回,而会随机等概率地驶向与这个城市有铁路连接的另外一个城市。
  跳蚤国王向广大居民征求意见,结果跳蚤们不太满意,因为这样修建铁路以后有可能只游览了3个城市(含出发的城市)以后就回来了,它们希望能多游览几个城市。于是跳蚤国王要求小C提供一个方案,使得每只跳蚤坐上火车后能多游览几个城市才回来。

小C提供了一种方案给跳蚤国王。跳蚤国王想知道这个方案中每个城市的居民旅游的期望时间(设火车经过每段铁路的时间都为1),请你来帮跳蚤国王。
输入格式
  输入的第一行包含两个正整数n、m,其中n表示城市的数量,m表示方案中的铁路条数。
  接下来m行,每行包含两个正整数u、v,表示方案中城市u和城市v之间有一条铁路。
  保证方案中无重边无自环,每两个城市之间都能经过铁路直接或间接到达,且火车由任意一条铁路到任意一个城市以后一定有路可走。
输出格式
  输出n行,第i行包含一个实数tBi,表示方案B中城市i的居民旅游的期望时间。你应当输出足够多的小数位数,以保证输出的值和真实值之间的绝对或相对误差不超过1e-9。
样例输入
4 5
1 2
2 3
3 4
4 1
1 3
样例输出
3.333333333333
5.000000000000
3.333333333333
5.000000000000
样例输入
10 15
1 2
1 9
1 5
2 3
2 7
3 4
3 10
4 5
4 8
5 6
6 7
6 10
7 8
8 9
9 10
样例输出
10.000000000000
10.000000000000
10.000000000000
10.000000000000
10.000000000000
10.000000000000
10.000000000000
10.000000000000
10.000000000000
10.000000000000
数据规模和约定
  对于10%的测试点,n <= 10;
  对于20%的测试点,n <= 12;
  对于50%的测试点,n <= 16;
  对于70%的测试点,n <= 19;
  对于100%的测试点,4 <= k <= n <= 21,1 <= u, v <= n。数据有梯度。

算法分析

不会

时间复杂度

Java 代码

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 213,014评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,796评论 3 386
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 158,484评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,830评论 1 285
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,946评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,114评论 1 292
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,182评论 3 412
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,927评论 0 268
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,369评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,678评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,832评论 1 341
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,533评论 4 335
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,166评论 3 317
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,885评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,128评论 1 267
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,659评论 2 362
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,738评论 2 351

推荐阅读更多精彩内容

  • 在C语言中,五种基本数据类型存储空间长度的排列顺序是: A)char B)char=int<=float C)ch...
    夏天再来阅读 3,339评论 0 2
  • 1、问题描述 1200000有多少个约数(只计算正约数)。答案提交这是一道结果填空的题,你只需要算出结果后提交即可...
    得力小泡泡阅读 1,232评论 0 1
  • 1.问题描述两个二进制数11110011101和1111101001的和是多少?请用二进制表示,注意在提交的时候不...
    简言之_阅读 12,199评论 0 1
  • 村里新修的路 闪闪发光 无论 白天或夜里 十年前我栽种的树 现是一片郁郁葱葱 在野草清芬中醒来 嘴里有梦中的果香 ...
    老晁阅读 183评论 0 1
  • 欲增强体能的跑者,必须採取超负荷训练,若训练强度不够,疲劳的身躯一转眼就恢复体力,恐怕很难达到强健体魄的效果。 当...
    健身客阅读 1,161评论 0 0