LV3

0.k倍区间

题目描述

给定一个长度为 N 的数列， $A_1$ , $A_2$ ,⋯ $A_N$ 如果其中一段连续的子序列 $A_i$ , $A_i+1$ ,⋯ $A_j$ ( i≤j ) 之和是 K 的倍数，我们就称这个区间 [i,j] 是 K 倍区间。

你能求出数列中总共有多少个 K倍区间吗？

输入描述

第一行包含两个整数 N 和 K( 1≤N,K≤ $10^5$ )。

以下 N 行每行包含一个整数 $A_i$ ( 1≤ $A_i$ ≤ $10^5$ )

输出描述

输出一个整数，代表 K 倍区间的数目。

输入输出样例

示例

输入

输出

运行限制

最大运行时间：2s
最大运行内存: 256M

题解

第一眼的做法是直接遍历获取所有子串的和，取模为0计数器++。但是扫了一眼别人的题解，得到这道题目无法使用暴力求解，会超时

首先前缀和=前n项的和，就有s[i]和s[j]，s[j]-s[i]就表示一个区间

原来的做法就是遍历所有的(s[j]-s[i])%k，看有多少能整除的，但是超时

要求的是**(s[j]-s[i])%k=0** ，转化一下就是s[j]%k-s[i]%k=0 ，也就是s[j]%k=s[i]%k

那就变成了先求出所有的s，再对其取模，得到n个余数，如果有余数相等的，那就说明这两个相等的余数对应的前缀和相减是符合要求的区间和

如果出现多个余数相同的前缀和，就要考虑有多少种区间可能，c(c-1)/2种

最后相加即可

代码

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int n = scan.nextInt();
        int k = scan.nextInt();

        long[] cnt = new long[k]; 
        cnt[0] = 1;               

        long ans = 0;
        long mod = 0;             

        for (int i = 0; i < n; i++) {
            long a = scan.nextLong();
            mod = (mod + a) % k;      
            int r = (int) mod;

            ans += cnt[r];            
            cnt[r]++;                 
        }

        System.out.println(ans);
        scan.close();
    }
}

代码解释

这里long[] cnt = new long[k]; 创建一个数组，这个数组里下标表示余数，对应存储的元素表示这个余数出现的次数，并且把余数为0的先加一个

ans是k倍区间个数，mod表示前缀和的余数=s[i]%k

在循环部分先循环获取下一个数字，因为**(a+b)%k=((a%k)+(b%k))%k+=((a%k)+b)%k** ，所以数字先和前面的前缀和的余数相加再求余数就等于包含此数的前缀和的余数

接下来的ans += cnt[r]; 每得到第n个余数相同的前缀和，就会多n个区间

1.弹珠堆放

问题描述

小蓝有 20230610 颗磁力弹珠，他对金字塔形状尤其感兴趣

高度为 1 的金字塔需要 1 颗弹珠；

高度为 2 的金字塔需要 4 颗弹珠；

高度为 3 的金字塔需要 10 颗弹珠；

高度为 4 的金字塔需要 20 颗弹珠。

小蓝想要知道用他手里的弹珠可以摆出的最高的金字塔的高度是多少？

答案提交

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

题解

第一层是1，第二层是1+(1+2)，第三层是1+(1+2)+(1+2+3)，第四层是1+(1+2)+(1+2+3)+(1+2+3+4)，将20230610从1开始减去，直到减到小于等于0。用两层循环来做

代码

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        
        int i=0,j=0,s=20230610;
        for(i=1; ;i++)
        {
          for(j=1;j<=i;j++) //这里注意要等于
          {
            s=s-j;
            if(s<0)
            {
              System.out.println(i-1);
              return;
            }
            if(s==0)
            {
              System.out.println(i);
              return;
            }
          }
        }
    }
}

2.电动车

问题描述

作为一位繁忙的程序员，小蓝经常需要在 N 座城市之间来回穿梭。他准备购买一辆电动车出行，但是担心电动车电量不足。

为了描述方便，我们把 N 座城市编号 1 至 N。城市之间一共有 M 条双向高速公路相连。其中第 i 条连接 $u_i$ 号城市和 $v_i$ 号城市，耗费 $w_i$ 个单位的电量。

假设小蓝可以在出发城市，以及任何中途经过的城市充满电。小蓝想知道，如果希望从任意城市开电动车到任意另一个城市，都可以找到一条由若干高速公路组成路径，使得不需要在任何高速公路内补充电量，那么这台电动车至少需要多少电量？

输入描述

第一行包含两个整数 N 和 M。

以下 M 行，每行包含 3 个整数 $u_i$ 、 $v_i$ 和 $w_i$ 。

输出描述

一个整数，代表答案。

如果存在两个城市不能通过高速公路相互到达，输出 −1。

样例输入

样例输出

样例说明

从 1 到 2 可以走：1→2，需要电量 3。

从 1 到 3 可以走：1→2→4→3，其中 1→2 需要电量 3，2→4 需要电量 2，4→3 需要电量 2，全程至少需要电量 3。

从 1 到 4 可以走：1→2→4，其中 1→2 需要电量 3，2→4 需要电量 2，全程至少需要电量 3。

从 2 到 3 可以走：2→4→3，其中 2→4 需要电量 2，4→3 需要电量 2，全程至少需要电量 2。

从 2 到 4 可以走：2→4，需要电量 2。

从 3 到 4 可以走：3→4，需要电量 2。

综上所述，电动车至少需要 3 个单位的电量。

题解

用图的最小生成树来解决问题，有kruskai和prim两种算法，这里选择用kruskai来做

kruskai就是将边的权值排序，然后从最小的开始选，不能形成环形，有n个顶点就要有n-1个边，小于n-1就是没有连通

首先要用一个列表来存储输入的两个城市编号和耗电量，再将其按照耗电量进行排序

再创建一个并查集，用于存储城市的父节点，开始的时候都是自己，每个城市独立

并查集的实现，需要一个查找，查找两个城市是否在同一个集合内，即递归查找根节点是否相同，如果不相同则需要一个合并的操作，将根节点指向另一个城市即可

然后遍历列表并查找，如果不在一个集合就合并，并且更新耗电最大值，计数器++

最后判断是否连通，即计数器是否小于n-1，小于则不连通，连通则输出耗电最大值

代码

import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {

    static int[] father; //这里得声明不然后面的两个函数无法使用
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int n = scan.nextInt();
        int m = scan.nextInt();

        int i=0;

        ArrayList<int[]> list = new ArrayList<>();
        for(i=0;i<m;i++)
        {
          int a = scan.nextInt();
          int b = scan.nextInt();
          int c = scan.nextInt();
          list.add(new int[]{a,b,c});
        }

        Collections.sort(list,(a1,a2)->(a1[2])-(a2[2])); //用于排序

        father = new int[n+1]; //这里+1方便后面城市编号与下标对应
        for(i=1;i<=n;i++)
        {
          father[i]=i;
        }

        int max=0;
        int count=0;
        for(int[] array:list) //用增强型for遍历
        {
          int a = array[0];
          int b = array[1];
          int c = array[2];

          if(find(a)!=find(b))
          {
            union(a,b);
            max=Math.max(max,c);
            count++;
          }
        }

        if(count<n-1)
        {
          System.out.println(-1);
        }
        else
        {
          System.out.println(max);
        }

        scan.close();
    }

    public static int find(int a)
    {
      if(father[a]!=a)
      {
        father[a]=find(father[a]);
      }
        return father[a];
      }

    public static void union(int a,int b)
    {
      a=find(a);
      b=find(b);
      father[a]=b;
    }    

}

3.松散子序列

