TC乱刷

r_64 posted @ 2016年1月06日 20:04 in 未分类 , 418 阅读

都是指div 1。

题解

【SRM593】

250.答案不会超过$3$,特判$0$和$1$的情况,$2$的情况写一个二分图匹配就好。复杂度$O(n^2)$,不要像我一样连单向边FST三次。

450.设A队中动物的$A$的和为$A_1$,$B$的和为$B_1$,总共$A$的和为$A_S$,$B$的和为$B_S$,那么你需要最小化$\max(|A_S-A_1-B_1|,|B_S-A_1-B_1|)$,dp出哪些$A_1+B_1$是可能的。复杂度$O(n^2\times 10000)$。

【SRM246】(这一场好像特别水)

250.→_→

500.你tm在逗我,$O(1000len)$简单暴力,为什么不放到div2的250啊。

1000.第一眼水题。。枚举$i\le D$。。FST了才知道这题的意义→_→比较的时候不要用实数跟实数比较,因为绝对误差可以到$10^{-12}$,long double都hold不住。

【SRM675】

300.我用的是奇怪的构造。。设$x,y,z,w$四个点的度数为$X,Y,Z,W$,那么路径条数为$XY+YZ+ZW$。枚举$X,Y,Z,W$,总是可以在玄学时间内出解。

500.对每个询问从高到低逐位(二进制位)确定答案,即把询问写成“二进制前$i$位为$h$的数中的第$k$大”,每次跑一遍数组更新$h,k$($i$反正就是减$1$)。最后答案就是$h$。

900.

这种题居然不是1000。。令人感动

看着myy的代码大概想到了什么。。%%%myy

首先计算面积的方法是这样的,对多边形(交集)的每一条边,把它跟原点连边形成三角形,把有向面积加起来。所以问题变成了找出所有可能在交集中的边及它们在交集中的概率。如图我们枚举边RS,求出它的出现概率乘上$\Delta RST$的有向面积就能得到它对答案的贡献。

可能的边数不多。它一定是某两个同色点的线段上的一部分。先枚举这两个同色点,假设为$A,D$,都是蓝色。再假设整个蓝色凸包都在下面(站在$A$往$D$看的右边)。那么找出上面的所有点,它们都在红色凸包里。枚举下面的所有点,例如$I$,假设它在红色凸包上且与上面某个点在凸包上相邻。对于一个点$I$定义它的$l$值为它到上面所有点的连线中,和$AD$交点最靠左的那个点到$A$的距离除以$AD$的距离。例如,$l_K=\frac{|AR|}{|AD|}$。如果交点在$A$左边那么$l=0$;如果在$D$右边那么$l=1$。那么$I$左边($l<l_i$的所有点)都是蓝色的,如$B$;同理枚举最右边的$O$,它更右边的点都是蓝色的(如$P$)(右边的定义与左边的略不同,令点的$r$值为最靠近$D$的那个交点到$D$的距离与$AD$的比值,右边是$r$更小的点)。

这样我们得到了一个$O(n^4)$的算法,应该是可以通过本题的。具体地说,首先枚举$A,D$(有顺序。站在$A$往$D$看)及$AD$的颜色(下面假设蓝色),再枚举下面的所有点对$I,O$,要求$l_I+r_O<1$,算出$R,S$两个点得到贡献;算出$I$左边、$O$右边所有点都是蓝色,$I,O$是红色的概率得到总概率,这个可以$O(n^2)$预处理。

【SRM674】

500.如果原来$i$的排名是$j$,那么无论什么时候$i$的排名都是$j$。如果原来有一辆车向左(右)在$x$位置,那么$t$时间有一辆车在$x-t$($x+t$)位置。所以二分两个数组的第$k$大,用UR4的元旦激光炮的做法就好。

【SRM628】

250.枚举$d$。$d\le 64$。

500.答案是某些电阻的和。假设确定了答案中电阻的个数,那么贪心选最大的几个就好。电阻形成二叉树的关系,用$f_i$表示子树$i$中选一些电阻最多选多少个,那么$f_i=f_l+f_r$(A类),$f_i=\max(f_l,f_r)$(B类),$f_i=1$(X类,即叶子)。然后搞出前$f_i$个就好。

1000.

$x,y$代表$0.001X,0.001Y$,即对应的概率。这里的$m$是题目中的$m-n$。

最优决策:先把所有游戏都玩通关(第一轮),然后选一些游戏玩到2星(第二轮)。那么我们需要求出第一遍的期望时间(所有的$\frac{1} {x+y}$加起来)、第一遍就玩出$\ge m$星的概率,以及对于每个$n\le i<m$,第一遍玩出$i$星的概率乘以补上$m-i$星的期望最优耗时。

我们知道把一个游戏玩到2星的期望时间是$\frac{1}{y}$。。按$y$升序排序,第一遍没有玩到$m$星那么第二遍一定按照这个顺序玩没有到2星的。

对于第$i$关求出它在第二轮中花费了时间的概率,乘上$\frac{1}{y_i}$就是它对答案的贡献。概率就是,第一轮它只拿了一颗星,且它后面拿了两颗星的关卡$\le m+i-n$个。$f_{i,j}$表示后$i$关中一颗星的关卡有$j$个的概率。

复杂度$O(n^2)$。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter