Rank：2600
A. 题目链接
没有思路，直接模拟。
B. 题目链接
算法标签：枚举。
思路：枚举N，i。用一个变量sum统计 power(3, i) 的和，如果sum等于m了，则找到一个合法方案，直接输出即可。
public static void solve() throws IOException {
int m = in.nextInt();
int[] A = new int[20];
int sum = 0;
int N = 0;
for (int i = 10; i >= 0; i--) {
int power = (int)Math.pow(3, i);
while (sum + power <= m && N < 20) {
A[N++] = i;
sum += power;
}
if (sum == m) {
break;
}
}
out.println(N);
for (int i = 0; i < N; i++) {
out.print(A[i] + " ");
}
out.println();
}C. 题目链接
算法标签：模拟、枚举。
思路：先统计s种所有ABC子串的个数记作cnt。根据题目要求模拟，如果修改的字符会影响组成ABC子串的字符，那么cnt--，然后将x位置的字符替换为c，再重新遍x的附近位置，检查是否会形成新的ABC子串，如果有则cnt++。
public static void solve() throws IOException {
int n = in.nextInt();
int q = in.nextInt();
String s = in.nextLine();
int cnt = 0;
for (int i = 0; i < n - 2; i++) {
String t = s.substring(i, i + 3);
if (t.equals("ABC")) {
cnt++;
}
}
List<Integer> ans = new ArrayList<>();
char[] cs = s.toCharArray();
while (q-- > 0) {
String line = in.nextLine();
String[] ss = line.split(" ");
int x = Integer.parseInt(ss[0]) - 1;
char c = ss[1].charAt(0);
int start = Math.max(0, x - 2);
int end = Math.min(n - 1, x + 2);
for (int i = start; i < end - 1; i++) {
if (cs[i] == 'A' && cs[i+1] == 'B' && cs[i+2] == 'C') {
cnt--;
}
}
cs[x] = c;
for (int i = start; i < end - 1; i++) {
if (cs[i] == 'A' && cs[i+1] == 'B' && cs[i+2] == 'C') {
cnt++;
}
}
ans.add(cnt);
}
for (int v : ans) {
out.println(v);
}
}D. 题目链接
算法标签：单调栈。
思路：倒着枚举i，如果栈顶元素小于当前元素的下一个值，那么就要pop栈顶。比如 2 5 4 这种，4肯定是要被pop的。ans[i]就是stk.size()。
public static void solve() throws IOException {
int n = in.nextInt();
int[] h = new int[n];
for (int i = 0; i < n; i++) {
h[i] = in.nextInt();
}
int[] ans = new int[n];
var stk = new ArrayDeque<Integer>();
for (int i = n - 2; i >= 0; i--) {
// 如果栈顶元素 < 当前值的下一个值 就要pop
while (!stk.isEmpty() && h[stk.peek()] < h[i + 1]) {
stk.pop();
}
stk.push(i + 1);
ans[i] = stk.size();
}
for (int v : ans) out.print(v + " ");
out.println();
}E. 题目链接
算法标签：并查集、启发式合并、排序。
思路：因为k很小（1≤k≤10），用并查集实现点与点的合并，并且每个连通分量要维护前k大的元素。如果当前联通分量的元素个数超过10了，就要poll。query的时候把并查集维护的元素取出来排个序，取第k大就行了。
思考：如果k很大，应该怎么做。
public static void solve() throws IOException {
int n = in.nextInt();
int q = in.nextInt();
List<Integer> ans = new ArrayList<>();
UnionFind uf = new UnionFind(n);
while (q-- > 0) {
String[] s = in.nextLine().split(" ");
int op = Integer.parseInt(s[0]);
if (op == 1) {
int u = Integer.parseInt(s[1]);
int v = Integer.parseInt(s[2]);
uf.merge(u, v);
} else {
int v = Integer.parseInt(s[1]);
int k = Integer.parseInt(s[2]); // k很小，只有10
int root = uf.find(v);
PriorityQueue<Integer> pq = uf.pqs[root];
if (pq.size() < k) {
ans.add(-1);
continue;
}
List<Integer> list = new ArrayList<>(pq);
list.sort((x, y) -> y - x);
ans.add(list.get(k - 1));
}
}
for (int v : ans) {
out.println(v);
}
}
static class UnionFind {
int[] fa;
PriorityQueue<Integer>[] pqs;
public UnionFind(int n) {
this.fa = new int[n + 1]; // n+1
this.pqs = new PriorityQueue[n + 1];
for (int i = 1; i <= n; ++i) {
fa[i] = i;
pqs[i] = new PriorityQueue<>((a, b) -> a - b);
pqs[i].add(i);
}
}
// 非递归版本 查询 (路径压缩版)
public int find(int x) {
while (x != fa[x]) {
fa[x] = fa[fa[x]];
x = fa[x];
}
return x;
}
// 合并
public void merge(int from, int to) {
int x = find(from);
int y = find(to);
if (x == y) return;
if (pqs[x].size() > pqs[y].size()) {
for (int v : pqs[y]) {
pqs[x].add(v);
if (pqs[x].size() > 10) pqs[x].poll();
}
fa[y] = x;
} else {
for (int v : pqs[x]) {
pqs[y].add(v);
if (pqs[y].size() > 10) pqs[y].poll();
}
fa[x] = y;
}
}
}