NOIP2019模拟赛（十）06.02
Link
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
代码语言：javascript复制#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 '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
代码语言：javascript复制#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 '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("%.6lfn",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
代码语言：javascript复制#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 '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;
}
