洛谷P4546 [THUWC2017]在美妙的数学王国中畅游 [LCT，泰勒展开]

传送门

毒瘤出题人卡精度……

思路

看到森林里加边删边，容易想到LCT。

然而LCT上似乎很难实现往一条链里代一个数进去求和，怎么办呢？

善良的出题人在下方给了提示：把奇怪的函数泰勒展开搞成多项式，就很好维护了。

注意到数都很小，精度问题不会太大（那你还被卡），可以直接在\(0\)处泰勒展开更为方便。

然后就做完啦~

代码

要开O2才能过QwQ

#include<bits/stdc++.h>

namespace my_std{

	using namespace std;

	#define pii pair<int,int>

	#define fir first

	#define sec second

	#define MP make_pair

	#define rep(i,x,y) for (int i=(x);i<=(y);i++)

	#define drep(i,x,y) for (int i=(x);i>=(y);i--)

	#define go(x) for (int i=head[x];i;i=edge[i].nxt)

	#define sz 100101

	typedef long long ll;

	template<typename T>

	inline void read(T& t)

	{

		t=0;char f=0,ch=getchar();

		double d=0.1;

		while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();

		while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();

		if(ch=='.')

		{

			ch=getchar();

			while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();

		}

		t=(f?-t:t);

	}

	template<typename T,typename... Args>

	inline void read(T& t,Args&... args){read(t); read(args...);}

	void file()

	{

		#ifndef ONLINE_JUDGE

		freopen("a.txt","r",stdin);

		#endif

	}

//	inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}

}

using namespace my_std;

typedef long double db;

#define B 20

namespace LCT

{

	int fa[sz],ch[sz][2];

	db sum[sz][B+5],a[sz][B+5];

	bool tag[sz];

	#define ls ch[x][0]

	#define rs ch[x][1]

	#define I inline

	I bool get(int x){return ch[fa[x]][1]==x;}

	I bool nroot(int x){return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}

	I void rev(int x){tag[x]^=1;swap(ls,rs);}

	I void pushup(int x){rep(i,0,B) sum[x][i]=sum[ls][i]+sum[rs][i]+a[x][i];}

	I void pushdown(int x){ if (!x||!tag[x]) return; rev(ls); rev(rs); tag[x]=0; }

	I void rotate(int x)

	{

		int y=fa[x],z=fa[y],k=get(x),w=ch[x][!k];

		if (nroot(y)) ch[z][get(y)]=x;ch[x][!k]=y;ch[y][k]=w;

		if (w) fa[w]=y;fa[y]=x;fa[x]=z;

		pushup(y);pushup(x);

	}

	void Pushdown(int x){if (nroot(x)) Pushdown(fa[x]);pushdown(x);}

	I void splay(int x)

	{

		Pushdown(x);

		while (nroot(x))

		{

			int y=fa[x];

			if (nroot(y)) rotate(get(x)==get(y)?y:x);

			rotate(x);

		}

	}

	void access(int x){for (int y=0;x;x=fa[y=x]) splay(x),rs=y,pushup(x);}

	void makeroot(int x){access(x);splay(x);rev(x);}

	int findroot(int x){access(x);splay(x);while (ls) x=ls;return x;}

	void split(int x,int y){makeroot(x);access(y);splay(y);}

	void link(int x,int y){makeroot(x);access(y);splay(y);fa[x]=y;}

	void cut(int x,int y){split(x,y);fa[x]=ch[y][0]=0;pushup(y);}

	#undef ls

	#undef rs

	#undef I

}

db fac[B+5];

void init(){fac[0]=1;rep(i,1,B) fac[i]=fac[i-1]*i;}

void calc(int x,int f,db a,db b)

{

	#define A LCT::a[x]

	if (f==1)

	{

		db Sin=sin(b),Cos=cos(b),t=1;

		rep(n,0,B)

		{

			db ret=t;

			if (n&1) ret*=Cos; else ret*=Sin;

			if (n%4>=2) ret=-ret;

			A[n]=ret;

			t*=a;

		}

	}

	if (f==2)

	{

		db t=exp(b);

		rep(i,0,B) A[i]=t,t*=a;

	}

	if (f==3)

	{

		A[0]=b;A[1]=a;

		rep(i,2,B) A[i]=0;

	}

	LCT::pushup(x);

	#undef A

}

int n,m;

int main()

{

	file();

	init();

	string type;

	int f,x,y;db a,b;

	read(n,m);cin>>type;

	rep(i,1,n) read(f,a,b),calc(i,f,a,b);

	while (m--)

	{

		cin>>type;read(x,y);

		if (type[0]=='a') LCT::link(x+1,y+1);

		else if (type[0]=='d') LCT::cut(x+1,y+1);

		else if (type[0]=='m') ++x,f=y,read(a,b),LCT::makeroot(x),calc(x,f,a,b);

		else

		{

			++x,++y;read(a);

			LCT::makeroot(x);if (LCT::findroot(y)!=x) { puts("unreachable"); continue; }

			LCT::split(x,y);

			db ans=LCT::sum[y][0],t=a;

			rep(i,1,B) ans+=LCT::sum[y][i]*t/fac[i],t*=a;

			printf("%.10Lf\n",ans);

		}

	}

}

巴特西

洛谷P4546 [THUWC2017]在美妙的数学王国中畅游 [LCT，泰勒展开]

思路

代码

最新文章

热门文章