Vibe Coding.
乍一看被吓到了,60%难度只有一个带权并查集.

User

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

以下是一个有着一百万用户的忙碌电话系统的部分记录：

编号	呼叫	接听
1	200007	100053
2	600183	500439
3	600863	701497
…	…	…
编号为n的记录中，呼叫者的电话号码是Caller(n) = S_{2n-1}，接听者的电话号码是Called(n) = S_{2n}，其中S_{1,2,3,…}来自于所谓“延迟斐波那契随机数生成器”：

对于1 ≤ k ≤ 55，Sk = [100003 - 200003k + 300007k^3] (modulo 1000000)
对于56 ≤ k，Sk = [S_{k-24} + S_{k-55}] (modulo 1000000)

如果Caller(n) = Called(n)，那么我们认为呼叫者拨错了号码，呼叫失败；否则我们认为呼叫成功。

根据这份记录，如果X曾经呼叫过Y或者Y呼叫过X，则我们认为这两个电话用户X和Y是朋友。同样的，如果X是Y的朋友，Y是Z的朋友，那么我们说X是Z的朋友的朋友；我们可以同理组成更长的“朋友”链。

首相的电话号码是524287。在多少次呼叫成功（不计呼叫失败）之后，99%的用户（包括首相）将会成为首相的朋友，或是朋友的朋友，或是朋友的朋友的朋友……？

我的思路:维护一个带权并查集,每次打电话先检查两个人在不在一个集合,如果在那就忽略,不在就合并ab,每一次打完电话之后检查524287这个集合的大小是不是99%.
我给你一个并查集板子,请使用c++写代码.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct dsu{
	int *ko,n;
	dsu(int num=1000000):n(num+5){
		ko=new int[num+5];
	}
	void init(int num=-1){
		if(num==-1)num=n;
		for(int i=0;i<num;++i){
			ko[i]=i;
		}
	}
	int ffind(int num){
		return ko[num]==num?num:ko[num]=ffind(ko[num]);
	}
	void uunion(int a,int b){//<--
		ko[ffind(b)]=ffind(a);
	}//b被a合并 
	char isUnion(int a,int b){
		return (ffind(a)==ffind(b))?1:0;
	}
};

DeepSeek

1
我来帮你实现这个问题的解决方案。根据你的思路，使用并查集来维护朋友关系，并在每次成功呼叫后检查首相所在集合的大小是否达到总用户数的99%。
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <iostream>
#include <vector>
#include <cstdint>

using namespace std;

// 并查集结构体（根据你提供的模板）
struct dsu {
    int *parent, *size, n;
    
    dsu(int num = 1000000) : n(num) {
        parent = new int[num];
        size = new int[num];
        init();
    }
    
    ~dsu() {
        delete[] parent;
        delete[] size;
    }
    
    void init() {
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
            size[i] = 1;  // 每个集合初始大小为1
        }
    }
    
    int ffind(int x) {
        if (parent[x] != x) {
            parent[x] = ffind(parent[x]);  // 路径压缩
        }
        return parent[x];
    }
    
    void uunion(int a, int b) {
        int rootA = ffind(a);
        int rootB = ffind(b);
        
        if (rootA == rootB) return;
        
        // 按大小合并，小的合并到大的
        if (size[rootA] < size[rootB]) {
            parent[rootA] = rootB;
            size[rootB] += size[rootA];
        } else {
            parent[rootB] = rootA;
            size[rootA] += size[rootB];
        }
    }
    
    bool isUnion(int a, int b) {
        return ffind(a) == ffind(b);
    }
    
    int getSize(int x) {
        return size[ffind(x)];
    }
};

// 延迟斐波那契随机数生成器
class LaggedFibonacciGenerator {
private:
    vector<long long> S;
    int k;
    
public:
    LaggedFibonacciGenerator() {
        S.resize(56, 0);  // 使用1-based索引
        k = 0;
    }
    
    long long next() {
        k++;
        
        if (k <= 55) {
            long long k3 = (long long)k * k * k;
            S[k] = (100003LL - 200003LL * k + 300007LL * k3) % 1000000LL;
        } else {
            // 确保有足够的元素
            if (k >= S.size()) {
                S.push_back(0);
            }
            S[k] = (S[k - 24] + S[k - 55]) % 1000000LL;
        }
        
        return S[k];
    }
    
    void reset() {
        S.clear();
        S.resize(56, 0);
        k = 0;
    }
};

int main() {
    const int TOTAL_USERS = 1000000;
    const int PRIME_MINISTER = 524287;
    const double TARGET_PERCENTAGE = 0.99;
    const int TARGET_COUNT = TOTAL_USERS * TARGET_PERCENTAGE;
    
    dsu uf(TOTAL_USERS);
    LaggedFibonacciGenerator generator;
    
    int successfulCalls = 0;
    int currentCall = 0;
    
    // 用于去重，防止重复初始化
    bool initialized = false;
    
    while (true) {
        currentCall++;
        
        // 获取呼叫者和接听者
        long long caller = generator.next();  // S_{2n-1}
        long long called = generator.next();  // S_{2n}
        
        // 如果呼叫者和接听者相同，呼叫失败
        if (caller == called) {
            continue;
        }
        
        successfulCalls++;
        
        // 将两个用户合并到同一个朋友圈
        uf.uunion(caller, called);
        
        // 检查首相所在集合的大小
        int pmGroupSize = uf.getSize(PRIME_MINISTER);
        
        // 输出进度（可选，每10000次成功呼叫输出一次）
        if (successfulCalls % 10000 == 0) {
            cout << "成功呼叫次数: " << successfulCalls 
                 << ", 首相朋友圈大小: " << pmGroupSize 
                 << " (" << (100.0 * pmGroupSize / TOTAL_USERS) << "%)" << endl;
        }
        
        // 检查是否达到目标
        if (pmGroupSize >= TARGET_COUNT) {
            cout << "\n达到目标!" << endl;
            cout << "成功呼叫次数: " << successfulCalls << endl;
            cout << "首相朋友圈大小: " << pmGroupSize << endl;
            cout << "占总用户比例: " << (100.0 * pmGroupSize / TOTAL_USERS) << "%" << endl;
            break;
        }
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
## 关键点说明：

1. **并查集优化**：
   - 添加了`size`数组来跟踪每个集合的大小
   - 实现了按大小合并的优化策略
   - 在`getSize()`方法中可以快速获取首相所在集合的大小

2. **延迟斐波那契生成器**：
   - 实现了题目中描述的随机数生成器
   - 使用`long long`防止整数溢出
   - 正确实现了递推关系

3. **主逻辑**：
   - 只有当呼叫者和接听者不同时才认为是成功呼叫
   - 每次成功呼叫后合并两个用户的集合
   - 检查首相所在集合的大小是否达到总用户数的99%
   - 添加了进度显示，可以观察程序运行过程

4. **效率考虑**：
   - 并查集操作的时间复杂度接近O(1)
   - 每次只检查首相所在集合的大小，不需要遍历所有用户
   - 内存使用合理（约8MB用于并查集）

这个程序会持续运行，直到首相的朋友圈达到总用户数的99%，然后输出所需的成功呼叫次数。根据题目难度，这个次数可能会比较大，程序需要运行一段时间。

fun fact

  1. 降智之后的GPT给的代码RE了,原因不明.

  2. Flu认为ds的v模型给的废话很多,总是”生成测试代码”之类的,一个简单需求能返回一堆代码吓死人.
    但是写一些小代码挺好使的.
    GPT和阶么奈适合写一些难的代码.