【水题合集】2.15考试

1.旅行的精灵

写的并查集。。结果并不对

其实正解是:

$$O(1000000n^3)暴力$$

呵呵←_←

2.糖果分配

这道题正解我不会 但是我A了

用了一些奇技淫巧23333 hhhhh

首先这道题可以转化为:给你一堆正整数,让你在前面加+-号,使得和尽可能接近0

那么dp 每次加上±第i个数,得到前i个数能组合成的所有数

最后判断最接近0的是几

$$复杂度O(200000tn)$$

显然会炸

于是我们用几个【奇技淫巧】

首先我们自信地认为某刻和超过某个数的都不可能,直接割掉【一开始我设的10000,结果T了,改成3000A了233

然后因为每一盒糖果的数目都不超过50,所以答案也应该小于等于50

那么记一下前缀和,如果某刻当前数-之后所有数的和>50就直接割掉

【你说这你随便卡掉?

我一开始打乱一下数的顺序看你怎么卡233

3.聪明的阿卑多

也是个水题【也用了一些奇技淫巧

首先找到最少要拿的金币数很简单 只要每次*2+1看多少次会≥n就可以了

然后就可以dfs了 加一点剪枝

但是这样好像T了

于是再加一点奇技淫巧

不dfs到最后一层 在倒数第二层时统计方案数直接加

因为如果在倒数第二层时,最后一个数选x满足,则比x大的那些不用想肯定也满足

割掉这一层之后就过了233

4.海底之城

tarjan裸题 有什么好说的吗?

再加个并查集就好了

【还好之前写了tarjan模板 嘿嘿嘿

 

说点什么

1 评论 在 "【水题合集】2.15考试"

提醒
排序:   最新 | 最旧 | 得票最多
游客

没戏了。。。

wpDiscuz