概述

虚拟机把描述类的数据从 Class 文件加载到内存，井对数据进行校验、转换解析和初始化，最终形成可以被虚拟机直接使用的 Java 类型，这就是虚拟机的类加载机制。

类加载的时机

类从被加载到虚拟机内存中开始，到卸栽出内存为止，它的整个生命周期包括了：加载、验证、准备、解析、初始化、使用和卸载七个阶段。其中验证、准备和解析三个部分统称为连接。

加载

加载是类加载过程中的一个阶段，这个阶段虚拟机要完成3件事。

快排的思想，选定一个基准数，将大于 $mid$ 的数放到右边，小于的放到左边，然后比较 $mid$ 和 $k$ 的位置，递归重复操作即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#pragma GCC optimize("Ofast")
#include <cstdio>

inline int read() {
<!--more--> 
  int x = 0, w = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') w ^= 1;
    c = getchar();
  }
  while (c <= '9' && c >= '0') {
    x = (x << 1) + (x << 3) + c - '0';
    c = getchar();
  }
  return w & 1 ? x : -x;
}

int kth_element(int* a, int l, int r, int k) {
  int mid = l - 1;
  for (int i = l; i < r; ++i) {
    if (a[i] < a[r] && a[i] ^ a[++mid]) a[i] ^= a[mid] ^= a[i] ^= a[mid];
  }
  if (a[++mid] ^ a[r]) a[mid] ^= a[r] ^= a[mid] ^= a[r];
  if (mid == k) return a[mid];
  return (mid >= k) ? kth_element(a, l, mid - 1, k)
                    : kth_element(a, mid + 1, r, k);
}

int a[2000006];

int main() {
  int n, k;
  n = read();
  k = read();
  for (int i = 0; i < n; ++i) a[i] = read();
  // random_shuffle(a, a + n);
  printf("%d\n", kth_element(a, 0, n - 1, n - k));
  return 0;
}

题目

给你两个队列$a$和$b$，问你能否构造出给定的队列$c$。

Solutuon

很经典的动态规划，$dp[i][j]$ 表示第一个队列的前 $i$ 个数和第二个队列的第 $j$ 个数能否组成第三个队列的前 $i+j$ 个数。状态转移方程：$dp[i][j] = (dp[i - 1][j]$ $and$ $a[i] == c[i + j]$ $or$ $dp[i][j - 1]$ $and$ $b[j] == c[i + j])$。

题目

给定一颗树，路径只能由父节点指向子节点，你可以增加一条有向边，使得联通点对最多。

Solution

容易发现，当叶子结点往根结点连一条边时，增加的点对会是最多的。$dp1[i]$ 表示从 $i$ 结点出发可以到达多少点，$dp2[i]$ 表示当前以 $i$ 为根结点，能增加的最大点对数（最大值）。

题目

求 $n$ 个节点，高度不超过 $h$ 的二叉树的个数，结果模 $1e9 + 7$。

Solution

题目

$n$ 个物体，每个物品都有 $k$ 个属性，实际上就是 $a[n][k]$ 的数组，满足 $a[i][0]+a[j][0]=a[i][1]+a[j][1]=…=a[i][k−1]+a[j][k−1]$ 的物体 $i$ 和物体 $j$ 称为一对完美对，求完美对对数。

Solution

题目

给你长度为 $n$ 的序列，你有一种能力可以将序列中的任意一个数变为相反数，在你不超过 $k$ 次使用能力的情况下，长度为 $len$ 的子区间的和的绝对值的最大值是多少？

Solution

用两个multiset维护区间前k大的负数，扫一遍就好了，细节略多。

题目

给定整数 $m$ 以及 $n$ 各数字 $A_1,A_2,..A_n$，将数列 $A$ 中所有元素两两异或，共能得到 $n(n-1)/2$ 个结果，请求出这些结果中大于 $m$ 的有多少个。

Solution

为了避免重复计算，字典树可以边维护边插入，先查询之前有多少个数与当前数 $x$ 异或和大于 $m$，我们从高位向低位枚举，对于两个数的同一个二进制位，需要分四种情况讨论：

写C++还是用vim爽啊，曾经三次尝试vim，寒假的时候终于能得到一份比较不错的配置了。

配色用的是atom的onedark，个人感觉挺好看的。

贴个配置，即开即用。

题目

Solution