BZOJ5020: [THUWC 2017]在美妙的数学王国中畅游(LCT,泰勒展开,二项式定理)
2024-10-01 18:35:13
Description
数字和数学规律主宰着这个世界。
机器的运转,
生命的消长,
宇宙的进程,
这些神秘而又美妙的过程无不可以用数学的语言展现出来。
这印证了一句古老的名言:
“学好数理化,走遍天下都不怕。”
学渣小R被大学的数学课程虐得生活不能自理,微积分的成绩曾是他在教室里上的课的最低分。然而他的某位陈姓室友却能轻松地在数学考试中得到满分。为了提升自己的数学课成绩,有一天晚上(在他睡觉的时候),他来到了数学王国。
数学王国中,每个人的智商可以用一个属于 [0,1]的实数表示。数学王国中有 n 个城市,编号从 0 到 n−1 ,这些城市由若干座魔法桥连接。每个城市的中心都有一个魔法球,每个魔法球中藏有一道数学题。每个人在做完这道数学题之后都会得到一个在 [0,1] 区间内的分数。一道题可以用一个从 [0,1] 映射到 [0,1]的函数 f(x) 表示。若一个人的智商为 x ,则他做完这道数学题之后会得到 f(x)分。函数 f有三种形式:
正弦函数 sin(ax+b) (a∈[0,1],b∈[0,π],a+b∈[0,π])
指数函数 e^(ax+b) (a∈[−1,1],b∈[−2,0],a+b∈[−2,0])
一次函数 ax+b (a∈[−1,1],b∈[0,1],a+b∈[0,1]
数学王国中的魔法桥会发生变化,有时会有一座魔法桥消失,有时会有一座魔法桥出现。但在任意时刻,只存在至多一条连接任意两个城市的简单路径(即所有城市形成一个森林)。在初始情况下,数学王国中不存在任何的魔法桥。
数学王国的国王拉格朗日很乐意传授小R数学知识,但前提是小R要先回答国王的问题。这些问题具有相同的形式,即一个智商为 x 的人从城市 u 旅行到城市 v(即经过 u 到 v 这条路径上的所有城市,包括 u和 v )且做了所有城市内的数学题后,他所有得分的总和是多少。
Input
第一行两个正整数 n,m 和一个字符串 type 。
表示数学王国中共有 n 座城市,发生了 m 个事件,该数据的类型为 type 。
typet 字符串是为了能让大家更方便地获得部分分,你可能不需要用到这个输入。
其具体含义在【数据范围与提示】中有解释。
接下来 n 行,第 i 行表示初始情况下编号为 i 的城市的魔法球中的函数。
一个魔法用一个整数 f表示函数的类型,两个实数 a,b 表示函数的参数,若
f=1,则函数为 f(x)=sin(ax+b)(a∈[0,1],b∈[0,π],a+b∈[0,π])
f=2,则函数为 f(x)=e^(ax+b)(a∈[−1,1],b∈[−2,0],a+b∈[−2,0])
f=3,则函数为 f(x)=ax+b(a∈[−1,1],b∈[0,1],a+b∈[0,1])
接下来 m行,每行描述一个事件,事件分为四类。
appear u v 表示数学王国中出现了一条连接 u 和 v 这两座城市的魔法桥 (0≤u,v<n,u≠v) ,保证连接前 u和 v 这两座城市不能互相到达。
disappear u v 表示数学王国中连接 u 和 v 这两座城市的魔法桥消失了,保证这座魔法桥是存在的。
magic c f a b 表示城市 c 的魔法球中的魔法变成了类型为 f ,参数为 a,b 的函数
travel u v x 表示询问一个智商为 x 的人从城市 u 旅行到城市 v
(即经过 u到 v 这条路径上的所有城市,包括 u 和 v )后,他得分的总和是多少。
若无法从 u 到达 v ,则输出一行一个字符串 unreachable。
1≤n≤100000,1≤m≤200000
Output
对于每个询问,输出一行实数,表示得分的总和。
Sample Input
3 7 C1
1 1 0
3 0.5 0.5
3 -0.5 0.7
appear 0 1
travel 0 1 0.3
appear 0 2
travel 1 2 0.5
disappear 0 1
appear 1 2
travel 1 2 0.5
1 1 0
3 0.5 0.5
3 -0.5 0.7
appear 0 1
travel 0 1 0.3
appear 0 2
travel 1 2 0.5
disappear 0 1
appear 1 2
travel 1 2 0.5
Sample Output
9.45520207e-001
1.67942554e+000
1.20000000e+000
1.67942554e+000
1.20000000e+000
解题思路:
题目描述如此毒瘤。
从操作3得到的启发,将多项式展开对应项相加。
这道题可以将sin(ax+b),eax+b泰勒展开。
精度的话16位肯定够。剩下的就是裸的LCT了。
听霉霉的歌写泰勒展开不容易错
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lll tr[spc].ch[0]
#define rrr tr[spc].ch[1]
#define ls ch[0]
#define rs ch[1]
const int N=;
const int oo=;
struct trnt{
int ch[];
int fa;
int lzt;
int type;
bool anc;
double a,b;
double C[oo];
double f[oo];
double val(double x)
{
double ans=f[];
double t=x;
for(int i=;i<oo;i++,t*=x)
ans+=f[i]*t;
return ans;
}
void Insert(void)
{
scanf("%d",&type);
scanf("%lf%lf",&a,&b);
return ;
}
void Taylor(double *fac)
{
double at[oo],bt[oo];
for(int i=;i<oo;i++)
C[i]=at[i]=bt[i]=;
at[]=;
bt[]=;
for(int i=;i<oo;i++)
at[i]=at[i-]*a,bt[i]=bt[i-]*b;
if(type==)
{//sin(ax+b)
double tmp=;
for(int i=;i<oo;i+=)
{
for(int j=;j<=i;j++)
C[j]+=tmp*at[j]*bt[i-j]/fac[j]/fac[i-j];
tmp*=-1.00;
}
return ;
}
if(type==)
{//e^(ax+b)
for(int i=;i<oo;i++)
{
for(int j=;j<=i;j++)
C[j]+=fac[i]/fac[j]/fac[i-j]*at[j]*bt[i-j]/fac[i];
}
return ;
}
if(type==)
{
C[]=b;
C[]=a;
return ;
}
}
}tr[N];
int n,m;
double fac[];
char tmp[];
bool whc(int spc)
{
return tr[tr[spc].fa].rs==spc;
}
void pushup(int spc)
{
for(int i=;i<oo;i++)
tr[spc].f[i]=tr[spc].C[i];
if(lll)
for(int i=;i<oo;i++)
tr[spc].f[i]+=tr[lll].f[i];
if(rrr)
for(int i=;i<oo;i++)
tr[spc].f[i]+=tr[rrr].f[i];
return ;
}
void trr(int spc)
{
if(!spc)
return ;
std::swap(lll,rrr);
tr[spc].lzt^=;
return ;
}
void pushdown(int spc)
{
if(tr[spc].lzt)
{
trr(lll);
trr(rrr);
tr[spc].lzt=;
}
return ;
}
void recal(int spc)
{
if(!tr[spc].anc)
recal(tr[spc].fa);
pushdown(spc);
return ;
}
void rotate(int spc)
{
int f=tr[spc].fa;
bool k=whc(spc);
tr[f].ch[k]=tr[spc].ch[!k];
tr[spc].ch[!k]=f;
if(tr[f].anc)
{
tr[f].anc=;
tr[spc].anc=;
}else
tr[tr[f].fa].ch[whc(f)]=spc;
tr[spc].fa=tr[f].fa;
tr[f].fa=spc;
tr[tr[f].ch[k]].fa=f;
pushup(f);
pushup(spc);
return ;
}
void splay(int spc)
{
recal(spc);
while(!tr[spc].anc)
{
int f=tr[spc].fa;
if(tr[f].anc)
{
rotate(spc);
return ;
}
if(whc(spc)^whc(f))
rotate(spc);
else
rotate(f);
rotate(spc);
}
return ;
}
void access(int spc)
{
int lst=;
while(spc)
{
splay(spc);
tr[rrr].anc=;
tr[lst].anc=;
rrr=lst;
lst=spc;
pushup(spc);
spc=tr[spc].fa;
}
return ;
}
void Mtr(int spc)
{
access(spc);
splay(spc);
trr(spc);
return ;
}
void split(int x,int y)
{
Mtr(x);
access(y);
splay(y);
return ;
}
void link(int x,int y)
{
Mtr(x);
tr[x].fa=y;
return ;
}
bool together(int x,int y)
{
split(x,y);
while(tr[y].ls)
y=tr[y].ls;
return x==y;
}
void cut(int x,int y)
{
split(x,y);
tr[x].fa=;
tr[x].anc=true;
tr[y].ls=;
pushup(y);
return ;
}
int main()
{
scanf("%d%d",&n,&m);
scanf("%s",tmp);
fac[]=;
for(int i=;i<oo;i++)
{
double x=i;
fac[i]=fac[i-]*x;
}
for(int i=;i<=n;i++)
{
tr[i].Insert();
tr[i].Taylor(fac);
tr[i].anc=;
}
while(m--)
{
scanf("%s",tmp+);
if(tmp[]=='a')
{
int a,b;
scanf("%d%d",&a,&b);
a++,b++;
link(a,b);
}else if(tmp[]=='d')
{
int a,b;
scanf("%d%d",&a,&b);
a++,b++;
cut(a,b);
}else if(tmp[]=='m')
{
int x;
scanf("%d",&x);
x++;
splay(x);
tr[x].Insert();
tr[x].Taylor(fac);
}else{
int a,b;
scanf("%d%d",&a,&b);
double x;
scanf("%lf",&x);
a++,b++;
if(!together(a,b))
puts("unreachable");
else{
double ret=tr[b].val(x);
printf("%.8e\n",ret);
}
}
}
return ;
}
最新文章
- ORACLE 博客文章目录(2015-05-27更新)
- 第2章 Linux系统安装(3)_SSH连接Linux工具:SecureCRT和WinSCP
- pycharm的一些设置和快捷键
- Bootstrap幻灯轮播如何支持触屏左右滑动手势?
- win10系统更新补丁时进度条一直卡在0%不动的解决方案
- Mac下批量打包
- Spring Boot 获取ApplicationContext
- CruiseControl.NET : svnrevisionlabeller
- SqlServer 笔记
- CMD下修改IP地址
- [ios3-地图] 如何在iOS地图上高效的显示大量数据 [转]
- seo优化 标点符号
- iOS imageio nsurlsession 渐进式图片下载
- Java SE 8 流库
- C# 内存模型
- js对象,set和get方法 的三种实现形式
- JavaScrip 入门第一课
- [CF1131C]Birthday【贪心】
- mysql order by 多个字段排序
- SqlServer索引碎片
热门文章
- _DataStructure_C_Impl:Dijkstra算法求最短路径
- 推荐一款优雅的jquery手风琴特效
- Design Pattern - Service Locator Pattern--转载
- Android控件-单选按钮RadioButton
- DevExpress Report打印边距越界问题
- 【Henu ACM Round#17 D】Hexagons!
- SQL脚本存在TABLE ACCESS FULL行为
- visualvm监控tomcat
- I帧、P帧和B帧的特点
- hdoj-1593-find a way to escape【数学题】