博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Codeforces Round #551 (Div. 2)(CF1153) EF
阅读量:4991 次
发布时间:2019-06-12

本文共 1310 字,大约阅读时间需要 4 分钟。

对于一个矩形,如果蛇的一条边与它相交,就意味着这条蛇从矩形内穿到矩形外,或者从矩形外穿到矩形内。所以如果某个矩形的答案为偶数,意味着蛇的头尾在矩形的同一侧(内或外),否则意味着头和尾中一个在矩形内,一个在矩形外。

所以可以通过

for(int i = 2 ; i <= n ; ++i)    ? i 1 n n

来询问出头和尾的横坐标。询问的答案从偶数变为奇数和从奇数变为偶数的位置就是头和尾分别的横坐标。对于纵坐标也这样做一遍。

可能存在头和尾在一条水平或者垂直直线上,这意味着横坐标或者纵坐标找不到答案。但因为头和尾的坐标一定不同,所以另一维坐标一定已知,所以可以在当前维度上二分求出未知的横/纵坐标。

上面方法求出了头和尾的横坐标和纵坐标,对应一个矩形的4个顶点,最后check一下它们的对应关系是左上、右下还是右上、左下。

这是一道看完样例解释就不想做的题目……

因为坐标为实数,所以长度为\(l\)的答案等于长度为\(1\)的答案\(\times l\)。而长度为\(1\)时的问题等价于:任意选择\(n\)条线段,任意选择一个点\(P\)满足\(P\)被至少\(k\)条线段覆盖的概率。

而这个概率只和\(n\)条线段的端点和\(P\)点构成的\(2n+1\)个点的排列方式以及\(2n\)个线段端点的组合方式有关。考虑DP求出满足条件的方案数,然后除掉总方案数。

注意因为实数范围内rand两个数,它们相同的概率为0,所以认为任意两个点位置不同。

\(dp_{i,j,k=0/1}\)表示考虑了前\(i\)个点,有\(j\)个线段端点没有找到对应的右端点,\(P\)点是否已经被放置的方案总数

转移:

①放一个\(P\)点:\(dp_{i,j,1} \leftarrow dp_{i-1,j,0}[j \geq K]\)

②放一条线段的左端点:\(dp_{i,j,k} \leftarrow dp_{i-1 , j-1 , k}\)

③放一条线段的右端点:\(dp_{i,j,k} \leftarrow dp_{i-1 , j+1 , k} \times (j+1)\)

满足条件的方案数就是\(dp_{2n+1 , 0 , 1}\)。注意这里DP出来的方案是无序的(按照右端点排序),所以下面的总方案数算的也是无序的。

接下来考虑总方案数。首先\(2n+1\)个点可以任意排列,所以方案数会有\((2n+1)!\),但是这样肯定是会算重的。

给每一个排列一个固定的意义:对于\((2n+1)!\)个排列,令第\(2n+1\)个数表示\(P\)的位置,\(2i\)\(2i-1(i \in [1,n])\)是一条线段的左右端点。这样任意一种方案会恰好对应\(n!2^n\)个排列(\(n\)条线段可以任意排列,线段的左右端点在排列上可以互换),所以总方案数为\(\frac{(2n+1)!}{n!2^n}\)

所以答案为\(l\frac{dp_{2n+1,0,1} n! 2^n}{(2n+1)!}\)

转载于:https://www.cnblogs.com/Itst/p/10708760.html

你可能感兴趣的文章
白话排序算法--冒泡排序
查看>>
imx6 18bit display
查看>>
Spring静态属性注入
查看>>
实验10:指针2
查看>>
【转】hibernate缓存:一级缓存和二级缓存
查看>>
第二个spring冲刺第3天
查看>>
AwSnap:让全版本(Windows、iOS、Android)Chrome浏览器崩溃的有趣漏洞
查看>>
线段树合并学习笔记
查看>>
AndroidAutoLayout
查看>>
样本不均衡下的分类损失函数
查看>>
node启动服务后,窗口不能关闭。pm2了解一下
查看>>
vsCode 改变主题
查看>>
【vijos】【树形dp】佳佳的魔法药水
查看>>
聚合新闻头条
查看>>
Ubuntu 关闭锁屏界面的 on-screen keyboard
查看>>
凸优化学习笔记
查看>>
使用ehcache-spring-annotations开启ehcache的注解功能
查看>>
Charles设置HTTPS抓包
查看>>
NGUI出现Shader wants normals, but the mesh UIAtlas doesn&#39;t have them
查看>>
Boost.Asio c++ 网络编程翻译(14)
查看>>