Loading...

2019.12.20学习记录

check评论:0 条 remove_red_eye浏览量:246 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-12-20

$1.JSOI2008$ 球形空间产生器

题意:给定$n$维空间中$n+1$个点,找到一个点$P(x_1,x_2...,x_n)$,使得对于$\forall i\in[1,n],\sum\limits_{j=1}^n (a_{ij}-x_j)^2=C$,$C$为一常数

显然可以展开式子,即$\sum\limits_{j=1}^n (a_{ij}^2+x_j^2-2a_{ij}x_j)=C$

考虑作差消去$x_j^2$将其转化为一次方程组,则$\sum\limits_{j=1}^n (a_{ij}^2-a_{i+1j}^2-2a_{ij}x_j+2a_{i+1j}x_j)=0$

故$\sum\limits_{j=1}^n 2(a_{ij}-a_{i+1j})x_j=\sum\limits_{j=1}^n (a_{ij}^2-a_{i+1j}^2)$

显然这个东西可以搞出增广矩阵,就可以高斯消元解$x_j$了

$2.「hihoCoder 1230」The Celebration of Rabbits$

题意:你需要构造长度$2n+1$的数组$a$,满足对于$\forall i \in[1,2n+1]$,$a_i\in[0,m]$,

且满足$\oplus_{i=1}^{2n+1} (a_i+x)=0,x\in[l,r]$,问方案数,两种方案不同当且仅当任意$a_i$不同或$x$不同

显然可以枚举$x$,然后构造$a$的生成函数,直接与自己$FWT$卷积$2n+1$次就可以,但其实只用$FWT$一次,每个位置再快速幂就可以了,时间复杂度$O(Tn^2logn)$

$3.$洛谷$P2345$ 奶牛集会

题意:有$n$个人,每个人有两个值$a_i,b_i$,求出$\sum\limits_{i=1}^n \sum\limits_{j=i+1}^n \max(a_i,a_j)\times |b_i-b_j|$

显然可以先对$a_i$排序,保证有序后从头到尾添加即可,然后用一棵权值线段树维护$b$的值即可,维护$b$的和以及个数,就可以快速查询前一部分数字中小于$x$的$b_i$之和了

$4.[SHOI2012]$信用卡凸包

题意:给定$n$个矩形,大小相等,第$i$个矩形的对角线交点是$(x_i,y_i)$,绕中心逆时针旋转了$\theta$度,这些矩形的凸包定义为顶点集合的凸包,现在每个矩形的顶点都变成了一个半径为$r$的$\frac{1}{4}$圆弧,凸包的定义为新的顶点(一个圆弧对应两个顶点)的凸包,其中由一段圆弧连接的两个顶点的距离是圆弧长度,求凸包长度

显然任意多边形内角和为$360^°$,所以总圆弧的长度一定是$2\pi r$,由矩形的性质可以得到,其他直线的距离总和就是由所有圆心组成的点集的凸包的周长,算出来相加即可

$5.PKUWC2018$随机游走

题意:给定一棵$n$个点的树,根为$x$,每次从$x$开始随机游走,$Q$次询问,每次询问期望游走多少次使得集合$S$中的每个点都至少到达过一次

典型的$\min-\max$容斥,这里的$\max$指的是这个集合被全部选择的期望,$\min$指的是集合被选择至少一个元素的期望,那么$\max(S)=\sum\limits_{T\subseteq S}\min(T)(-1)^{|T|-1}$

考虑到这是一棵树,那么我们令$dp[i]$表示的从$i$开始随机游走走到任意一个$x\in S$的期望次数,显然是可以$dp$的,那么

$$ dp[u]= \begin{equation} \begin{cases} 0\quad u\in S\\ \frac{1}{d[u]}(dp[fa]+1+\sum\limits_{v\in son_u}(dp[v]+1)) u\notin S \end{cases} \end{equation} $$

