Project Euler 186

发表于 更新于 分类于 阅读次数： 本文字数： 1.2k 阅读时长 ≈ 1 分钟

Project Euler 186

题目

Connectedness of a network

Here are the records from a busy telephone system with one million users:

Rec Nr Caller Called
$1$ $200007$ $100053$
$2$ $600183$ $500439$
$3$ $600863$ $701497$
$\dots$ $\dots$ $\dots$

The telephone number of the caller and the called number in record $n$ are $\text{Caller}(n) = S{2n-1}$ and $\text{Called}(n) = S{2n}$ where $S_{1,2,3,\dots}$ come from the “Lagged Fibonacci Generator”:

For $1 \le k \le 55, S_k = [100003 - 200003k + 300007 k^3] (\text{modulo\ } 1000000)$

For $56 \le k, S_k = [S_k-24 + S_k-55] (\text{modulo\ } 1000000)$

If $\text{Caller(n)} = \text{Called(n)}$ then the user is assumed to have misdialled and the call fails; otherwise the call is successful.

From the start of the records, we say that any pair of users $X$ and $Y$ are friends if $X$ calls $Y$ or vice-versa. Similarly, $X$ is a friend of a friend of $Z$ if $X$ is a friend of $Y$ and $Y$ is a friend of $Z$; and so on for longer chains.

The Prime Minister’s phone number is $524287$. After how many successful calls, not counting misdials, will $99\%$ of the users (including the PM) be a friend, or a friend of a friend etc., of the Prime Minister?

并查集

并查集：用于高效处理一些不相交集合的数据结构。一般有两个操作：合并两个集合；查询两个元素是否在同一个集合中。

可以通过优化将并查集这两种单次操作优化到$O(\alpha(n))$级别，其中$\alpha(n)$是反阿克曼函数（一个增长速率非常接近于零的函数）。

解决方案

本题为并查集的模板题，直接用并查集数据结构实现。

代码中需要维护每个集合的大小。为了避免错误，只有两个元素不属于同一个集合时才需要合并。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000000,P=524287,A=N/100*99;
const int M=N*5;
int fa[N],sz[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x,int y){
    int u=find(x),v=find(y);
    if(u!=v){
        fa[u]=v;
        sz[v]+=sz[u];
    }
}
int s[M];
int main(){
    int cnt=0,ans=0;
    for(int i=0;i<N;i++)
        fa[i]=i,sz[i]=1;
    for(int i=1;i<=55;i++)
        s[i]= (1ll * 300007 * i * i * i + 100003 - 200003 * i) % N;
    for(int i=56;i<M;i++)
        s[i]= (s[i - 24] + s[i - 55]) % N;
    for(int i=2;i<M;i+=2){
        if(s[i] == s[i - 1]) ++cnt;
        else{
            merge(s[i], s[i - 1]);
            if(sz[find(P)]>=A){
                ans=i/2-cnt;
                break;
            }
        }
    }
    printf("%d\n",ans);
}