分类:未分类

密码保护:derangement

这是一篇受密码保护的文章,您需要提供访问密码:

圆面积并

利用了辛普森微积分的知识…即:

\int_a^b f(x) \approx \frac{(b-a)}{6} \cdot(f(a)+f(b)+f(\frac{a + b}{2}))

而这里的f(x) 就是在 x轴上的一条为x=k的直线被圆覆盖的长度.

Code

这里的代码之前90分是因为直接有l, r, mid会担心刚好割到的函数值是空的, 那么得到的答案就会是0了, 但是我们可以预处理出连续的一些圆, 那么就不会出现这种问题了.

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

const int N = 2e3 + 50, INF = 0x3f3f3f3f;
const db eps = 1e-10;

# define P pair<db, db> 
# define l first
# define r second

int n, m, tot, tag[N];
struct circle
{
    db x, y, r;
    friend bool operator < (circle a, circle b)
    {
        return a.r < b.r;
    }
}a[N];
P c[N];

inline bool cmp1(circle a, circle b) { return a.x - a.r < b.x - b.r; }
inline bool judge(circle a, circle b)
{
    return ((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)) <= (a.r - b.r) * (a.r - b.r);    
}
db doit(db x)
{
    int cnt = 0;
    for(int i = 1; i <= n; i++)
        if(fabs(a[i].x - x) < a[i].r)
        {
            db cross = sqrt(a[i].r * a[i].r - (a[i].x - x) * (a[i].x - x));
            c[++cnt] = P(a[i].y - cross, a[i].y + cross);
        }
    sort(c + 1, c + 1 + cnt);
    db h = -INF, len = 0;
    for(int i = 1; i <= cnt; i++)
    {
        if(c[i].l > h) len += c[i].r - c[i].l, h = c[i].r;
        else if(c[i].r > h) len += c[i].r - h, h = c[i].r;
    }
    return len;
}
db calc(db l, db r, db fa, db fb, db fc)
{
    return (r - l) / 6.0 * (fa + fb + 4.0 * fc);
}
db solve(db l, db r, db mid, db fl, db fr, db fmid, db r1)
{
    db lmid = (l + mid) / 2.0, rmid = (mid + r) / 2.0;
    db k1 = doit(lmid), k2 = doit(rmid);

    db g1 = calc(l, mid, fl, fmid, k1), g2 = calc(mid, r, fmid, fr, k2);
    if(fabs(g1 + g2 - r1) < eps) return g1 + g2;
    return solve(l, mid, lmid, fl, fmid, k1, g1) + solve(mid, r, rmid, fmid, fr, k2, g2);
}
db work()
{
    db res = 0;
    sort(a + 1, a + 1 + n, cmp1);
    for(int i = 1, j; i <= n; i++)
    {
        db l = a[i].x - a[i].r, r = a[i].x + a[i].r;
        for(j = i + 1; j <= n; j++)
        {
            if(a[j].x - a[j].r > r) break;
            r = max(r, a[j].x + a[j].r);
        }
        i = j - 1;
        db aa = doit(l), bb = doit(r), mid = (l + r) / 2.0, cc = doit(mid);
        res += solve(l, r, mid, aa, bb, cc, calc(l, r, aa, bb, cc));
    }
    return res;
}
int main()
{
    // freopen("data.in", "r", stdin);
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%lf%lf%lf", &a[i].x, &a[i].y, &a[i].r);
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; i++)
        for(int j = i + 1; j <= n; j++)
            if(judge(a[i], a[j]))
            {
                tag[i] = 1;
                break;
            }
    for(int i = 1; i <= n; i++) if(!tag[i])
        a[++tot] = a[i];
    n = tot;
    // db aa = doit(-2000.0), bb = doit(2000.0), cc = doit(0.0);
    // printf("%.3lf\n", solve(-2000.0, 2000.0, 0.0, aa, bb, cc, calc(-2000.0, 2000.0, aa, bb, cc)));
    printf("%.3lf\n", work());
    return 0;
}

Endless Spin(区间染色)

题意:

