🔗 参考地址
亮灭
🔗 亮灭
🎉 模拟
import java.util.Scanner;
public class Main {
// 亮灯数组：a[1][2][3] 表示 数字1的第2行第3列，1 表示亮
static int[][][] a = new int[10][10][10];
public static void main(String[] args) {
// 初始化数字 0~9 的亮灯数组
initializeArray();
Scanner scanner = new Scanner(System.in);
int T = scanner.nextInt();
while (T-- > 0) {
int n = scanner.nextInt();
int x = scanner.nextInt();
int y = scanner.nextInt();
// 读取字符串 st
String st = scanner.next();
int ans = 0;
// 遍历字符串 st，计算状态变化的次数
for (int i = 1; i < n; i++) {
if (a[Character.getNumericValue(st.charAt(i))][x][y] != a[Character.getNumericValue(st.charAt(i - 1))][x][y]) {
ans += 1;
}
}
// 输出结果
System.out.println(ans);
}
scanner.close();
}
// 设置数字 1~9 的亮灯数组
static void initializeArray() {
row(0, 1);
row(0, 5);
col(0, 1);
col(0, 4);
col(1, 4);
pos(1, 1, 3);
row(2, 1);
row(2, 3);
row(2, 5);
pos(2, 2, 4);
pos(2, 4, 1);
row(3, 1);
row(3, 3);
row(3, 5);
col(3, 4);
row(4, 3);
col(4, 3);
pos(4, 1, 1);
pos(4, 2, 1);
row(5, 1);
row(5, 3);
row(5, 5);
pos(5, 2, 1);
pos(5, 4, 4);
row(6, 1);
row(6, 3);
row(6, 5);
col(6, 1);
pos(6, 4, 4);
row(7, 1);
col(7, 4);
row(8, 1);
row(8, 3);
row(8, 5);
col(8, 1);
col(8, 4);
row(9, 1);
row(9, 3);
row(9, 5);
col(9, 4);
pos(9, 2, 1);
}
// 设置 x 数字的第 r 行的特定列为 1
static void row(int x, int r) {
a[x][r][1] = a[x][r][2] = a[x][r][3] = a[x][r][4] = 1;
}
// 设置 x 数字的特定列的行（从 1 到 5）为 1
static void col(int x, int c) {
for (int i = 1; i < 6; i++) {
a[x][i][c] = 1;
}
}
// 设置 x 数字的 r 行 c 列为 1
static void pos(int x, int r, int c) {
a[x][r][c] = 1;
}
}
01串
🔗 题目地址
🎉 贪心
//交换 01 串
import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while (T-- > 0) {
int n = sc.nextInt();
int k = sc.nextInt();
String s = sc.next();
char[] st = s.toCharArray();
List<Integer> one = new ArrayList<>();// 记录 1 的位置
List<Integer> zero = new ArrayList<>();// 记录 0 的位置
// 遍历字符串，记录 '1' 的位置到 one 列表，记录 '0' 的位置到 zero 列表
for (int i = 0; i < n; i++) {
if (st[i] == '1') {
one.add(i);
}
if (st[n - 1 - i] == '0') { // 逆序记录 0 的下表
zero.add(n - 1 - i);
}
}
// 特殊情况处理：当 n == 2 时
if (n == 2) {
if (k % 2 == 1) {
// 如果 k 是奇数，交换 st[0] 和 st[1]
char temp = st[0];
st[0] = st[1];
st[1] = temp;
}
// 输出结果
System.out.println(new String(st));
continue;
}
// 只要 n > 2, 两次交换是可以互相抵消的（n > 2 保证了至少会出现 两个 1 或 两个 0）
k = Math.min(k, n / 2); // 最多需要 n/2 次就可以达到最小字典序
int cnt = 0; // 统计移动的次数(0 出现的位置看)
// 贪心算法：将 '0' 移动到前面，将 '1' 移动到后面
for (int idx1 : one) {
if (cnt == k || cnt == zero.size() || zero.get(cnt) < idx1) {
break;
}
st[idx1] = '0';
st[zero.get(cnt)] = '1';
cnt++;
}
// 输出结果
System.out.println(new String(st));
}
sc.close();
}
}
数组的最大MEX求和
🔗 题目地址
- 个人理解：这里好像不能切分成单元素区间 或者 不切分
- 样例1
- 不切分：(0110)，结果为 2
- 单元素区间：(011) (0)，结果为 3 （2+1=3）
🎉 区间DP
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读取测试用例的数量
int T = sc.nextInt();
while (T > 0) {
// 读取数组的长度 n
int n = sc.nextInt();
int[] a = new int[n + 1];
// 读取数组元素
for (int i = 1; i <= n; i++) {
a[i] = sc.nextInt();
}
// 初始化辅助数组
int[] f = new int[n + 1];
int[][] mex = new int[n + 1][n + 1];// mex[i][j] 表示区间 [i,j] 没出现的最小自然数
// 预处理 mex(i, j)
for (int i = 1; i <= n; i++) {
int min = 0; // 记录最小的自然数
f = new int[n + 1];// 在 n 个数中没出现过的最小的自然数 的最大可能值为 n
for (int j = i; j <= n; j++) {
f[a[j]] = 1;
while (f[min] == 1) min++;
mex[i][j] = min;
}
}
int[][] dp = new int[n + 1][n + 1]; // dp[i][j]表示前 i 个数中，最后一段是从 j 开始的这段最大 MEX 和
// 初始化 dp 数组
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
dp[i][j] = -1;
}
}
dp[1][1] = mex[1][1];
// 动态规划求解
for (int i = 1; i < n; i++) {
for (int j = 1; j <= i; j++) {
if (dp[i][j] != -1) { // dp[i][j] 作为起点做状态转移
dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j] - mex[j][i] + mex[j][i + 1]);// 复用当前区间[j,i]
dp[i + 1][i + 1] = Math.max(dp[i + 1][i + 1], dp[i][j] + mex[i + 1][i + 1]);// 从i+1开始新开一段区间[i+1.i+1]
}
}
}
// 找到最大 MEX 和
int ans = 0;
for (int i = 1; i <= n; i++) {
ans = Math.max(ans, dp[n][i]);
}
System.out.println(ans);
T--;
}
sc.close();
}
}
最长元音回文子串
TODO