问题描述

给定一个仅含小写字母的字符串 s，假设 s 的一个子序列 t 的第 i 个字符对应了原字符串中的第 $p_i$ 个字符。我们定义 s 的一个松散子序列为：对于 i>1 总是有 $p_i$ − $p_{i−1}$ ≥2。设一个子序列的价值为其包含的每个字符的价值之和 (a∼z 分别为 1∼26)。

求 s 的松散子序列中的最大价值。

输入格式

输入一行包含一个字符串 s。

输出格式

输出一行包含一个整数表示答案。

样例输入

azaazaz

样例输出

题解

看了半天没看懂题目描述。从力扣上的打家劫舍看明白了，就是子序列中不能有两个连续的字符，满足这个条件，并且价值最高

这道题要用动态规划，首先考虑第一个字符，其价值就是本身，再考虑第二个字符，由于不能连续，只能和第一个对比，选一个值高的，从第三个开始，可以选择这个字符加上之前的字符，也可以选择不加上这个字符，那就是选择了上一个

假设字符串 s = "abcde"。

第一步：初始化

首先，我们需要初始化 dp 数组，并计算每个字符的价值。

dp[0] = 1（'a’的价值）
dp[1] = max(dp[0], 2) = max(1, 2) = 2（'b’的价值）

第二步：动态规划递推

接下来，我们从 i = 2 开始，使用状态转移公式来更新 dp[i]。

对于 i = 2（字符 ‘c’）：
- 可以选择不选 ‘c’，那么 dp[2] = dp[1] = 2。
- 或者选择 ‘c’，则需要加上 dp[0]，即 dp[2] = dp[0] + 3 = 1 + 3 = 4（‘c’ 的价值是 3）。
- 因此，dp[2] = max(2, 4) = 4。
对于 i = 3（字符 ‘d’）：
- 可以选择不选 ‘d’，那么 dp[3] = dp[2] = 4。
- 或者选择 ‘d’，则需要加上 dp[1]，即 dp[3] = dp[1] + 4 = 2 + 4 = 6（‘d’ 的价值是 4）。
- 因此，dp[3] = max(4, 6) = 6。
对于 i = 4（字符 ‘e’）：
- 可以选择不选 ‘e’，那么 dp[4] = dp[3] = 6。
- 或者选择 ‘e’，则需要加上 dp[2]，即 dp[4] = dp[2] + 5 = 4 + 5 = 9（‘e’ 的价值是 5）。
- 因此，dp[4] = max(6, 9) = 9。

代码

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String s = scan.nextLine();
      
        int[] dp = new int[s.length()];
        
        dp[0] = s.charAt(0) - 'a' + 1;  

        if (s.length() > 1) 
        {
            dp[1] = Math.max(dp[0], s.charAt(1) - 'a' + 1); 
        }
        
        for (int i = 2; i < s.length(); i++) 
        {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + s.charAt(i) - 'a' + 1);  
        }
        
        System.out.println(dp[s.length() - 1]);
    }
}

4.冶炼金属

问题描述

小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个炉子有一个称作转换率的属性 V，V 是一个正整数，这意味着消耗 V 个普通金属 O 恰好可以冶炼出一个特殊金属 X，当普通金属 O 的数目不足 V 时，无法继续冶炼。

现在给出了 N 条冶炼记录，每条记录中包含两个整数 A 和 B，这表示本次投入了 A 个普通金属 O，最终冶炼出了 B 个特殊金属 X。每条记录都是独立的，这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。

根据这 N 条冶炼记录，请你推测出转换率 V 的最小值和最大值分别可能是多少，题目保证评测数据不存在无解的情况。

输入格式

第一行一个整数 N，表示冶炼记录的数目。

接下来输入 N 行，每行两个整数 A、B，含义如题目所述。

输出格式

输出两个整数，分别表示 V 可能的最小值和最大值，中间用空格分开。

样例输入

样例输出

20 25

样例说明

当 V=20 时，有：⌊ $\frac{75}{20}$ ⌋=3，⌊ $\frac{53}{20}$ ⌋=2，⌊ $\frac{59}{20}$ ⌋=2，可以看到符合所有冶炼记录。

当 V=25 时，有：⌊ $\frac{75}{25}$ ⌋=3，⌊ $\frac{53}{25}$ ⌋=2，⌊ $\frac{59}{25}$ ⌋=2，可以看到符合所有冶炼记录。

且再也找不到比 20 更小或者比 25 更大的符合条件的 V 值了。

题解

用贪心算法，A/B是一定大于等于V的，也就是最大值。计算最小值，则考虑如果多做一个要多少个V，也就是A/(B+1)，但是实际做出来的是B，所以实际的V一定比A/(B+1)大，再+1则就是可能的值里最小的

再进行比较，在最大值里选择最小值，最小值里选最大值

代码

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int n = scan.nextInt();

        int i=0;
        int max = Integer.MAX_VALUE;
        int min = 0;

        for(i=1;i<=n;i++)
        {
          int a = scan.nextInt();
          int b = scan.nextInt();
          
          max = Math.min(max,a/b);
          min = Math.max(min,a/(b+1)+1);

        }

        System.out.println(min+" "+max);

        scan.close();
    }
}

5.染色时间

问题描述

小蓝有一个 n 行 m 列的白色棋盘, 棋盘的每一个方格都可以被染成彩色。

每个方格有一个染色时间 tij, 不同方格的染色时间可能不同。如果一个方格被触发了染色, 这个方格就会在 tij 秒之后变成彩色, 然后将自己上下左右四个方向相邻的方格触发染色。每个方格只能被触发染色一次, 第一次触发之后的触发为无效触发。

给定每个方格的染色时间, 在时刻 0 触发第一行第一列的方格染色, 请问多长时间后整个棋盘完成染色。

输入格式

输入的第一行包含两个整数 n,m, 分别表示棋盘的行数和列数。

接下来 n 行, 每行 m 个正整数, 相邻的整数之间用一个空格分隔, 表示每个方格的染色时间。该部分的第 i 行第 j 个整数表示 tij, 即第 i 行第 j 列的方格的染色时间。

输出格式

输出一行包含一个整数, 表示整个棋盘完成染色的时间。

样例输入

样例输出

题解

这道题涉及的是BFS广度优先搜索，正常的广度优先是用队列，先第一个节点入队列，然后找到其子节点后，第一个节点出队列，但是正常的队列只能是先进先出，但是这里还要考虑染色时间的问题，所以要结合上优先队列，按时间来排序

需要一个类用来表示每一个格子，并实现Comparable这个接口，这个类需要有时间和坐标，同时重载compareTo这个方法用来排序

用一个二维数组来表示棋盘上每一个点的染色时间，再定义一个函数对这个棋盘进行操作

这个函数首先要把第一个点入队列，用PriorityBlockingQueue创建一个按时间排序的队列，当这个队列非空的时候就把时间最小的先出队列，把这个时间和记录的时间相比较，记录下大的时间，然后再用一个二维数组表示四个方向，循环遍历四个方向向外扩展，判断四个方向是否都还在棋盘上，并且是否被染色，如果没有就将当前染色时间加上当前格子所需时间入队列，并且先将其标记为已染色。最后输出记录的最大时间

代码