一个长度为 n 的区间,刚开始时区间中所有元素都是白色。
每一次均匀随机一个子区间,将这个子区间染成黑色。
期望多少次将整个序列染黑。
n ≤ 50
陈立杰的题, emmmm

分析:

随机变量(\chi):
对于一次实验结果我们可以一个变量的数值, 这个变量的取值随偶然因素变化
但又遵从一定的概率分布规律,这种变量叫做随机变量

有公式:

E(\chi) = \sum_{k=0}^{\infty} k \cdot Pr(\chi = k) = \sum_{x = 0} ^ {\infty} Pr(\chi > k)

其中, 我们令Pr(x) 表示概率.这个式子其实就是利用了一个前缀和的思想而已!

那么在这题之中, Pr(\chi > k) 就变成了k次覆盖, 不会将整个棋盘变成黑色的概率

我们考虑单独一个k, 假设A_i 表示no.i个点最后是白点的概率, 我们其实就是求|A_1 \cup A_2 \cup A_3…\cup A_n|的概率

于是我们就可以容斥了…

就是求|A_{a_1}\cap A_{a_2} …\cap A_{a_n}|考虑一下,不难发现就是要求{a_1, a_2…a_n}这些点都是白点的概率, 这个就很好求了

我们假设 a_0 = 0, a_{n+1} = n + 1

p(a_1, a_2…a_n) = \frac{\frac 1 2 \sum_{i=0} ^ n (a_{i + 1} – a_i – 1) \cdot (a_{i + 1} – a_i)}{\binom n 2 + n}

那么k次覆盖就是上述式子的k次方就好了!

对原式进行化简我们有:

\begin{gathered}
\sum_{k=0}^{\infty} Pr(\chi > k)&=&\sum_{k=0}^{\infty}\sum_{r=1}^n\sum_{1\leq a_1 \leq a_2 …\leq a_r} p^k(a_1,a_2\dots a_r)\\
&=&\sum_{r=1}^n\sum_{k=0}^{\infty}\sum_{1\leq a_1 \leq a_2 …\leq a_r} p^k(a_1,a_2\dots a_r)\\
&=&\sum_{r=1}^n\sum_{1\leq a_1 \leq a_2 …\leq a_r} \frac{1}{1-p(a_1,a_2 \dots a_r)}
\end{gathered}

然后我们就可以在2的次幂的时间内完成这一道题目了, 但是由于n是50左右的范围, 还是需要优化一下, 考虑dp转移: dp[i][j][k] 表示最后一个白点在i号位置,j为选取的白点数的奇偶性, 可选的区间的方案数为k的子集数目, 那么我们就可以枚举最后的可选区间数然后dp转移了, 详见代码!

Code:

Ps: 首先声明一点, 这道题目会了正解可能还有要高精度, 但是本人用了\colorbox{red}{float128} 来搞事情! 但是HDU好像不给力, 最后就草草的打表过了…

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double db;
typedef __float128 f128;

# define R register
# define P pair<int, int>
# define lowbit(x) ((x) & (~x + 1))

const int N = 53;
const f128 eps = 1e-18;

int T, n;
f128 ans, dp[N][2][N * (N + 1) >> 1];


inline int calc(int x, int y)
{
    return (y - x - 1) * (y - x) / 2;
}
int main()
{
    scanf("%d", &T);
    for(int _ = 1; _ <= T; _++)
    {
        ans = 0;
        scanf("%d", &n);
        dp[0][0][0] = 1;
        for(int i = 1; i <= n; ++i)
            for(int j = 0; j < 2; ++j)
                for(int k = ((i + 1) * i >> 1); ~k; --k)
                {
                    dp[i][j][k] = 0;
                    for(int u = 0; u < i; u++) if(k >= calc(u, i))
                        dp[i][j][k] += dp[u][j ^ 1][k - calc(u, i)];
                    if(!dp[i][j][k]) continue;
                    f128 res = (f128)(k + calc(i, n + 1)) / (n * (n + 1) / 2); 
                    // if(res - 1.0 < eps && 1.0 - res < eps) continue;
                    res = dp[i][j][k] / (1 - res);
                    if(j) ans += res;
                    else ans -= res;
                }
        long double Ans = ans;
        printf("%.15Lf\n", Ans);
    }
    return 0;
}

