前言
整体评价
比赛刚开始的时候，看到清一色的英语题目，就有种不祥的预感，果然......
感觉这场练习赛好难，在知识范围内是前四题，但是实际能ac 4题的却很少，是真的难。
A. Mountain sequence
要求构建一个山峰数组，求累计的方案总数
其实这题是构造题，按照要求确定山峰(最大值)后, 然后决策其他的数往那放置。
可以分组(按值)排序，然后从大到小放置。
对于某组(size=m), 则左右侧{(0, m), (1, m - 1), ..., (m, 0)} 总共m+1种方式。
所以这题显然易见，就是除最大数以外的组大小累乘。
import java.io.BufferedInputStream;
import java.util.Scanner;
import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
int kase = sc.nextInt();
while (kase-- > 0) {
int n = sc.nextInt();
TreeMap<Integer, Integer> hash = new TreeMap<>();
for (int i = 0; i < n ;i++) {
int v = sc.nextInt();
hash.merge(v, 1, Integer::sum);
}
// treemap是保序的
int[] arr = hash.values().stream().mapToInt(Integer::valueOf).toArray();
long mod = 998244353l;
long ans = 1l;
// 这边需要把最大数的组(山峰)去掉, 所以枚举到[0, arr.length - 1)
for (int i = 0; i < arr.length - 1; i++) {
int m = arr[i];
ans = ans * (m + 1) % mod;
}
System.out.println(ans);
}
}
}
B. Antiamuny wants to leaern binary search again
既然是通过次数来求可能的目标值，那完全可以逆序模拟二分.
1. 模拟二分+贪心
二分区间的时候，右侧的区间更大一些，所以尽量往右侧寻找。
import java.io.BufferedInputStream;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
int kase = sc.nextInt();
while (kase-- > 0) {
int l = sc.nextInt(), r = sc.nextInt();
int cnt = sc.nextInt();
int ans = -1;
while (l <= r) {
int m = l + (r - l) / 2;
cnt--;
if (cnt == 0) {
ans = m;
break;
}
// 贪心走右侧
l = m + 1;
}
System.out.println(ans);
}
}
}
2. 记忆化
因为这题范围为, 而
这题也可以用dp的方式求解，不过记忆化的话，更容易书写
, m表示长度，s表示次数，存在的情况对应的数字(偏移)
import java.io.BufferedInputStream;
import java.util.Scanner;
public class Main {
static Integer[][] opt = new Integer[100_0001][21];
static int dfs(int l, int r, int z) {
if (r < l) return -1;
int span = r - l + 1;
int mid = l + (r - l) / 2;
if (z == 1) {
return mid;
}
if (opt[span][z] != null) {
return opt[span][z] == -1 ? -1 : opt[span][z] + l;
}
int r1 = dfs(l, mid - 1, z - 1);
if (r1 != -1) {
opt[span][z] = r1 - l;
return r1;
}
int r2 = dfs(mid + 1, r, z - 1);
if (r2 != -1) {
opt[span][z] = r2 - l;
return r2;
}
opt[span][z] = -1;
return -1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
int kase = sc.nextInt();
while (kase-- > 0) {
int l = sc.nextInt(), r = sc.nextInt();
int cnt = sc.nextInt();
System.out.println(dfs(l, r, cnt));
}
}
}
C. Find the maximum slope
如果把这个公式，看做斜率k=(arr[i] - arr[j])/(i-j)
那这个斜率极值(最大/最小)，必然是相邻。
反证法，假如不是相邻的元素构成的斜率最大。
结合数形，可以发现，除非在一条直线上，否则必然能找到一条更大的斜率.
因此，我们可以证明：
最大值，一定是相邻元素构造的。
那剩下的事情，就简单很多了。
按要求构建相邻两元素的差分数组。
对于区间修改，只会影响区间的边界两个点差分值。
import java.io.BufferedInputStream;
import java.util.Scanner;
import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
int n = sc.nextInt(), q = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
// treemap是维护差分的最大值
TreeMap<Integer, Integer> range = new TreeMap<>();
int[] diff = new int[n - 1];
for (int i = 0; i < n - 1; i++) {
diff[i] = arr[i] - arr[i + 1];
range.merge(Math.abs(diff[i]), 1, Integer::sum);
}
System.out.println(range.lastKey());
for (int i = 0; i < q; i++) {
int l = sc.nextInt() - 1, r = sc.nextInt() - 1;
int x = sc.nextInt();
// 区间修改只会影响2个端边界
if (l > 0) {
range.computeIfPresent(Math.abs(diff[l - 1]), (a, b) -> b > 1 ? b - 1 : null);
diff[l - 1] -= x;
range.merge(Math.abs(diff[l - 1]), 1, Integer::sum);
}
if (r + 1 < n) {
range.computeIfPresent(Math.abs(diff[r]), (a, b) -> b > 1 ? b - 1 : null);
diff[r] += x;
range.merge(Math.abs(diff[r]), 1, Integer::sum);
}
System.out.println(range.lastKey());
}
}
}
这题，出题者真的太贼了，故意引入浮点数，限定值域大小，不知道多少小伙伴直接被带偏了。
D. Genealogy in the trees
因为涉及树上的祖先判定，因此dfn序是免不了的。
dfn序之后，该如何求解，成了这题的关键。
这题应该非常的经典，一种思路借鉴了何老师的做法，时间序模拟操作，树状数组支持区间查询。
另一种是 树上启发式合并，需要AVL树的支持。
1. 树状数组
预处理dfn时间序，每个对都有一个start, end时间戳
按照离线计算的思路，再构建一个操作序列
- 点对按p，的时间序start加入，按end离开, 进行bit操作
- 查询按a，的时间点，进行bit查询
这题数据量有点大，需要用快读模板。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
import java.util.stream.Collectors;
public class Main {
static class BIT {
int n;
int[] arr;
public BIT(int n) {
this.n = n;
this.arr = new int[n + 1];
}
public void update(int p, int d) {
while (p <= n) {
arr[p] += d;
p += p & -p;
}
}
public int query(int p) {
int res = 0;
while (p > 0) {
res += arr[p];
p -= p & -p;
}
return res;
}
}
static class Solution {
int timestamp = 0;
int[] start, end;
int n;
List<Integer> []g;
int[] solve(int n, int[][] es, int[][] ms, int[][] qs) {
this.n = n;
this.start = new int[n + 1];
this.end = new int[n + 1];
this.g = new List[n + 1];
Arrays.setAll(g, x -> new ArrayList<>());
for (int i = 0; i < es.length; i++) {
int u = es[i][0], v = es[i][1];
g[u].add(v);
g[v].add(u);
}
// 有根树，root=1
dfs(1, -1);
// 离线计算，转换为操作序列
// 三元组 (time, type, time/id)
List<int[]> ops = new ArrayList<>();
for (int i = 0; i < ms.length; i++) {
int p = ms[i][0], q = ms[i][1];
ops.add(new int[] {start[p], 1, start[q]});
ops.add(new int[] {end[p], -1, start[q]});
}
for (int i = 0; i < qs.length; i++) {
int a = qs[i][0];
ops.add(new int[] {start[a], 0, i});
}
ops.sort((x, y) -> {
int r = Integer.compare(x[0], y[0]);
if (r != 0) return r;
return -Integer.compare(Math.abs(x[1]), Math.abs(y[1]));
});
int[] res = new int[qs.length];
BIT bit = new BIT(timestamp);
for (int[] e: ops) {
int type = e[1];
if (type == 0) {
int idx = e[2];
int b = qs[idx][1];
res[idx] = bit.query(end[b]) - bit.query(start[b] - 1);
} else {
bit.update(e[2], e[1]);
}
}
return res;
}
// 做dfn序
void dfs(int u, int fa) {
start[u] = ++timestamp;
for (int v: g[u]) {
if (v == fa) continue;
dfs(v, u);
}
end[u] = ++timestamp;
}
}
public static void main(String[] args) {
AReader sc = new AReader();
int n = sc.nextInt(), m = sc.nextInt(), q = sc.nextInt();
int[][] es = new int[n - 1][2];
for (int i = 0; i < n - 1; i++) {
es[i][0] = sc.nextInt();
es[i][1] = sc.nextInt();
}
int[][] ms = new int[m][2];
for (int i = 0; i < m; i++) {
ms[i][0] = sc.nextInt();
ms[i][1] = sc.nextInt();
}
int[][] qs = new int[q][2];
for (int i = 0; i < q; i++) {
qs[i][0] = sc.nextInt();
qs[i][1] = sc.nextInt();
}
Solution solution = new Solution();
int[] res = solution.solve(n, es, ms, qs);
System.out.println(Arrays.stream(res).mapToObj(String::valueOf)
.collect(Collectors.joining("\n")));
}
static
class AReader {
private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
private StringTokenizer tokenizer = new StringTokenizer("");
private String innerNextLine() {
try {
return reader.readLine();
} catch (IOException ex) {
return null;
}
}
public boolean hasNext() {
while (!tokenizer.hasMoreTokens()) {
String nextLine = innerNextLine();
if (nextLine == null) {
return false;
}
tokenizer = new StringTokenizer(nextLine);
}
return true;
}
public String nextLine() {
tokenizer = new StringTokenizer("");
return innerNextLine();
}
public String next() {
hasNext();
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
}
}
2. 启发式合并
先占个坑，需要名次树支持
dfn时间序做预处理
离线计算做法，每个节点有两个名次数，一个维护前缀(节点的start时间戳)，一个维护后缀(节点的end时间戳)
自底向上，做启发式合并
很像LCA的tarjan解法，即在dfs过程中，离线把结果计算了。
前缀rank - 后缀rank
京公网安备 11010502036488号