玖的数学&算法录

Floyd算法

本书使用教材为：《数学分析教程（第3版）》，大部分以抄书为笔记内容。

第一章 实数和数列极限

1.1 实数

Def 1. 对所有的有理数而言，均可用 p / q 来表示。

数域 ： 有理数经过加减乘除后仍为有理数，由此称全体有理数为数域。

Q1：试证明 \sqrt{2} 不是有理数。

tips：反证，表示为p / q,并且p与q无公因子。

若要证明 P + Q 为有理数，其中 Q 是无理数，那么考虑 (P + Q) - P = Q即可。

无穷递降法：

见课本P5，若 n 为正整数且不是完全平方数，那么 \sqrt{n} 是无理数。

tips: 同Q1,反证法，造出两串递减的正整数列说明这样的正整数不可能无止境地递减下去即可。

1.2 数列与收敛数列

Def 1. 收敛数列定义

$$\displaystyle 对\forall \epsilon > 0, \exists N \in N^*, 使得当 n > N 时，有 |a_n - a| < \epsilon$$

对于发散数列，对上面的话反着说即可。

$$\displaystyle \lim_{n \to \infty} q ^ n = 0,|q| < 1$$

$$\displaystyle \lim_{n \to \infty} n^{\frac{1}{n}} = 1$$

1.3 收敛数列的性质

Def 1. 收敛数列的极限是唯一的。

tips: 假设一个数列收敛于两个值，最后两个值进行做差的结果是 < \epsilon => 即 a = b

Def 2. 收敛数列必有界

tips: 任取一个数，使用一次三角不等式。

Def 3. 设{an}的极限为a,那么他的任何一个子列都收敛于a。

tips: 显然。

Def 4. 若数列 {an} 的两个子列收敛于不同极限，那么 {an} 发散

tips: 书上例子：an = sin n。

Def 5. 收敛必有界，有界不一定收敛。

tips: (-1) ^ n。

Def 6. 设 {an} {bn} 是两个收敛数列，那么他们必然是满足四则运算的,(要求做除法的时候分母不为0，若分母为0则分子也需要为0)。

tips: 证明见书P15

Def 7. 若 {an} 是无穷小，那么 {|an|} 也是无穷小，反之亦能推出。

Def 8. 有界数列乘无穷小量仍为无穷小量。

Def 9. 若 0 <= an <= bn,那么当{bn} 为无穷小量时，{an}也为无穷小。（若没有an >= 0这个条件，那么这个结论不成立。）

Def 10. {an} 的极限为 a,那么 {an - a} 也是无穷小。

Def 11. 若 an <= bn <= cn, 若{an} {cn}极限均为 a , 那么 {bn} 的极限也为 a。（对于条件不强制要求等号）。

Def 12. 约定 {an} 的极限为 a

Case 1： α < a < β，则当 n 充分大的时候，有 α < an < β。

Case 2： {bn} 的极限为 b，且 a < b,n > N, an < bn。

Case 3： {bn} 的极限为 b，若 n > N, an <= bn, 那么 a < b。

1.4 数列极限概念的推广

$$\displaystyle 对\forall A > 0, \exists N, 使得当 n > N 时，有 |a_n| > A$$

Def 1. 无穷大量一定无界，反之不成立。

tips: (1,0,2,0,……)

Def 2. 从无界数列中必然可以取出一个无穷大的子列。

tips: 显然。

Def 3. 如果说{an}是发散数列，那么他的任何子列都有{a_{kn}} 必发散。

Def 4. 若 {an} {bn} 都是发散数列，那么他们的和或者乘积也是发散的。

Def 5. 若 {an} 是无穷大， 那么其倒数必然是无穷小。

1.5 单调数列

Def 1. 单调有界数列必有极限。

tips: 见书P26（有点繁琐

Def 2. (闭区间套定理)

$$\displaystyle 设 I_n = [a_n,b_n] 是一列闭区间，满足$$

$$\displaystyle (1): [a_1,b_1] \supset [a_2,b_2] \supset \cdots \supset [a_n,b_n]$$

