2017 蓝桥杯模拟赛

た入场券 2022-05-29 13:57 299阅读 0赞

*   *   *  1. 算年龄
         *  2. 猜算式
         *  3. 排列序数
         *  4. 字符串比较
         *  5. 报数游戏
         *  6. 滑动解锁
         *  7. 奇怪的捐赠

### 1. 算年龄 ###

英国数学家德摩根出生于19世纪初叶（即18xx年）。 他年少时便很有才华。一次有人问他的年龄，他回答说： “**到了x的平方那年，我刚好是x岁**”。

请你计算一下，德摩根到底出生在哪一年。 题中的年龄指的是周岁。

请填写表示他出生年份的四位数字，不要填写任何多余内容。

> 1806

public class Main {   
        public static void main(String[] args) {  
            for(int x=0;;x++){  
                int y = x*x -x;  
                if(y>1800){  
                       System.out.println(y);  
                       break;  
                }  
            }  
        }  
    }

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

### 2. 猜算式 ###

![猜算式][20170328215834732]

> 40096

**程序代码：**

public class Main {   
        public static void main(String[] args) {  
            for(int i=100;i<1000;i++)  
                for(int j= 100;j<1000;j++){  
                    int[] a = new int[10];  
                    int tempA = i * (j/100);  
                    int tempB = i * (j/10%10);  
                    int tempC = i * (j%10);  
                    if(tempA > 999 || tempA < 100 || tempB > 999 || tempB < 100 || tempC > 999 || tempC < 100)  
                        continue;  
                    if(f(i,a) && f(j,a) && f(tempA,a) && f(tempB,a) && f(tempC,a) && f(i*j, a))  
                        System.out.println(i*j);          
                }  
        }  
    
        private static boolean f(int i, int[] a) {  
             while(i>0){  
                 a[i%10]++;  
                 if(a[i%10]>2)  
                     return false;  
                 i /= 10;  
             }  
             return true;  
        }  
    }

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

### 3. 排列序数 ###

X星系的某次考古活动发现了史前智能痕迹。  
这是一些用来计数的符号，经过分析它的计数规律如下：  
（为了表示方便，我们把这些奇怪的符号用a~q代替）

abcdefghijklmnopq 表示0  
abcdefghijklmnoqp 表示1  
abcdefghijklmnpoq 表示2  
abcdefghijklmnpqo 表示3  
abcdefghijklmnqop 表示4  
abcdefghijklmnqpo 表示5  
abcdefghijklmonpq 表示6  
abcdefghijklmonqp 表示7  
…..

在一处石头上刻的符号是：  
bckfqlajhemgiodnp

请你计算出它表示的数字是多少？

请提交该整数，不要填写任何多余的内容，比如说明或注释。

> 22952601027516

//考察康托展开式
    public class Main{ 
        public static void main(String[] args) {
            String str = "bckfqlajhemgiodnp" ;
            long fs[] = new long[17] ;
            fs[0] = 1;
            for(int i = 1 ; i < 17 ; i++){
       //1~16的阶乘
                fs[i] = fs[i-1] * i ;
            }
            long sum = 0;
            for(int i = 0 ; i < 16 ; i++){
                char tempCh = str.charAt(i);
                int k = 0 ;
                for(int j = i + 1 ; j < 17 ; j ++){
                    if(tempCh-'a' > str.charAt(j)-'a'){
                        k ++ ;
                    }
                }
                sum += k * fs[16 - i] ;
            }
            System.out.println(sum);
        }
    }

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

### 4. 字符串比较 ###

我们需要一个新的字符串比较函数compare(s1, s2).  
对这个函数要求是：  
1. 它返回一个整数，表示比较的结果。  
2. 结果为正值，则前一个串大，为负值，后一个串大，否则，相同。  
3. 结果的绝对值表示：在第几个字母处发现了两个串不等。

下面是代码实现。对题面的数据，结果为：

> \-3  
> 2  
> 5