基本套路,树上到达一个点的期望$dp[u]$可以写作$A*dp[fa]+B$

则$dp[u]=\frac{1}{d[u]}(dp[fa]+\sum\limits_{v\in son_u}(A[v]*dp[u]+B[v]))+1$

$(1-\frac{\sum A[v]}{d[u]})dp[u]=\frac{1}{d[u]}(dp[fa]+\sum (B[v]))+1$

$dp[u]=\frac{dp[fa]+\sum (B[v])}{d[u]-\sum A[v]}+\frac{d[u]}{d[u]-\sum A[v]}$

$dp[u]=\frac{1}{d[u]-\sum A[v]}dp[fa]+\frac{d[u]+\sum B[v]}{d[u]-\sum A[v]}$

显然$A=\frac{1}{d[u]-\sum A[v]}$,$B=\frac{d[u]+\sum B[v]}{d[u]-\sum A[v]}$

递推就好了,显然最后的答案就是$B[root]$

然后对于每次询问,$\min-\max$容斥即可

时间复杂度$O(n 2^n+q2^n)$

然后还有更优秀的做法,可以直接$FWT$计算出所有状态的答案,不过我还不会QwQ

$6.[HDU4336]\ Card \ Collector$

题意:有$n$张卡片,每次有$p_i$的概率获得第$i$张,问获得所有卡片期望次数

解法$1:$状压$dp$,令$dp[u]$代表到达状态$u$期望次数,显然转移的图是个$DAG$,可以直接$dp$

解法$2:$$min-max$容斥,显然$max(S)=sumlimits_{Tsubseteq S} min(T) (-1)^{|T|-1}$,对于一个集合$T$,$min(T)=sumlimits_{xin T}p[x]$,直接容斥就可以了,复杂度$O(2^n)$

$7.P2116 $城墙

刚做完信用卡凸包,所以这题算双倍经验吗?

题意:给定$n$个点,要求一圈周长最小的城墙,满足城墙到任意点的距离大于等于$r$,

显然还是求出$n$个点的凸包周长,所有圆弧的总圆心角和是$360^°$,答案加上$2\pi r$即可

$8.[HAOI2015]$按位或

题意:每秒钟有$p_i$的概率选择一个数$i\in[0,2^n-1]$并将$ans$与$i$进行$or$操作,求期望多少秒后$ans$变为$2^n-1$

显然可以$\min-\max$容斥,令$\max(S)$表示集合$S$中最晚出现的$1$的出现期望时间,$\min(T)$表示集合$T$中最早出现的$1$的出现期望时间

那么$\max(S)=\sum\limits_{T\subseteq S}(-1)^{|T|-1}\min(T)$

现在考虑怎么快速求$\min(T)$

由于期望的可加性,显然$\min(T)=\frac{1}{\sum\limits_{G\cap T \not= \varnothing } P[G]}$

就是要求出所有与$T$有交的$G$的概率之和

正难则反,考虑与$T$无交的就是所有$T$的补集的子集

子集和显然$FWT$就可以了,补充说明一下

在$FWT$中,我们求$C_S=\sum\limits_{G\cup T} A_G * B_T$

令$\widehat{C_s}=\sum\limits_{T\subseteq S}C_T$

则$\widehat{C_s}=\sum\limits_{G\cap T \subseteq S}\widehat{A_g}\times \widehat{B_T}$

所以用$FWT$就好了

$9.P2245$ 星际导航

题意:给定一张$n$点$m$边的无向图,每次询问给定两点$x,y$,求所有$x\rightarrow y$的路径中属于当前路径的所有边的边权最大值的最小值

看到最大值求最小,显然就是$Kruskal$重构树题了,但这题只用跑出最小生成树就可以了,然后树链剖分,将边权下放的儿子节点,查询的时候不查$lca$即可,但不知道为什么分别把$x$和$y$跳到$lca$的两个儿子再分别$query$会错

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名