import java.util.*;
import java.util.concurrent.PriorityBlockingQueue;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    static int[][] w = new int[][] { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } }; 
    static int[][] a;
    static int count = 0;
    static int n, m;

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        
        n = scan.nextInt();
        m = scan.nextInt();
        a = new int[n][m];
        for(int i=0;i<n;i++)
        {
          for(int j=0;j<m;j++)
          {
            a[i][j]=scan.nextInt();
          }
        }
        dfs();

    }

        public static void dfs()
        {
          PriorityBlockingQueue<color> query = new PriorityBlockingQueue<>();
          query.offer(new color(a[0][0],0,0));
          a[0][0]=0;

          while(!query.isEmpty())
          {
            color t = query.poll();
            if(t.time>count)
            {
              count=t.time;
            }

            for (int i = 0; i < 4; i++) 
            {
              int x = t.x + w[i][0];
              int y = t.y + w[i][1];

              if(x >= 0 && x < n && y >= 0 && y < m && a[x][y] > 0)
              {
                query.offer(new color(a[x][y] + t.time, x, y));
                a[x][y] = 0;
              }

            }
          }
          System.out.println(count);
        }
}
class color implements Comparable<color>
{
  public int time;
  public int x;
  public int y;
        
    public color(int time,int x,int y)
    {
      this.time=time;
      this.x=x;
      this.y=y;      
    }
    @Override
    public int compareTo(color o)
    {
      return this.time-o.time;
    }
}

6.城邦

问题描述

小蓝国是一个水上王国, 有 2021 个城邦, 依次编号 1 到 2021。在任意两个城邦之间, 都有一座桥直接连接。

为了庆祝小蓝国的传统节日, 小蓝国政府准备将一部分桥装饰起来。

对于编号为 a 和 b 的两个城邦, 它们之间的桥如果要装饰起来, 需要的费用如下计算: 找到 a 和 b 在十进制下所有不同的数位, 将数位上的数字求和。

例如, 编号为 2021 和 922 两个城邦之间, 千位、百位和个位都不同, 将这些数位上的数字加起来是 (2+0+1)+(0+9+2)=14 。注意 922 没有千位, 千位看成 0 。

为了节约开支, 小蓝国政府准备只装饰 2020 座桥, 并且要保证从任意一个城邦到任意另一个城邦之间可以完全只通过装饰的桥到达。

请问, 小蓝国政府至少要花多少费用才能完成装饰。

提示: 建议使用计算机编程解决问题。

答案提交

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。

题解

依旧是最小生成树，直接参考前面的电动车的问题，依旧把每个出发编号和抵达编号和费用存到一个列表里。

这里没有理解题目，以为是一个数内部有相同的数就只保留一个，ai告诉我应该是两个数的相同数位上有相同的数字才抵消掉，被卡了半天。

用三层循环，第一层控制出发编号，第二层控制抵达编号，第三层控制数字的位数，把不相同的累加上，二三两层结束后将数据都添加到列表中

下面就是和之前一样了

但是这道题不适合用Kruskal，这里的边太多，要这下存储这么多的边然后再排序，而用prim的话就是处理节点，不用一次存储所有的边

代码

import java.util.*;
public class Main {
    static int[] father;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int i=0;
        father = new int[2022];
        for(i=1;i<=2021;i++)
        {
          father[i]=i;
        }

        ArrayList<int[]> list = new ArrayList<>();
        int j=0,q=0,k=0,p=0;    
        int n1=0,n2=0;
        int t=0,g=0;
        int cost=0;
        for(i=1;i<=2021;i++)
        {
          for(p=i+1;p<=2021;p++)
          {
            t=i;
            g=p;
            cost=0;
            for(q=0;q<4;q++)
            {
              n1=t%10; //这里用临时变量
              t=t/10;
              n2=g%10;
              g=g/10;
              if(n1!=n2)
              {
                cost=cost+n1+n2;
              }
            }
            list.add(new int[]{i,p,cost});
          }
        } 

        Collections.sort(list,(a1,a2)->(a1[2])-(a2[2]));

        int sum=0;
        for(int[] array:list)
        {
          int a = array[0];
          int b = array[1];
          int c = array[2];

          if(find(a)!=find(b))
          {
            union(a,b);
            sum=sum+c;
          }
        }
        
        System.out.println(sum);  

        scan.close();
    }

    public static int find(int a)
    {
      if(father[a]!=a)
      {
        father[a]=find(father[a]);
      }
        return father[a];
      }

    public static void union(int a,int b)
    {
      a=find(a);
      b=find(b);
      father[a]=b;
    } 

}

7.X 图形

问题描述

给定一个字母矩阵。一个 X 图形由中心点和由中心点向四个 45 度斜线方向引出的直线段组成，四条线段的长度相同，而且四条线段上的字母和中心点的字母相同。

一个 X 图形可以使用三个整数 r,c,L 来描述，其中 r,c 表示中心点位于第 r 行第 c 列，正整数 L 表示引出的直线段的长度。对于 1 到 L 之间的每个整数 i，X 图形满足：第 r−i 行第 c−i 列与第 r 行第 c 列相同，第 r−i 行第 c+i 列与第 r 行第 c 列相同，第 r+i 行第 c−i 列与第 r 行第 c 列相同，第 r+i 行第 c+i 列与第 r 行第 c 列相同。

例如，对于下面的字母矩阵中，所有的字母 L 组成一个 X图形，中间的 5 个 L 也组成一个 X 图形。所有字母 Q 组成了一个 X 图形。

LAAALA

ALQLQA

AALQAA

ALQLQA

LAAALA

给定一个字母矩阵，请求其中有多少个 X 图形。

输入格式

输入第一行包含两个整数 n,m，分别表示字母矩阵的行数和列数。

接下来 n 行，每行 m 个大写字母，为给定的矩阵。

输出格式

输出一行，包含一个整数，表示答案。

样例输入

5 6
LAAALA
ALQLQA
AALQAA
ALQLQA
LAAALA

样例输出

题解

这道题的思路就是暴力，先把整个二维数组定义好，接收好数据。然后去循环中心点的位置，从第二个到倒数第二个之间循环就行，中间的一层循环用来控制线段长度，四条线段长度的最大值是整个矩阵的边长减去1再除2，取最小值，然后根据题目中给出的x图形的定义检查是否满足。

在不满足条件后就立刻退出当前循环，不要再继续下次更长线段的检查了，一开始没加退出循环，被卡在30%

代码

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int n = scan.nextInt();
        int m = scan.nextInt();
        char[][] a = new char[n][m];
        for(int i=0;i<n;i++)
        {
          String str = scan.next();
          for(int j=0;j<m;j++)
          {
            a[i][j] = str.charAt(j);
          }
        }
        int count=0;
        for(int r=1;r<n-1;r++)
        {
          for(int c=1;c<m-1;c++)
          {
            char x=a[r][c];
            for(int l=1;l<=Math.min((n-1)/2,(m-1)/2);l++)
            {
              if(r-l>=0&&r+l<n&&c-l>=0&&c+l<m&&
                 a[r-l][c-l]==x&&a[r-l][c+l]==x&&
                 a[r+l][c-l]==x&&a[r+l][c+l]==x)
              {
                count++;
              }
              else
              {
                break; //线段由小到大的去判断是否满足x形，如果小的x都不满足后面就不要再判断了
              }
            }
          }
        }
        System.out.println(count);
        scan.close();
    }
}

8.出差

问题描述

A 国有 N 个城市, 编号为 1…N 。小明是编号为 1 的城市中一家公司的员工, 今天突然接到了上级通知需要去编号为 N 的城市出差。

由于疫情原因, 很多直达的交通方式暂时关闭, 小明无法乘坐飞机直接从城市 1 到达城市 N, 需要通过其他城市进行陆路交通中转。小明通过交通信息网, 查询到了 M 条城市之间仍然还开通的路线信息以及每一条路线需要花费的时间。

