20160507+8+9之吐槽大合集=。==。==。=

嗯……前两天都浪到很晚就没更新,今天把吐槽补上喵=。=

首先是5月7日,

今天是APIO2016 Day 1。这次的比赛采用IOI赛制,也就是可以即时提交即时查看结果的(事实上并不是[即时]后面会解释),然后一道题分为一些个子任务,通过子任务的全部测试点才能拿到子任务的分数。

T1:赛艇

水能载舟,亦可赛艇。现在有两个元素个数均为n的序列A和B \((1 \le n \le 500)\) 。保证 \(1 \le {A_i} \le {B_i} \le {10^9}\) ,现在要得到一个元素个数为n的序列C,并满足 \({C_i}\) 要么为0,要么大于等于A[i]且小于等于B[i],并且序列C除去所有0得到的序列是严格上升的。

求满足条件的序列方案(两个序列被视为不同当且仅当它们至少有一个对应元素不同)对1e9+7取模的结果。

输入第一行为一个整数n,接下来n行每行2个整数分别为A[i]和B[i]

输出一行一个整数表示答案。

第一个子任务9分保证A[i]==B[i],随便 \(O(n^2)\) dp一下就搞定了。

第二个子任务22分,保证 \(W = \sum_{i=1}^n(B_i-A_i) \le 10^6\)

于是我用一个map搞了一个O(WlogW)的算法,然而不知道怎么回事没过。

这个就有意思了,明明可以提交为啥没过呢,是因为这题我最后做的,然而从距离考试结束1小时左右韩国服务器就变得不给力起来,特别的卡,具体表现就是你提交程序一直在运行中,看不到结果,并且一直到比赛结束都看不到QAQ

最后还不给补时,于是就gg了。

正解是把这个dp优化一下,推个奇怪的数学公式,离散化一下,在乱搞搞就可以了。

T2:烟花表演

烟花表演啊他十分的亦可赛艇。现在有一棵n+m个节点的树(其中m个叶子节点, \(1 \le n+m \le 300000\) ),树上的每条边都有一个边权,定义叶子节点的距离为该节点到根节点路径的边权和(保证根节点是1号点,叶子节点是n+1到n+m号点)。现在可以对树上任何边的边权进行修改,修改的代价是修改后长度与修改前长度之差的绝对值,要求用最小的代价使得所有叶子节点的距离相等。

输入第一行为两个数n,m

第二行到第n+m行分别代表2号节点到n+m号节点的信息,为两个整数,分别是父亲节点编号和连向父亲的边权(为小于等于1e9的正整数)。

输出一行一个整数代表最小代价。

第一个子任务7分保证一个菊花图,直接取中位数即可。

第二个子任务保证n+m小于等于300,任何叶子节点距离不超过300,弄了一个奇怪的dp就水过去了。

正解非常的复杂。首先呢容易发现如果x为叶子节点的距离,f(x)为调整到该距离需要的最小花费,则f(x)为一个单峰凹函数(也就是有且仅有一个最小值,没有最大值),而且该函数由数个一次函数拼接而成(就是个下凸包),所以我们奇怪的自底向上维护一下这个下凸包,并不断的合并子树的凸包,最后到根节点就可以了(听起来很简单然而完全懵逼)。

T3:最大差分

这是一道交互题。

给定一个严格递增的非负整数序列A(元素个数 \(n \le 100000\)\(A_i \le 10^{18}\) ),求 \(max\{A_{i+1}-A_i|1 \le i \le n-1\}\)

需要实现一个函数接受n返回答案。

然而这个序列他不给你,你只能通过一个函数MinMax查询,这个函数的功能是查询一个闭区间[s,t]里的最小值和最大值(严格来说,他告诉你 \(max\{A_i|s \le A_i \le t\}\)\(min\{A_i|s \le A_i \le t\}\) 的值)。

就是这么一回事。

一共两个子任务,分别是30分和70分,对于n的约束都一样,就是计算得分的方式有点区别。

对于第一个子任务,记m为调用MinMax函数的次数,对于所有测试点,需要满足 \(m \le \frac{n+1}2\) 才能获得全部分数。

对于第二个子任务,每次调用MinMax函数时,记k为[s,t]中的元素个数总和+1,如果满足 \(\sum k \le 3n\) 则得到全部分数,否则得一个部分分(就是 \(\sum k\) 越大分越少)

第一个很简单,两边往中间夹就可以了。

第二个其实也很简单,然而我并没有想出来=。=(其实是没咋想,觉得这个好像能挺难的,结果炒鸡简单)

根据抽屉原理,设所有元素所在区间为[s,t](可通过一次代价为n+1的操作求出),则把这个区间平均分成n份分别查询,只有以下两种情况。

1.每个小区间中恰好有一个元素,很容易得到答案。

2.至少有一个小区间中没有元素,也很容易得到答案。

于是就解了。(总代价为3n-1,第一次求区间n+1,后来n次操作是n,一共覆盖了n-2个元素(因为不必覆盖首尾),因此总和是3n-1)


晚上saffah来了我们一块出去浪了一波,然后一天就这么结束了。


接下来是5月8日。

今天是APIO Day1.5

首先呢上午上课讲了一堆OI无关,于是下午就在酒店睡了一下午,并没有去听课,结果听说就这一天下午是OI相关,于是不由得慨叹起雪舞喵的rp看来用光了。

晚上是颁奖典礼,得知Cu滚粗十分的不爽。

然后就去uoj群聚了,又浪了一波。

然后一天就这么结束了喵。


然后是今天。

一早上起来退房,前面不知道哪个学校的带队老师态度奇差无比还耽误了好长好长时间才整完。

然后体验了一下帝都早高峰的地铁,感觉要上天了。

接下来就是长达6个多小时的火车,然后就彻底滚粗了。

因此到现在雪舞喵的CTSC&&APIO2016之行就彻底结束了喵。

20160509

Yukimai(^=。=^)

发表评论