怎样做网站的子网,wordpress会员收费,网站建设灬金手指下拉,长沙专业网站建设哪家好Description 数字和数学规律主宰着这个世界。机器的运转#xff0c;生命的消长#xff0c;宇宙的进程#xff0c;这些神秘而又美妙的过程无不可以用数学的语言展现出来。这印证了一句古老的名言#xff1a;“学好数理化#xff0c;走遍天下都不怕。”学渣小R被大学的数学课…Description 数字和数学规律主宰着这个世界。 机器的运转 生命的消长 宇宙的进程 这些神秘而又美妙的过程无不可以用数学的语言展现出来。 这印证了一句古老的名言 “学好数理化走遍天下都不怕。” 学渣小R被大学的数学课程虐得生活不能自理微积分的成绩曾是他在教室里上的课的最低分。然而他的某位陈姓室友却能轻松地在数学考试中得到满分。为了提升自己的数学课成绩有一天晚上在他睡觉的时候他来到了数学王国。 数学王国中每个人的智商可以用一个属于 [0,1]的实数表示。数学王国中有 n 个城市编号从 0 到 n−1 这些城市由若干座魔法桥连接。每个城市的中心都有一个魔法球每个魔法球中藏有一道数学题。每个人在做完这道数学题之后都会得到一个在 [0,1] 区间内的分数。一道题可以用一个从 [0,1] 映射到 [0,1]的函数 f(x) 表示。若一个人的智商为 x 则他做完这道数学题之后会得到 f(x)分。函数 f有三种形式 正弦函数 sin(axb) (a∈[0,1],b∈[0,π],ab∈[0,π]) 指数函数 e^(axb) (a∈[−1,1],b∈[−2,0],ab∈[−2,0]) 一次函数 axb (a∈[−1,1],b∈[0,1],ab∈[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 表示函数的参数若 f1,则函数为 f(x)sin(axb)(a∈[0,1],b∈[0,π],ab∈[0,π]) f2,则函数为 f(x)e^(axb)(a∈[−1,1],b∈[−2,0],ab∈[−2,0]) f3,则函数为 f(x)axb(a∈[−1,1],b∈[0,1],ab∈[0,1]) 接下来 m行每行描述一个事件事件分为四类。 appear u v 表示数学王国中出现了一条连接 u 和 v 这两座城市的魔法桥 (0≤u,vn,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 Sample Output 9.45520207e-001 1.67942554e000 1.20000000e000 解题思路 题目描述如此毒瘤。 从操作3得到的启发将多项式展开对应项相加。 这道题可以将sin(axb),eaxb泰勒展开。 精度的话16位肯定够。剩下的就是裸的LCT了。 听霉霉的歌写泰勒展开不容易错 代码 1 #includecstdio2 #includecstring3 #includealgorithm4 #define lll tr[spc].ch[0]5 #define rrr tr[spc].ch[1]6 #define ls ch[0]7 #define rs ch[1]8 const int N100010;9 const int oo16;10 struct trnt{11 int ch[2];12 int fa;13 int lzt;14 int type;15 bool anc;16 double a,b;17 double C[oo];18 double f[oo];19 double val(double x)20 {21 double ansf[0];22 double tx;23 for(int i1;ioo;i,t*x)24 ansf[i]*t;25 return ans;26 }27 void Insert(void)28 {29 scanf(%d,type);30 scanf(%lf%lf,a,b);31 return ;32 }33 void Taylor(double *fac)34 {35 double at[oo],bt[oo];36 for(int i0;ioo;i)37 C[i]at[i]bt[i]0;38 at[0]1;39 bt[0]1;40 for(int i1;ioo;i)41 at[i]at[i-1]*a,bt[i]bt[i-1]*b;42 if(type1)43 {//sin(axb)44 double tmp1;45 for(int i1;ioo;i2)46 {47 for(int j0;ji;j)48 C[j]tmp*at[j]*bt[i-j]/fac[j]/fac[i-j];49 tmp*-1.00;50 }51 return ;52 }53 if(type2)54 {//e^(axb)55 for(int i0;ioo;i)56 {57 for(int j0;ji;j)58 C[j]fac[i]/fac[j]/fac[i-j]*at[j]*bt[i-j]/fac[i];59 }60 return ;61 }62 if(type3)63 {64 C[0]b;65 C[1]a;66 return ;67 }68 }69 }tr[N];70 int n,m;71 double fac[50];72 char tmp[10000];73 bool whc(int spc)74 {75 return tr[tr[spc].fa].rsspc;76 }77 void pushup(int spc)78 {79 for(int i0;ioo;i)80 tr[spc].f[i]tr[spc].C[i];81 if(lll)82 for(int i0;ioo;i)83 tr[spc].f[i]tr[lll].f[i];84 if(rrr)85 for(int i0;ioo;i)86 tr[spc].f[i]tr[rrr].f[i];87 return ;88 }89 void trr(int spc)90 {91 if(!spc)92 return ;93 std::swap(lll,rrr);94 tr[spc].lzt^1;95 return ;96 }97 void pushdown(int spc)98 {99 if(tr[spc].lzt)
100 {
101 trr(lll);
102 trr(rrr);
103 tr[spc].lzt0;
104 }
105 return ;
106 }
107 void recal(int spc)
108 {
109 if(!tr[spc].anc)
110 recal(tr[spc].fa);
111 pushdown(spc);
112 return ;
113 }
114 void rotate(int spc)
115 {
116 int ftr[spc].fa;
117 bool kwhc(spc);
118 tr[f].ch[k]tr[spc].ch[!k];
119 tr[spc].ch[!k]f;
120 if(tr[f].anc)
121 {
122 tr[f].anc0;
123 tr[spc].anc1;
124 }else
125 tr[tr[f].fa].ch[whc(f)]spc;
126 tr[spc].fatr[f].fa;
127 tr[f].faspc;
128 tr[tr[f].ch[k]].faf;
129 pushup(f);
130 pushup(spc);
131 return ;
132 }
133 void splay(int spc)
134 {
135 recal(spc);
136 while(!tr[spc].anc)
137 {
138 int ftr[spc].fa;
139 if(tr[f].anc)
140 {
141 rotate(spc);
142 return ;
143 }
144 if(whc(spc)^whc(f))
145 rotate(spc);
146 else
147 rotate(f);
148 rotate(spc);
149 }
150 return ;
151 }
152 void access(int spc)
153 {
154 int lst0;
155 while(spc)
156 {
157 splay(spc);
158 tr[rrr].anc1;
159 tr[lst].anc0;
160 rrrlst;
161 lstspc;
162 pushup(spc);
163 spctr[spc].fa;
164 }
165 return ;
166 }
167 void Mtr(int spc)
168 {
169 access(spc);
170 splay(spc);
171 trr(spc);
172 return ;
173 }
174 void split(int x,int y)
175 {
176 Mtr(x);
177 access(y);
178 splay(y);
179 return ;
180 }
181 void link(int x,int y)
182 {
183 Mtr(x);
184 tr[x].fay;
185 return ;
186 }
187 bool together(int x,int y)
188 {
189 split(x,y);
190 while(tr[y].ls)
191 ytr[y].ls;
192 return xy;
193 }
194 void cut(int x,int y)
195 {
196 split(x,y);
197 tr[x].fa0;
198 tr[x].anctrue;
199 tr[y].ls0;
200 pushup(y);
201 return ;
202 }
203 int main()
204 {
205 scanf(%d%d,n,m);
206 scanf(%s,tmp);
207 fac[0]1;
208 for(int i1;ioo;i)
209 {
210 double xi;
211 fac[i]fac[i-1]*x;
212 }
213 for(int i1;in;i)
214 {
215 tr[i].Insert();
216 tr[i].Taylor(fac);
217 tr[i].anc1;
218 }
219 while(m--)
220 {
221 scanf(%s,tmp1);
222 if(tmp[1]a)
223 {
224 int a,b;
225 scanf(%d%d,a,b);
226 a,b;
227 link(a,b);
228 }else if(tmp[1]d)
229 {
230 int a,b;
231 scanf(%d%d,a,b);
232 a,b;
233 cut(a,b);
234 }else if(tmp[1]m)
235 {
236 int x;
237 scanf(%d,x);
238 x;
239 splay(x);
240 tr[x].Insert();
241 tr[x].Taylor(fac);
242 }else{
243 int a,b;
244 scanf(%d%d,a,b);
245 double x;
246 scanf(%lf,x);
247 a,b;
248 if(!together(a,b))
249 puts(unreachable);
250 else{
251 double rettr[b].val(x);
252 printf(%.8e\n,ret);
253 }
254 }
255 }
256 return 0;
257 } 转载于:https://www.cnblogs.com/blog-Dr-J/p/10116746.html