同样由于疫情原因, 小明到达一个城市后需要隔离观察一段时间才能离开该城市前往其他城市。通过网络, 小明也查询到了各个城市的隔离信息。(由于小明之前在城市 1 , 因此可以直接离开城市 1 , 不需要隔离）

由于上级要求, 小明希望能够尽快赶到城市 N, 因此他求助于你, 希望你能帮他规划一条路线, 能够在最短时间内到达城市 N 。

输入格式

第 1 行: 两个正整数 N,M,N 表示 A 国的城市数量, M 表示末关闭的路线数量

第 2 行: N 个正整数, 第 i 个整数 Ci 表示到达编号为 i 的城市后需要隔离的时间

第 3…M+2 行: 每行 3 个正整数, u,v,c 表示有一条城市 u 到城市 v 的双向路线仍然开通着, 通过该路线的时间为 c

输出格式

第 1 行: 1 个正整数, 表示小明从城市 1 出发到达城市 N 的最短时间（到达城市 N, 不需要计算城市 N 的隔离时间）

样例输入

样例输出

题解

这道题是单源最短路问题，并且所有路径都是正数，应该用Dijkstra算法来解决。

首先要一个邻接表，这个二维数组表示，从一个城市到另一个城市所需要的时间，在初始化的时候将时间全部设置为一个较大的值，用于表示不可到达，但也不能太大，一开始用了int最大值，结果溢出了。然后遍历输入的数字，将对应的两个城市之间的时间更新，更新的时候加上停留时间。再把第一个城市到其他所有城市的最短时间都更新为第一个城市直接到对应城市的时间。

再用循环去找所有未被访问过的城市中距离当前城市最近的，再用一层循环找到是否存在从当前城市到另一个城市比直接从起点到这个城市时间更短的，有则更新到这个城市的时间

代码

import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int n = scan.nextInt();
        int m = scan.nextInt();

        int[] time = new int[n+1];
        for(int i=1;i<=n;i++)
        {
          time[i]=scan.nextInt();
        }

        int[] dist = new int[n+1]; //存储到第n个城市所需的最短时间
        boolean[] visited = new boolean[n+1];
        int[][] graph = new int[n+1][n+1]; //存储从一个城市到另一个城市所需时间
        for(int[] g:graph)
        {
          Arrays.fill(g,10000); //先将每一个都填充为无穷大，都是无法直接抵达
        }

        for (int i = 0; i < m; i++) 
        {
          int u = scan.nextInt();
          int v = scan.nextInt();
          int c = scan.nextInt();
          graph[u][v] = u == 1 ? c : time[u] + c; //对于可以直接抵达的城市，更新其时间
          graph[v][u] = v == 1 ? c : time[v] + c;
        }

        for (int i=2;i<=n;i++) 
        {
          dist[i] = graph[1][i];
        }

        visited[1] = true;
        for (int i=0;i<n-1;i++) 
        {
          int min = 100000;
          int u = 0;
          for (int j=1;j<=n;j++) 
          {
            if (!visited[j]&&dist[j]<min) 
            {
              min = dist[j];
              u = j;
            }
          }

          visited[u] = true;
          for (int j = 1; j <= n; j++) 
          {
            if (!visited[j] && graph[u][j] + dist[u] < dist[j]) 
            {
              dist[j] = graph[u][j] + dist[u];
            }
          }
        }

        System.out.println(dist[n]);

        scan.close();
    }
}

graph LR
A[图论]-->B[最短路]
A-->C[最小生成树]
A-->D[二分图]

B-->E[单源最短路]
B-->F[多源汇最短路]

C-->G[Prim算法]
C-->H[Kruskal算法]

D-->I[染色法]
D-->J[匈牙利算法]

E-->K[所有边权都是正数]
E-->L[存在负权边]

F-->M[Floyd算法]

K-->N[稠密图]-->P[朴素Dijkstra算法]
K-->O[稀疏图]-->Q[堆优化Dijkstra算法]

L-->R[有步数限制]-->S[Bellman-Ford算法]
L-->T[无步数限制]-->U[SPFA]

9.刷题统计

问题描述

小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天做 a 道题目, 周六和周日每天做 b 道题目。请你帮小明计算, 按照计划他将在第几天实现做题数大于等于 n 题?

输入格式

输入一行包含三个整数 a,b 和 n.

输出格式

输出一个整数代表天数。

样例输入

10 20 99

样例输出

题解

这道题看着简单，但是因为测试数据过大，不能用简单的循环。

要先求这些题够写至少几周，再求还需要几天

代码

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        long a = scan.nextLong();
        long b = scan.nextLong();
        long n = scan.nextLong();

        long w = n/(a*5+b*2);
        long y = n%(a*5+b*2);

        long num=0;
        long ant=1;

        while(num<y)
        {
          if(ant%7==0||ant%6==6)
          {
            num=num+b;
          }
          else
          {
            num=num+a;
          }
          ant++;
        }
        System.out.println(w*7+ant-1);

        scan.close();
    }
}

10.顺子日期

问题描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

小明特别喜欢顺子。顺子指的就是连续的三个数字：123、456 等。顺子日期指的就是在日期的 yyyymmdd 表示法中，存在任意连续的三位数是一个顺子的日期。例如 20220123 就是一个顺子日期，因为它出现了一个顺子：123；而 20221023 则不是一个顺子日期，它一个顺子也没有。小明想知道在整个 2022 年份中，一共有多少个顺子日期?

题解

日期上能连续的只有012和123，在后面的四位数中出现即可

代码

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        System.out.println(14);

        scan.close();
    }
}

11.出现最多的字符

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

下面的矩阵中包含 ABCDEF 六种字符，请问出现最多的字符出现了几次？

FFEEFEAAECFFBDBFBCDA
DACDEEDCCFFAFADEFBBA
FDCDDCDBFEFCEDDBFDBE
EFCAAEECEECDCDECADDC
DFAEACECFEADCBFECADF
DFBAAADCFAFFCEADFDDA
EAFAFFDEFECEDEEEDFBD
BFDDFFBCFACECEDCAFAF
EFAFCDBDCCBCCEADADAE
BAFBACACBFCBABFDAFBE
FCFDCFBCEDCEAFBCDBDD
BDEFCAAAACCFFCBBAAEE
CFEFCFDEEDCACDACECFF
BAAAFACDBFFAEFFCCCDB
FADDDBEBCBEEDDECFAFF
CDEAFBCBBCBAEDFDBEBB
BBABBFDECBCEFAABCBCF
FBDBACCFFABEAEBEACBB
DCBCCFADDCACFDEDECCC
BFAFCBFECAACAFBCFBAF

题解

遍历排序即可

代码

import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        String str ="FFEEFEAAECFFBDBFBCDADACDEEDCCFFAFADEFBBAFDCDDCDBFEFCEDDBFDBEEFCAAEECEECDCDECADDCDFAEACECFEADCBFECADFDFBAAADCFAFFCEADFDDAEAFAFFDEFECEDEEEDFBDBFDDFFBCFACECEDCAFAFEFAFCDBDCCBCCEADADAEBAFBACACBFCBABFDAFBEFCFDCFBCEDCEAFBCDBDDBDEFCAAAACCFFCBBAAEECFEFCFDEEDCACDACECFFBAAAFACDBFFAEFFCCCDFADDDBEBCBEEDDECFAFFCDEAFBCBBCBAEDFDBEBBBABBFDECBCEFAABCBCFFBDBACCFFABEAEBEACBBDCBCCFADDCACFDEDECCCBFAFCBFECAACAFBCFBAF";

        int[] count = new int[6];
        for(int i=0;i<str.length();i++)
        {
          count[str.charAt(i)-'A']=count[str.charAt(i)-'A']+1;
        }
        Arrays.sort(count);
        System.out.println(count[5]);

        scan.close();
    }
}