$$\displaystyle (2): b_n - a_n \rightarrow 0 (n\rightarrow \infty)$$

$$\displaystyle 那么存在唯一的一点a \in [a_n,b_n],n = 1,2,\cdots,(a\in\cap [a_n,b_n])$$

1.6 自然对数的底数e

讨论数列 {e_n} 和 {s_n} 之间的关系，其中S_n为 e 的泰勒展开

e 是无理数

1.7 基本列和Cauchy收敛原理

{a_n}是个基本列：

$$\displaystyle 对\forall \epsilon > 0, \exists N,有n,m > N,都有|a_n - a_m| < \epsilon $$

或者

$$\displaystyle 对\forall \epsilon > 0, \exists N,有n > N,都有|a_{n + p} - a_n| < \epsilon,对\forall p \in N^*均成立 $$

Def 1.(Bolzano-Weierstrass定理) 从任何数列中必能取出单调的子列。（也叫列紧性定理）

Def 2. 数列{an}收敛的充分必要条件是：{an}是一个基本列。

1.8 上确界和下确界

数集 (不是数列)，eg: E = (0,1)

$$\displaystyle \begin{cases} \forall x \in E,x \leq B \ \forall x \in E,x \geq A\end{cases}$$

Def 1. 设 E 是一个非空的有上界的集合，若有 α，β满足

$$\displaystyle Case 1: \forall x \in E , x\leq \beta$$

$$\displaystyle Case 2: \forall \epsilon > 0, \exists x_\epsilon \in E , x_\epsilon > \beta - \epsilon$$

那么称 β 是 E 的上确界，认为 β = sup E (supremum)

Def 2. 设 E 是一个非空的有下界的集合，若存在 α 满足

$$\displaystyle Case 1: \forall x \in E , x\geq \alpha$$

$$\displaystyle Case 2: \forall \epsilon > 0, \exists y_\epsilon \in E , y_\epsilon < \alpha + \epsilon$$

那么称 α 是 E 的上确界，认为 α = inf E (infimum)

Def 3. 有上界的非空集合必有上确界

**tips:**（二分法）。

Def 4. 有下界的非空集合必有下确界

tips: 同上。

Def 5.

$$\displaystyle \begin{cases} 若 E 无上界，规定 supE = +\infty \ 若 E 无下界，规定 infE = -\infty \end{cases}$$

1.9 有限覆盖定理

一族开区间

$$\kappa = {I_\lambda,\lambda \in A}$$

其中 I_A为开区间。

$$\kappa = {I_\lambda}覆盖了E：\forall x \in E,\exists I_\lambda \in \kappa,使得x \in I_\lambda$$

def 1:(Heine-Borel) 设有限闭区间 [a,b] 被一族开区间所覆盖，那么必然可以从中取出有限的开区间，它们仍然构成 [a,b] 的一个开覆盖。

tips: 反证 + 二分。

特别得，该定理有限区间不能为无穷区间。

$$eg : {(0,n)}_{n =1,2,\cdots},区间[1,+\infty]$$

1.10 上极限和下极限

Def 1: {a_n} 有界，那么子列收敛于 l （称之为一个极限点）

Def 2:

$$约定 E = {a_n 的所有极限点的全体}$$

$$a^* = sup E, a_* = inf E$$

$$\displaystyle \begin{cases} a^* = \lim_{n \to \infty} sup (a_n) ,上极限 \ a_* = \lim_{n \to \infty} inf (a_n) ,下极限 \end{cases}$$

Def 3:

前缀和

截断数组（acwing）

题面：

给定一个长度为 n 的数组 a

现在，要将数组从中间截断，得到三个 非空 子数组。

要求，三个子数组内各元素之和都相等，问有几种截法。

数据范围：

$$1 \leq n \leq 10^5 , -10000 \leq a_i \leq 10000$$

题解：

如果整个数组之和 除不尽3，那么一定分割不成功，如果现在的段刚好为sum / 3那么说明这一段能分出来，用 a去记录可以分成几段，最后在找一个位置，使得sum / 3 * 2的位置即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