仔细阅读源程序，填写划线位置缺少的代码。

static int compare(String s1, String s2)
    {
        if(s1==null && s2==null) return 0;
        if(s1==null) return -1;
        if(s2==null) return 1;
    
        if(s1.isEmpty() && s2.isEmpty()) return 0;
        if(s1.isEmpty()) return -1;
        if(s2.isEmpty()) return 1;
    
        char x = s1.charAt(0);
        char y = s2.charAt(0);
    
        if(x<y) return -1;
        if(x>y) return 1;
    
        int t = compare(s1.substring(1),s2.substring(1));
        if(t==0) return 0;
    
        return ____________________ ; //填空位置
    }
    
    public static void main(String[] args)
    {
        System.out.println(compare("abc", "abk"));
        System.out.println(compare("abc", "a"));
        System.out.println(compare("abcde", "abcda"));          
    }

> t < 0 ? t - 1 : t + 1

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

### 5. 报数游戏 ###

有n（1< n < 10000）个小朋友站成一个圆圈。  
选定一个小朋友为1号，从他开始顺时针编号：1,2,3,4，……

游戏开始！从1号小朋友开始，顺时针报数，从1报起。即：1号小朋友报1，2号小朋友报2，3号小朋友报3，……

游戏规定，报到数字m（1 < m < 100）的小朋友立即退出报数圈。在他的顺时针方向的下一个小朋友开始重新从1报数……游戏一直进行下去，直到圈中只剩下一个小朋友。

求最后剩下的小朋友的编号。

**输入：**  
两个整数，n和m，用空格分开。

**输出：**  
一个整数，表示最后剩下的小朋友的编号。

**资源约定：**  
峰值内存消耗（含虚拟机） < 256M  
CPU消耗 < 1000ms

**示例输入：**

> 15 3

**示例输出：**

> 5

**程序代码**

import java.util.Scanner;
    import java.util.Vector;
    
    public class Main { 
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            Vector<Integer> vector = new Vector<>();
            int N = sc.nextInt();
            int M = sc.nextInt();
    
            for (int i = 1; i <= N; i++)
                vector.add(i);
    
            int k = 0;
            while (vector.size() > 1) {
                for (int i = 1; i < M; i++) {
                    k++;
                    if (k == vector.size())
                        k = 0;
                }
                vector.remove(k);
                if (k == vector.size())
                    k = 0;
            }
    
            System.out.println(vector.get(0));
        }
    }

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

### 6. 滑动解锁 ###

**题目：**  
滑动解锁是智能手机一项常用的功能。你需要在3x3的点阵上，从任意一个点开始，反复移动到一个尚未经过的”相邻”的点。这些划过的点所组成的有向折线，如果与预设的折线在图案、方向上都一致，那么手机将解锁。

所谓两个点“相邻”：当且仅当以这两个点为端点的线段上不存在尚未经过的点。

此外，许多手机都约定：这条折线还需要至少经过4个点。

为了描述方便，我们给这9个点从上到下、从左到右依次编号1-9。即如下排列：

1 2 3  
4 5 6  
7 8 9

那么1->2->3是非法的，因为长度不足。  
1->3->2->4也是非法的，因为1->3穿过了尚未经过的点2。  
2->4->1->3->6是合法的，因为1->3时点2已经被划过了。

某大神已经算出：一共有389112种不同的解锁方案。没有任何线索时，要想暴力解锁确实很难。  
不过小Hi很好奇，他希望知道，当已经瞥视到一部分折线的情况下，有多少种不同的方案。  
遗憾的是，小Hi看到的部分折线既不一定是连续的，也不知道方向。

例如看到1-2-3和4-5-6，  
那么1->2->3->4->5->6，1->2->3->6->5->4, 3->2->1->6->5->4->8->9等都是可能的方案。

你的任务是编写程序，根据已经瞥到的零碎线段，求可能解锁方案的数目。

**输入：**

