洛谷算法1-3 暴力枚举

1 P2241统计方形

2 三连击

3 选数

4 P1088 [NOIP2004 普及组] 火星人

5 P3799 小 Y 拼木棒排列组合

6 P2392 kkksc03考前临时抱佛脚

7 P2036 [COCI2008-2009 #2] PERKET

1 P2241统计方形

思路：

本题中，矩阵数量=正方形数量+长方形数量，得出正方形个数和矩阵个数即可求出长方形个数
求正方形个数：正方形右下角i，j，取min（i，j）即为到这个点可能的正方形个数
求矩阵个数，i*j

public static void main(String[] args) {Scanner scanner=new Scanner(System.in);int n = scanner.nextInt();int m= scanner.nextInt();// 1*1正方形long countZheng=0;long countJu=0;for (int i = 1; i <=n ; i++) {for (int j = 1; j <=m ; j++) {countZheng+=Math.min(i,j);countJu+= (long) i *j;}}System.out.print(countZheng+" ");System.out.println(countJu-countZheng);
}

2 三连击

思路：

将9个数分成三个三位数，要找到成比例的一组数，枚举出所有可能的数
采用深度搜索，使用boolean数组判断该数是否被使用
要记录三个三位数，因为题目中直接输出即可，不是先输出组数，所以不需要保存该组数据，使用一个number数组，前3位为第一个三位数，中间三位为第二个三位数，后三位为第三个三位数

import java.util.ArrayList;
import java.util.Enumeration;
import java.util.Scanner;public class P1618 {static Scanner scanner=new Scanner(System.in);static int A = scanner.nextInt();static int B = scanner.nextInt();static int C = scanner.nextInt();static boolean flags=false;public static void main(String[] args) {int[]number=new int[10];boolean[]flag=new boolean[10];// 深度搜索枚举所有情况digui(1,number,flag);if (!flags){System.out.println("No!!!");}}public static int judge(int m,int[] number){int sum=0;for (int i = 3*m-2; i <=3*m ; i++) {int ele=number[i];sum=sum*10+ele;}return sum;}public static void digui(int index,int[]number, boolean[]flag){if (index>=10){// 9位数全部使用完了 判断比例关系int one=judge(1,number);int two=judge(2,number);int three=judge(3,number);if (one*B==two*A && one*C==three*A && two*C==three*B){System.out.print(one+" ");System.out.print(two+" ");System.out.print(three);System.out.println();flags=true;}return;}for (int i = 1; i <= 9; i++) {if (!flag[i]){// 拼接这个数number[index]=i;flag[i]=true;digui(index+1,number,flag);// 回溯flag[i]=false;}}}
}

3 选数

思路：

组合，从一些数中选取一部分(子集)，判断是否是素数
递归深度搜索，深度为子集的个数
该题中组合不可以重复，使用start来标记从哪里开始

import java.util.Scanner;public class P1036 {static int count=0;public static void main(String[] args) {Scanner scanner=new Scanner(System.in);int n = scanner.nextInt();int k = scanner.nextInt();int[] array=new int[n];int sum=0;boolean[] flags=new boolean[n];for (int i = 0; i < n; i++) {array[i]=scanner.nextInt();}digui(1,array,k,sum,flags,0);System.out.println(count);}public static void digui(int index,int[]array,int k,int sum,boolean[] flags,int start){if (index>k){// 已经选择够数量 判断sum是否是素数if (isPrime(sum)){count++;}return;}for (int i = start; i < array.length; i++) {if (!flags[i]){sum+=array[i];flags[i]=true;// 这里start是i+1而不是start+1 因为i指向的是当前数 i+1是之后的数 // start是第一次进入该循环开始的数 之后循环继续而start不变 会造成重复digui(index+1,array,k,sum,flags,i+1);flags[i]=false;sum-=array[i];}}}private static boolean isPrime(int sum) {for (int i = 2; i <= sum/i; i++) {if (sum%i==0){// 不是素数return false;}}return true;}
}

4 P1088 [NOIP2004 普及组] 火星人

思路：

题目给出一个手指数，将其转换为数字，加上给定数之后，找到对应的排列数输出
直接定位题目给定排列， i=array[index-1];

- array是程序给定的一个排列数数组，array[index-1];是当前层数的值
- 我们需要找到初始时给定的排列数，我们把i值赋给 num[index-1]
- 在深度达到层数后，第一次找到的排列数即为给定排列数

System.exit(0);直接结束程序，return只能结束方法，在递归深度很深时，程序依然需要很长时间

import java.util.Arrays;
import java.util.Scanner;public class P1088 {static int count=0;static int[]array;static int M;static int target;static boolean flag=false;public static void main(String[] args) {new Thread(null, () -> {Scanner scanner=new Scanner(System.in);int N = scanner.nextInt();M = scanner.nextInt();// array是火星人的手指array=new int[N];for (int i = 0; i < N; i++) {array[i]=scanner.nextInt();}// 1.将手指转为所代表的数字boolean[] flags=new boolean[N+1];int[]num=new int[N];// 2.加上小整数// 3.转为手指数digui(1,flags,N,num);scanner.close();},"t",2<<24).start();// 2<<24 是stackSize 测试样例第二个爆栈，改一下虚拟机栈内存大小}/*** 全排列* @return*/public static void digui(int index,boolean[]flags,int N,int[]num)  {if (index>N){count++;if (count==1){// 第一次找到的排列数 皆为输入的数// 计算目标值target=count+M;}if (count==target){for (int ele : num) {System.out.print(ele+" ");}flag=true;}return;}for (int i = 1; i <= N; i++) {if (count==0){// count==0 还没有找到第一个排列的数// array是给定的数组 1 2 3 4 5 多次递归之后 直接到达给定的位置i=array[index-1];}if (!flags[i]){num[index-1]=i;flags[i]=true;digui(index+1,flags,N,num);flags[i]=false;if (flag){// 结束System.exit(0);}}}}
}

5 P3799 小 Y 拼木棒排列组合

思路：

n根木棒中挑出4根组成正三角形(3条边都相等，则有两根木棒长度相等，另外两根木棒相加为前两根木棒的长度
纯暴力解法会TLE，采用数学中组合的方式，

- 首先统计每个长度出现的次数
- 外层循环，挑选2个长度相等的木棒，注意：木棒长度需要大于2，否则两根木棒相加之和大于此木棒，在数量为n的木棒中，挑选两个a=C(counts[i],2) n*(n-1)/2
- 内层循环，一根木棒长度为j，另一根木棒长度为i-j，如果j=i-j,则需要在长度为j的木棒中挑选两根，c=C(count[j],2),注意该长度为j的木棒个数需要>=2个;如果j!=i-j,则需要在长度为j的木棒中挑选一根，长度为i-j的木棒中挑选一根，c=C(counts[j],1)*C(counts[i-j],1);
- 则 count+=a*c;注意需要每次都取模，以免超出范围

细节：运算的优先顺序

count += a * c;
首先计算 a * c 的结果，然后将这个结果加到 count 上。
接着对 count 进行取模运算，即 count %= (int) mod;，这会确保 count 的值不会超过 mod。
count += a * c % mod;
首先计算 a * c 的结果，然后对这个结果进行取模运算，得到 (a * c) % mod。
然后将这个取模结果加到 count 上。

import java.util.Scanner;public class P3799 {static double mod = Math.pow(10, 9) + 7;public static void main(String[] args) {Scanner scanner=new Scanner(System.in);int n = scanner.nextInt();int[]array=new int[n];int[]counts=new int[n];// 记录最大长度int maxLength=0;int menLength=Integer.MAX_VALUE;for (int i = 0; i < n; i++) {array[i]=scanner.nextInt();counts[array[i]]++;maxLength=Math.max(maxLength,array[i]);menLength=Math.min(menLength,array[i]);}int count=0;// 外层循环 拿到两个长度为i值木棒 i和j是长度 counts.length是有多少种长度不同的元素 无法代表最长长度for (int i = menLength+1; i <= maxLength; i++) {// 排列组合的方式 在长度等于i的木棒中挑两个if (counts[i]<2){continue;}int a=C(counts[i],2);// 内层循环 拿到两根长度和为i的木棒for (int j = menLength; j <= i/2; j++) {int c;// 两根木棒相等 则总长度为j的木棒中挑2个if (j==i-j){if (counts[j]<2){continue;}c=C(counts[j],2);}else{// 两根木棒长度相等 则总长度为j的木棒中挑1个 i-j的木棒中挑一个c=C(counts[j],1)*C(counts[i-j],1);}// 注意每次计算完都要取模count+=a*c;count %= (int) mod;}}System.out.println(count);;}public static int C(int  n,int k){if (k==2){// 从n个数中取2个数return n*(n-1)/2;}else{return n;}}
}

排列公式：

A 有顺序

组合公式：

C 无顺序
C35=5*4*3/1*2*3
C62=6*5/1*2

6 P2392 kkksc03考前临时抱佛脚

思路：

每次选择让时间加到较小值的思想不成立
每个科目独立，则进行多次循环，算出每个科目需要的最短时间
左右脑同时学习，则本道题要不左脑，要不右脑，两种情况可以类比为背包问题，在左右脑的时间都接近t/2时，所用时间最短效率最高，则背包容量为t/2，每道题为所放物品，求怎样放时长最接近t/2
每个科目所需的时间为Math.max(v,t-v);
v为背包所求时间，t-v为剩余题目的时间

细节：背包容量设置为sumTime / 2 + 1，这样可以避免0容量

import java.util.Arrays;
import java.util.Scanner;public class P2392 {public static void main(String[] args) {Scanner scanner=new Scanner(System.in);int[] array=new int[4];for (int i = 0; i < 4; i++) {array[i]=scanner.nextInt();}int sum=0;for (int value : array) {// 将时间比作价值int[] values = new int[value];// 总时间int sumTime = 0;for (int j = 0; j < values.length; j++) {values[j] = scanner.nextInt();sumTime += values[j];}// 比作01背包问题 当左右脑时间最接近t/2时 效率高int[][] dp = new int[value][sumTime / 2 + 1];for (int j = 0; j < sumTime / 2+1; j++) {if (j >= values[0]) {dp[0][j] = values[0];}}for (int j = 1; j < value; j++) {for (int k = 0; k < sumTime / 2 + 1; k++) {if (k < values[j]) {dp[j][k] = dp[j - 1][k];} else {dp[j][k] = Math.max(dp[j - 1][k], dp[j - 1][k - values[j]] + values[j]);}}}sum += Math.max(dp[value - 1][sumTime / 2], sumTime - dp[value - 1][sumTime / 2]);}System.out.println(sum);}
}

7 P2036 [COCI2008-2009 #2] PERKET

思路

本题中说至少使用一种配料，即可能使用一种，两种...n种，我们要找到酸度和苦读绝对差最小的组合，采用dfs深度搜索
注意：因为配料数目不同，可以多次深度搜索，通过层数来决定每次搜索的组合数

import javax.sound.midi.SysexMessage;
import java.util.Scanner;public class P2036 {static int result=Integer.MAX_VALUE;public static void main(String[] args) {Scanner scanner=new Scanner(System.in);int n = scanner.nextInt();int[][] array=new int[n][2];for (int i = 0; i < n; i++) {array[i][0] = scanner.nextInt();array[i][1] = scanner.nextInt();}int s=1;int b=0;boolean[]flags=new boolean[n];// n次深度搜索 每次深度不同for (int i = 1; i <= n; i++) {dfs(i,1,array,0,flags,s,b);}System.out.println(result);}
// num是本次深度搜索的层数（组合数）  index是当前递归的层数public static void dfs(int num,int index,int[][]array,int start,boolean[]flags,int s,int b){if (index>num){int abs = Math.abs(s - b);if (abs<result){result=abs;}return ;}for (int i = start; i <array.length ; i++) {if (!flags[i]){s*=array[i][0];b+=array[i][1];flags[i]=true;dfs(num,index+1,array,i+1,flags,s,b);flags[i]=false;s/=array[i][0];b-=array[i][1];}}}
}