算法蓝桥杯-唯一的XX(XX题目)

更好的阅读体验
蓝桥杯题解

题目

问题描述
　　腿铮找2255有点事，但2255太丑了，所以腿铮不知道他的长相。正愁不知道到如何找他的时候，他突然看见计33班围成了一个圈在领微积分试卷。计33班有n个人，其中班长编号为0，其余同学依次按顺时针方向编号。
　　只听见计33小导说“x号同学顺时针方向往后数的第k个的神犇出列（不包括x号同学），领取满分试卷！”。剩下的人继续围成一个小圈。这样一个过程持续了n-1次，那么显然，最后只剩下了一个人。众所周知，2255是个大傻子，门门挂科，不符合满分试卷这一前提条件。通过这样一个过程，腿铮终于找到了2255并血虐了他。
　　求2255的编号是多少。

题解

首先,写了个暴力算法，直接使用vis数组 + 对于每一个k寻找下一个k，果不其然超时了。代码见代码1，
然后，想到使用树状数组做树上的二分，也超时了，分析了一下，时间复杂度是$O(n(logn{)}^2)$能到$3e8$的复杂度，超时很正常。代码见代码2
之后，想着使用hash保存链表的地址，可以实现查找和删除的$O(1)$,后来想了想这样好像是不对的，加上实现复杂，就没有写。
最后，看了个答案，直接让我大跌眼镜，他说$O(n\ast 1000)是1e7$,真不知道他的数学是不是语文老师教的。但是但是，他的代码能过。最后分析了一下，他的代码和他说的是两码事，可能他自己都不知道自己的代码啥意思。说了半天，说使用链表然后找到前一个，直接删除，巴拉巴拉一大堆，然后写了一大堆不会执行的代码。真正有用的其实就一行，就是直接输出了最后一行的第一个数字，然后就行了代码3,能过的代码3。

最后的最后，看了一眼数据，发现k < min(数组长度， 1000),注意这里是小于，再加上题目的描述：剩下的人围城一个圈，注意是剩下的人。那么最后剩下两个人的时候，傻子一定在里面 ，并且k = 1,那么傻子就是输入的最后一个x，因为要把x后面的第一个数字数字去掉。

代码

代码1

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author: Zekun Fu
 * @date: 2022/10/27 23:31
 * @Description: 唯一的傻子
 */
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] vis = new int[n + 1];
        Arrays.fill(vis, 0);
        for (int i = 0; i < n - 1; i++) {
            int x = sc.nextInt();
            int k = sc.nextInt();
            int cnt = 0, j = 0;
            while (cnt < k) {
                j++;
                if (vis[(x + j) % n] == 0) cnt++;
            }
            vis[(x + j) % n] = 1;
        }
        for (int i = 0; i < n; i++) {
            if (vis[i] == 0) {
                System.out.println(i);
                break;
            }
        }
    }
}

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

代码2

• java版本

package lanqiao.imporve;

import java.util.*;

/**
 * @author: Zekun Fu
 * @date: 2022/10/27 23:31
 * @Description: 唯一的傻子
 */
public class WeiYiDeShaZi {
    private static int maxn = (int)1e6 + 5;
    private static int[] c = new int[maxn];
    private static int[] vis = new int[maxn];
    private static Scanner sc = new Scanner(System.in);

    private static int lowbit(int x) {
        return x & - x;
    }
    public static void add(int x, int num) {
        for (int i = x; i < maxn; i += lowbit(i)) {
            c[i] += num;
        }
    }
    public static int sum(int x) {
        int res = 0;
        for (int i = x; i != 0; i -= lowbit(i)) {
            res += c[i];
        }
        return res;
    }
    public static void main(String[] args) {
        int n = sc.nextInt();
        Arrays.fill(vis, 0);
        for (int i = 1; i <= n; i++) add(i, 1);
        for (int i = 0; i < n - 1; i++) {
            int x = sc.nextInt() + 1;
            int k = sc.nextInt();
            int pre = sum(x);
            int behind = sum(n) - pre;
            int l, r;
            if (behind >= k) {
                k += pre;
                l = x + 1;
                r = n + 1; // [x + 1, n]
            } else {
                k -= behind;
                l = 1;
                r = x + 1;   // [1, x]中
            }
            while (l < r) {
                int mid = l + r >> 1;
                if (sum(mid) >= k) { // 一定是左边界
                    r = mid;
                } else l = mid + 1;
            }
            add(l, -1);         // 别忘了更新
            vis[l] = 1;
        }
        for (int i = 1; i <= n; i++) {
            if (vis[i] == 0) {
                System.out.println(i - 1);
                break;
            }
        }
    }
}

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

• cpp版本

#include 
using namespace std;

/**
 * @author: Zekun Fu
 * @date: 2022/10/27 23:31
 * @Description: 唯一的傻子
 */

const int maxn = (int)1e6 + 5;
int c[maxn];
int vis[maxn];
int lowbit(int x) {
    return x & - x;
}
void add(int x, int num) {
    for (int i = x; i < maxn; i += lowbit(i)) {
        c[i] += num;
    }
}
int sum(int x) {
    int res = 0;
    for (int i = x; i != 0; i -= lowbit(i)) {
        res += c[i];
    }
    return res;
}

// 时间复杂度是O(n(logn)^2), 树状数组二分，前缀和二分，但
int main() {
    int n, x, k;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) add(i, 1);
    for (int i = 0; i < n - 1; i++) {
        scanf("%d%d", &x, &k);
        x ++;
        int pre = sum(x);
        int behind = sum(n) - pre;
        int l, r;
        if (behind >= k) {
            k += pre;
            l = x + 1;
            r = n + 1; // [x + 1, n]
        } else {
            k -= behind;
            l = 1;
            r = x + 1;   // [1, x]中
        }
        while (l < r) {
            int mid = l + r >> 1;
            if (sum(mid) >= k) { // 一定是左边界
                r = mid;
            } else l = mid + 1;
        }
        add(l, -1);         // 别忘了更新
        vis[l] = 1;
    }
    for (int i = 1; i <= n; i++) {
        if (vis[i] == 0) {
            cout << i - 1 << endl;
            break;
        }
    }
    return 0;
}

/*

5
0 1
3 2
4 1
3 1

*/

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

代码3

#include 
using namespace std;

/**
 * @author: Zekun Fu
 * @date: 2022/10/27 23:31
 * @Description: 唯一的傻子
 */
int main() {
    int n, x, k;
    scanf("%d", &n);
    //for (int i = 1; i <= n; i++) add(i, 1);
    for (int i = 0; i < n - 1; i++) {
        scanf("%d%d", &x, &k);
        if (i == n - 2) printf("%d\n", x);
    }
    return 0;
}


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