杂题
105 油漆面积
错误描述 ： 发生了段错误
原因： 保持二维数组时使用了int数组，一个int占4字节。10004*10004(个int类型变量) * 4 (转换成字节) / 1000 (转换为kb/千字节) / 1024 (转换为mb) 约为390mb， 远超题目最大运行内存256mb,所以会报段字节的错误
解决方法： 使用占用内存更小的类型，如boolean,占用1个字节
代码实现
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
ArrayList<int[]> rectangles = new ArrayList<>();
boolean[][] grid = new boolean[10004][10004];
for(int i = 0 ; i < n ; i++) {
int x1 = scan.nextInt();
int y1 = scan.nextInt();
int x2 = scan.nextInt();
int y2 = scan.nextInt();
int temp = 0;
if(x1 > x2) {
temp = x2;
x2 = x1;
x1 = temp;
}
if(y1 > y2) {
temp = y2;
y2 = y1;
y1 = temp;
}
rectangles.add(new int[]{x1,y1,x2,y2});
}
for(int[] arr: rectangles) {
for(int x = arr[0]; x < arr[2]; x++) {
for(int y = arr[1]; y< arr[3]; y++) {
grid[x][y] = true;
}
}
}
int result = 0;
for(int i = 0 ; i < grid.length ; i++) {
for(int j = 0 ; j < grid[0].length ; j++) {
if(grid[i][j]) {
result++;
}
}
}
System.out.println(result);
}
3527 阶乘的和
解题方法 从最小的数开始，尽可能多地将它的次数合并到更高一阶的数，直到无法合并为止。最终的min就是最大的m，因为此时所有比min小的阶乘已经被合并，而当前的min的阶乘次数不足以再合并到更高阶，所以m!就是最大的可能。
数学依据 阶乘的一个性质：k+1个k!可以合并成一个(k+1)!，因为(k+1)! = (k+1) × k!。
代码逻辑
循环条件
map.get(min) >= min+1- 核心目的：判断当前最小值
k的出现次数是否足够合并到(k+1)!。 - 数学依据：将
k+1个k!合并为1个(k+1)!（因(k+1)! = (k+1) × k!）。 - 例：若
min=2（即k=2），需至少3个2!才能合并为1个3!。
- 核心目的：判断当前最小值
整除检查
map.get(min) % (min+1) == 0- 确保合并后不产生余数（无法完全合并）。
- 例1：
4个2!→4 % 3 ≠ 0→ 无法合并为3!。 - 例2：
6个2!→6 % 3 = 0→ 合并为2个3!。
合并操作
- 若可合并，将
k!的个数按k+1分组，生成(k+1)!的个数。 - 更新
map：将合并后的值累加到k+1的计数中。 - 提升
min：将当前最小值设为k+1，尝试更高阶合并。
- 若可合并，将
终止条件
- 当无法整除或次数不足时，当前
min即为最大m。
- 当无法整除或次数不足时，当前
代码实现
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int[] nums = new int[n];
for(int i = 0 ; i < n ; i++) {
nums[i] = scan.nextInt();
}
int min = Integer.MAX_VALUE;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0 ; i < n; i++) { //统计个数
min = Math.min(min, nums[i]); //找到最小值
if(!map.containsKey(nums[i])) {
map.put(nums[i], 1);
}else {
map.put(nums[i], map.get(nums[i])+1);
}
}
while(map.get(min) >= min + 1) { //有可能合并
if(map.get(min) % (min+1) == 0) {//可以合并
if(!map.containsKey(min+1)) { //把新合并的值加入map
map.put(min+1, 0);
}
map.put(min+1, map.get(min+1) + map.get(min) / (min + 1)); //更新当前合并值的数量
min += 1; //更新最小值
} else {
break; //无法进一步合并，直接退出
}
}
System.out.println(min);
}
2154 矩形拼接
注意的点
1.注意思考角度：从结果思考，而不是过于专注于细节。三个矩形拼接：只有三种可能情况：4 ， 6 ， 8条边。
2.矩形4条边：说明合并成了一个大矩形->细分成两种合并情况
3.矩形6条边，说明其中两个合并成了一个大矩形->细分两种情况
合并情况：1.边相同 2.两条边可以拼成大边的大小 3.如果结果是4，还要考虑拼大边的两个矩形的另外两条边也相同
代码实现
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int T = scan.nextInt();
for(int t = 0 ; t < T ; t++) {
int[] edges = new int[6];
//三个矩形拼接有三种情况:
//1.三个矩形刚好成一个大矩形
//2.三个矩形中两个可以拼成一个矩形
//3.三个矩形不能完美拼接
int result = 8;
for(int j = 0 ; j < 6; j++) {
edges[j] = scan.nextInt();
}
for(int i = 0 ; i < 2 ; i++) { //第一个矩形
for(int j = 2; j < 4 ; j++) //第二个矩形
for(int k = 4; k <6; k++) { //第三个矩形
int x1 = edges[i], x2 = edges[j], x3 = edges[k];
if(x1 == x2 && x2 == x3)result = Math.min(result, 4); //如果三个矩形有一条边都相同，可以拼成一个大矩形
if(check1(x1, x2, x3, edges))result = Math.min(result, 4); //如果三个矩形， 三个矩形能拼成一个大矩形
if(x1 == x2 || x1 == x3 || x2 == x3)result = Math.min(result, 6);//三个矩形中，其中两个矩形的一条边相同。可以拼成一个矩形
if(check2(x1, x2, x3))result = Math.min(result, 6); //两个矩形可以拼成一个矩形
//注意判断的顺序，这样下面的判断不会影响上面的结果，或者判断后手动退出当前循环
//都不满足，说明拼不到一起
}
}
System.out.println(result);
}
}
public static boolean check1(int x1, int x2, int x3, int[] edges) { //检查是否能拼成一个整体
if(x1 >= x2 && x1 >= x3) { //看看x2 和 x3 能不能拼成x1的一条边的大小，从而合并成一个矩形
//其中一条边的长度可以由合并两个其他小矩形的边达到
//另外一条边相等
//edges[2] + edges[3] - x2 == edges[4] + edges[5] - x3 相当于 求 另外两个三角形 非 x2 和 x3的那条边相等
if(x1 == x2 + x3 && edges[2] + edges[3] - x2 == edges[4] + edges[5] - x3) {
return true;
}
}
//同理，考虑另外两个边更大的情况
if(x2 >= x1 && x2 >= x3) {
if(x2 == x1 + x3 && edges[0] + edges[1] - x1 == edges[4] + edges[5] - x3) {
return true;
}
}
if(x3 >= x1 && x3 >= x2) {
if(x3 == x1 + x2 && edges[0] + edges[1] - x1 == edges[2] + edges[3] - x2) {
return true;
}
}
return false;
}
public static boolean check2(int x1, int x2, int x3) {//检查是否至少能有两个矩形拼为一个整体
//只考虑一条边， 其中两条能不能拼成大的那条
if(x1 > x2 && x1 > x3) {
if(x1 == x2 + x3) {
return true;
}
}
if(x2 > x1 && x2 > x3) {
if(x2 == x1 + x3) {
return true;
}
}
if(x3 > x2 && x3 > x1) {
if(x3 == x2 + x1) {
return true;
}
}
return false;
}
前缀和
3142 可获得的最小取值
解题思路 模拟 用前缀和模拟从前面取几次最小的两个数，用后缀和记录从后面取几次最大的数
- 操作 k 次， 如果从前面取i 次， 那就从后面取 k - i 次
代码实现
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int k = scan.nextInt();
int[] arr = new int[n];
for(int i = 0 ; i < n ; i++) {
arr[i] = scan.nextInt();
}
Arrays.sort(arr);
//记录两种操作在k次操作中所有可能的值
//通过枚举，在k次操作中各进行几次不同的操作得到最小值，从而得到答案
long[] preSum = new long[k+1];
long[] sufSum = new long[n+1];
//前两个最小元素的前缀和：注意最多计算到k次，因为最对操作k次
for(int i = 1 ; i <= k ; i++) {
preSum[i] = preSum[i-1] + arr[2*i - 2] + arr[2*i - 1];
}
//所有元素的后缀和
for(int i = n - 1 ; i>= 0 ; i--) {
sufSum[i] = sufSum[i+1] + arr[i];
}
long result = Long.MAX_VALUE;
for(int i = 0 ; i <= k ; i++) {
//取前两元素操作i次，需要取最大元素的操作次数k-i次
int t = k - i;
//两种操作完后的和，注意t为0的情况
// 最大的t个元素的和：从后往前取t个，即从n-t的位置开始
long current = preSum[i] + (t > 0 ? sufSum[n - t] : 0);
result = Math.min(result, current);
}
System.out.println(result);
}
1811: [NewOJ Week 5] 并行处理
思路分析 最短运行时间： 找在两个GPU上运行任务时间最长的那一个，再从所有最长时间中找出最短的一个(这样就包含了运势时间短的那个GPU)
把总的运行时间通过前缀和记录，在第i个位置进行划分。左部分为preSum[i],右部分为preSum[n] - preSum[i] (总任务数为n)。这样就把运行时间以 i 为界限划分为两半，只需要遍历从中比较找出最小时间即可。
代码实现
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long sum[] = new long[n+1]; //前缀和数组
for(int i = 1 ; i <= n ; i++) { //求前缀和
int a = sc.nextInt();
sum[i] = sum[i-1] + a;
}
long ans = sum[n]; //答案，默认最大值
for(int i = 0 ; i <= n; i++) {
ans = Math.min(ans, Math.max(sum[i], sum[n] - sum[i])); //找划分时间耗费大的，结果是从大耗费时间里面找最小的
}
System.out.println(ans);
}
注意事项 注意题目要求的取值范围，防止类型范围不匹配出错。
3507 异或和之和
所有子段：数组中长度为1，2，…,n 的子段
异或和:对两个数进行二进制异或比较后得到的结果，如: 1(01) or 2(10),结果为 (11) 十进制3
解题思路:
1.直接遍历所有子段，得到结果相加。时间复杂度高，为O（n^3）
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for(int i = 0 ; i < n; i++)arr[i] = sc.nextInt();
long result = 0;
for(int L = 0; L < n; L++){ //遍历所有子段
for(int R = L ; R < n; R++){
long sum = 0;
for(int i = L ; i <= R; i++)sum ^= arr[i]; //以L开始到R的每段子段和
result += sum; //累加所有子段，这里先求了，再加上
}
}
2.使用前缀和优化，每次求包含arr[L]开始的所有异或子段，再累加求和。时间复杂度O(n^2)：
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for(int i = 0 ; i < n; i++)arr[i] = sc.nextInt();
long result = 0;
for(int L = 0 ; L < n ; L++) { //求前缀和
long sum = 0;
for(int R = L; R < n ; R++) { //包含arr[L]的所有异或子段和
sum ^= arr[R]; //求当前子段异或前缀和
result += sum; //累加所有子段和，注意是在最里面
}
}
3.进一步优化(待补充)
P2004 领地选择
前缀和递推公式:sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+arr[i][j]
计算 i,j 到 x2,y2 指定区域的大小：map[x2][y2] - map[x2][j-1] - map[i-1][y2] + map[i-1][j-1]
计算指定区域的和
void print_sum()//计算某个区域和 (x1,y1)到(x2,y2)的和
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if(x1==0 && y1==0)
printf("%d\n",sum[x2][y2]);
else if(x1==0)
printf("%d\n",sum[x2][y2]-sum[x2][y1-1]);
else if(y1==0)
printf("%d\n",sum[x2][y2]-sum[x1-1][y2]);
else
printf("%d\n",sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]);
}
解题思路 1.枚举每个可能位置的和，比较得到结果。时间复杂度O(n^4)
int x,y,result;
x = y = 0;result =Integer.MIN_VALUE ;
// 只遍历有效范围
for (int i = 0; i <= N - C; i++) {
for (int j = 0; j <= M - C; j++) {
int currentSum = 0;
// 计算C×C区域的和
for (int dx = 0; dx < C; dx++) {
for (int dy = 0; dy < C; dy++) {
currentSum += map[i + dx][j + dy];
}
}
if (currentSum > result) {
result = currentSum;
x = i;
y = j;
}
}
}
System.out.println((x + 1) + " " + (y + 1)); // 若题目坐标从1开始则+1
2.二维前缀和，得到每一块的和，比较得到结果，时间复杂度O(n^2)
//这里把map数组直接用作了前缀和数组，没有开辟额外空间
int[][] map = new int[N + 1][M + 1];
for(int i = 1 ; i <= N ; i++) {
for(int j = 1 ; j <= M ; j++) {
map[i][j] = sc.nextInt();
map[i][j] = map[i-1][j] + map[i][j-1] - map[i-1][j-1] + map[i][j];
//相当于: sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+arr[i][j]
}
}
int x,y,result;
x = y = 0;result =Integer.MIN_VALUE ;
// 只遍历有效范围
for (int i = 1; i <= N - C + 1; i++) {
for (int j = 1; j <= M - C + 1; j++) {
int x2 = i + C - 1;
int y2 = j + C - 1;
//右下角坐标
int cur = map[x2][y2] - map[x2][j-1] - map[i-1][y2] + map[i-1][j-1];
if(cur > result) {
result = cur;
x = i;
y = j;
}
}
}
System.out.println(x + " " + y );
差分
差分数组主要用于高效处理区间更新和范围查询问题，特别适用于需要多次对数组的连续区间进行统一增减操作，且最终需要获取操作后的结果或统计信息的场景。以下是其核心应用类型及优势：
一、适用问题类型
区间批量增减操作
- 场景：对数组的某个区间
[L, R]内的所有元素同时增加或减少一个值。- 示例：
- 给数组
[1, 2, 3, 4, 5]的区间[2, 4]每个元素加 3，结果变为[1, 2, 6, 7, 8]。- 使用差分数组可将多次此类操作的时间复杂度从
O(n)优化到O(1)。统计区间覆盖次数
- 场景：统计每个位置被多个区间覆盖的总次数。
- 示例：
- 障碍物缺口问题中，统计每个高度位置被所有列的缺口覆盖的次数，以计算最少需清理的面积。
动态范围查询优化
- 场景：在多次更新后，快速回答“某个元素的值是多少”或“某段区间的和是多少”。
- 示例：
- 航班座位预订系统，每次预订从座位
L到R，需要快速查询每个座位被预订的次数。二、差分数组的核心原理
定义
- 差分数组
d与原数组arr的关系：
\[ > ==d[i] = arr[i] - arr[i-1] ({其中 } arr[-1] = 0)== > \]- 通过差分数组的前缀和可还原原数组：
\[ > ==arr[i] = arr[i - 1] + d[i]== > \]区间更新操作
- 对区间
[L, R]增加k的操作，只需修改差分数组的两处：
\[ > d[L] += k, d[R+1] -= k > \]- 例如，对区间
[2,4]加 3，只需：d[2] += 3; d[5] -= 3; // 假设数组足够大三、优势与复杂度分析
时间复杂度
- 单次区间操作：
O(1)（仅修改差分数组的两个端点）。- 还原原数组：
O(n)（通过一次前缀和计算）。- 总复杂度：处理
m次区间操作的总时间为O(m + n)，远优于暴力法的O(mn)。空间复杂度
- 仅需额外
O(n)空间存储差分数组。
重新排序
解题思路 通过统计查询区间时，各个元素的出现次数，再应用排序不等式，进行排序，得到新的结果，从而得到答案。
代码实现 时间复杂度O(mn)
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n+1];
int[] cnt = new int[n+1]; //第i个数被加的次数
for(int i = 1 ; i <=n; i++)arr[i] = sc.nextInt();
long res1 = 0, res2 = 0; //ans1:原区间和 ans2：新区间和
int m = sc.nextInt();
while(m-- > 0) {
int L = sc.nextInt();
int R = sc.nextInt();
for(int i = L ; i <= R; i++) {
cnt[i]++; //第i个数被加了一次，累计一共加了多少次
}
}
for(int i = 1; i<=n ; i++) {
res1 += (long)arr[i]*cnt[i]; //在原数组上求区间和
}
Arrays.sort(arr, 1, n+1);
Arrays.sort(cnt, 1, n+1);
for(int i = 1 ; i<=n ; i++) {
res2 += (long)arr[i]*cnt[i]; //在新排序数组上求区间和
}
System.out.println(res2 - res1);
}
优化 每次查询[L,R]就是对arr[L] ~ arr[R]中所有数的累加次数加一，也就是对cnt[L]~cnt[R]中的所有cnt[]加1。对cnt[]数组使用差分数组d[]即可。
时间复杂度O（nlog2n）
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = 1000003;
int n = sc.nextInt();
int[] arr = new int[N];
int[] cnt = new int[N]; //第i个数被加的次数
int[] d= new int[N];
for(int i = 1 ; i <=n; i++)arr[i] = sc.nextInt();
long res1 = 0, res2 = 0; //ans1:原区间和 ans2：新区间和
int m = sc.nextInt();
while(m-- > 0) {
int L = sc.nextInt();
int R = sc.nextInt();
d[L]++; //表示从位置 L 开始，每个元素的值比前一个元素多 1。
d[R+1]--; //表示从位置 R+1 开始，每个元素的值比前一个元素少 1（抵消前面的增加）。
}
cnt[0] = d[0];
for(int i = 1 ; i<= n; i++) {
cnt[i] = cnt[i-1] + d[i]; //用差分数组d[] 求 cnt[]； 区间 [L, R] 内的所有位置会被加 1，而区间外的位置保持不变
}
for(int i = 1; i<=n ; i++) {
res1 += (long)arr[i]*cnt[i]; //在原数组上求区间和
}
Arrays.sort(arr, 1, n+1); //排序不等式：当两个数组均为升序时，对应元素乘积之和最大。
Arrays.sort(cnt, 1, n+1);
for(int i = 1 ; i<=n ; i++) {
res2 += (long)arr[i]*cnt[i]; //在新排序数组上求区间和
}
System.out.println(res2 - res1);
}
推箱子
解题思路
使用arr数组记录每行的空位置，看哪连续H行的空位置最多。例如题目样例，arr[]数组为 0, 2, 5, 3, 0 , H为2， 空位最多的连续H行为5,3。5 + 3 = 8。 需要移除的最少障碍物数量: N * H - 8 = 2。
暴力解法 直接从左到右依次对H个整数进行求和，或是直接按列进行统计得到结果。时间复杂度为O（NH），超时。
差分优化 使用差分数组记录每个缺口区间的长度，再还原成arr[]数组。之后再进行计算比较。
为什么arr[i] = arr[i-1] + d[i-1]
在代码中，差分数组
d的索引与障碍物的高度位置（从0开始）直接对应，而arr数组的索引设计为从1开始，每个arr[i]对应高度i-1的覆盖次数。因此：差分操作的意义
d[L]++和d[R+1]--标记了高度区间[L, R]的覆盖次数变化。- 例如，缺口
L=2, R=3对应d[2]++和d[4]--，表示高度2和3的覆盖次数增加1。前缀和还原逻辑
arr[i] = arr[i-1] + d[i-1]是因为：
arr[i]表示高度i-1的总覆盖次数。- 通过累加
d[0]到d[i-1]的差分值，得到高度i-1的覆盖次数。索引对齐示例
- 当
i=3时，arr[3]对应高度2，需要加上d[2]（即d[i-1]）来反映该高度的覆盖次数。模拟样例验证 以输入样例为例，处理完所有列的差分后：
- 高度2的覆盖次数为
3（被3列覆盖）。- 通过
arr[3] = arr[2] + d[2] = 2 + 3 = 5正确反映。最终通过滑动窗口找到最大覆盖和
8，计算最小清理面积5*2 -8 = 2，与样例一致。使用
arr[i] = arr[i-1] + d[i-1]是为了正确对齐差分数组索引与实际高度位置，确保每个arr[i]对应高度i-1的覆盖次数。这是索引设计（1-based数组 vs 0-based高度）的必然要求。
代码实现、
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = 1000010;
int n = sc.nextInt();
int h = sc.nextInt();
long[] arr = new long[N];
long[] d = new long[N];
long[] sum = new long[N];
for(int i = 1 ; i <= n; i++) {
int L = sc.nextInt();
int R = sc.nextInt();
d[L]++;
d[R+1]--; //差分数组记录
}
for(int i = 1; i<=n ; i++) {
arr[i] = arr[i-1] + d[i - 1]; //计算原数组
}
for(int i = 1 ; i<=n ; i++) {
sum[i] = sum[i-1] + arr[i];//用原数组计算前缀和数组
}
long result = sum[h-1];//第一个h区间
for(int left = 1; left + h - 1 <= n ; left++) {
result = Math.max(result, sum[left + h - 1] - sum[left - 1]);
}
System.out.println((long)n * h - result);
}
棋盘
核心模板
==修改指定区间的d[][]:==
d[x1][y1]++;
d[x1][y2+1]--;
d[x2+1][y1]--;
d[x2+1][y2+1]++;
==使用d[][]还原arr[][]数组:==
arr[i][j] = d[i][j] + arr[i-1][j] + arr[i][j-1] - arr[i-1][j-1];
解题思路 1.模拟,三重for循环，时间复杂度o(n^3)
- 每次操作的时候使用for循环改变指定范围内的数
- 最后统计，得到结果
int n = sc.nextInt();
int m = sc.nextInt();
int[][] arr = new int[n][n];
for(int i = 0 ; i < m ; i++) {
int x1 = sc.nextInt() - 1;
int y1 = sc.nextInt() - 1;
int x2 = sc.nextInt();
int y2 = sc.nextInt();
for(int j = x1; j < x2; j++) { //统计当前棋盘位置状态
for(int k = y1; k < y2; k++) {
arr[j][k]++;
}
}
}
for(int i = 0 ; i< n; i++) {
for(int j = 0 ; j< n ; j++) {
System.out.print(arr[i][j] & 1); //使用按位与判断奇偶，效率比用%的方式高
}
System.out.println();
}
2.使用二维差分,时间复杂度o(n^2)
- 每次操作直接使用二维差分增加区间大小
- 结果使用按位与判断奇偶，奇数为1，偶数为0 (位与：用来判断奇偶数)
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] arr = new int[n+2][n+2];
int[][] d = new int[n+2][n+2];
for(int i = 0 ; i < m ; i++) {
int x1 = sc.nextInt();
int y1 = sc.nextInt();
int x2 = sc.nextInt();
int y2 = sc.nextInt();
d[x1][y1]++; //二维差分数组记录
d[x1][y2+1]--;
d[x2+1][y1]--;
d[x2][y2]++;
}
//还原arr数组
for(int i = 1 ; i<=n; i++) {
for(int j = 1 ; j<=n ; j++) {
arr[i][j] = d[i][j] + arr[i-1][j] + arr[i][j-1] - arr[i-1][j-1];
System.out.print(arr[i][j] & 1); //使用按位与判断奇偶，效率比用%的方式高
}
System.out.println();
}
二分
求阶乘
解题思路 尾数0是由因子2*5得到的，由于因子2的数量肯定大于因子5，所以只需要统计阶乘里因子5的数量，就等于统计了此时尾数为0的数量。
暴力解法
- 从头开始计算尾数为0的数，直到算到尾数为0==k时，找到答案。
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long k = sc.nextLong();
for(int i = 5;;i += 5) {
long cnt = check(i);
if(cnt == k) {
System.out.println(i);
break;
}
if(cnt > k) {
System.out.println(-1);
break;
}
}
}
public static long check(long n) { //计算n有几个尾数0
long cnt = 0;
while(n > 0) {
cnt += n / 5; //就是计算n有几个因子5
n /= 5;
}
return cnt;
}
二分查找优化
- 每次找mid值的尾数0的个数，与k进行比较;根据比较结果缩小范围，直到找到合适的结果。
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long k = sc.nextLong();
long l = 0;
long r = Long.MAX_VALUE;
while(l < r) {
long mid = (l + r) >> 1; //找到mid
if(check(mid) >= k) { //说明当前mid尾数0个数大于k
l = mid; //缩小范围到左边
}else {
r = mid + 1; //缩小范围到右边
}
}
if(check(r) == k) {
System.out.println(r);
}else {
System.out.println(-1);
}
}
public static long check(long n) { //计算n有几个尾数0
long cnt = 0;
while(n > 0) {
cnt += n / 5; //就是计算n有几个因子5
n /= 5;
}
return cnt;
}
青蛙过河
解题思路 每次往返需要消耗石头的总高度至少为2x次（去和回各x次）。跳跃能力y决定了小青蛙每次能跨越的最大距离，因此需要确保任意连续y长度的区间内石头高度总和≥2x，否则无法支撑足够次数。
1.使用前缀和存储前i个位置的石头高度总和
2.对于任意区间[i, i+y-1]，其总和为sum[i+y-1] - sum[i-1],不能超过最后一个石头的位置n-1（河对岸的位置n不需要石头
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int x = sc.nextInt();
int[] arr = new int[n];
int[] sum = new int[n];
for(int i = 1 ; i < n; i++) {
arr[i] = sc.nextInt();
sum[i] += sum[i-1]+arr[i];
}
int l = 1;
int r = n;
while(l < r) {
int mid = (l + r) >> 1;
if(check(sum,mid,x)) {
r = mid;
}else {
l = mid+1; // mid不可行，必须增大
}
}
System.out.println(l);
}
public static boolean check(int[] sum, int mid, int x) {
for(int i = 1; i < sum.length - mid + 1 ; i++) { //以当前mid跳跃能力，能跳的次数
if(sum[i + mid - 1] - sum[i - 1] < 2 * x) {//这个区间的高度>=2x,说明石头足够支撑跳完
// i + mid - 1 ：不能超过最后一个石头的位置n-1（河对岸的位置n不需要石头
return false; // 存在不满足的区间
}
}
return true;
}
贪心
部分背包问题
解题思路 算出每堆单个金币价值，按价值大小对金币堆进行排序。按价值大小顺序选金币堆里的金币，直到背包装满。
代码实现
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int t = sc.nextInt();
Gold[] list = new Gold[n];
for(int i = 0 ;i < n; i++) {
double m = sc.nextInt();
double v = sc.nextInt();
double p = v/ m;
list[i] = new Gold();
list[i].m = m;
list[i].v = v;
list[i].p = p;
}
Arrays.sort(list, (o1,o2)->Double.compare(o2.p, o1.p)); //按价值对金币堆进行排序
double result = 0;
for(int i = 0 ; i< list.length; i++) {
if(t <= 0)break;
double m = list[i].m;
double p = list[i].p;
for(int j = 0 ; j < m ; j++) {
if(t <= 0)break;
result += p;
t -= 1;
}
}
System.out.printf("%.2f",result);
}
static class Gold { //写类实现金币堆
double m ;
double v;
double p;
}
线段覆盖
解题思路 要求的是不相交区间的最大个数
不相交区间问题
1.设法按照最短的时间段进行排序，如果当前时间段的左区间小于之前时间段的右区间，肯定不符合要求。
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
List<int[]> list = new ArrayList<>();
for(int i = 0 ;i < n; i++) {
int begin = sc.nextInt();
int end = sc.nextInt();
list.add(new int[] {begin, end});
}
//按最小时间段排序
Collections.sort(list, (o1,o2) -> o1[0] - o2[0]);
Collections.sort(list, (o1,o2) -> o1[1] - o2[1]);
int result = 1;
int[] pre = list.get(0);
boolean flag = false;
int mark = 0;
for(int i = 1 ; i < n; i++) {
int[] cur = list.get(i);
if(flag) {
pre = list.get(mark); //更新之前的时间段
}
if(pre[1] <= cur[0]) {
result++;
flag = true;
mark = i;
}else {
flag = false;
}
}
System.out.println(result);
2.直接按右端点排序，如果当前左区间大于等于之前右区间，符合要求。
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
List<int[]> list = new ArrayList<>();
for(int i = 0 ;i < n; i++) {
int begin = sc.nextInt();
int end = sc.nextInt();
list.add(new int[] {begin, end});
}
//按右端点排序
Collections.sort(list, (o1,o2) -> o1[1] - o2[1]);
int result = 1;
int[] pre = list.get(0);
for(int i = 1 ; i < n; i++) {
int[] cur = list.get(i);
if(pre[1] <= cur[0]) {
result++;
pre = list.get(i);//更新当前pre
}
}
System.out.println(result);
区间覆盖
解题思路
区间合并问题
1.按左端点排序，这样就从最小位置的端点依次往后比较
2.判断： 1.如果当前区间的右端点大于等于之前区间的右端点，这样就包含了区间相交的情况 2.比较当前区间左端点和之前区间右端点，这样就避免了重复计算覆盖范围
代码实现
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Data[] a = new Data[n];
for(int i = 0 ;i < n; i++) {
long begin = sc.nextInt();
long end = sc.nextInt();
a[i] = new Data();
a[i].l = begin;
a[i].r = end;
}
//按左端点排序
Arrays.sort(a, (o1,o2) -> Long.compare(o1.l, o2.l));
int result = 0;
long mark = -1;
for(int i = 0 ; i < n; i++) {
if(a[i].r >= mark) {
result += a[i].r - Math.max(mark, a[i].l) + 1;//得到区间长度，加入,避免重复计算
mark = a[i].r + 1; //更新右端点
}
}
System.out.println(result);
}
static class Data{
long l;
long r;
}
填充
解题思路 要求00,11尽可能的多，可以分为下面四种判断情况
字符串看做str[]
1.如果
str.charAt(i) == str.charAt(i+1): 可能是00,11或者??,可以当做一个符合要求的子串进行统计，下次从i+2. i+3开始。2.如果
str.charAt(i) 或 str.charAt(i+1) == '?': 可能是0?,?0,1?,?1可以看做一个答案进行统计，下次从i+2, i+3开始3.如果
str.charAt(i) == '1' , str.charAt(i+1) == '0'或者str.charAt(i) == '0' , str.charAt(i+1) == '1'：不符合要求，下次从i+1. i+2开始，防止漏掉符合要求的子串
代码实现
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
int result = 0;
for(int i = 0 ; i < str.length() - 1; i++) {
//只需要计算第1，2种情况即可
if(str.charAt(i) == str.charAt(i + 1) || str.charAt(i) == '?' || str.charAt(i + 1) == '?') {
result++;
i++;
}
}
System.out.println(result);
}
买二赠一
解题思路 贪心，按照商品价值从大到小查找，每购买标记两个商品，得到一个免费的数值，进一步在数组中查找，把符合免费领取的商品做标记，防止重复查找。如此循环直到结束。
代码实现 1.双层for循环，时间复杂度高
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
//实现倒序需要使用包装类
Integer[] prices = new Integer[n];
boolean[] check = new boolean[n];
for(int i = 0 ; i < n; i++) {
prices[i] = sc.nextInt();
}
Arrays.sort(prices, (o1,o2) -> o2-o1);
int result = 0;
int free = 0;
int count = 0;
for(int i = 0; i< prices.length; i++) {
if(!check[i]) {
count++;
result += prices[i];
check[i] = true;
if(count == 2) {
free = prices[i] / 2;
count = 0;
for(int j = 0; j < prices.length; j++) {
if(!check[j] && prices[j] <= free) {
check[j] = true;
break;
}
}
}
}
}
System.out.println(result);
}
2.使用二分查找
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Integer[] prices = new Integer[n];
boolean[] check = new boolean[n];
for(int i = 0 ; i < n; i++) {
prices[i] = sc.nextInt();
}
Arrays.sort(prices);
long res = 0; //注意需要用long
int cnt = 0;
int last = -1;//用于得到免费额度
int last_index = n-1;//用于找到正确的能免费购买商品的索引
for(int i = n - 1 ; i >= 0; i--) {
if(!check[i]) {
cnt++;
res += prices[i];
last = prices[i];
}
if(cnt == 2) {
cnt = 0;
int x = lowerBound(prices, 0, last_index, last / 2); //得到正确的索引
if(x > last_index || prices[x] > last / 2)x--; //不符合要求，说明在前一个
if(x >= 0) {
check[x] = true; //找到了正确的位置
last_index = x - 1;
}
}
}
System.out.println(res);
}
public static int lowerBound(Integer[] a, int l_index, int r_index, int target) {
while(l_index < r_index) {
int mid = l_index + (r_index - l_index) / 2;
if(a[mid] >= target) {
r_index = mid;
}else {
l_index = mid + 1;
}
}
return l_index;
}
购物
解题思路 已经能组合出1~s的面值，如何拓展到s+1？
在s 的基础上加一个面值为v的硬币,可以选1 - s+1。如：v = 1, s+1 = s+v… v = s+1, s+1 = v。
v 的取值范围是1 - s+1, 为了最大拓展，选v为1 - s+1 内的最大硬币，此时 s 扩展到 s+v.
代码实现
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int x = sc.nextInt();
int n = sc.nextInt();
int[] coins = new int[n];
for(int i = 0 ; i < n; i++) {
coins[i] = sc.nextInt();
}
Arrays.sort(coins);
if(coins[0]!= 1) { //没有为1的硬币，组合不到1
System.out.println(-1);
return;
}
int s = 0; //表示当前能组合出的面值
int res = 0;
while(s < x) { //s >= x，说明已经能拓展到x
for(int v = n - 1; v >= 0; v--) { //用于拓展可以组合出的面值
if(coins[v] <= s + 1) {//在 1 - s+1的范围内，取最大值拓展s的范围
s += coins[v];
res++;
break;
}
}
}
System.out.println(res);
}
牛奶优惠券
解题思路 什么是最优解？
按优惠价排序，买优惠价最便宜的 ×： 优惠价最便宜不代表优惠力度最大
改进： 把优惠卷转移到优惠力度更大的牛上，看看能不能获得更大的优惠
- 假设反悔之前：第i只牛用原价p1买，前面第j只牛用优惠卷cj买，共花费tot + pi + cj, tot是购买其他牛的花费
- 反悔后：把买第j只牛的优惠券转移给第i件，改成原价pj,第i只牛用优惠价ci,共花费tot + cj + pj, ==如果反悔更好，则有 tot + pi + cj < tot + cj + pi， 有 pj - cj < pi - ci==, p - c为原价和优惠价之间的差额。
改进后的问题: 可能导致超过总花费。转移优惠卷之后超过了总价。所以只是比较差额来选择是否用优惠卷买不行。
最终改进，如何选才能最优惠: 1.用原价买，应该是牛中的最低原价 2.用优惠券买，应该是牛中的最低优惠价
代码实现时，维护三个优先队列，分别保存原价p，优惠价c，以及折扣d（用于转移）
1.先用完k个优惠卷，从c中选择连续k个最便宜的 2.优惠券替换：从p中取出原价最便宜的p1,从c中取出优惠价最便宜的c2,从d中取出优惠幅度最小的d
- 1).若d > p1 - c2, 说明替换优惠券不值得，不用替换。下一件衣服原价买
- 2.）若d <= p1 - c2,说明替换优惠券值得，下一件衣服用优惠价c2买，原来用优惠价的改回原价。
代码实现
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
long m = sc.nextLong();
int[] p = new int[n+1];
int[] c = new int[n+1];
//存储衣服原价的优先队列，升序排序
PriorityQueue<int[]> P = new PriorityQueue<>((a,b) -> a[0] - b[0]);
//存储衣服优惠价的优先队列，升序排序
PriorityQueue<int[]> C = new PriorityQueue<>((a,b) -> a[0] - b[0]);
PriorityQueue<Integer> D = new PriorityQueue<>(); //用于存储转移的优惠力度，默认都为0
boolean[] buy = new boolean[n+1];
for(int i = 0 ; i < k ; i++) {
D.add(0);
}
for(int i = 1; i<= n; i++) {
p[i] = sc.nextInt();
c[i] = sc.nextInt();
P.add(new int[] {p[i],i});
C.add(new int[] {c[i],i});
}
long ans = 0;
while(!P.isEmpty() && !C.isEmpty()) {
int[] p1 = P.peek(); //取出原价最便宜的，包括价值和对应索引
int[] c2 = C.peek(); //取出打折价最便宜的，包括价值和对应索引
//已经买过，跳过
if(buy[p1[1]]) {
P.poll();
continue;
}
if(buy[c2[1]]) {
C.poll();
continue;
}
if(D.peek() > p1[0] - c2[0]) { //替换优惠券不值得，用原价买
m -= p1[0];
P.poll();
buy[p1[1]] = true;
}else { //替换优惠券
m -= c2[0] + D.peek(); //这里加上了之前替换后应该加上的价格
C.poll();
buy[c2[1]] = true;
D.poll(); //原来的优惠差价退出
D.add(p[c2[1]] - c[c2[1]]); //用于下次加上转移后，应当用原价买的差价
}
if(m >= 0)ans++; //说明能买牛
else break;
}
System.out.println(ans);
}
食堂
解题思路 贪心思路，最大化利用6人桌和4人桌
代码实现
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
int q = scan.nextInt();
while(q!=0){
q--;
int a2=scan.nextInt();
int a3=scan.nextInt();
int a4=scan.nextInt();
int b4=scan.nextInt();
int b6=scan.nextInt();
int sum=0;
//分配6桌分配给3人寝室,3人寝为奇数时剩下一个；若(2*b6>a3)6人桌剩余，a3为0或1；若(2*b6<a3)前3人寝室剩余,b6==0;
while(a3>1 && b6>0){
a3-=2;b6--;sum+=6;
}
//将剩余的6人桌拆分给2人寝室，剩下的当作4人桌；若(b6>a2)6人桌剩余,a2为0；若(b6<a2)2人寝室剩余,b6==0;
while(a2>0 && b6>0){
a2--;b6--;b4++;sum+=2;
}
//若6人桌还有剩余，分给4人寝室；若(b6>a4)6人桌剩余，a4为0；若(b6<a4),b6==0;
while(a4>0 && b6 > 0){
a4--;b6--;sum+=4;
}
//若6人桌还有剩余，分给可能剩余一个的a3,则所有寝室分完，结束
while(b6>0 && a3>0){
b6--;a3--;sum+=3;
}
//将4人桌分给4人寝室;若(b4>a4)4人桌剩余，a4==0;(b4<a4)4人寝室剩余,b4==0，没桌子，结束;
while(a4>0 && b4>0){
a4--;b4--;sum+=4;
}
//将剩余的4人桌分给2人寝,当2人寝室为奇数时剩下一个;若(2*b4>a2)4人桌剩余,a2为1或0;若(2*b4<a2)2人寝剩余,没桌子，结束
while(a2>1 && b4>0){
a2-=2;b4--;sum+=4;
}
//将剩余的4人桌子分给剩余的3人寝室;若(b4>a3)4人桌剩余a3==0;若(b4<a3)3人寝室剩余，没桌子，结束
while(a3>0 && b4>0){
a3--;b4--;sum+=3;
}
//将剩余的4人桌分给可能剩余的a2;a2==0,分配完毕
while(b4>0 && a2>0){
b4--;a2--;sum+=2;
}
System.out.println(sum);
}
scan.close();
}
}
DFS
全排列
解题思路 注意场宽为5，注意内存优化
代码实现
static int n;
static boolean[] vis;
static int[] b;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n =sc.nextInt();
vis = new boolean[10];
b = new int[10];
dfs(1);
}
public static void dfs(int depth) {
if (depth == n + 1) {
for(int i = 1; i <=n ; i++) {
System.out.printf("%5d",b[i]);
}
System.out.println();
return;
}
for (int i = 1; i <= n; i++) {
if(!vis[i]) {
b[depth] = i;
vis[i] = true;
dfs(depth + 1);
vis[i] = false;
}
}
}
最大连通
解题思路 DFS, BFS
代码实现
//dfs
static int result = 0;
static int[][] move = new int[][] {{0,0,1,-1},{1,-1,0,0}};
// 递归DFS计算连通块大小
private static int dfs(int[][] matrix, int i, int j) {
// 边界检查或非1位置直接返回0
if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length || matrix[i][j] != 1) {
return 0;
}
// 标记当前节点为已访问
matrix[i][j] = 0;
int count = 1; // 当前节点贡献1个计数
// 递归四个方向并累加结果
for (int k = 0; k < 4; k++) {
int newI = i + move[0][k];
int newJ = j + move[1][k];
count += dfs(matrix, newI, newJ);
}
return count;
}
//bfs
private static int bfs(int[][] matrix, int i, int j) {
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{i, j});
matrix[i][j] = 0; // 标记为已访问
int size = 0;
while (!queue.isEmpty()) {
int[] current = queue.poll();
size++;
for (int[] dir : DIRECTIONS) {
int newI = current[0] + dir[0];
int newJ = current[1] + dir[1];
if (newI >= 0 && newI < ROWS && newJ >= 0 && newJ < COLS && matrix[newI][newJ] == 1) {
queue.offer(new int[]{newI, newJ});
matrix[newI][newJ] = 0; // 标记为已访问
}
}
}
return size;
}
数的划分
解题思路 简化划分过程，让k个数从小到大进行
- 第一个数字：1
- 第二个数字: 大于或等于第一个数，最大不能超过
(n - 1) / (k - 1),设第二个数是x - 第三个数字: 大于或等于第二个数，最大不能超过
(n - 1 - x) / (k - 2) - 继续上面划分过程，直到划分了k个数，和为n,就是一个符合要求的答案
代码实现
static int n,k,count;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
k = scan.nextInt();
dfs(1, 0, 0);
System.out.println(count);
}
public static void dfs(int x, int sum, int u) {
if(u == k) { //已经分成了k个数
if(sum == n)count++; //k个数加起来等于n,说明找到一个解
return;
}
for(int i =x; sum + i * (k - u) <= n; i++) {
//剪枝， i的最大值不超过(n - sum)/(k - u)
dfs(x, sum + i, u + 1);
}
}
有奖问答
解题思路 DFS爆搜，注意终止条件和单层的逻辑先后顺序
代码实现
static int res = 0;
public static void main(String[] args) {
dfs(0, 0, 0);
System.out.println(res);
}
public static void dfs(int score, int count, int statue) {
if(statue == 1) { //当前是错还是对
score += 10;
if(score == 100) //达到100，直接返回
return;
}else {
score = 0;
}
if(score == 70) { //达到70，一种可能
res++;
}
if(count == 30)return; //达到题目总数（注意是从0开始，30，包含第一道题的两种情况），返回
for(int i =0; i < 2; i ++) { //每道题两种情况
dfs(score, count + 1, i);
}
}
最大数字
解题思路 1.使用贪心思路依次处理N的每一位，先把最高位尽量变成最大的数字，再把次高位尽量变成最大的数字 2.操作1和操作2不能混用，因为会互相抵消 3.如何让最高位尽量变大，设最高位数为d:
- 先进行1操作，取操作次数t=math.min(A, 9-d):9-d表示能取到9所需的操作次数，如果操作A次到不了9，就取A次。
- 再再进行2操作，因为是减1，所以只有能变成9才有意义。在B > d的情况下，操作d + 1次变为9。
代码实现 舍弃了for循环，用空间换时间。
static long A,B;
static String s;
static long ans = 0; //注意使用long
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
s = scan.next();
A = scan.nextLong();
B = scan.nextLong();
dfs(0, A, B, 0);
System.out.println(ans);
}
//i :当前位数 v: 当前的已经得到的值
public static void dfs(int i, long A, long B, long v) {
if( i < s.length()) {
long x = (long)(s.charAt(i) - '0'); // 第i位的数字
long t = Math.min(A, 9 - x); //能一号操作的次数， 9-x小，说明能操作到9, 不到的话就改为操作A次
dfs(i + 1, A - t, B, v * 10l + x + t); //一号操作
if(B > x) {
dfs(i + 1, A, B - x - 1l, v * 10L + 9);///B > x，操作x + 1 次才能得到9
//二号操作
}
}else {
ans = Math.max(ans, v);
}
}
}
使用for循环，时间复杂度更高
public static void dfs(int i, long A, long B, long v) {
if(i >= s.length()) {
ans = Math.max(ans, v);
return;
}
for(int k =i ; k < s.length(); k++) {
long x = (long)(s.charAt(k) - '0'); // 第i位的数字
long t = Math.min(A, 9 - x); //能一号操作的次数， 9-x小，说明能操作到9, 不到的话就改为操作A次
dfs(k + 1, A - t, B, v * 10l + x + t); //一号操作
if(B > x) {
dfs(k + 1, A, B - x - 1l, v * 10L + 9);///B > x，操作x + 1 次才能得到9
//二号操作
}
}
生日蛋糕
解题思路 设最上面一层是第1层,最下面一层是第m层。从第m层开始DFS。用函数dfs(k.r,h,s,v)枚举所有层,当前处理到第k层第k层的半径为r、高度为h,s是最底层到第k层的上表面面积,是最底层到第k层的体积;并预处理数组sk[]、v[],sk[i]表示第1 ~ i层的最小侧面积、vk[i]表示第1~i层的最小体积。
①最优性剪枝
- 1:面积。记录已经得到的最小面积ans,如果在DFS中得到的面积大于ans,返回。当前处理到第k层,第k层的半径是r。第k层的体积是n-v=rh^2,得h=(n-v)/r^2;第k层的侧面积sc=2rh=2r(n-v)/r^2=2(n-v)/r。剪枝判断:若sc+s=2(n-v)/r+s>=ans,返回。
②可行性剪枝
- 2:体积。如果当前已经遍历的各层的体积之和大于题目给定的体积返回。剪枝判断:若v+vk[k一1]>n,返回。
③可行性剪枝
- 3:半径和高度。在枚举每一层的半径i和高度j时,应该比下面一层半径和高度小。第k-1层的体积是i^2 * h,它不能超过n-v-vk[k-1],由i^2 * h ≤ n-vk[k-1]得 h ≤ (n-v-vk[k一1])/i^2。剪枝判断:高度j应该小于(n-v-vk[k一1])/ i ^ 2
代码实现
static int sk[]; //1~i层最小侧面积
static int vk[]; //1~i层最小体积
static int n,m;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
sk = new int[m+1];
vk = new int[m+1];
sk[0] = 0;
vk[0] = 0;
for(int i = 1; i <= m; i++) { //初始化表面积，体积为最小值
sk[i] = sk[i-1] + 2 * i * i; //1~i层：侧面积最小值
vk[i] = vk[i - 1] + i * i * i; //1~i层。体积最小值
}
dfs(m, n, n, 0, 0);
if(ans == Integer.MAX_VALUE)System.out.println(0);
else System.out.println(ans);
}
//层，半径，高度，上表面总面积， 体积
public static void dfs(int k, int r, int h, int s, int v) {
int max_h = h;
if(k == 0) { //蛋糕做完了
if(v == n)ans = Math.min(ans, s); //更新表面积
return;
}
if(v + vk[k-1] > n)return; //体积大于n, 退出，剪枝2
if(2*(n - v) / r + s >= ans) { //侧面积+ 上面总面积大于ans, 退出，剪枝1
return;
}
for(int i = r - 1; i >=k; i--) {
//枚举k-1层的半径i, i比下一层的半径小，剪枝3
if(k == m)s = i * i; // 表面总面积
max_h = Math.min(h - 1, (n - vk[k-1] - v)/ i / i); //第 k - 1 层的最大高度
for(int j = max_h ;j >=k; j--) {
dfs(k - 1, i, j, s + 2 * i * j, v + i * i * j);
}
}
}
最长距离
dfs搜索所有路径 解题思路 对每个位置进行dfs,得到从节点(i , j)开始的连通情况，从而得到距离。得到所有距离，从中选出最大值就是答案。
因为每个位置都要进行一遍dfs,所以用来判断距离和检查是否已走过的数组每次都要置为初始值，另外每次dfs结束后都要立刻进行比较
代码实现
static int n, m, t;
static int[][] a;
static int[][] dis; //dis[x][y] 代表起点到 (x,y)的最短路径（最少障碍物数量）
static int[][] vis; //vis[x][y] = 1, 坐标(x,y)已经走过，不能再走
static int[][] dxy = new int[][] {{0,0,1,-1},{1,-1,0,0}};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
t = sc.nextInt();
sc.nextLine();
a = new int[n+1][m+1];
dis = new int[n+1][m+1];
vis = new int[n+1][m+1];
for(int i = 1; i <= n; i++) { //初始化地图
String line = sc.next();
for(int j = 1; j <=m; j++) {
char ch = line.charAt(j - 1);
a[i][j] = ch - '0';
}
}
int ans = 0;
for(int i = 1; i <=n; i++) {
for(int j = 1; j<=m; j++) {
//对每个节点，都要重新初始化一遍，得到正确的结果
for(int[] row: dis) {
Arrays.fill(row, Integer.MAX_VALUE);
}
for(int[]row: vis) {
Arrays.fill(row, 0);
}
int cnt = a[i][j] == 1? 1:0; //初始化障碍物数量
dfs(i, j, cnt);
for(int x = 1; x <=n ; x++) {
for(int y = 1; y <= m; y++) {
if(dis[x][y] <= t) //当前障碍物数量少于t，说明可以走到，算距离
//距离取最大的
ans = Math.max(ans, (x - i) * (x - i) + (y - j) * (y - j));
}
}
}
}
System.out.printf("%.6f",Math.sqrt(ans));
}
public static void dfs(int x, int y, int cnt) {
//走到(x,y), 已经走过的路径长度为cnt（障碍物数量）
if(cnt > t)return; //已经移走了t个障碍物，不能再移了
if(cnt > dis[x][y])return; //当前cnt比之前保存的最短路径长,不符合要求
dis[x][y] = cnt;
for(int i =0; i < 4; i++) {
int nx = x + dxy[0][i];
int ny = y + dxy[1][i];
if(nx > n || nx < 1 || ny > m || ny < 1)continue; //判断越界
if(vis[nx][ny] == 1)continue; //这个点已经走过
vis[nx][ny] = 1;
dfs(nx, ny, cnt + a[nx][ny]);
vis[nx][ny] = 0;
}
}
小木棍
解题思路 猜原始木棍的长度是L，然后测试n个小木棍能否拼出k = sum/L 根原始木棍。
模拟拼木棍的过程: 在n个小木棍中选几个，拼第一个L。可以用DFS求全排列的方法选小木棍。
1.在DFS求全排列的过程中，用几根小木棍拼出了一根L。把这几根小木棍置为己用，然后对其他的小木棍继续用DFS开始新一轮的拼一根L的操作。如果能一直拼出L，并且拼出了K根，那么L是一个合法的长度。
2.如果在拼一个L时，能用的小木棍的所有排列只能拼出一部分L，失败退出，下一次测试L + 1。
对n个数求全排列，一共有n!个全排列，时间复杂度高
剪枝方案:
- 1.搜索顺序剪枝：把小木棍按照从大到小排序，在全排列时，先选长mu’gun木棍再选短木棍，用的木棍更少，能减少枚举次数，贪心的思想。
- 2.可行性剪枝：若在做某个排列时，加入某个小木棍，导致长度大于L，说明这个小木棍不合适。
- 3.排除冗余。如果在第一轮的全排列中拼不出k根L，那么不需要再次进行后面的轮次。
代码实现
public class Main {
static int N = 70;
static int maxn = 0, minn = N;
static int[] Hash = new int[N]; //Hash[i] :长度为i的木棍的数量
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int sum = 0;
while(n -- > 0) {
int a = sc.nextInt();
Hash[a]++;
sum += a;
maxn = Math.max(maxn, a);
minn = Math.min(minn, a);
}
for(int L = maxn; L <= sum/2; L++) { //长度为L的原始木棍，枚举L
if(sum % L == 0) { //总长度能整除L，说明L是一个可能的数字
dfs(sum /L, 0, L, maxn);
}
}
System.out.println(sum); //所有L都拼不出来，说明原始木棍只有一根，长度为sum
}
public static void dfs(int k, int len, int L, int p) {
//尝试拼出k根长度为L的木棍
if(k == 0) { //已经拼出k根L，输出结果，退出程序
System.out.println(L);
System.exit(0);
}
if(len == L) { //拼出了一根长度为L的木棍
dfs(k - 1, 0, L, maxn); //继续，用剩下的小木棍拼L，再拼k-1根
return;
}
for(int i = p; i >= minn; i--) { //遍历每根小木棍，生成排列
if(Hash[i] > 0 && i + len <= L) {
//Hash[i] > 0 : 存在长度为L的小木棍 , i + len <= L : 确保加上小木棍的长度后，总长度不大于L
Hash[i]--;
dfs(k, len + i, L, p); //继续找下一根合适的小木棍
Hash[i]++;//回溯
if(len == 0)break; //剪枝,去掉重复的组合
if(len + i == L)break; //剪枝
}
}
return;
}
}
N皇后
解题思路 DFS,注意题目要求输出前三个正确答案和总答案数。 考虑设置一个count用于存前三个正确的答案
代码实现
static int n;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
int[][] map = new int[n][n];
dfs(0, map);
for(ArrayList<Integer> path : res) {
for(int i = 0; i < path.size() - 1; i++) {
System.out.print(path.get(i)+" ");
}
System.out.println(path.get(path.size()-1));
}
System.out.println(ans);
}
static ArrayList<Integer> path = new ArrayList<Integer>();
static ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
static int ans;
static int count = 0;
public static void dfs(int depth, int[][] map) {
if(depth == n) {
if(count < 3) {
res.add(new ArrayList<>(path));
count++;
}
ans++;
return;
}
for(int i =0 ; i < n ; i++) {
if(check(depth, i, map)) {
map[depth][i] = 1;
path.add(i + 1);
dfs(depth + 1, map);
path.remove(path.size() - 1);
map[depth][i] = 0;
}
}
}
public static boolean check(int x, int y, int[][] map) {
for(int i = 0 ; i < x ; i++) {
if(map[i][y] == 1)return false;
}
for(int i = x , j = y ; i >= 0 && j >= 0; i--,j--) {
if(map[i][j] == 1)return false;
}
for(int i = x , j = y; i>=0 && j < map[0].length; i--,j++) {
if(map[i][j] == 1)return false;
}
return true;
}
与或异或
解题思路 分为三个方法：
- logic() : 返回此时两值的逻辑操作结果
- check() : 检查10个逻辑门的排列是否符合要求
- dfs() : 更新逻辑门的选择，进入下一个逻辑门。终止条件：判断达到第10个逻辑门时是否符合答案要求
** 代码实现**
public static void main(String[] args) {
dfs(0);
System.out.println(ans);
}
static int[][] num = new int[5][5];
static int[] gate = new int[11]; //10个逻辑门
static int ans;
public static void dfs(int k) { //第k个逻辑门
if(k == 10) { //10个都分配好了
if(check() == 1) { //如果此时结果符合要求
ans++;
}
return;
}
for(int i = 1 ; i<=3; i++) {
gate[k] = i; //记录第k个逻辑门的状态
dfs(k + 1);//继续下一个逻辑门
}
}
public static int logic(int x,int y, int op) { //逻辑操作
if(op == 1)return x & y;
if(op ==2)return x | y;
return x ^ y;
}
public static int check() { //检查10个逻辑门的排列
int op = 0;
num[0][0] = 1;
num[0][1] = 0;
num[0][2] = 1;
num[0][3] = 0;
num[0][4] = 1;
for(int i = 1 ; i <= 4; i++) { //四行逻辑门
for(int j = 0; j <= 4 - i; j++) { //从左到右
num[i][j] = logic(num[i-1][j], num[i-1][j+1], gate[op++]);
}
}
if(num[4][0] == 1)return 1;
return 0;
}
}
LITS游戏
解题思路 DFS搜索是否能放下所有图案
重点在于实现图像的存储已经如何实现DFS
- 使用四维数组存储所有图像的格式,如：
{// 对于L
{{0, 0}, {1, 0}, {2, 0}, {2, 1}}, // 0
{{0, 0}, {0, 1}, {0, 2}, {1, 0}}, // 正向90
{{0, 0}, {0, 1}, {1, 1}, {2, 1}}, // 180
{{0, 2}, {1, 0}, {1, 1}, {1, 2}} // 反向90
},
{// 对于I
{{0, 0}, {1, 0}, {2, 0}, {3, 0}}, // 0
{{0, 0}, {0, 1}, {0, 2}, {0, 3}} // 180
},
这样,pl[0]代表当前选择哪个图像，pl[0][1]代表当前选择哪个图像的哪种方向的图
- DFS需要的方法：
- 1.边界检查
- 2.能否成功画图
- 3.将能画的图的位置进行占位填充，防止后面的图重复占用位置
- 4.DFS主方法，递归当前能否画图，能画的话递归继续画下一张。终止条件：所有的图成功画完。
代码实现
import java.io.*;
import java.util.*;
public class Main {
final static int[][][][] pl = {
{// 对于L
{{0, 0}, {1, 0}, {2, 0}, {2, 1}}, // 0
{{0, 0}, {0, 1}, {0, 2}, {1, 0}}, // 正向90
{{0, 0}, {0, 1}, {1, 1}, {2, 1}}, // 180
{{0, 2}, {1, 0}, {1, 1}, {1, 2}} // 反向90
},
{// 对于I
{{0, 0}, {1, 0}, {2, 0}, {3, 0}}, // 0
{{0, 0}, {0, 1}, {0, 2}, {0, 3}} // 180
},
{// 对于T
{{0, 0}, {0, 1}, {0, 2}, {1, 1}}, // 0
{{0, 0}, {1, 0}, {2, 0}, {1, -1}}, // 正向90
{{0, 1}, {1, 0}, {1, 1}, {1, 2}}, // 180
{{0, 0}, {1, 0}, {2, 0}, {1, 1}} // 反向90
},
{// 对于S
{{0, 0}, {0, 1}, {-1, 1}, {-1, 2}}, // 0
{{0, 0}, {1, 0}, {1, 1}, {2, 1}} // 90
}
};
static int[][] g = new int[55][55];
static int n;
static boolean success = false;
static boolean inBound(int x, int y) { // 判断是否在边界内
return x >= 1 && x <= n && y >= 1 && y <= n;
}
static boolean canPlace(int type, int chosen, int startX, int startY) {
for(int[] pos : pl[type][chosen]) {
int x = startX + pos[0], y = startY + pos[1];
if(!inBound(x, y) || g[x][y] != 1) return false; // 超出边界或者已经被占用
}
return true;
}
static void draw(int type, int chosen, int startX, int startY, int target) {
for(int[] pos : pl[type][chosen]) g[startX + pos[0]][startY + pos[1]] = target;
}
static void choosePlan(int now) { // dfs主函数, 选择第now类型的图案
if(success) return;
if(now == 4) success = true; // 4种图案都放完了, 说明成功
else for(int i = 0; i < pl[now].length; i++) { // 遍历第now种图案的摆放方式
if(success) return;
for(int x = 1; x <= n; x++) { // 选择起始坐标
for(int y = 1; y <= n; y++) {
if(!canPlace(now, i, x, y)) continue; // 检查是否可以放
draw(now, i, x, y, 2); // 进行特殊标记，其他图案不能放在这里
choosePlan(now + 1); // 递归下一个图案
draw(now, i, x, y, 1); // 恢复现场
}
}
}
}
static boolean solve() {
success = false;
choosePlan(0);
return success;
}
public static void main(String[] args) {
int t = in.nextInt();
while(t-- > 0) {
n = in.nextInt();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
g[i][j] = in.nextInt();
}
}
out.println(solve() ? "Yes" : "No");
}
out.flush();
}
static FastReader in = new FastReader();
static PrintWriter out = new PrintWriter(System.out);
static class FastReader {
static BufferedReader br;
static StringTokenizer st;
FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
String str;
while (st == null || !st.hasMoreElements()) {
try {
str = br.readLine();
} catch (IOException e) {
throw new RuntimeException(e);
}
st = new StringTokenizer(str);
}
return st.nextToken();
}
int nextInt() { return Integer.parseInt(next()); }
double nextDouble() { return Double.parseDouble(next()); }
long nextLong() { return Long.parseLong(next()); }
}
}
数学
最优分组
概率计算
解题思路 一组K只宠物,那么没有宠物感染的概率就是P=(1-p)^K,至少有一只宠物感染的概率即1-P,对于一共N/K组,自然即有PN/K组未感染,(1-P)N/K组感染,未感染的话只需1只药剂,否则需要(1+K)支药剂(K==1时除外),那么用药数量就是E=(P+(1-P)(K+1))*N/K
代码实现
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
double p = sc.nextDouble();
double minCousume = Double.MAX_VALUE;
int minK = Integer.MAX_VALUE;
for(int k = n; k >= 1; k--) {
if(n % k == 0) {
//可以分组
double P = Math.pow(1-p, k); //组里宠物未感染的概率
double E = (P + (1- P)*(k + 1)) * n / k; //当前所需最少药剂数量
if(k==1)E=n;//k=1时，需要消耗药剂数量等于n
if(E <= minCousume) { //更新最小需要的药剂数量和分组
minCousume = E;
minK = k;
}
}
}
System.out.println(minK);
图
星际旅行
解题思路 考虑使用Dijkstra算法解题，把使用传送门的距离看做能够移动的距离。
1.由于边的权值相同，所以不需要使用优先队列，不需要实现Edge结构。
2.修改while中的逻辑，使其每次得到正确的能走到的位置，得到答案。
代码实现
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int Q = sc.nextInt();
List<List<Integer>> map = new ArrayList<List<Integer>>();
//构建邻接矩阵
for(int i =0 ; i <= n; i++) {
List<Integer> node = new ArrayList<Integer>();
map.add(node);
}
//保存边关系
for(int i = 0; i < m; i++) {
int start = sc.nextInt();
int b = sc.nextInt();
map.get(start).add(b);
map.get(b).add(start);
}
double ans = 0;
for(int i = 0 ; i < Q; i++) {
int x = sc.nextInt();
int y = sc.nextInt();
int[] steps = new int[n+1];
Arrays.fill(steps, -1); //表示未访问过
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(x);
steps[x] = 0;//起点步数为0
int count = 1;//至少包含起点自己
while(!queue.isEmpty()) {
int cur = queue.poll();
//当前步数达到上限，不再拓展
if(steps[cur] >= y)continue;
//遍历所有邻居
for(int neighbor: map.get(cur)) {
if(steps[neighbor] == -1) {
steps[neighbor] = steps[cur] + 1;
if(steps[neighbor] <= y) {
count++;
}
queue.add(neighbor);
}
}
}
ans += count;
}
double exp = ans / Q;
System.out.printf("%.2f", exp);
}
说些什么吧！