蓝桥杯算法集训 - Week1
本系列随笔用于整理AcWing题单——《蓝桥杯集训·每日一题2024》的系列题型及其对应的算法模板。
一、二分查找
二分算法原理复习参考：二分查找 - Hello 算法
Ⅰ、二分模板
bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
Ⅱ、分巧克力
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static final int N = 100010;
static int n, k;
static int[][] a = new int[N][2];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] split = br.readLine().split(" ");
n = Integer.parseInt(split[0]);
k = Integer.parseInt(split[1]);
for (int i = 0; i < n; i++) {
split = br.readLine().split(" ");
a[i][0] = Integer.parseInt(split[0]);
a[i][1] = Integer.parseInt(split[1]);
}
br.close();
// 二分枚举边长
int l = 1, r = N;
while (l < r) {
int mid = l + (r - l + 1) / 2;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
System.out.println(l);
}
// 检查是否可以分出k块巧克力
static boolean check(int mid) {
int cnt = 0;
for (int i = 0; i < n; i++) {
cnt += (a[i][0] / mid) * (a[i][1] / mid);
if (cnt >= k)
return true;
}
return false;
}
}
二、前缀和
前缀和原理复习参考：【优选算法】—— 前缀和算法
Ⅰ、前缀和模板
// 一维前缀和
S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]
// 二维前缀和
// S[i, j] = 第i行j列格子左上部分所有元素的和
// 以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
Ⅱ、一维数组的动态和
给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i]) 。
请返回 nums 的动态和。
public class Main{
public int[] runningSum(int[] nums) {
int[] prefix = new int[nums.length];
prefix[0] = nums[0];
for (int i = 1; i < nums.length; ++i) {
prefix[i] = prefix[i - 1] + nums[i];
}
return prefix;
}
}
Ⅲ、统计子矩阵
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static final int N = 510;
static int n, m, k;
static int[][] martix = new int[N][N];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] split = br.readLine().split(" ");
n = Integer.parseInt(split[0]);
m = Integer.parseInt(split[1]);
k = Integer.parseInt(split[2]);
for (int i = 1; i <= n; i++) {
split = br.readLine().split(" ");
for (int j = 1; j <= m; j++) {
// 计算矩阵的前缀和数组
martix[i][j] = martix[i - 1][j] + martix[i][j - 1] - martix[i - 1][j - 1] + Integer.parseInt(split[j - 1]);
}
}
br.close();
long res = 0;
for (int x1 = 1; i <= n; i++) {
for (int y1 = 1; j <= m; j++) {
for (int x2 = x1, x2 <= n; x2++) {
for (int y2 = y1, y2 <= m; y2++) {
// 枚举每一个二维矩阵的前缀和，符合时s++
while (martix[t][j] - martix[s - 1][j] - martix[t][i - 1] + martix[s - 1][i - 1] <= k) s++;
}
}
}
}
System.out.println(res);
}
}
三、差分
差分算法复习参考：【详解】手撕 一维、二维、三维差分数组原理（附图解，模板，例题分析）
注：差分算法实际为《蓝桥杯集训·每日一题2024》的 Week 2 内容。但差分与前缀和算法关系很大，互为逆运算，故提前放置于本章。
Ⅰ、差分模板
// 初始化一维差分
B[n] = a[n] - a[n - 1];
// 给区间[l, r]中的每个数加上c：
B[l] += c, B[r + 1] -= c;
// 初始化二维差分
S[i][j] = a[i][j] − a[i−1][j] − a[i][j−1] + a[i−1][j−1];
// 给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c;
S[x2 + 1, y1] -= c;
S[x1, y2 + 1] -= c;
S[x2 + 1, y2 + 1] += c;
Ⅱ、借教室
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] split = reader.readLine().split(" ");
int n = Integer.parseInt(split[0]);
int m = Integer.parseInt(split[1]);
int[] count = new int[n + 1];
String[] cns = reader.readLine().split(" ");
for (int i = 1; i <= n; i++) {
count[i] = Integer.parseInt(cns[i-1]);
}
// 初始化差分数组
for (int i = n ; i >= 1; i--){
count[i] -= count[i-1];
}
int[][] orders = new int[m + 1][3];
for (int i = 1; i <= m; i++) {
String[] ods = reader.readLine().split(" ");
orders[i][0] = Integer.parseInt(ods[0]);
orders[i][1] = Integer.parseInt(ods[1]);
orders[i][2] = Integer.parseInt(ods[2]);
}
reader.close();
// 二分查找最后符合要求的日期
int l = 1, r = m;
while (l < r){
int mid = (l + r) / 2;
if (check(count, orders, mid)){
l = mid + 1;
}else {
r = mid;
}
}
if (check(count, orders, r)) {
System.out.println(0);
} else {
System.out.println(-1);
System.out.println(r);
}
}
// 使用差分算法优化计算效率
private static boolean check(int[] count, int[][] orders, int mid) {
// 复制一份差分数组
long[] copy = new long[count.length];
for (int i = 1; i < copy.length; i++) {
copy[i] = count[i];
}
// 将第一天到第mid天的教室减去
for (int i = 1; i <= mid ; i++) {
// orders[i][0]为第i个订单所需教室数、orders[i][1]为起始天数、orders[i][2]为结束天数
copy[orders[i][1]] -= orders[i][0];
if (orders[i][2] != copy.length - 1){
copy[orders[i][2] + 1] += orders[i][0];
}
}
long res = 0;
for (int i = 1; i < copy.length; i++) {
res += copy[i]; // 对差分数组求前缀和获得原始数据
if (res < 0){
return false;
}
}
return true;
}
}
Ⅲ、棋盘
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
public class Main {
static final int N = 2010;
static int n, m;
static int matrix[][] = new int[N][N];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(System.out);
String[] split = br.readLine().split(" ");
n = Integer.parseInt(split[0]);
m = Integer.parseInt(split[1]);
for (int i = 1; i <= m; i++) {
split = br.readLine().split(" ");
// 初始化二维差分
insert(Integer.parseInt(split[0]), Integer.parseInt(split[1]), Integer.parseInt(split[2]), Integer.parseInt(split[3]));
}
br.close();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
// 求二维前缀和获取结果
matrix[i][j] += matrix[i - 1][j] + matrix[i][j-1] - matrix[i - 1][j - 1];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (matrix[i][j] % 2 == 0) pw.print("0");
else pw.print("1");;
}
pw.print("\n");
}
pw.close();
}
// 对二维差分进行修改的代码模板
static void insert(int x1, int y1, int x2, int y2) {
matrix[x1][y1]++;
matrix[x1][y2 + 1]--;
matrix[x2 + 1][y1]--;
matrix[x2 + 1][y2 + 1]++;
}
}