void JiuCherish(){
   int n;
   std::cin >> n;
   i64 sum = 0;
   for(int i=1;i<=n;i++) {
      std::cin >> a[i];
      b[i] = b[i - 1] + a[i];
      sum += a[i];
   }
   int aa = 0;
   i64 ans = 0;
   if(sum % 3) {
      std::cout << 0 << endl;
      return;
   } else {
      for(int i=1;i<n;i++) {
         if(b[i] == sum / 3 * 2)  ans += aa;
         if(b[i] == sum / 3) aa++;
      }
      std::cout << ans << endl;
   }
}

前缀和

题面：

给你一个长度为 n 的整数序列。

在进行 m 次询问，每次询问输入一对l,r

问：区间[l,r]的和。

数据范围：

$$1 \leq l \leq r\leq n$$

$$1 \leq n,m \leq 100000$$

$$-1000 \leq a_i \leq 1000$$

题解：

模板题。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13

void JiuCherish(){
    int n,q;
    std::cin >> n >> q;
    for(int i=1;i<=n;i++) {
        std::cin >> a[i];
        b[i] = b[i - 1] + a[i];
    }
    while(q--) {
        int l,r;
        std::cin >> l >> r;
        std::cout << b[r] - b[l - 1] << endl;
    }
}

子矩阵的和

题意：

给n 行 m 列的整数矩阵，在给 q次询问

问 x1,y1,x2,y2 所围成的矩阵数值之和是多少？

数据范围

$$1 \leq n,m \leq 1000$$

$$1 \leq q \leq 200000$$

$$1 \leq x_1 \leq x_2 \leq n$$

$$1 \leq y_1 \leq y_2 \leq m$$

$$-1000 \leq a_i \leq 1000$$

题解：

模板题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

void JiuCherish(){
    int n,m,q;
    std::cin >> n >> m >> q;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            std::cin >> a[i][j];
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + a[i][j];
        }
    }
    while(q--) {
        int x1,x2,y1,y2;
        std::cin >> x1 >> y1 >> x2 >> y2;
        std::cout << b[x2][y2] - b[x2][y1 - 1] - b[x1 - 1][y2] + b[x1 - 1][y1 - 1] << endl;
    }
}

k倍区间

题意：

给长度为 n 的数列，约定 k 倍区间表示 数列区间[i,j]的和是 k 的倍数。

问数列中有几个 k 被区间。

数据范围

$$1 \leq n,k \leq 100000$$

$$1 \leq a_i \leq 100000$$

题解：

只需要知道

$$(a + b)mod c 等价于 a modc + bmod c$$

即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void JiuCherish(){
    int n,k;
    std::cin >> n >> k;
    i64 sum = 0;
    for(int i=1;i<=n;i++) {
        std::cin >> a[i];
        b[i] = b[i - 1] + a[i];
    }
    res[0] = 1;
    for(int i=1;i<=n;i++) {
        sum += res[b[i] % k];
        res[b[i] % k]++;
    }
    std::cout << sum << endl;
}

差分

改变数组元素

给定一个空数组 V 和一个整数数组a。

现在对数组V进行 n 次操作

第 i 次操作的具体流程如下：

1. 从数组 V 尾部插入整数 0。
2. 将位于数组 V 末尾的 ai 个元素都变为 1（已经是 1 的不予理会）。

注意：

• ai 可能为 0，即不做任何改变。
• ai 可能大于目前数组 V 所包含的元素个数，此时视为将数组内所有元素变为 1。

请你输出所有操作完成后的数组 V。

数据范围

$$1 \leq T \leq 20000$$

$$1 \leq n \leq 2 \times 10^5$$

$$0 \leq a_i \leq n$$

保证 $$\sum T * n < 2 \times 10^5$$

题解：

维护区间，用当前数是k，就把该数和该数前面k个数变成1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