12.鲁卡斯队列

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

黄金分割数 0.618与美学有重要的关系。舞台上报幕员所站的位置大约就是舞台宽度的 0.618 处，墙上的画像一般也挂在房间高度的 0.618 处，甚至股票的波动据说也能找到 0.618 的影子…

黄金分割数是个无理数，也就是无法表示为两个整数的比值。0.618 只是它的近似值，其真值可以通过对 5 开方减去 1 再除以 2 来获得，我们取它的一个较精确的近似值：0.618034。

有趣的是，一些简单的数列中也会包含这个无理数，这很令数学家震惊！

1 3 4 7 11 18 29 47…称为“鲁卡斯队列”。它后面的每一个项都是前边两项的和。

如果观察前后两项的比值，即：1/3,3/4,4/7,7/11,11/18…会发现它越来越接近于黄金分割数！

你的任务就是计算出从哪一项开始，这个比值四舍五入后已经达到了与 0.618034 一致的精度。

请写出该比值。格式是：分子/分母。比如：29/47。

题解

先把鲁卡斯队列先循环出来，然后循环除，得到的小数变成整数再比较

代码

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        double[] a = new double[1000000];
        a[0]=1;
        a[1]=3;

        for(int i=2;i<1000000;i++)
        {
          a[i]=a[i-1]+a[i-2];
        }

        double x=0;
        for(int j=01;j<1000000;j++)
        {
          x=a[j-1]/a[j];
          if(Math.round(x*1000000)==618034)
          {
            System.out.println((int)a[j-1]+"/"+(int)a[j]);
            break;
          }
        }

        scan.close();
    }
}

13.找素数

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

素数就是不能再进行等分的整数。比如：7，11。而 9 不是素数，因为它可以平分为 3 等份。一般认为最小的素数是2，接着是 3，5，…

请问，第 100002(十万零二)个素数是多少？

请注意：“2” 是第一素数，“3” 是第二个素数，依此类推。

题解

一个数被循环除到自己的开根号，如果都不能除尽那就是素数。

代码

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        
        int count=0;
        for(int i=2;i<Integer.MAX_VALUE;i++)
        {
          boolean a=true;
          for(int j=2;j<=i/j;j++)
          {
            if(i%j==0)
            {
              a=false;
              break;
            }

          }
          if(a)
          {
            count++;
          }
          if(count==100002)
          {
            System.out.println(i);
            break;
          }
        }
        
    }
}

14.切面条

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

一根高筋拉面，中间切一刀，可以得到 2 根面条。

如果先对折 1 次，中间切一刀，可以得到 3 根面条。

如果连续对折 2 次，中间切一刀，可以得到 5 根面条。

那么，连续对折 10 次，中间切一刀，会得到多少面条呢？

题解

找规律，下一次是上一次的2倍减1

代码

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int[] a=new int[10];
        a[0]=3;
        a[1]=5;
        for(int i=2;i<10;i++)
        {
          a[i]=a[i-1]*2-1;
        }
        System.out.println(a[9]);

        scan.close();
    }
}

15.立方尾不变

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

有些数字的立方的末尾正好是该数字本身。比如：1,4,5,6,9,24,25,…

请你计算一下，在 104 以内的数字中（指该数字，并非它立方后的数值），符合这个特征的正整数一共有多少个。

题解

循环逐个比较取模后的数字，比较的时候可以直接用endsWith比较字符串

i.endsWith(j)可以比较i是否以j结尾

代码

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        
        int count=0;
        for(long i=1;i<=10000;i++)
        {
          long x=i*i*i;
          /*boolean a=true;
          long t1=x;
          long t2=i;
          while(t2>0)
          {
            if(t1%10!=t2%10)
            {
              a=false;
              break;
            }
            t1=t1/10;
            t2=t2/10;

          }
          if(a)
          {
            count++;
          }*/
          String str1=String.valueOf(x);
          String str2=String.valueOf(i);
          if(str1.endsWith(str2))
          {
            count++;
          }

        }
        System.out.println(count);

    }
}

16.星系炸弹

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

在 X 星系的广袤空间中漂浮着许多X星人造“炸弹”，用来作为宇宙中的路标。每个炸弹都可以设定多少天之后爆炸。

比如：阿尔法炸弹 2015 年 1 月 1日放置，定时为15天，则它在2015年1月16 日爆炸。

有一个贝塔炸弹，2014 年 11 月 9 日放置，定时为 1000 天，请你计算它爆炸的准确日期。

请输出该日期，格式为 yyyy−mm−dd 即 4 位年份 2 位月份 2 位日期。比如：2015−02−19。

题解

可以和刷题统计一样，先算至少要几年，再算要几个月几天。更好的方法是用时间api

代码

import java.util.Scanner;
import java.time.*;
import java.time.format.DateTimeFormatter;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {

        LocalDate start = LocalDate.of(2014,11,9);
        LocalDate end = start.plusDays(1000);
        System.out.print(end.format(DateTimeFormatter.ofPattern("yyyy-MM-dd")));

    }
}

17.平方怪圈

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

如果把一个正整数的每一位都平方后再求和，得到一个新的正整数。对新产生的正整数再做同样的处理。

如此一来，你会发现，不管开始取的是什么数字，最终如果不是落入 1，就是落入同一个循环圈。

请输出这个循环圈中最大的那个数字。

题解

面向答案编程，已经口算出来了，用4作为起始值是可以的，用2就不行，也能进循环，但是不会回到2了

最好是用HashSet，seen.add(n);加入元素，seen.contains(n);检查元素是否存在

代码

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        int n = 4;
        int max = 4, t = n;
        while(true) 
        {
          n = Sum(n);
          if(max < n) 
          {
            max = n;
          }
                        
          if(n == t)
          {
            break;
          }
                        
        }
        System.out.print(max);
    }
    public static int Sum(int a) 
    {
      int sum = 0;
      while(a > 0) 
      {
        int m = a % 10;
        sum += (m * m);
        a /= 10;
      }
      return sum;
          
    }
}

18.年龄问题

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

S 夫人一向很神秘。这会儿有人问起她的年龄，她想了想说： “2020 年前，我丈夫的年龄刚好是我的 2 倍，而现在他的年龄刚好是我的 1.5倍”。

你能算出 S 夫人现在的年龄吗？

题解

。二元一次方程组

代码

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
      /*
        y-20=2*x;
        y=1.5*x;
      */
      System.out.println(40);

    }
}

19.激光样式

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

X 星球的盛大节日为增加气氛，用 3030 台机光器一字排开，向太空中打出光柱。

安装调试的时候才发现，不知什么原因，相邻的两台激光器不能同时打开！国王很想知道，在目前这种 bug存在的情况下，一共能打出多少种激光效果？

显然，如果只有 3 台机器，一共可以成 5 种样式，即：全都关上（sorry, 此时无声胜有声，这也算一种）；开一台，共 3 种；开两台，只 1 种。

30 台就不好算了，国王只好请你帮忙了。

要求输出一个整数，表示 30 台激光器能形成的样式种数。

题解

找规律得到这是一个斐波那契数列，可以直接算出

但是也可以用动态规划状态机来做，dp[i][0] = 前 i 台里，第 i 台关着(0) 的方案数，dp[i][1] = 前 i 台里，第 i 台开着(1) 的方案数，即dp[i][0] = dp[i-1][0] + dp[i-1][1]，dp[i][1] = dp[i-1][0]

代码

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        int a = 2;
        int b = 3;
        int res = 0;
        for (int i = 3; i <= 30; i++) {
            res = a + b;
            a = b;
            b = res;
        }
        System.out.println(res);
    }
}

