NOIP2019模拟赛（十）06.02

(Updated: )
oi
, , , , ,

NOIP2019模拟赛（十）06.02

A. transfer

题意

有$n$个小孩，他们会进行$t$轮游戏。一开始，鲜花在第一个孩子手里，每轮游戏持有鲜花的小孩可以把鲜花传递给除了自己以外的任意一个小孩。那么，一共有多少种传递方法，可以让鲜花在游戏结束时回到第一个小孩上呢？ 对于$100$%的数据，$n,t \leq 10^{18}$

思路

每一轮，每个小孩都可以传递给另外一个小孩，那么就有$n-1$种传递方法。 有$t$轮，所以总共有$(n-1)^t$种传递方法。 每种传递方法的概率都是相同的，所以传递给第一个孩子的可能性为$\frac{(n-1)^t}{n}$。 注意，$n,t$的范围都很大，所以需要快速幂$+$乘法逆元。 对于$NOIPPJ$等级的我，只需要明白：费马小定理：当$ p $为素数时，$ a^{p-1}=1 (mod p) $。那么$ a*a^{p-2}=1 (mod p) $。即可。

Code

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
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
#define mod 1000000007
using namespace std;
int read(){
    char ch=getchar();int res=0,f=1;
    while(ch<'0'ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
    return res*f;
}
void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x<10) putchar(x+'0');
    else write(x/10),putchar(x%10+'0');
}
int n,t;
int fpow(int a,int b){//快速幂
    int res=1;
    while(b){
        if(b%2==1) res=(res*a)%mod;
        a=(a*a)%mod,b>>=1;
    }
    return res;
}
int ans;
signed main(){
    n=read();t=read();n%=mod;
    if(t==1){
        puts("0");
        return 0;
    }
    ans=fpow(n-1,t-1);
    if(t%2==1) ans=((ans-1)*(n-1))%mod;//分奇偶讨论
    else ans=((ans+1)*(n-1))%mod;
    ans=(ans+mod)%mod;
    ans=ans*fpow(n,mod-2)%mod;//乘法逆元
    write(ans);
    return 0;
}

B. minecraft

题意

不要问我为什么这么懒就放一个pdf

思路

首先$O(n^2)$求出每个点到其他点的距离：$sqrt({(x_1-x_2)}^2+{(y_1-y_2)}^2)-(z_1+z_2)$ 然后跑一遍最短路就好了。 但是二分答案来check也行。

Code

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
#include<bits/stdc++.h>
#define eps 1e-8
#define int long long
#define sqr(x) ((x)*(x))
using namespace std;
int read(){
    char ch=getchar();int res=0,f=1;
    while(ch<'0'ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
    return res*f;
}
void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x<10) putchar(x+'0');
    else write(x/10),putchar(x%10+'0');
}
int n,s,t,vis[5010];
double f[5010][5010],Max,ans;
map<string,int> mp;
string tmp;
struct node{
    int x,y,z;
}a[5010];
double dist(int i,int j){
    return ((double)sqrt((double)((double)sqr(a[i].x-a[j].x)+(double)sqr(a[i].y-a[j].y)))-(double)(a[i].z+a[j].z));
}
queue<int> q;
bool check(double x){
    memset(vis,0,sizeof(vis));
    while(!q.empty()) q.pop();
    q.push(s);vis[s]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=1;i<=n;i++){
            if(vis[i]==0&&f[u][i]<=x){
                q.push(i);
                vis[i]=1;
                if(i==t) return 1;
            }
        }
    }
    return 0;
}
signed main(){
    n=read();
    for(int x,y,z,i=1;i<=n;i++){
        cin>>tmp;a[i].x=read();a[i].y=read();a[i].z=read();
        mp[tmp]=i;
    }
    cin>>tmp;s=mp[tmp];
    cin>>tmp;t=mp[tmp];
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            f[i][j]=f[j][i]=((dist(i,j)<0.0)?0.0:dist(i,j));
            Max=max(Max,f[i][j]);
        }
    }
    memset(vis,0,sizeof(vis));
    double l=0.0,r=Max,mid;
    while(r-l>=eps){
        mid=(l+r)/2.0;
        if(check(mid)) ans=mid,r=mid-eps;
        else l=mid+eps;
    }
    printf("%.6lf\n",ans);
    return 0;
}

C. rewrite

题意

对于一片森林，有两个操作： 1. 输入$x,y$把$ x,y $两点连通，并且把他们的权值修改为$\frac{⌊Vx+Vy⌋}{2}$，若$x,y$已经连通，则忽略此操作。 2.查询$ x,y $两点之间的唯一路径上有多少种不同的点权，若$x,y $此时还不连通，输出$-1$。

