【题解】10-3提高组模拟

握草，这四题我都不会，可以重开了

A.[蓝桥杯 2020 国 ABC] 皮亚诺曲线距离

lnk

（🏀🍵最质量的一集）

这个是分治，然后把两点到原点的距离相减就得到了

// Problem:Luogu P8730 [蓝桥杯 2020 国 ABC] 皮亚诺曲线距离

#include<bits/stdc++.h>
using namespace std;
#define int long long
int qpow(int a,int b)
{
	if(b==0)return 1;
	int t=qpow(a,b/2);
	if(b%2==0)return t*t;
	else return t*t*a;
}
int dis(int k,int x,int y)
{
	if(k==0)return 1;
	int len=qpow(3,k);
	int step=qpow(3,2*k-2);
	
	if(x<len/3)
	{
		if(y<len/3)return dis(k-1,x,y);
		else if(y<2*len/3)return step+dis(k-1,len/3-1-x,y-len/3);
		else return 2*step+dis(k-1,x,y-2*len/3);
	}
	else if(x<2*len/3)
	{
		if(y<len/3)return 5*step+dis(k-1,x-len/3,len/3-1-y);
		else if(y<2*len/3)return 4*step+dis(k-1,2*len/3-1-x,2*len/3-1-y);
		else return 3*step+dis(k-1,x-len/3,len-1-y);
	}
	else
	{
		if(y<len/3)return 6*step+dis(k-1,x-2*len/3,y);
		else if(y<2*len/3)return 7*step+dis(k-1,len-1-x,y-len/3);
		else return 8*step+dis(k-1,x-2*len/3,y-2*len/3);
	}
}
signed main()
{
	int k,x1,Y1,x2,y2;
	cin>>k>>x1>>Y1>>x2>>y2;
	if(k>=40)k=39;
	cout<<abs(dis(k,x1,Y1)-dis(k,x2,y2));
	return 0;
}

B.[USACO03FALL] Milking Grid（数据加强版）

lnk

这道题是KMP，我还没学，题解还没看懂，就先搁这

C. [Code+#4] 最短路

lnk

这是dijkstra的最短路，就是加了一点料（黑暗料理），要找到异或的规律

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100010;
struct edge
{
	int v,w;
};
vector <edge> g[MAXN];
int n,m,c,s,t;
int dis[MAXN];
bool vis[MAXN];
struct node
{
	int u,dis;
	bool operator <(const node a)const
	{
		return dis>a.dis;
	}
};
priority_queue <node> q;
void dijkstra()
{
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	q.push({s,0});
	while(!q.empty())
	{
		node front=q.top();
		q.pop();
		int u=front.u;
		if(vis[u])continue;
		if(u==t)return ;
		vis[u]=1;
		for(auto tmp:g[u])
		{
			int v=tmp.v,w=tmp.w;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				q.push({v,dis[v]});
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>c;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back({v,w});
	}
	cin>>s>>t;
	for(int i=0;i<=n;i++)
		for(int j=1;j<=n;j<<=1)
			if((i^j)<=n)
				g[i].push_back({i^j,c*j});
	dijkstra();
	cout<<dis[t];
	return 0;
}

D.[LnOI2019] 加特林轮盘赌

这名字看起来就细思鼻孔（谁家用加特林啊）

由于这个是概率DP，比较猎奇，也是先搁这（听说这是NOIP的……放在CSP-S的模拟赛里干啥啊？）

名言：

$\Huge 加特林轮盘赌是一个养生游戏$

// Problem:Luogu P5249 [LnOI2019] 加特林轮盘赌

#include<bits/stdc++.h>
using namespace std;
double f[10010],d[10010],tmp,sum,p,a,b;
void calc(int x)
{
	if(x==1){a=1,tmp=1,b=0;return ;}
	calc(x-1);
	tmp+=(1-p)*a;
	sum+=p*d[x]+(1-p)*b;
	a=(1-p)*a;
	b=p*d[x]+(1-p)*b;
}
int main()
{
	int n,m;
	cin>>p>>n>>m;
	if(p==0)
	{
		if(n>1)cout<<0;
		else cout<<1;
		return 0;
	}
	f[1]=1;
	d[2]=1;
	for(int i=2;i<=n;i++)
	{
		tmp=0.0,sum=0.0;
		calc(i);
		f[1]=(1-sum)/tmp;
		for(int j=2;j<=i;j++)
			f[j]=p*d[j]+(1-p)*f[j-1];
		for(int j=2;j<=i+1;j++)
			d[j]=f[j-1];
	}
	cout<<fixed<<setprecision(8)<<f[m];
	return 0;
}