20.换零钞

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

X 星球的钞票的面额只有：100 元，5 元，2 元，1 元，共 4 种。

小明去 X 星旅游，他手里只有 2 张 100 元的 X 星币，太不方便，恰好路过 X 星银行就去换零钱。

小明有点强迫症，他坚持要求 200 元换出的零钞中 2 元的张数刚好是 1 元的张数的 10 倍，剩下的当然都是 5 元面额的。

银行的工作人员有点为难，你能帮助算出：在满足小明要求的前提下，最少要换给他多少张钞票吗？（5 元，2 元，1 元面额的必须都有，不能是 0）

题解

三层循环

代码

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {

      int count=1000000;
      for(int i=1;i<=200/5;i++)
      {
        for(int j=1;j<=200/2;j++)
        {
          for(int k=1;k<=200/1;k++)
          {
            if(5*i+2*j+1*k==200&&j==10*k)
            {
              count=Math.min(count,i+j+k);
            }
          }
        }
      }
      System.out.println(count);

    }
}

21.数列求值

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

给定数列 1,1,1,3,5,9,17,⋯，从第 4 项开始，每项都是前 3 项的和。

求第 20190324 项的最后 4 位数字。

题解

这道题不能用正常的暴力，无论什么类型都会溢出

因为题目要求的是后四位，所以每次只存后四位

代码

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {

        int a = 1,b = 1,c = 1,d = 0;
        for(int i = 4;i<=20190324;i++){
            d = (a+b+c)%10000;
            a = b;
            b = c;
            c = d;
        }
        System.out.println(d);

    }
}

22.跳跃

题目描述

小蓝在一个 n 行 m 列的方格图中玩一个游戏。

开始时，小蓝站在方格图的左上角，即第 1 行第 1 列。

小蓝可以在方格图上走动，走动时，如果当前在第 r 行第 c 列，他不能走到行号比 r 小的行，也不能走到列号比 c 小的列。同时，他一步走的直线距离不超过 3。

例如，如果当前小蓝在第 3 行第 5 列，他下一步可以走到第 3 行第 6 列、第 3 行第 7 列、第 3 行第 8 列、第 4 行第 5 列、第 4 行第 6 列、第 4 行第 7 列、第 5 行第 5 列、第 5 行第 6 列、第 6 行第 5 列之一。

小蓝最终要走到第 n 行第 m 列。

在图中，有的位置有奖励，走上去即可获得，有的位置有惩罚，走上去就要接受惩罚。奖励和惩罚最终抽象成一个权值，奖励为正，惩罚为负。

小蓝希望，从第 1 行第 1 列走到第 n 行第 m 列后，总的权值和最大。请问最大是多少？

输入描述

输入的第一行包含两个整数 n,m，表示图的大小。

接下来 n 行，每行 m 个整数，表示方格图中每个点的权值。

其中，1≤n,m≤100， $−10^4$ ≤权值≤ $10^4$ 。

输出描述

输出一个整数，表示最大权值和。

输入输出样例

示例 1

输入

3 5
-4 -5 -10 -3 1
7 5 -9 3 -10
10 -2 6 -10 -4

输出

题解

题目的意思是一次最多走三格。可以考虑dp动态规划和dfs深度优先搜索，这里用dp比较合适。先接收好数据。然后定义数组来表示，位移的可能情况，共九种。dp的核心是dp[i][j]=在其前面的九种情况中选择一个最大的然后加上i和j对应位置的权值。然后从0开始循环dp的值，注意要跳开都为0的时候。

代码

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int n = scan.nextInt();
        int m = scan.nextInt();
        int[][] a = new int[n][m];
        for(int i=0;i<n;i++)
        {
          for(int j=0;j<m;j++)
          {
            a[i][j]=scan.nextInt();
          }
        }

        int[][] dp = new int[n][m];
        dp[0][0]=a[0][0];

        int[] dx={1,2,3,0,0,0,1,1,2};
        int[] dy={0,0,0,1,2,3,1,2,1};

        //dp[n-1][m-1]=Math.max(dp[n-1][m-1-3],dp[n-1-1][m-1-2],dp[n-1-2][m-1-1],dp[n-1-3][m-1],dp[n-1-1][m-1],dp[n-1-2][m-1],dp[n-1][m-1-1],dp[n-1][m-1-2],dp[n-1-1][m-1-1])+a[n-1][m-1];
        for(int q=0;q<n;q++)
        {
          for(int p=0;p<m;p++)
          {
            if(q==0&&p==0)
            {
              continue;
            }
            int max=Integer.MIN_VALUE;
            for(int k=0;k<9;k++)
            {
              int x=q-dx[k];
              int y=p-dy[k];
              if(x>=0&&y>=0)
              {
                max=Math.max(max,dp[x][y]);
              }
          
            }

            dp[q][p]=max+a[q][p];
          }
        }
        System.out.println(dp[n-1][m-1]);
        
        scan.close();
    }
}

23.全排列

题目描述

本题为代码补全填空题，请将题目中给出的源代码补全，并复制到右侧代码框中，选择对应的编译语言（C/Java）后进行提交。若题目中给出的源代码语言不唯一，则只需选择其一进行补全提交即可。复制后需将源代码中填空部分的下划线删掉，填上你的答案。提交后若未能通过，除考虑填空部分出错外，还需注意是否因在复制后有改动非填空部分产生错误。

对于某个串，比如：“1234”，求它的所有全排列。并且要求这些全排列一定要按照字母的升序排列。

对于“1234”，应该输出(一共4!=24行)：

下面是实现程序，请仔细分析程序逻辑，并填写划线部分缺少的代码。

源代码

#include <stdio.h>
#include <string.h>

//轮换前n个，再递归处理
void permu(char* data, int cur)
{
    int i,j;
    
    if(data[cur]=='\0'){
        printf("%s\n", data);
        return;
    }
    
    for(i=cur; data[i]; i++){
        char tmp = data[i]; 
        for(j=i-1; j>=cur; j--) data[j+1] = data[j];
        data[cur] = tmp;            

        permu(data, cur+1);            

        tmp = data[cur]; 
        for(int j = cur; j <= i - 1; j ++) data[j] = data[j + 1];  //填空
        data[i] = tmp;            
    }
}

int main()
{
    char a[105];
    scanf("%s",a);
    permu(a,0);
    return 0;
}

题解

求全排列，这里permu(data, cur+1); 之前是在dfs插入法，一般是用交换法。将第i个元素插入到目标位置cur后其他字符右移。然后递归调用接着下一位。要填空的地方就是最关键的回溯部分，把这个字符串还原回去，因为这里是直接改的原字符串

24.手机尾数

题目描述

30 年的改革开放，给中国带来了翻天覆地的变化。2011 全年中国手机产量约为 11.72 亿部。手机已经成为百姓的基本日用品！

给手机选个好听又好记的号码可能是许多人的心愿。但号源有限，只能辅以有偿选号的方法了。

这个程序的目的就是：根据给定的手机尾号（4 位），按照一定的规则来打分。其规则如下：

如果出现连号，不管升序还是降序，都加 5 分。例如：5678,4321 都满足加分标准。
前三个数字相同，或后三个数字相同，都加 3 分。例如：4888,6665,7777 都满足加分的标准。注意：7777 因为满足这条标准两次，所以这条规则给它加了 6 分。
符合 AABB 或者 ABAB 模式的加 1 分。例如：2255,3939,7777 都符合这个模式，所以都被加分。注意：7777 因为满足这条标准两次，所以这条标准给它加了 2 分。
含有：6，8，9 中任何一个数字，每出现一次加 1 分。例如：4326,6875,9918 都符合加分标准。其中，6875 被加 2 分；9918 被加 3 分。

