2018年七月
« 三    
1234567
891011121314
15161718192021
22232425262728
293031  

☆在这里搜索文章

Siroi edit by Tusik

【奇怪的训练】Four Points

11/17/2014

题意描述:给定平面上四个点,求它的一个外接正方形。

 

解法:

稍有常识的人即可看出,

最上、最下的两个点做平行于X轴的线,

最左、最右的两个点做平行于Y轴的线,

这是一定可以构造出一个外接矩形的。

那么稍有常识的人便可看出,

假如我们构造出了一个w>h的矩形,

那么将四个点顺时针旋转90°(立起来),

就可以得到h>w的矩形。

那么问题来了,

在这个旋转过程中是否可以形成一个w=h的矩形,即我们需要的正方形呢?

答案是显而易见的。。

因此,我们在[0,π/2]区间内二分需要旋转的弧度,

然后判断形成的矩形是否是正方形即可。

 

 

-----------------------------反正也没人看我的博客,谁想做这道题加我qq来要链接好了= =

 

偏序集及Dilworth定理

08/26/2014

很炫酷的东西QQ图片20140826103745

首先我们要了解一下什么是偏序关系:

【注:“≤”在此中的意义为“偏序关系” 而非 “小于等于”,不过不难发现“小于等于”也是一种偏序关系。

设集合X为一个非空集,关系P(≤)为集合X上的一个二元关系,

若关系P满足:

①自反性:a≤a

②反对称性:若a≤b , b≤a , 则a=b。

③传递性 :若a≤b , b≤c , 则a≤c。

那么我们称P(≤)为在集合X上的 偏序关系   ,带有偏序关系的集合我们称为 偏序集  (如X)。

在偏序集中,若存在 a≤b 或者b≤a,那么我们称a与b是可比的。

在偏序集中的元素a,若对于所有与a可比的元素均有a≤b,则称a为偏序集中的极小元

 

举几个偏序关系的栗子:

①小于等于显然是偏序关系!

②整除关系显然也是偏序关系!

