6
13
2015
0

2015百度之星

初赛1

h5246

首先注意到打倒最大的那个人就赢了,所以之前要不断打与自己相同的来增强能力。

所以我们的算法就是贪心的选取当前能到达的最大的能力值(存在与其相等的)

然后这为什么是正确的呢?假设这样打不到$boss$,那么一定是出现了一个无法逾越的鸿沟,现在这么早来到这里还过不去,再迟点儿就不用说了。

h5247

算法绝壁是每次$O(n)$。

考虑如何判断一段区间是连续的。首先最大值和最小值相差k,然后这其中的每个数都出现了一次。

那么考虑所有的k区间,用倍增求最大最小,然后出现了一次我们可以离散化后记录一下。

还有一种解法是这其中的每个数都不相同,用$hash$实现。也很兹瓷的样子。

h5248

傻逼题随便二分

h5249

傻逼题随便线段树

h5250

傻逼。。。好吧,我是傻逼。。不会做弃疗

h5251

计算几何?弃疗。。。

初赛2

h5252  

首先我们要知道曼哈顿距离和切比雪夫距离的转化:

$$max(|x1-x2|,|y1-y2|)=|\frac{x1+y1}{2}-\frac{x2+y2}{2}|+|\frac{x1-y1}{2}-\frac{x2-y2}{2}|$$

变换一下字母就有

$$|x1-x2|+|y1-y2|=max(|(x1+y1)-(x2+y2)|,|(x1-y1)-(x2-y2)|)$$

对于这道题我们可以考虑转化一下,变成切比雪夫距离。

那么在曼哈顿上移动距离$1$相当于在切比雪夫上斜着移动一格。

显然答案具有单调性。那么不妨设当前二分的答案为$mid$。

那么XXX在$T$时刻必须处于$i$点周围边长为$2*mid$的一个正方形内。

所以说任何时候XXX的可行区域都是一个矩形,每次加入一个正方形求交。

一旦出现交为空说明无解。

根据样例稍微思考下可以知道只会在整点或者两个整点的中点。

所以一开始全部乘2即可。

hdu5253

傻逼MST,我就是不用prim你来咬我啊

hdu5254

傻逼bfs

hdu5255

这种含有等式的问题可以考虑列方程。

所以我们枚举首和尾,计算中间那部分合法不合法即可。

为了避免精度问题可以先乘以$1000000$然后转成整数做。

hdu5256

刚开始想偏了,想了一个线段树做法,就是用线段树来维护f[i][j]表示前i个已经不降,第i个<=j最少需要改变多少。

这个暴力的$DP$。应该也是可以过得。

后来发现我傻逼了,补集转化一下,修改较少的,不就是留下最多的?留下的必须是不降的,不就是$LIS$?

QAQ 

为了做此题还去A了 BZOJ1367

卡内存卡的我真恶心,本来就打算用线段树合并水过的。。。

有一个结论就是

若某序列
前半部分 $a[1], a[2], … , a[n]$ 的最优解为 $(u,u,…,u)$
后半部分$a[n+1], a[n+2], ... , a[m]$ 的最优解为 $(v,v,…,v)$,
那么整个序列的最优解是什么呢?
若 $u≤ v$,显然整个序列的最优解为 $(u,u,…,u,v,v,…,v)$
否则整个序列的最优解围$(w,w,…w,w,w…,w)%其中$w$是整个序列的中位数。
 
所以就不断得合并就行了。
可以用左偏树时刻维护中位数来做也可以用线段树。
 
 
这题很容易让人想到 BZOJ3503  
 
很容易看出确定了第一行的所有格子翻不翻就能知道剩下所有的格子。
 
我们不妨设第一行所有格子翻不翻的情况为$X_{1-m}$
 
一个想法就是和3503一样把每个格子的翻或不翻的情况用$X$中的一些元素异或起来。
 
然后推出第$n+1$行所有格子的表达式强制$=0$。解一下方程即可。
 
但这对于此题是不行的,因为一个格子并不一定能用$X$中的某些元素异或起来。可能最后需要异或$1$.
 
这其实也很好解决,我们在第一行新拓一个格子强制它必须最后为$1$.
 
其他的就和3503一样了。
 
 
Category: 百度之星 | Tags: | Read Count: 672

登录 *


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

| Theme: Aeros 2.0 by TheBuckmaker.com