尾号最终得分就是每条标准的加分总和！

要求程序从标准输入接收数据，在标准输出上输出结果。

输入描述

第一行是一个整数 n （n<100），表示下边有多少输入行。

接下来是 n 行 4 位一组的数据，就是等待计算加分的手机尾号。

输出描述

输出 n行整数。

输入输出样例

示例

输入

输出

题解

按规则写判断条件，注意不能直接获取数字，可能存在以0开头的尾号，要先获取成字符串形式

代码

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int n = scan.nextInt();
        for(int i=0;i<n;i++)
        {
          String str = scan.next();
          int[] a=new int[4];
          int count=0;
          for(int j=0;j<4;j++)
          {       
            a[j]=str.charAt(j)-'0';
          }
            if(a[3]==a[2]-1&&a[2]==a[1]-1&&a[1]==a[0]-1)count=count+5;
            if(a[3]==a[2]+1&&a[2]==a[1]+1&&a[1]==a[0]+1)count=count+5;
            if(a[3]==a[2]&&a[2]==a[1])count=count+3;
            if(a[2]==a[1]&&a[1]==a[0])count=count+3;
            if(a[0]==a[1]&&a[2]==a[3])count++;
            if(a[0]==a[2]&&a[1]==a[3])count++;

            for(int k=0;k<4;k++)
            {
              if(a[k]==6)count++;
              if(a[k]==8)count++;
              if(a[k]==9)count++;
            }
            System.out.println(count);
        }

        scan.close();
    }
}

25.音节判断

题目描述

小明对类似于 hello 这种单词非常感兴趣，这种单词可以正好分为四段，第一段由一个或多个辅音字母组成，第二段由一个或多个元音字母组成，第三段由一个或多个辅音字母组成，第四段由一个或多个元音字母组成。

给定一个单词，请判断这个单词是否也是这种单词，如果是请输出yes，否则请输出no。

元音字母包括 a, e, i, o, u，共五个，其他均为辅音字母。

输入描述

输入一行，包含一个单词，单词中只包含小写英文字母。单词中的字母个数不超过 100。

输出描述

输出答案，或者为yes，或者为no。

输入输出样例

示例

输入

lanqiao

输出

yes

题解

用四个循环来判断是元音还是辅音，如果不是当前要的就跳到下一个循环，四个循环结束判断一共判断了几个字符，如果相等就输出yes。同时要注意可能存在少于四段的情况，要在二三循环中加入判断

代码

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String str = scan.nextLine();
        char[] word = new char[str.length()];
        for(int i=0;i<str.length();i++)word[i]=str.charAt(i);
        int j=0;
        boolean a=true;
        while(j<str.length()&&!judge(word[j]))j++;
        while(j<str.length()&&judge(word[j]))
        {
          if(j==str.length()-1)
          {
            a=false;
            break;
          }
          j++;
        }
        while(j<str.length()&&!judge(word[j]))
        {
          if(j==str.length()-1)
          {
            a=false;
            break;
          }
          j++;
        }
        while(j<str.length()&&judge(word[j]))j++;
        if(j==str.length()&&a==true)System.out.println("yes");
        else System.out.println("no");
        scan.close();
    }
    public static boolean judge(char a)
    {
      if(a=='a'||a=='e'||a=='i'||a=='o'||a=='u')return true;
      else return false;
    }

}

26.矩阵计数

题目描述

一个 N×M 的方格矩阵，每一个方格中包含一个字符 O 或者字符 X。

要求矩阵中不存在连续一行 3 个 X 或者连续一列 3 个 X。

问这样的矩阵一共有多少种？

输入描述

输入一行包含两个整数 N,M (1≤N,M≤5)。

输出描述

输出一个整数代表答案。

输入输出样例

示例

输入

2 3

输出

题解

状态压缩dp，有点难度。定义dp数组用来表示，已完成前n行，在n-2行的状态和n-1行的状态下的合法排列数量，所以先用两层循环来循环出n-2行和n-1行，再用cur表示当前行，通过<<左移，>>右移和&的与运算进行二进制的运算来判断这一行是否存在连续三个的情况，再用一层循环来做列的判断，最后把dp数组更新

代码

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);        
        int n=scan.nextInt();
        int m=scan.nextInt();
        int[][][] dp=new int[n+1][(1<<m)][1<<m];
        dp[0][0][0]=1;
          for (int i = 1; i <= n; i++) 
          {  
            for (int prev2 = 0; prev2 < (1 << m); prev2++) 
            {  
                for (int prev1 = 0; prev1 < (1 << m); prev1++) 
                {  
                    for (int cur = 0; cur < (1 << m); cur++) 
                    {  
                        if ((cur & (cur >> 1) & (cur >> 2)) == 0) 
                        {
                            boolean valid = true;
                            for (int j = 0; j < m; j++) 
                            {
                                if (((prev2 >> j) & 1) == 1 && ((prev1 >> j) & 1) == 1 && ((cur >> j) & 1) == 1) 
                                {
                                    valid = false;
                                    break;
                                }
                            }
                            if (valid)dp[i][prev1][cur] += dp[i - 1][prev2][prev1];  
                        }
                    }
                }
            }
        }
        int result = 0;
        for (int prev2 = 0; prev2 < (1 << m); prev2++) {
            for (int prev1 = 0; prev1 < (1 << m); prev1++) {
                result += dp[n][prev2][prev1];
            }
        }
        System.out.println(result);  

        scan.close();
    }
}

27.密码脱落

题目描述

X 星球的考古学家发现了一批古代留下来的密码。

这些密码是由 A、B、C、D 四种植物的种子串成的序列。

仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。

由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。

你的任务是：给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。

输入描述

输入一行，表示现在看到的密码串（长度不大于 1000）。

输出描述

要求输出一个正整数，表示至少脱落了多少个种子。

输入输出样例

示例 1

输入

ABCBA

输出

示例2

输入

1	ABDCDCBABC CBABCDCDBA

输出

题解

还是用动态规划，外层循环len从1到n，表示当前考虑的子串长度。内层循环i表示子串的起始位置，j是子串的结束位置。长度为1的时候就是回文，如果 s[i]不等于s[j]，那么最长回文子序列的长度是去掉 s[i]或去掉s[j]后的最长回文子序列长度，即f[i][j]=Math.max(f[i+1][j], f[i][j-1])。如果 s[i]等于s[j]，那么这两个字符可以成为回文子序列的一部分，因此 f[i][j] =f[i+1][j-1] + 2，再加上这两个相同的字符。

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) {
    int N = 1001;
    char[] s = new char[N];
    int[][] f = new int[N][N];
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        s = str.toCharArray();
        int n = s.length;
        for(int len = 1; len <= n; len ++) 
        {
            for(int i = 0 ;i + len - 1 < n; i ++) 
            {
                int j = i + len - 1;
                if(len == 1) f[i][j] = 1;
                else 
                {
                    f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
                    if(s[i] == s[j]) 
                    {
                        f[i][j] = Math.max(f[i][j], f[i + 1][j - 1] + 2);
                    }
                }
            }
        }
        System.out.println(n - f[0][n - 1]);
    }
}

28.糖果

题目描述

糖果店的老板一共有 M 种口味的糖果出售。为了方便描述，我们将 M 种口味编号 1∼ M。

小明希望能品尝到所有口味的糖果。遗憾的是老板并不单独出售糖果，而是 K 颗一包整包出售。