void JiuCherish(){
    int n;
    std::cin >> n;
    for(int i=1;i<=n;i++) std::cin >> a[i];
    int l = 1e9;
    std::vector<int> ans;
    for(int i=n;i>=1;i--) {
        l = std::min(l,i - a[i] + 1);
        if(l <= i) {
            ans.pb(1);
        } else {
            ans.pb(0);
        }
    }
    std::reverse(ans.begin(),ans.end());
    for(auto x : ans) std::cout << x << " ";
    std::cout << endl;
}

差分

给你一个 长度为 n 的数组

你有 m 次操作，包括了 l,r,c，表示将数组 [l,r] 之间的每个数都加上 c

请你输出进行完成所有操作后的数组。

数据范围：

$$1 \leq l \leq r\leq n$$

$$1 \leq n,m \leq 100000$$

$$-1000 \leq c \leq 1000$$

$$-1000 \leq a_i \leq 1000$$

题解

模板

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

void JiuCherish(){
    int n,q;
    std::cin >> n >> q;
    for(int i=1;i<=n;i++) {
        std::cin >> a[i];
        b[i] = a[i] - a[i - 1];
    }
    while(q--) {
        int l,r,x;
        std::cin >> l >> r >> x;
        b[l] += x;
        b[r + 1] -= x;
    }
    int x = 0;
    for(int i=1;i<=n;i++) {
        x += b[i];
        std::cout << x << " ";
    }
}

差分矩阵

输入一个 n 行 m 列的整数矩阵，再输入 q 个操作，每个操作包含五个整数 x1,y1,x2,y2,c，其中 (x1,y1)(x1,y1) 和 (x2,y2)(x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。

每个操作都要将选中的子矩阵中的每个元素的值加上 c。

请你将进行完所有操作后的矩阵输出。

数据范围：

$$1 \leq n,m \leq 1000$$

$$1 \leq q \leq 100000$$

$$1 \leq x_1 \leq x_2\leq n$$

$$1 \leq y_1 \leq y_2\leq m$$

$$-1000 \leq c \leq 1000$$

$$-1000 \leq a_i \leq 1000$$

题解

模板

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

void JiuCherish(){
    int n,m,q;
    std::cin >> n >> m >> q;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            std::cin >> res[i][j];
            ans[i][j] = -res[i - 1][j] - res[i][j - 1] + res[i - 1][j - 1] + res[i][j];
        }
    }
    while(q--) {
      int x1,x2,y1,y2,val;
      std::cin >> x1 >> y1 >> x2 >> y2 >> val;
      x2++;
      y2++;
      ans[x1][y1] += val;
      ans[x1][y2] -= val;
      ans[x2][y2] += val;
      ans[x2][y1] -= val;
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            res[i][j] = res[i - 1][j] + res[i][j - 1] - res[i - 1][j - 1] + ans[i][j];
            std::cout << res[i][j] << " ";
        }
        std::cout << endl;
    }
}

增减序列

给定一个长度为 n 的数列，每次可以选一个区间 [l,r] 使下标在这个区间内的数都加一或者都减一。

求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。

数据范围：

$$0 < n \leq 10^5$$

$$0 \leq a_i < 2147483648$$

题解：

找到中位数即可。

最少操作次数就是最少的pos或neg 加上这两个差值的绝对值。

结果就是：差值绝对值+1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void JiuCherish(){
    int n;
    std::cin >> n;
    for(int i=1;i<=n;i++) {
        std::cin >> a[i];
        b[i] = a[i] - a[i - 1];
    }
    i64 pos = 0,neg = 0;
    for(int i=2;i<=n;i++) {
        if(b[i] > 0) pos += b[i];
        else neg -= b[i];
    }
    std::cout << std::min(pos,neg) + std::abs(pos - neg) << endl;
    std::cout << std::abs(pos - neg) + 1 << endl;
}

二分

数的范围

给一个升序的长度为 n 的整数数组，以及 q 个查询。

对于每个查询，返回一个元素 k 的起始位置和终止位置（从 0 开始计数）

如果数组中不存在该元素，返回两个 -1 -1。

