[关闭]
@ysner 2018-08-07T12:18:59.000000Z 字数 4438 阅读 1642

在美妙的数学王国中畅游

数论


题面

数学王国有座城市(森林状),每个城市有三个参数,当一个智商为的人经过会得到的收益。

个事件,分为类:
1、建边
2、断边
3、修改一个城市的参数
4、询问一个智商为的人,判断是否联通,若联通则答从的收益和。

(除最下一档,各档分互不包含)

解析

“删边”这操作钦定使用于是一只不会lct的蒟蒻就gg啦
没有人像我一样在计算器上二分出的吧。

算法

我们可以用邻接矩阵维护一条边有没有被删掉。
暴力修改。
询问收益就从出发对全图
复杂度

算法

不需要删边,判连通性就可以并查集了。

代表可以预处理出每个城市收益。
询问就是问一条链上的区间和。
用树状数组维护前缀和即可做到查询与修改。
总复杂度

  1. il void BL2()
  2. {
  3. fp(i,1,n) ff[i]=i;
  4. fp(i,1,n)
  5. {
  6. if(f[i]==1) w[i]=sin(a[i]+b[i]);
  7. if(f[i]==2) w[i]=pow(E,a[i]+b[i]);
  8. if(f[i]==3) w[i]=a[i]+b[i];
  9. Add(i,w[i]);
  10. }
  11. while(m--)
  12. {
  13. cin>>op;re int u,v;
  14. if(op[0]=='a')
  15. {
  16. cin>>u>>v;++u;++v;
  17. ff[find(v)]=find(u);
  18. }
  19. if(op[0]=='m')
  20. {
  21. cin>>u;++u;cin>>f[u]>>a[u]>>b[u];
  22. re double las=w[u];
  23. if(f[u]==1) w[u]=sin(a[u]+b[u]);
  24. if(f[u]==2) w[u]=pow(E,a[u]+b[u]);
  25. if(f[u]==3) w[u]=a[u]+b[u];
  26. Add(u,w[u]-las);
  27. }
  28. if(op[0]=='t')
  29. {
  30. cin>>u>>v>>x;++u;++v;if(u>v) swap(u,v);
  31. if(find(u)!=find(v)) puts("unreachable");
  32. else printf("%.9Lf\n",Query(v)-Query(u-1));
  33. }
  34. }
  35. }

算法

这是个森林,不太好搞出序,于是应该只能上

算法

怕是模板。

算法

注意到题目最下方有一个奇奇怪怪的公式。
那个玩意儿能够方便地近似将转化为

题目中这一条件显然能给我们以启迪。
如果我们一开始预处理所有的,我们在询问时就可以先得到,再在常数时间内将转化为答案

但是对一个不会求导的高一学生就很伤了:

(为常数)

(周期!)
对复合函数:

代入这道题
对三角函数:

对自然对数幂次方:

代表阶导数。
对一次函数:

(一阶导数就是斜率)
于是代入公式即可得解。

算法