幸好糖果包装上注明了其中 K 颗糖果的口味，所以小明可以在买之前就知道每包内的糖果口味。

给定 N 包糖果，请你计算小明最少买几包，就可以品尝到所有口味的糖果。

输入描述

第一行包含三个整数 N,M,K。

接下来 N 行每行 K 个整数 $T_1,T_2,⋅⋅⋅,T_K$ ，代表一包糖果的口味。

其中，1≤N≤100,1≤M≤20,1≤K≤20,1≤ $T_i$ ≤M。

输出描述

输出一个整数表示答案。如果小明无法品尝所有口味，输出 −1。

输入输出样例

示例

输入

输出

题解

这道题不适合用贪心算法来做，贪心只能保证在局部是最优解，但是不能保证整体最优解。所以要用状压dp。接收好数据后先把dp数组都填充为最大值，第一个为0。然后开始遍历，外层循环控制包数，内层循环用左移并-1表示全选的状态，并且逐渐递减控制口味数。如果一个dp数组不是最大值，也就是已经选过一包以上了，执行if中的内容（第一次触发这个if是在dp0），就是加上当前口味得到的新的状态，这里用的是按位或，然后选一个最小值更新新状态。最后判断dp数组的最后一个值也就是全选择状态是否还是最大值，最大值就意味着遍历不能到达这种状态

代码

import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int n=scan.nextInt();
        int m=scan.nextInt();
        int k=scan.nextInt();

        int[] dp=new int[(1<<m)];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0]=0;

        int[] candy=new int[n];
        for(int i=0;i<n;i++)
        {
          int candymask=0;
          for(int j=0;j<k;j++)
          {
            int a=scan.nextInt()-1;
            candymask=candymask|(1<<a);
          }
          candy[i]=candymask;
        }

        for(int q=0;q<n;q++)
        {
          int candymask=candy[q];
          for(int p=((1<<m)-1);p>=0;p--)
          {
            if(dp[p]!=Integer.MAX_VALUE)
            {
              int newmask=p|candymask;
              dp[newmask]=Math.min(dp[newmask],dp[p]+1);
            }
          }
        }

        if(dp[(1<<m)-1]==Integer.MAX_VALUE)
        {
          System.out.println(-1);
        }
        else
        {
          System.out.println(dp[(1<<m)-1]);
        }

        scan.close();
    }
}

29.大臣的旅费

题目描述

很久以前，T 王国空前繁荣。为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。

为节省经费，T 国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。

J 是 T 国重要大臣，他巡查于各大城市之间，体察民情。所以，从一个城市马不停蹄地到另一个城市成了 J 最常做的事情。他有一个钱袋，用于存放往来城市间的路费。

聪明的 J 发现，如果不在某个城市停下来修整，在连续行进过程中，他所花的路费与他已走过的距离有关，在走第 x 千米到第 x +1 千米这一千米中（ x 是整数），他花费的路费是 x +10 这么多。也就是说走 1 千米花费 11，走 2 千米要花费 23。

J 大臣想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？

输入描述

输入的第一行包含一个整数 n，表示包括首都在内的 T 王国的城市数。

城市从 1 开始依次编号，1 号城市为首都。

接下来 n -1 行，描述 T 国的高速路（ T 国的高速路一定是 n -1 条）。

每行三个整数 $P_i,Q_i,D_i$ ，表示城市 $P_i$ 和城市 $Q_i$ 之间有一条高速路，长度为 $D_i$ 千米。

输出描述:

输出一个整数，表示大臣 J 最多花费的路费是多少。

输入输出样例

示例

输入

输出

样例说明

大臣 J 从城市 4 到城市 5 要花费 135 的路费。

题解

要求最大费用，先求出这个树的直径，树的直径的求法是先从一点用dfs到最远点，再从这个点用dfs到其最远点

代码

import java.io.*;
import java.util.*;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int maxNode = 0; 
    static int maxLen = 0;  
    static List<int[]>[] list; 

    public static void main(String[] args) throws Exception {
        int n = Integer.parseInt(br.readLine());
        list = new List[n + 1];
        for (int i = 0; i <= n; i++) list[i] = new ArrayList<>();

        for (int i = 0; i < n - 1; i++) {
            String[] sp = br.readLine().split(" ");
            int x = Integer.parseInt(sp[0]);
            int y = Integer.parseInt(sp[1]);
            int len = Integer.parseInt(sp[2]);
            list[x].add(new int[] {y, len});
            list[y].add(new int[] {x, len});
        }
        dfs(1, 1, 0);
        
        dfs(maxNode, maxNode, 0);

        int sum = maxLen * 10 + maxLen * (maxLen + 1) / 2;
        System.out.println(sum);
    }

    private static void dfs(int x, int father, int len) {
        for (int[] arr : list[x]) 
        {
            if (arr[0] == father) continue;
            
            if (len + arr[1] > maxLen) 
            {
                maxLen = len + arr[1];
                maxNode = arr[0];
            }

            dfs(arr[0], x, len + arr[1]);
        }
    }
}

30.危险系数

题目描述

抗日战争时期，冀中平原的地道战曾发挥重要作用。

地道的多个站点间有通道连接，形成了庞大的网络。但也有隐患，当敌人发现了某个站点后，其它站点间可能因此会失去联系。

我们来定义一个危险系数 DF(x,y)：

对于两个站点 x 和 y (x!=y), 如果能找到一个站点 z，当 z 被敌人破坏后，x 和 y 不连通，那么我们称 z 为关于 x,y 的关键点。相应的，对于任意一对站点 x 和 y，危险系数 DF(x,y) 就表示为这两点之间的关键点个数。

本题的任务是：已知网络结构，求两站点之间的危险系数。

输入描述

输入数据第一行包含 2 个整数 n (2≤n≤1000),m (0≤m≤2000),分别代表站点数，通道数；

接下来 m 行，每行两个整数 u,v (1≤u,v≤n,u!=v) 代表一条通道；

最后 1 行，两个数 u,v，代表询问两点之间的危险系数 DF(u,v)。

输出描述

输出一个整数，如果询问的两点不连通则输出 -1.

输入输出样例

示例

输入

输出

题解

割点问题，即失去这个点会破坏图的连通性，还是用邻接表来接收数据。先用dfs检查一遍两点之间是否连通。然后遍历每一个点对应移除的情况下用dfs是否还是连通的，不连通了则是割点，也就是这里的危险系数

代码

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Arrays;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    static ArrayList<ArrayList<Integer>> graph;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int n = scan.nextInt(); 
        int m = scan.nextInt(); 

        graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) 
        { 
            graph.add(new ArrayList<Integer>());
        }
        
        for (int i = 0; i < m; i++) 
        {
            int u = scan.nextInt();
            int v = scan.nextInt();

            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        
        int a = scan.nextInt();
        int b = scan.nextInt();
        scan.close();

        boolean[] visited = new boolean[n + 1];
        Arrays.fill(visited,false);
        dfs(a, visited);
        if (!visited[b]) 
        {
            System.out.println(-1); 
            return;
        }

        int count = 0;
        for (int node = 1; node <= n; node++) 
        {
            if (node == a || node == b) 
            {
                continue; 
            }

            visited = new boolean[n + 1];
            visited[node] = true; 
            dfs(a, visited);

            if (!visited[b]) 
            {
                count++;
            }
        }
        
        System.out.println(count);
    }
    
    public static void dfs(int node, boolean[] visited) {
        visited[node] = true;
        
        for (int i = 0; i < graph.get(node).size(); i++) 
        {
            int neighbor = graph.get(node).get(i);
            if (!visited[neighbor]) {
                dfs(neighbor, visited);
            }
        }
    }
}