本文最后更新于2021年5月30日,已超过 12 个月没更新!
👨💻 AcWing·在线竞赛
🏆 第 1 场周赛
3. 数字移动
🎖️ 并查集
import java.util.*;
public class Main {
static int[] p;
static int[] size;
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
int n = sc.nextInt();
p = new int[n + 1];
size = new int[n + 1];
for (int i = 1; i <= n; ++ i) {
p[i] = i;
size[i] = 1;
}
for (int i = 1; i <= n; ++ i) {
int j = sc.nextInt();
if (find(i) != find(j)) {
size[find(j)] += size[find(i)];
p[find(i)] = find(j);
}
}
for (int i = 1; i <= n; ++ i) System.out.print(size[find(i)] + " ");
System.out.println();
}
}
private static int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
}
类似题型:算法基础课 - 连通块中点的数量
🏆 第 2 场热身赛
2. 双端队列
import java.util.*;
import java.io.*;
public class Main {
public static void main (String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
Map<Integer, Integer> map = new HashMap<>();
int left = 0, right = -1;
int q = Integer.parseInt(br.readLine());
for (int i = 0; i < q; ++ i) {
String[] s = br.readLine().split(" ");
int num = Integer.parseInt(s[1]);
if ("L".equals(s[0])) {
map.put(num, -- left);
}
else if ("R".equals(s[0])) {
map.put(num, ++ right);
}
else {
int idx = map.get(num);
bw.write(Math.min(idx - left, right - idx) + "\n");
}
}
br.close();
bw.close();
}
}
3. 最长非递减子序列⭐
import java.util.*;
import java.io.*;
public class Main {
public static void main (String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
String[] s = br.readLine().split(" ");
int s1 = 0, s2 = 0, s3 = 0, s4 = 0;
for (int i = 0; i < s.length; ++ i) {
if ("1".equals(s[i])) {
s1 ++;
s3 = Math.max(s3 + 1, s2 + 1);
} else {
s2 = Math.max(s1 + 1, s2 + 1);
s4 = Math.max(s3 + 1, s4 + 1);
}
}
bw.write(Math.max(s3, s4) + "\n");
bw.close();
br.close();
}
}

🍹y总笔记🍹