考试策略

T1不可做,T2不可做,T3不可做......

今天考试看到题目第一句话就是:“凸包是什么”,第二句话是:“Day3是什么”,后来经WY大佬指示才发现是“NOIp”模拟,注意,只有“p”是小写啊!

由于T1的暴力容易写一些,所以先写了T1,然后写了T2的暴力。

结果今天只考了60分就Rank1了......T3所有人都爆0......

T1

期望得分: 40 实际得分:40

题目描述

在不存在 (所以我们今天考了场假试?) 的 noip day3 里小w 见到了一堆堆的谜题。
比如这题为什么会叫共轭?
他并不知道答案。
有 n 堆谜题,每堆有 a i 个,小 w 每次从剩下的谜题中选择一个,然后把所在的那一堆谜题全部丢掉。
小 w 期望多少次后丢掉第一堆?

数据范围

对于20%的数据,$n \leq 10$
对于40%的数据,$n \leq 1000$
对于另外20%的数据,$a_i=1$
对于100%的数据$n \leq 10^5 ,1 \leq a_i \leq 10^9$

题目分析

首先对于$n \leq 10$,我们可以暴力搜出每一种丢掉方式和发生这种方式的概率,以此算期望。

对于$a_i=1$的情况,设f(x)表示还剩下x堆的时候丢掉第一堆的期望,显然$f(x)=\frac{1}{x}+\frac{x-1}{x}(f(x-1)+1)$

于是我们有了40分。

你会发现40分做法很优美 个鬼啊 ,然而100分算法也很容易......我们可以单独算除了1以外某一堆对期望的贡献,会发现任何一堆,如果它在第一堆被丢掉之前被丢掉,带来的丢掉次数是1,而它在第一堆被丢掉之前被丢掉的概率是$\frac{a_i}{a_i+a_1}$,所以......代码见下......

所以到底是为什么这道题没有人做出来啊喂,看来我们的期望都白学了......

代码

T2

期望得分:40 实际得分:20(然而是题目的锅)

题目描述

小w 有一个由 0、1、2 构成的序列。
他可以每次选一个序列中的数,把它移动到序列中任意一个位置。
要用最少多少次可以让 0 和 1 不相邻?
为了考验你的真实水平,小 w 决定使用多组数据。

数据范围

对于20%的数据,每个$n \leq 10$
对于40%的数据,每个$n \leq 100$
对于另外20%的数据,保证只有一个2
对于100%的数据,保证$\sum n \leq 5000$

暴力分析

对于20%保证只有一个2的数据,组成的序列里只要既有1又有0(当然要判断0或1只有一个的情况),那么一定是2放在某个位置,一边全是0一边全是1。所以枚举2放的位置,把某一边的1全部挪到另一边,把另一边的0全部挪过了即可。

对于20%的$n \leq 10$,我们可以使用迭代加深搜索。由于每一次移动最多只有三个数字的“前面数字”会发生改变(挪动的数,挪动的数后面的数,挪动的数到新位置后其后面的数),所以我们令h()表示“前面数字”不符合要求的情况,然后设maxd为当前最大层数,d为当前层数,当$h()+3d>maxd$时可以剪枝。不过这样还是扩展了很多无用状态,由于可能会有500组数据,这样还是拿不到20分。于是我们需要用哈希来判重。

于是我花了两个小时打好了一个价值20分的迭代A星加哈希剪枝优化的深搜,结果这个迭代A星加哈希剪枝优化的深搜没有给我带来20分,因为出题人并没有说无解输出-1但是有无解的情况并且要输出-1,于是我白打了这个迭代A星加哈希剪枝优化的深搜。

暴力代码

正解分析

好的那么问题来了:正解是什么?

正解是dp(我花了大约两个半小时来看懂正解QAQ)。

首先我们可以发现,我们移动数的过程可以看作是不动原序列与最终序列的lcs,然后把其他数都动一次。因此我们只要在原序列里选出一段最长的符合要求的子序列(注意此处的“子序列”并不一定是在原序列中截取的连续的一段)即可。

什么叫符合要求?显然最珍贵的资源是2,选出一个子序列后,对于2的需求量就求出来啦(子序列里的2的数量+子序列里相邻的0和1的数量),而对于2的需求量不超过原序列里2的数量的子序列就是符合要求的......所以我们需要记录子序列上一个选择的数是什么......

等等!还没完!假如对于一个既有0又有1并且只有一个2的序列,我选出了一个这样的序列:1 1 2 1 1 剩下的0往什么地方放啊???所以这样的子序列显然也是不符合要求的。因此我们还需要记录两个东西:d0和d1,分别表示当前选出的子序列中有没有可以放一段0的地方,有没有可以放一段1的地方。

好的,得到状态后我们继续分析实现代码。

1.如果整个序列没有1或者没有0,可以直接输出“1”

2.如果整个序列没有2,可以直接输出无解的“-1”

3.接下来,我们需要两个状态:f(i,d0,d1)和g(x,i,d0,d1),其中f是一个临时数组,g是永久的。g的含义:子序列的末尾是x,子序列已经带来了i的对2的需求量,子序列是否留给0和1位置(d0和d1),这样一个状态下选出的最长子序列长度。而f的含义中i,d0,d1同g中的i,d0,d1,不过f是临时的(具体含义等下讲)

4.现在我们看一看状态转移方程:

正解代码

T3

期望得分: 0.4 实际得分:0

题目描述

听说 noip 不会考几何(那你还考?),所以当 Day3 出现了一道几何题的时候,小 w 的内心是崩溃的。
有 n 个三维空间里的点,每个点有 p i 的概率出现,求期望意义下凸包上有多少个点。
一个点不在凸包上,当且仅当存在一个四面体严格包含了这个点。

数据范围

对于20%的数据,保证$n \leq 15$
对于40%的数据,保证$n \leq 30$
对于另外20%的数据,保证$p_i=1$
对于100%的数据,保证$n \leq 50$,保证任意三点不共线,任意四点不共面

题目分析

我不会凸包......

更不会三维凸包......

我好弱啊......

另外所有人这题都爆0了......

吾不言,吾不言......