数据范围：

$$1 \leq n \leq 100000$$

$$1 \leq q \leq 10000$$

$$1 \leq k \leq 10000$$

题解：

第一次二分看看左边界是否能找到数，找不到直接结束。

输出第一次左边界找到的。

第二次二分找到最右边是否能找到数。

代码

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

void JiuCherish(){
    int n,q;
    std::cin >> n >> q;
    for(int i=0;i<n;i++) std::cin >> a[i];
    while(q--) {
        int x;
        std::cin >> x;
        int l = 0,r = n - 1;
        int mid = 0;
        while(l < r) {
            mid = l + r >> 1;
            if(a[mid] >= x) r = mid;
            else l = mid + 1;
        }
        if(a[l] != x) {
            std::cout << "-1 -1" << endl;
            continue;
        }
        std::cout << l <<" ";
        l = 0,r = n - 1;
        while(l < r) {
            mid = l + r + 1 >> 1;
            if(a[mid] <= x) l = mid;
            else r = mid - 1;
        }        
        std::cout << l << endl;
    }
}

四平方和

求一个数，他恰好能写成4个正整数的平方和，并按顺序输出。

数据范围

$$0 < N < 5 \times 10 ^ 6$$

题解：

先预处理出一对能求和的，模拟成哈希表存值，在暴力枚举a和b，通过查询数组发现如果存在的话，那么说明是一定有解的。

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

void JiuCherish(){
   int n;
   std::cin >> n;
   memset(R,-1,sizeof R);
   for(int i=0;i * i <= n;i++) {
      for(int j=i;j * j + i * i <= n;j++) {
         int now = j * j + i * i;
         if(R[now] == -1) {
            R[now] = i;
         }
      }
   }
   for(int i=0;i*i<=n;i++) {
      for(int j=i;j*j + i*i <= n;j++) {
         int last = n - (j * j + i * i);
         if(R[last] == -1) {
            continue;
         }
         int c = R[last];
         int d = sqrt(last - c * c);
         std::cout << i << " " << j << " " << c << " " << d << endl;
         return;
      }
   }
}

分巧克力

儿童节那天有 K 位小朋友到小明家做客。

小明拿出了珍藏的巧克力招待小朋友们。

小明一共有 N 块巧克力，其中第 i 块是 Hi×Wi 的方格组成的长方形。

为了公平起见，小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。

切出的巧克力需要满足：

1. 形状是正方形，边长是整数
2. 大小相同

例如一块 6×5 的巧克力可以切出 6 块 2×2 的巧克力或者 2 块 3×3 的巧克力。

当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？

数据范围

$$1 \leq n,k \leq 10^5$$

$$1 \leq H_i,W_i \leq 10^5$$

题解：

直接二分就好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

bool check(int x,int n,int k) {
    int res = 0;
    for(int i=1;i<=n;i++) {
        res += (h[i] / x) * (w[i] / x);
        if(res >= k) return true;
    }
    return res >= k;
}

void JiuCherish(){
    int n,k;
    std::cin >> n >> k;
    for(int i=1;i<=n;i++) std::cin >> h[i] >> w[i];
    int l = 0,r = 1e5 + 10;
    while(l < r) {
        int mid = l + r + 1 >> 1;
        if(check(mid,n,k)) l = mid;
        else r = mid - 1;
    }
    std::cout << l << endl;
}

双指针

字符串删减

给定一个由 n 个小写字母构成的字符串。

现在，需要删掉其中的一些字母，使得字符串中不存在连续三个或三个以上的 x。

请问，最少需要删掉多少个字母？

如果字符串本来就不存在连续的三个或三个以上 x，则无需删掉任何字母。

数据范围

$$3 \leq n \leq 100$$

题解：

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void JiuCherish(){
    int n;
    std::string s;
    std::cin >> n >> s;
    int cnt = 0;
    for(int i=0;i<n;i++) {
        int j = i;
        while(s[j] == s[i] && s[i] == 'x' && j < n) j++;
        if(j - i > 2) {
            cnt += (j - i - 2);
        }
        i = j;
    }
    std::cout << cnt << endl;
}

