蓝桥杯31天冲刺 Day14

算式900

链接: 算式900.

这道题只要掌握最基本的全排列模板，把0~9全排列出来，问题就解决一大半了

这里，我使用int[]（nums数组设置为公共常量）来存放排序好的数字，具体实现方法：

    public static void DFS(int start) {
    if(start == 9) {
    if(check()) {
    cal();}}for(int i=start;i<=9;i++) {
    swap(nums,start,i);DFS(start+1);swap(nums,start,i);}}public static void swap(int[] nums,int i ,int j) {
    int t=nums[i];nums[i]=nums[j];nums[j]=t;}

这里的check()函数和cal()函数后面会讲到

其中，满足全排列终止条件后（也就说明找到了一种全排列组合），我们就可以对这组数字进行进一步处理了

• check()函数：检查三个数字是否符合规范（开头不为0）

    public static boolean check() {
    if(nums[0] == 0 ||nums[4]==0||nums[8]==0)return false;return true;}

• cal()函数：进行式子的验证，将nums中的数字转换成相应数字，进行计算即可

    public static void cal() {
    int a =nums[0] * 1000 + nums[1] * 100 + nums[2] *10 + nums[3] ;int b =nums[4] *1000 + nums[5] * 100 +nums[6] * 10 + nums[7];int c = nums[8] *10 + nums[9];if(a>b&&(a-b) * c ==900)System.out.println(a+" "+b+" "+c);}

整体代码：

package 题库;
import java.util.*;public class 算式900 {
    public static int[] nums = {
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9};public static void main(String[] args) {
    // TODO Auto-generated method stubDFS(0);}public static void DFS(int start) {
    if(start == 9) {
    if(check()) {
    cal();}}for(int i=start;i<=9;i++) {
    swap(nums,start,i);DFS(start+1);swap(nums,start,i);}}public static void swap(int[] nums,int i ,int j) {
    int t=nums[i];nums[i]=nums[j];nums[j]=t;}public static void cal() {
    int a =nums[0] * 1000 + nums[1] * 100 + nums[2] *10 + nums[3] ;int b =nums[4] *1000 + nums[5] * 100 +nums[6] * 10 + nums[7];int c = nums[8] *10 + nums[9];if(a>b&&(a-b) * c ==900)System.out.println(a+" "+b+" "+c);}public static boolean check() {
    if(nums[0] == 0 ||nums[4]==0||nums[8]==0)return false;return true;}}

谈判

链接: 谈判.

这是一个很简单的贪心思想

拿题目中的例子举例

题意是什么呢？谈判就是将两个村落合并，直到只剩一个村落为止。我们先按顺序来模拟一下

此时已经合并为了一个村落，我们再复盘一下，数一下每个村庄都花费了几次

这样我们可以很容易看出，把人数越少的村庄排在前面，花费越少，我们就可以很容易解决这题了

完整代码：

import java.util.*;public class 谈判 {
    public static void main(String[] args) {
    // TODO Auto-generated method stubScanner sc = new Scanner(System.in);int n = sc.nextInt();int[] nums = new int[n];for(int i =0;i<n;i++)nums[i] = sc.nextInt();Arrays.sort(nums);int res = 0;int j =n-1;for(int i =0;i<n;i++) {
    if(i==0) {
    res+=nums[i]*j;continue;}res+=nums[i] * j;j--;}System.out.println(res);}}

幸运数

链接: 幸运数.

这道题我们直接模拟来实现

首先，我们需要建一个大小为n+1的数组，下标值也就代表对应数字值。 比如说nums[10] = 10。同时，由于数组初始化，其中填充的数字都是0，所以我们用1来表示当前位置数字已被删除。

然后，想要模拟这一过程，就要用循环来实现

我们先设立一个变量i，来表示当前的幸运数。但是，前提是，当前位置的数字得存在，我们就需要把i挪动到存在的幸运数，就有了以下代码：

        while(nums[i]!=0) {
    i++;}

然后，根据题意，从头开始数存在的数字个数，只要当前的个数%i==0，我们就要删除它，也就是将nums[j] = 1

            int cnt=0;for(int j=1;j<=n;j++) {
    if(nums[j] == 0) {
    cnt++;if(cnt%i == 0) {
    nums[j] = 1;}

最后，我们遍历一下(m,n)，数一下nums[i]==0的个数，最后输出即可

        int res = 0;for(int i =m+1 ;i < n ;i++ ) {
    if(nums[i] == 0)res++;}System.out.println(res);

整体代码：

package 题库;
import java.util.*;
public class 幸运数 {
    public static void main(String[] args) {
    // TODO Auto-generated method stubScanner sc = new Scanner(System.in);int m = sc.nextInt();int n = sc.nextInt();int[] nums = new int[n+1];//模拟for(int i =2;i<=n;i++) {
    while(nums[i]!=0) {
    i++;}int cnt=0;for(int j=1;j<=n;j++) {
    if(nums[j] == 0) {
    cnt++;if(cnt%i == 0) {
    nums[j] = 1;}}}}int res = 0;for(int i =m+1 ;i < n ;i++ ) {
    if(nums[i] == 0)res++;}System.out.println(res);}
}