Fork me on GitHub

同余系BFS

发表于 | | 阅读次数:
字数统计: 468

题目链接：P3403 跳楼机

题目意思：给定x,y,z,H,求x,y,z由加法能得到的H以内的数的个数。

体节 ：

乍一看是个数论，心里一想，不对~~~~
于是蒟蒻只能去学了一发同余系BFS（%%%Newuser大佬）
那这题就成了模板啦！
设x为x,y,z最小的，在模x意义下，由i->(i+y)%x，权值为y；由i->(i+z)%x，权值为z。
最后跑一遍最短路或BFS，求出dis[i],那么dis[i]+k*x都能取到，于是此题得解。

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
#include<stdio.h>
#include<iostream>
#include<math.h>
#include<algorithm>
#include<string.h>
#include<queue>
#define ll long long
#define maxn 100005
using namespace std;
ll H;
int P[4];
ll dis[maxn];
bool vis[maxn];
int Last[maxn],Next[maxn<<1],End[maxn<<1],Len[maxn<<1],o;
void ins(int a,int b,int c){
    End[++o]=b;
    Next[o]=Last[a];
    Last[a]=o;
    Len[o]=c;
}
void spfa(int x){
    queue<int>Q;
    memset(dis,0x3f,sizeof(dis));
    dis[x]=1;
    vis[x]=1;
    Q.push(x);
    while(Q.size()){
        int u=Q.front();
        Q.pop();
        vis[u]=0;
        for(int i=Last[u],v;i;i=Next[i]){
            v=End[i];
            if(dis[u]+Len[i]<dis[v]){
                dis[v]=dis[u]+Len[i];
                if(!vis[v]){
                    vis[v]=1;
                    Q.push(v);
                }
            }
        }
    }
}
int main(){
    scanf("%lld%d%d%d",&H,&P[1],&P[2],&P[3]);
    sort(P+1,P+3);
    if(P[1]==1){
        printf("%lld",H);
        return 0;
    }
    for(int i=0;i<P[1];++i){
        int pos2=(i+P[2])%P[1];
        int pos3=(i+P[3])%P[1];
        ins(i,pos2,P[2]),ins(i,pos3,P[3]);
    }
    spfa(1);
    ll ans=0;
    for(int i=0;i<P[1];++i){
        if(dis[i]<=H){
            ans+=(H-dis[i])/P[1]+1;
        }
    }
    printf("%lld",ans);
    return 0;
}

NOIP来了，看似慌得一笔实际慌得一笔，只有%大佬们才能攒人品呢。

1
2
3
while(1){
    if(%hdhd&&%PHD&&%Newuser&&%Washington)RP++;
}
0%
``` ```