首页 > 其他分享 >P8139 [ICPC2020 WF] Sweep Stakes 题解

P8139 [ICPC2020 WF] Sweep Stakes 题解

时间:2024-09-06 14:52:03浏览次数:13  
标签:WF ICPC2020 cur int 题解 mid Poly double 多项式

思路

容易发现,题目要求我们动态维护这样一个多项式。

\[\prod_{i}(1-p_i+p_ix) \]

如何维护。

由于精度问题,我们很难去进行一个多项式除法将其暴力求出。

考虑 \(p_i\le 0.2\)。

可以得知,我们的多项式的数的增减是比较大的。

那么在一定数量后,一些可能有值的系数在当前精度下是可以认为是零的。

这样就对多项式长度有了保障。

我们可以将所有询问丢到线段树上。

暴力维护两个多项式。

在多项式乘法的时候。

我们仅维护有值的位置。

就可以以较快的速度通过此题。

复杂度不会算。

Code

#include <bits/stdc++.h>
using namespace std;

int m, n, t, q, ln[1010];
double a[510];
double b[510];
set<pair<int, int>> v[1010];

struct Poly {
  int l, r;
  double f[300000]{};
  Poly() { l = 0, r = 0, f[0] = 1; }
  inline void add(int x, int y) {
    double p = a[x] + b[y];
    double q = 1 - p;
    r++;
    for (int i = r; i >= l; i--) {
      f[i] = f[i] * q;
      if (i != l) f[i] += f[i - 1] * p;
    }
    while (l < r && f[l] < 1e-12) l++;
    while (l < r && f[r] < 1e-12) r--;
  }
};

Poly cur;

inline void build(int p, int l, int r) {
  if (l == r) {
    cin >> ln[p];
    for (int i = 1; i <= ln[p]; i++) {
      int x, y;
      cin >> x >> y, v[p].emplace(x, y);
    }
  } else {
    int mid = (l + r) >> 1;
    build(mid<<1, l, mid);
    build(mid<<1|1, mid + 1, r);
    for (auto i : v[mid<<1]) v[p].insert(i);
    for (auto i : v[mid<<1|1]) v[p].insert(i);
  }
}
inline void solve(int p, int l, int r) {
  if (l == r) {
    Poly res;
    for (auto i : v[p])
      res.add(i.first, i.second);
    double pos = 0;
    for (int i = 0; i <= ln[p]; i++) {
      if (t - i >= 0) pos += res.f[i] * cur.f[t - i];
    }
    for (int i = 0; i <= ln[p]; i++) {
      if (t - i >= 0) printf("%.9lf ", res.f[i] * cur.f[t - i] / pos); else printf("0 ");
    }
    printf("\n");
  } else {
    int mid = (l + r) >> 1;
    Poly back = cur;
    for (auto i : v[p]) if (!v[mid<<1].count(i)) cur.add(i.first, i.second);
    solve(mid<<1, l, mid);
    cur = back;
    for (auto i : v[p]) if (!v[mid<<1|1].count(i)) cur.add(i.first, i.second);
    solve(mid<<1|1, mid + 1, r);
    cur = back;
  }
}

int main() {
  cin >> m >> n >> t >> q;
  if (!q) return 0;
  for (int i = 1; i <= m; i++) cin >> a[i];
  for (int i = 1; i <= n; i++) cin >> b[i];
  build(1, 1, q);
  for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) if (!v[1].count({i, j})) cur.add(i, j);
  solve(1, 1, q);
}

标签:WF,ICPC2020,cur,int,题解,mid,Poly,double,多项式
From: https://www.cnblogs.com/JiaY19/p/18400231