最长连续不重复子序列

给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

数据范围

$$1 \leq n \leq 10^5$$

1
2
3
4
5
6
7
8
9
10
11
12

void JiuCherish(){
    int n;
    std::cin >> n;
    for(int i=1;i<=n;i++) std::cin >> a[i];
    int ans = 0;
    for(int i=1,j=1;i<=n;i++) {
        b[a[i]]++;
        while(b[a[i]] > 1) --b[a[j++]];
        ans = std::max(ans,i - j + 1);
    }
    std::cout << ans << endl;
}

数组元素的目标和

给定两个升序排序的有序数组 A 和 B，以及一个目标值 x。

数组下标从 0 开始。

请你求出满足 A[i] + B[j] = x 的数对 (i,j) 。

数据保证有唯一解。

数据范围

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

void JiuCherish(){
    int n,m,x;
    std::cin >> n >> m >> x;
    for(int i=1;i<=n;i++) std::cin >> a[i];
    for(int i=1;i<=m;i++) std::cin >> b[i];

    for(int i=1;i<=n;i++) {
        int y = x - a[i];
        int l = 1,r = m;
        while(l <= r) {
            int mid = l + r >> 1;
            if(b[mid] == y) {
                std::cout << i - 1 << " " << mid - 1 << endl;
                return;
            } else if(b[mid] > y) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
    }
}

判断子序列

给定一个长度为 n 的整数序列 a1,a2,…,an 以及一个长度为 m 的整数序列 b1,b2,…,bm。

请你判断 a 序列是否为 b 序列的子序列。

子序列指序列的一部分项按原有次序排列而得的序列，例如序列 {a1,a3,a5} 是序列 {a1,a2,a3,a4,a5} 的一个子序列。

数据范围

$$1 \leq n \leq m \leq 10^5$$

$$-10^9 \leq a_i,b_i \leq 10^9$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void JiuCherish(){
    int n,m;
    std::cin >> n >> m;
    for(int i=1;i<=n;i++) std::cin >> a[i];
    for(int i=1;i<=m;i++) std::cin >> b[i];
    int now = 1;
    for(int i=1;i<=m;) {
        if(a[now] == b[i] && now < n + 1) {
            now++;
            i++;
        } else {
            i++;
        }
    }
    std::cout << (now == n + 1 ? "Yes" : "No") << endl;
}

日志统计

小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 N 行。

其中每一行的格式是：

1

ts id  

表示在 ts 时刻编号 id 的帖子收到一个”赞”。

现在小明想统计有哪些帖子曾经是”热帖”。

如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞，小明就认为这个帖子曾是”热帖”。

具体来说，如果存在某个时刻 T 满足该帖在 [T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 K 个赞，该帖就曾是”热帖”。

给定日志，请你帮助小明统计出所有曾是”热帖”的帖子编号。

数据范围

$$1 \leq K \leq N \leq 10^5 $$

$$0 \leq ts,id \leq 10^5$$

$$1 \leq D \leq 10000$$

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

struct Node {
    int x,y;
}t[MAXN];

bool cmp(Node a,Node b) {
    if(a.y == b.y) return a.x < b.x;
    return a.y < b.y;
}
void JiuCherish(){
    int n,d,k;
    std::cin >> n >> d >> k;
    for(int i=0;i<n;i++) std::cin >> t[i].x >> t[i].y;

    std::sort(t,t + n,cmp);
    for(int i=0,j=0;i<n;i++) {
        int now = t[i].y;
        cnt[now]++;
        while(abs(t[i].x - t[j].x) >= d && j < n) {
            cnt[t[j].y]--;
            j++;
        }
        if(cnt[t[i].y] >= k) {
            ans[t[i].y] = true;
        }
    }
    for(int i=0;i<=100005;i++) {
        if(ans[i]) std::cout << i << endl;
    }
}

难度：

签到：A

简单：CDGH

中等偏下：EFI

中等偏上：BJKL