③集合间的子集关系是偏序关系!(`·ω·丿)

 

若偏序集X中的一个子集X1满足X1内所有元素都相互可比,那么我们称X1是X中的一条

反之,若子集X2中的所有元素都相互不可比,我们称X2是X的一条反链

 

定理①:对于偏序集(X,≤),若 r 为其最长链的长度,则集合X的最小反链划分为 r 。

其对偶定理即为 Dilworth定理

(定理②) 对于偏序集(X,≤),若 r 为其最长反链的长度,则集合X的最小链划分为 r 。

我们仅需证明定理①成立,对偶定理即成立。

定理①的证明:

 

首先证明r的必要性:

对于最长链中,任意的两个元素都是可比的,因此最长链的任意两个元素都不可以同时存在于一条反链中,因此r条反链是必要的。

其次证明r的充分性:

将集合X中所有的极小元组成集合A,每次剔除集合A,如此反复处理下去,必然每次剔除的集合与上次剔除的集合均有元素满足偏序关系。而当X被剔除至空集后,所有被剔除的集合即为最小链划分,我们设被剔除的集合的个数为k ,由于每个集合之间均有偏序关系的元素,而最长链的长度为r,因此k<=r。

至此,定理①证明完毕。

 

通过这些定理的转化,我们便可以解决或者证明一些奇♂怪的问题啦。

举个例子:

炒鸡经典的入门级DP 导弹拦截  的第二问:“集合X能最少划分为几组不上升子序列?”

按照朴素题意的算法,我们需要求最小路径覆盖。

但是不难看出,这是求一个偏序关系“x先于y出现,且x大于y”的最少链划分,

所以根据定理,我们可以发现这就是求“x先于y出现,且x大于y”的最长反链长度,

即为最长上升子序列的的长度。

因此我们可以以nlgn的复杂度求出答案。

 

更多例题:SPOJ 3196. Divisibility Relation

 

ZOJ3806 Incircle and Circumcircle

08/25/2014

题意:给定r1与r2,要求构造出一个以r1为内切圆半径、r2为外接圆半径的三角形,无解则输出No Solution!

 

思路:

不难发现,对于一个给定的外接圆而言,圆内接等腰三角形的内切圆半径是关于三角形底边的一个单峰函数。

再次不难发现,当三角形为等边三角形时内切圆半径最大,为R/2 ,由此可以判断出无解的情况。

由于我们只需构造出一个解,所以从等边(最大)的情况二分即可。

……

虽然很想再说些什么= =可是似乎已经写完了……

嘛,注意精度!

HDU4773 简单的圆的反演

08/23/2014

题意:给定相离的两个圆(圆心坐标以及半径)以及圆外的一个定点P,求出过点p的且与已知的两个圆外切的所有圆(输出总数+圆心、半径)。

 

应该是高中生们在准备自招是喜闻乐见的“阿波罗尼奥斯问题”13种情况中的一种较为特殊的情况中的一种较为特殊的情况。

( ·ω·、)窝们来分别使用{(x0,y0),(x1,y1,r1),(x2,y2,r2)}表示定点P与两个圆。

首先考虑最先想到的笔算解法:

联立方程组

{\sqrt{(x-x1)^2+(y-y1)^2}-\sqrt{(x-x0)^2+(y-y0)^2}=r1}

{\sqrt{(x-x2)^2+(y-y2)^2}-\sqrt{(x-x0)^2+(y-y0)^2}=r2}

这么奇怪的方程组用简短的代码在保证精度的情况下是比较难解决的,
所以我们考虑  开挂   反演!

在这里窝先来介绍一些比较简单、这道题目中会用到的反演结论姿势。(x1 因为我也只会这些比较简单的……

对于二维上的反演,我们通常是以一个圆 α {(x_{\alpha},y_{\alpha},r_{\alpha})} 为基础而进行的,我们称它的圆心为反演中心,半径为反演半径。

对于平面上与 圆α的圆心O  不同的一点A,与它的反演点A'满足如下关系:

{OA\cdot{}OA'=r^2}

不难发现,圆外的点对应的反演点处于圆内,圆内的反演点处于圆外,圆上的反演点依然是它自身,并且每个点有且仅有唯一的一个反演点(互为反演点)。

特殊地,反演中心没有反演点。

实际上,稍加推导我们即可得到对于这道题目而言相当实用的两个结论:

①不经过反演中心的直线,它的反形为经过反演中心的圆。

②不经过反演中心的圆,它的反形仍为一个圆,并且反演中心为这两个互为反形的圆的位似中心。

 

通过这两个结论,不难YY得到:

以点P为反演中心,不与已知两个圆相交的距离R为反演半径做反演圆,(建议设大一些,以防出现精度问题。)

分别做出{(x1,y1,r1),(x2,y2,r2)}的反演圆,

求出两个反演圆的公切线,

再将公切线反演变换回去,即可得到同时经过反演中心P、又与之前两个圆相切的圆。(因为唯一的交点反演回去仍旧是唯一的交点)。

 

思路已经理清楚了,现在来逐个步骤推倒:

①如何求反演圆:

设两个关于{(O,r)}反演的圆为{(C1?r1),(C2,r2)}

则可以根据反演关系列出如下式子:

{(OC1+r1)\cdot{}(OC2-r2)=r^2}

{(OC1-r1)\cdot{}(OC2+r2)=r^2}

若我们已知C1与r1、r,则不难求出:

{r2=\frac{1}{2}(\frac{1}{OC1-r1}-\frac{1}{OC1+r1})r^2}

{x2=x0+\frac{OC2}{OC1}(x1-x0)}

{y2=y0+\frac{OC2}{OC1}(y1-y0)}

如此即可在已知原圆与反演中心、半径的时候求出原圆的反演圆。

 

②求两个圆的公切线

这道题目只需求外公切线即可(x2 外婆切线【

我们可以通过在大圆内构造同心,半径为(R-r)的辅助圆。

可以发现“过小圆圆心”的辅助员切线是与外公切线平行的。

如此即可方便的计算啦。

 

Uestc(CdOj) 1888(New 747) Birthday party

08/22/2014

组合数学的题。

题目链接:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=25539#problem/G←可以点= =

一句话题意:给定N个点,每个点随机向自己以外的点连一条线,询问恰好存在一个K元环的概率。

 

思路在这里ww:

 

首先我们来考虑  至少有一个环  的概率,

我们从N个点中选出K个点,来组成一个K元环,剩下的点随意连……

显然答案为:{\frac{C_{n}^{k}*(k-1)!*(n-1)^{n-k}}{(n-1)^n}}

稍微化个简:{\frac{C_{n}^{k}*(k-1)!}{(n-1)^k}}

 

至此我们已经可以稍微得到一些思路了:

分别算出 至少有1~[n/k]个环的概率  ,然后做一次容斥即可得出结果。

按照类似如上的的思路,我们不难算出   至少存在m个环的概率  

{\frac{n!}{m!*(n-mk)!*k^m*(n-1)^{mk}}}

 

倘若我们设 F[i] 为至少存在 i 个K元环的概率的话,

显然有 ANS=F[1]-F[2]+F[3]-F[4]+……(+-)F[n/k]。

注意到直接每次暴力运算F[i]会超时,不难发现我们可以通过 F[i+1]/F[i]的値以O(i)的时间来求出F[i],

这样均摊起来时间为O(n)的。

只要代码实现不是很丑即可AC啦~。

 

/w\调完代码高亮功能就来贴代码【雾

 

8月8日校内测试题解。

08/08/2014

这里是为了新开的BLOG 丧心病狂到宁愿少敲一道题也要骗访问量的草稿版题解。

若关于我对题目做法的叙述有何建议或疑问,欢迎在下方评论/w\。

 

A:  POJ 1417  True Liars

集合并查集+类背包dp

 

首先用并查集维护 坏蛋 与 好蛋 。

不难发现,无论一个人蛋的好坏,只要判断条件为YES,就说明这两个人在相同集合,否则在不同集合。

我们依靠输入给定的关系可以将蛋们分成若干个大集合,每个大集合有两种元素:①与根节点处于同一小集合(好坏立场相同) 。 ②与根节点不处于同一小集合(好坏立场不同)。

接下来,我们对于一个集合I,可以得到  SAME[I]:大集合I内与根节点立场相同的人数。

DIF[I]    :大集合I内与根节点立场不同的人数。

如此这般如此这般……

因为我们要判断的是“有P1个好蛋与P2个坏蛋的情况是否成立且唯一。”

所以由此可以通过类似于背包的动态规划来求解。

F[I][J]代表前I个集合有J个好蛋的情况,

P[I][J]记录状态[I][J]从哪里转移过来,即选的是SAME[I]还是DIF[I]。

不难得到:

{F[i][j]=F[i-1][j-SAME[i]]+F[i-1][j-DIF[i]]}

 

最后通过解的唯一性(个数)判断逻辑是否矛盾,如果可行的话通过P[I][J]搞输出就好了w。

 

B  同C。

C  同J。

 

D:POJ 2828   Buy Tickets

离线处理+线段树。

利用了自顶向下线段树的二分的性质,

对于线段树的某一个结点[l,r],我们维护 [l,r]有多少个空位置没有被人占用。

稍微脑补一下就不难发现,

倘若我们从后开始往队伍里塞人,将第 i 个人每次往[1,maxn]区间内的第 pos[i]+1 个位置塞,即可达到最终队伍的状态。

初始每个节点的权值设为0,每次塞人的时候自上而下递归寻找应该被塞的叶子节点,将叶子节点权值+1后Update即可。

 

E   Hdu 4893  标题太长懒得打字系列.

这道题我来做一下嘴巴选手……

首先我们要用线段树维护两个值:

SumA:区间内所有数字之和,

SumB:当区间内所有数字都为最近的斐波那契数时,区间内所有数字之和。

分别叙述3个操作的做法:

1号操作:将位置k的数字增加d 。维护SumA : 直接单点修改后UPDATE即可。

维护SumB : 寻找更改后的数字最近的斐波那契数,单点修改SumB的値,UpDate.

2号操作:直接求和,注意下传标记的姿势即可。

3号操作:给区间L,R打上标记,代表该节点的値将更新为SumB。

 

F 同B。

 

G 不会Q_Q字符串苦手。

 

H 并查集维护联通性即可,当遇到合并两个在相同集合内的元素时输出FALSE。

 

I  : ZOJ 2632   Watermelon Full of Water

优先队列维护DP。

 

首先我们容易得到这个式子:

{F[i]=MIN_{j=1}^{i}\{F[i],F[j-1]+V[j]\},(D[j]+j-1>=i)}.

其中F[I]代表到第I天为止都有西瓜吃(好开心)的最少花费。

身为一个O(N^2)复杂度的DP,显然会TLE。

那么我们该怎么办呢……

该怎么办呢……

怎么办呢……

么办呢……

办呢……

呢……

……

用priority_queue 维护一个结构体:

Node[i]=(F[i-1]+V[i] , i+D[i]-1)。

每次转移前Q.push(Node[i])入队,

再不停地Q.pop(),

直至Q.top()的天数满足支持到第i天,转移即可。

 

J 同F。

 

QQ图片20140808165630

 

不要问我B、C、F、J的题解在哪里,讲课的老师们会哭泣的。

 

这次又一次作为嘴巴选手手残了= =b

 

URAL1936 Roshambo

08/06/2014

              一天不敲浮点数就调试跪成马系列……
             题意:输入一个n(<101) ,询问一场有n个人玩的猜拳游戏,若“每局赢的人留下、输的人退场、平局就继续”,那么期望经过多少局可以决出胜者,即只剩下最后一个人?
             硬要说的话……暴力推倒(导?)公式就好辣w。

F[i]    代表“剩下i个人时期望 f[i] 局能够决出胜者”。
M[i]  代表“含有 i 个人的回合 未平局时对期望的贡献为M[I]”。
P[i]    代表“含有 i 个人的回合 进行一次猜拳,平局(没有人被淘汰)的概率为P[i]”。
按照通常的思路,我们先考虑 F[i] 与 P[i]、M[i]的关系:
显然我们有:

{F[i]=M[i]*(1-P[i])+(M[i]+1)*(1-P[i])*P[i]+...+(M[i]+n)*(1-P[i])*P^n+...+(M[i]+{\infty})*(1-P[i])*P^{+\infty}}
通过高中的数列姿势,最终我们可以化简为:
{F[i]=M[i]+\frac{P[i]}{1-P[i]}}

然后,我们来考虑如何计算M[i]:

首先从三种获胜姿势中选出一种,其次再从 i 个人当中选出 j 个人获胜,此时对于期望的贡献为当前情况的概率乘以(F[j]+1),即为:
{M[i]=\sum_{j=1}^{i-1}\frac{3*C_{i}^{j}*(F[j]+1)}{3*(2^i-2)}}

↑感谢GLY学长的指正,样本空间的大小已经由\color{white}{2^i-2}更正为\color{white}{3*(2^i-2)}  ——Updated 2014/12/16

最后考虑P[i]:

设Q[i]为 i 个玩家进行一轮猜拳游戏有人被淘汰(未平局)的概率,则有:
{P[i]=1-Q[i]}

{Q[i]=\sum_{j=1}^{i-1}\frac{3*C_{i}^{j}}{3^i}}

{Q[i]=\frac{2^i-2}{3^{i-1}}}

 

用程序实现递推运算即可。

 

 

阿卡林哭一些关于这道题目不得不吐槽的事情……
C++的double精度实在是令人感动……人脑对拍了两个小时才敢交了过去,做好了加Eps的准备结果1Y,傲娇的评测姬一定不是按
照10^-6精度来评测的,大家试一下就知道了囧。
目测用Java来做是可以保证正确的,或许是因为C++党的愤怒导致放宽了评测标准……?

Newer Posts