相关文章

  • ORCLE数据库语言设置原因查询不出数据的问题解决
    问题现象:oracle数据库视图中存在数据,但是jdbc查询视图查询不出来,后发现视图中有根据默认语言的过滤,如下图: 客户端查询环境语言为 web服务器查询环境语言为US,所以数据查询不出来。解决方案:修改应用端的NLS_LANG的配置与SQL保持一致linux执行下面代码exportNLS_LANG="......
  • CF1469D Ceil Divisions题解
    CF1469DCeilDivisions感觉是很巧妙的一题?一开始想到,对于任何小于$n$的数$x$,直接对它除以$n$可以得到$1$。那么对$3\simn-1$做完此操作后,还剩下$1$、$2$、$n$。将$n$变成$1$要花费$logn$次,显然总操作次数超过了$n+5$次。进一步地,发现瓶颈在于把$n$变成$1$,于是利用根号,用$\sqr......
  • 9.6 上午 becoder 模拟赛总结&题解
    T1语言水题不多说,很容易发现NP需要满足的只是最后一个单词为N,前面是A或N都可以随意放。所以用两个数组,\(v1_i\)记录以\(i\)结尾的前缀是否可以构成NP,\(v2_i\)记录以\(i\)为开头的后缀是否可以构成NP。最后for循环扫一遍是否有同时满足\(v1_{i-1}=true\)和......
  • CF381B题解
    我们先理解题意,大致意思是:给你一个序列让你组成一个中间有一个数,左侧递增右侧递减的数列。从这道题的题意来看,大概思路是:1.我们要将最大值设为中间的数,然后左右两端尽可能的小。2.跑两遍循环,分别为左边的递增边的递减。3.还有,因为一个数可以出现很多次,我们需要一个vis......
  • 2024 年高教社杯全国大学生数学建模竞赛B题解题思路(第一版)
    原文链接:https://www.cnblogs.com/qimoxuan/articles/18399372赛题:问题1:抽样检测方案设计分析:抽样检测方案需要在保证决策准确性的同时,尽量减少检测成本。需要考虑抽样误差对决策的影响,以及如何设置抽样大小和接受/拒绝标准。解题思路:1.确定抽样方法:采用属性抽样,......
  • 【洛谷 P1449】后缀表达式 题解(栈+分支)
    后缀表达式题目描述所谓后缀表达式是指这样的一个表达式:式中不再引用括号,运算符号放在两个运算对象之后,所有计算按运算符号出现的顺序,严格地由左而右新进行(不用考虑运算符的优先级)。如:对应的后缀表达式为:。在该式中,@为表达式的结束符号。.为操作数的结束符号。输入格式输入一行......
  • CodeForces 2009G Yunli's Subarray Queries 题解
    云璃!高质量Div.4,吊打某些Div.2Only/Edu/Div.3。本题是下面四道题目的有机结合,优雅且经典。LuoguP4168[Violet]蒲公英|LuoguP1997faebdc的烦恼|LuoguP3203[HNOI2010]弹飞绵羊|LuoguP3246[HNOI2016]序列建议先完成这四题。(必须指出:用蒲公英的分块方......
  • P3688 [ZJOI2017] 树状数组 题解
    P3688[ZJOI2017]树状数组题解记录一下做这道题的心路历程,说明在没有事先知道“九条是求成了后缀和”的情况下如何发现,以及解释一些部分分的做法。sub1,18pts:暴力搜索无脑枚举,复杂度\(\mathcalO(n^m)\)。代码:#include<bits/stdc++.h>#defineintlonglong#defineloop......
  • AT_arc151 题解 & 数组字典序大小比较求方案数
    很好的一题,做的时候没有一点思路,看了题解。看来做过的题目还是太少了,记录一下经验。注意到$1\leN\le2\times10^5$和$1\leM\le10^9$,如此庞大的数据,dp是肯定不行的。当字典序$A<B$时,当且仅当存在$i$,使得$\forallx\in[1,i)$,$A_x=B_x$且$A_i<B_i$。那么我们对于$......
  • CF704B Ant Man 题解
    题目传送门前置知识预设性DP解法考虑统计每个数单独的贡献,然后进行预设性DP。设\(f_{i,j}\)表示当前填了\([1,i]\)时有\(j\)个连续段的最小权值,边界为\(f_{0,0}=0\)。对\(i(i\nes,i\nee)\)填入的位置进行分讨。新开一段后面填入的数都比\(i\)大(如果存......