简单树结构初探

树结构PDF


1.LCA(最近公共祖先)

做法有以下:

  1. 倍增: dp[i][j] 表示以i节点向上2^j的节点, 不难有dp方程dp[i][j+1] = dp[ dp[i][j] ][j
  2. RMQ, 在欧拉序上维护两个点的入戳的点的深度最短点, lca 就是它

2.DFS序

意在维护树的每个节点的入戳和出戳, 然后我们就可以搞事情了(下面提及)

2018-07-14 23-58-07屏幕截图.png
dfs序

3.树的重心

我们把一棵树的中心定义为所有子树的大小都不超过 size / 2 的节点, 不难证明一定存在该点

它具有以下性质:

  1. 在所有的点中, 重心到所有点的距离和最短(可同证明存在重心的方法, 若不是重心, 则有颗子树size > n / 2 我们可移动该点是的 ∑ dis 变小!
  2. 将两颗树通过一条边相连时, 总的重心在两颗树的重心的路径上
  3. 将树的叶子处添加或者删除一个节点, 重心最多只会偏移一个单位
  4. 一棵树最多有两个重心, 且会相邻! (prove: 我们考虑一颗树的root就是重心, 当我们往它的孩子移动的时候, 若孩子也是重心, 那么势必会有∑otherchild_size + 1 ≥ n / 2, 则最多只会相同, 而且只有一个孩子会满足情况! )

tree.png

找重心的时候可以O(n) 寻找 只要满足找到的点 使得 min{max_son_size[u], n – size[u]} 最小的点即可!

4.树的直径

就是寻找到树的两点(s, t)满足dis(s, t) 最大bi

  1. 我们可以两边dfs求出直径, 第一次找出以某点为根的最远的点(设为s) , 再以它为根进行dfs, 找到的点设为t (s,t)即为所求!
  2. 所有的直径中, 必定交于连续的一段

证明:

我们易得如果从 s – t 的路径之中的某个点开始dfs或者在dfs的过程中经过了路径某个点, 则最后答案必然是s – t, 不然如果搜不到s点, 最远点为 v – t 了!

若从root开始搜到的点为v , 两个路径与 s – t的路径没有交集:

tree.png

如何判断某条边是否一定在直径上

做法: 先随便找一条 s – t 的直径, 从 s 出发 至 u, 若 u 至少有两条最长路, 则路上的边都不是必经边, 标记掉就好了! 从 t 再做一遍就好了 (正确性未知, 意会一下)

然后直径的数量: 是需要找出这个连续的一段, 求出左边的最长路的数量, 和右边最长路的数量, 相乘即可!

几道例题:

1.Codeforces 191C – 树上差分

题目: 给出m次操作, 每一次将(u, v)的路径的边权加上1, 问最后每条边的边权!

假设边权的计算是根据较低的点, 我们可以树上差分, 假设(u, v)的lca 为 k , 我们只要在 u ++, v ++, k -= 2, 最后边的权值就是其子树的权值之和!

2.Codeforces 734E

题目: 一颗黑白树, 每一次可以把一个黑白联通块变色, 问最少多少次变成黑树或者白树.

做法: 缩点之后, 答案就是(树直径 + 1) / 2

3.动态树直径

题目: 每次删去 x 与 y 的子树, 求树的直径! (数据均为1e5)

我们考虑在DFS序上操作这道题

合并两个区间的时候只要取 max_len , 以及将 左区间的直径上2点和右边的直径上2点分别挑出2点看看能否比直径更大就好了, 然后我们只要将 x子树的区间剔掉, y子树的区间剔掉, 然后把剩下的区间合并就是答案了, 也许你们会认为这样的直径不合法, 但是一开始它是不一定合法的, 但是最后一定是合法的, 因为就是一个去掉x, y 的树!