> 每个测试数据第一行是一个整数N(0 <= N <= 8)，代表小Hi看到的折线段数目。  
> 以下N行每行包含两个整数 X 和 Y (1 <= X, Y <= 9)，代表小Hi看到点X和点Y是直接相连的。

**输出：**

> 对于每组数据输出合法的解锁方案数目。

**示例输入：**

> 8  
> 1 2  
> 2 3  
> 3 4  
> 4 5  
> 5 6  
> 6 7  
> 7 8  
> 8 9

**示例输出：**

> 2

**示例输入：**

> 4  
> 2 4  
> 2 5  
> 8 5  
> 8 6

**示例输出：**

> 258

**资源约定：**

> 峰值内存消耗（含虚拟机） < 256M  
> CPU消耗 < 1000ms

**程序代码：**

public class Main { 
        private static boolean f[] = new boolean[10];
        private static int N;
        private static int[][] path;
        static int count = 0;
        public static boolean isOK(int a,int b){
            int[][] dig = {
       {
       1,3,2},{
       1,7,4},{
       1,9,5},{
       2,8,5},{
       3,7,5},{
       3,9,6},{
       4,6,5},{
       7,9,8}};
            for(int i = 0;i<8;i++){
                if(dig[i][0]==a&&dig[i][1]==b||dig[i][1]==a&&dig[i][0]==b){
                    if(!f[dig[i][2]])return false;
                }
            }
            return true;
        }
        public static void dfs(int number,int step,int[] process){
            if(step>=2){
       //当process数组里面至少有2个数时开始判断，代表我要选取最近划中的2个数字是否合法
                int a = process[step-2];
                int b = process[step-1];
                if(!isOK(a,b))return;
            }
            if(step==number){
       //判断是否存在此数组，存在则继续，不存在直接返回代表不符合
                for(int i = 0;i<N;i++){
                    int a = path[i][0];
                    int b = path[i][1];
                    for(int j = 0;j<step-1;j++){
                        if(a==process[j]&&b==process[j+1]||a==process[j+1]&&b==process[j])break;
                        if(j==step-2)return;
                    }
                }
                count++;
                return;
            }else if(step>number)return;
            for(int i = 1;i<=9;i++){
                if(!f[i]){
                    f[i] = true;
                    process[step] = i;
                    dfs(number,step+1,process);
                    f[i] = false;
                }
            }
        }
        public static void main(String[] args) {
            Scanner sn = new Scanner(System.in);
            N = sn.nextInt();
            path = new int[N+1][2];
            int[] process = new int[10];
            for(int i = 0;i<N;i++){
                path[i][0] = sn.nextInt();
                path[i][1] = sn.nextInt();
            }
            for(int i = N>4?N:4;i<=9;i++){
       //枚举划中的数字个数
                dfs(i,0,process);
            }
            System.out.println(count);
            sn.close();
        }
    }

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

### 7. 奇怪的捐赠 ###

**题目：**

地产大亨Q先生临终遗愿是：拿出100万元给X社区的居民抽奖，麻烦的是，他有个奇怪的要求：

1.100万元必须被正好分成若干份（不能有剩余）。每份必须是7的若干次方元。

比如：1元，7元，49元，343元，……

2.相同金额的份数不能超过5份。

3.在满足上述要求的情况下，分成的份数越多越好！

请你帮忙算一算，最多可以分为多少份？

**输出：**

只需输出分成的份数。

public class Main { 
        public static void main(String[] args) {
            String tmp = Integer.toString(1000000, 7);
            int sum = 0;
            for(int i=0;i<tmp.length();i++) {
                sum += tmp.charAt(i) - '0';
            }
            System.out.println(sum);
        }
    }

**解题技巧：**

必须为7的倍数其实就是7进制的问题，将100万转换为7进制，每一位的和就是分的份数和。

题目中的不能超过5份是迷惑条件，因为某个数的7进制表示是唯一的，不受条件的限制。

[20170328215834732]: /images/20220529/db56ae72591f4e5a955996632c39a17c.png