思路

开一个$ 60 $位的二进制，某一位为$ 1 $就表示有这种颜色，然后用线段树维护区间信息就好了，每次合并或者查询就是一个二进制“或”的操作。 当然，用$LCT$与树剖都可以。

Code

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
151
152
153
#include<bits/stdc++.h>
#define int long long
#define MAXN 100010*2
using namespace std;
int read(){
    char ch=getchar();int res=0,f=1;
    while(ch<'0'ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
    return res*f;
}
void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x<10) putchar(x+'0');
    else write(x/10),putchar(x%10+'0');
}
int n,m,op,u,v;
int fa[MAXN];
int getfa(int x){
    return x==fa[x]?x:fa[x]=getfa(fa[x]);
}
class LinkCutTree{
    public:
        struct node{
            int f,c[2],v,xs,tag,xx;
        }t[300010];
        bool Isroot(int x){
            int y=t[x].f;
            return !(t[y].c[0]==xt[y].c[1]==x);
        }
        void Upd(int x){
            t[x].xs=(1ll<<t[x].v)t[t[x].c[0]].xst[t[x].c[1]].xs;
        }
        void Psd(int x){
            if(t[x].tag){
                swap(t[x].c[0],t[x].c[1]);
                if(t[x].c[0])t[t[x].c[0]].tag^=1;
                if(t[x].c[1])t[t[x].c[1]].tag^=1;
                t[x].tag=0;
            }
        }
        void Rotate(int x){
            int y=t[x].f,z=t[y].f;
            Psd(y);
            Psd(x);
            int c=t[y].c[1]==x;
            if(!Isroot(y)){
                int gc=t[z].c[1]==y;
                t[z].c[gc]=x;
            }
            t[x].f=z;
            t[y].c[c]=t[x].c[c^1];
            t[t[x].c[c^1]].f=y;
            t[x].c[c^1]=y;
            t[y].f=x;
            Upd(y);
            Upd(x);
        }
        void Splay(int x){
            Psd(x);
            while(!Isroot(x)){
                int y=t[x].f,z=t[y].f;
                if(Isroot(y))Rotate(x);
                else{
                    Psd(z);
                    Psd(y);
                    int c=t[y].c[1]==x,gc=t[z].c[1]==y;
                    if(c==gc)Rotate(y);
                    else Rotate(x);
                    Rotate(x);
                }
            }
        }
        void Access(int x,int lst){
            if(!x)return;
            Splay(x);
            t[x].c[1]=lst;
            Upd(x);
            Access(t[x].f,x);
        }
        void Makeroot(int x){
            Access(x,0);
            Splay(x);
            t[x].tag^=1;
        }
        void Split(int x,int y){
            Makeroot(x);
            Access(y,0);
            Splay(y);
        }
        int Findroot(int x){
            Access(x,0);
            Splay(x);
            Psd(x);
            while(t[x].c[0]){
                x=t[x].c[0];
                Psd(x);
            }
            Splay(x);
            return x;
        }
        int Link(int x,int y){
            Makeroot(x);
            if(Findroot(y)!=x){
                t[x].f=y;
                return 1;
            }
            return 0;
        }
        void Cut(int x,int y){
            Makeroot(x);
            Psd(x);
            if(Findroot(y)==x&&t[y].f==x&&!t[y].c[0]){
                t[x].c[1]=t[y].f=0;
                Upd(x);
            }
        }
        int Query(int x,int y){
            if(Findroot(x)!=Findroot(y)){
                return -1;
            }
            Split(x,y);
            int tmp=t[y].xs,sum=0;
            while(tmp){
                tmp-=(tmp&-tmp),++sum;
            }
            return sum;
        }
        void Change(int x,int y){
            Splay(x);
            t[x].v=y;
            Upd(x);
        }
}tr;
signed main(){
    n=read();m=read();
    for(int i=1;i<=n;i++) tr.t[i].v=read(),fa[i]=i,tr.Upd(i);
    for(int i=1;i<=m;i++){
        op=read();u=read();v=read();
        if(op==1){
            int tmp=tr.Link(u,v);
            if(tmp==1){
                int Cost=(tr.t[u].v+tr.t[v].v);
                Cost>>=1;
                tr.Change(u,Cost);
                tr.Change(v,Cost);
            }
        }else if(op==2){
            int tmp=tr.Query(u,v);
            write(tmp),putchar('\n');
        }
    }
    return 0;
}