维护信息。

  1. #include<iostream>
  2. #include<cstring>
  3. #include<cmath>
  4. #include<cstdio>
  5. #include<cstdlib>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define M 15
  11. #define eps 1e-12
  12. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  13. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  14. using namespace std;
  15. const int N=5e5+100;
  16. const double E=2.718281828;
  17. int n,m,f[N],ff[N],t[N][2],st[N];
  18. bool r[N];
  19. double a[N],b[N],ans,x,sum[20][N],jc[N],ssin[N],ccos[N];
  20. char c[10],op[20];
  21. il int gi()
  22. {
  23. re int x=0,t=1;
  24. re char ch=getchar();
  25. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  26. if(ch=='-') t=-1,ch=getchar();
  27. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  28. return x*t;
  29. }
  30. il double Sin(re int u,re double x)
  31. {
  32. if(ssin[u]>-eps&&ssin[u]<eps) return ssin[u]=sin(x);
  33. else return ssin[u];
  34. }
  35. il double Cos(re int u,re double x)
  36. {
  37. if(ccos[u]>-eps&&ccos[u]<eps) return ccos[u]=cos(x);
  38. else return ccos[u];
  39. }
  40. il bool isrt(re int u){return t[f[u]][0]==u||t[f[u]][1]==u;}
  41. il void pushup(re int u)
  42. {
  43. fp(i,0,M) sum[i][u]=sum[i][t[u][0]]+sum[i][t[u][1]];
  44. if(ff[u]==1)
  45. {
  46. double tmp=1;
  47. fp(i,0,M)
  48. {
  49. if(i%4==0) sum[i][u]+=Sin(u,b[u])*tmp;
  50. if(i%4==1) sum[i][u]+=Cos(u,b[u])*tmp;
  51. if(i%4==2) sum[i][u]+=-Sin(u,b[u])*tmp;
  52. if(i%4==3) sum[i][u]+=-Cos(u,b[u])*tmp;
  53. tmp*=a[u];
  54. }
  55. }
  56. if(ff[u]==2)
  57. {
  58. double w=pow(E,b[u]);sum[0][u]+=w;
  59. fp(i,1,M) w*=a[u],sum[i][u]+=w;
  60. }
  61. if(ff[u]==3)
  62. sum[0][u]+=b[u],sum[1][u]+=a[u];
  63. }
  64. il void pushr(re int u)
  65. {
  66. swap(t[u][0],t[u][1]);r[u]^=1;
  67. }
  68. il void pushdown(re int u)
  69. {
  70. if(r[u])
  71. {
  72. if(t[u][0]) pushr(t[u][0]);if(t[u][1]) pushr(t[u][1]);
  73. r[u]=0;
  74. }
  75. }
  76. il void rotate(re int x)
  77. {
  78. re int y=f[x],z=f[y],k=t[y][1]==x,v=t[x][!k];
  79. if(isrt(y)) t[z][t[z][1]==y]=x;t[x][!k]=y;t[y][k]=v;
  80. if(v) f[v]=y;f[y]=x;f[x]=z;
  81. pushup(y);
  82. }
  83. il void splay(re int u)
  84. {
  85. re int v=u,top=0;
  86. st[++top]=v;
  87. while(isrt(v)) st[++top]=v=f[v];
  88. while(top) pushdown(st[top--]);
  89. while(isrt(u))
  90. {
  91. v=f[u];top=f[v];
  92. if(isrt(v)) rotate((t[v][0]==u)^(t[top][0]==v)?v:u);
  93. rotate(u);
  94. }
  95. pushup(u);
  96. }
  97. il void access(re int u)
  98. {
  99. for(re int v=0;u;u=f[v=u])
  100. {
  101. splay(u),t[u][1]=v,pushup(u);
  102. }
  103. }
  104. il void makert(re int u)
  105. {
  106. access(u);splay(u);pushr(u);
  107. }
  108. il int findrt(re int u)
  109. {
  110. access(u);splay(u);while(t[u][0]) pushup(u),u=t[u][0];//
  111. return u;
  112. }
  113. il void split(re int u,re int v)
  114. {
  115. makert(u);access(v);splay(v);
  116. }
  117. il void link(re int u,re int v)
  118. {
  119. makert(u);
  120. if(findrt(v)!=u) f[u]=v;
  121. }
  122. il void cut(re int u,re int v)
  123. {
  124. split(u,v);//
  125. f[u]=t[v][0]=0;pushup(v);
  126. }
  127. int main()
  128. {
  129. freopen("math.in","r",stdin);
  130. freopen("math.out","w",stdout);
  131. ios::sync_with_stdio(false);
  132. jc[0]=1;
  133. fp(i,1,M) jc[i]=jc[i-1]*i;
  134. cin>>n>>m>>c;
  135. fp(i,1,n) cin>>ff[i]>>a[i]>>b[i];
  136. while(m--)
  137. {
  138. re int u,v,w;
  139. cin>>op;
  140. if(op[0]=='a') cin>>u>>v,++u,++v,link(u,v);
  141. if(op[0]=='d') cin>>u>>v,++u,++v,cut(u,v);
  142. if(op[0]=='m') cin>>u,++u,makert(u),cin>>ff[u]>>a[u]>>b[u],ssin[u]=0,ccos[u]=0,pushup(u);
  143. if(op[0]=='t')
  144. {
  145. cin>>u>>v>>x;++u;++v;re double tmp=1;
  146. if(findrt(u)^findrt(v)) {puts("unreachable");continue;}
  147. split(u,v);ans=0;
  148. fp(i,0,M) ans+=sum[i][v]*tmp/jc[i],tmp*=x;
  149. printf("%.8e\n",ans);
  150. }
  151. }
  152. return 0;
  153. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注