ACM ICPC 2018 青岛赛区 部分金牌题题解(KLIG)

ps:楼主脑残有点严重,很容易写错别字和语言组织混乱,如果在读文章时遇到,可以在评论区里回复一下,我好改(花式骗评论)

顺便好人做到底,给大家凑个11/13的题解出来。(据说A题题解某个大佬是有写的,但是我找不到,有没有好心人告诉我一下)

虽然K题现场过的比较少,但实际上是一个排个序 ,按顺序枚举x0,大力数数的垃圾题,只是现场榜歪没人看而已。emmmm,根据重现的结果,可能k确实有一点难度,这里给一下提示,首先这个人啊,是优先先动y,再动x的,所以不和x=x0在同一条线)的曼哈顿距离相同就有可能会撞。因此我们要在(x0,y0)的左右两边分别数每种曼哈顿距离出现的次数。显然左右的是可以拆开数,所以我们先把所有x0左侧曼哈顿距离相同的点的数量数完,在数右边,最后在数一下多少个点的x=x0就行,如果你有注意到题目有说所有点的初始位置是不一样的,可能会好写很多。

现在以数左边曼哈顿距离相同的点的数量为例,首先要注意到什么情况下曼哈顿距离相同点并不会抵消掉而是会留下一个,这里举个栗子,当有三个点对于(x0,y0)的曼哈顿距离相同时,万一有两个因为比较早相遇而挂掉,则最后一个人就能活到空投那里。解决办法也简单,注意到,他们只能在y=y0这条直线上相遇,早相遇的点,他们相遇的x也比较小,只要在从左往右枚举x0的过程中,顺便把在上个x0的相撞死的人对于的数量贡献去掉就好了。再维护一下当前有多少个曼哈顿距离只出现了1次,只出现一次的点都是能活着到空投的。

最后的最后,在教一下怎么数量,因为对于不同的x0,y0所有点的曼哈顿距离都在变的,我们不能每次重新数所有距离出现的次数。但是对于在(x0,y0)左侧点,如果他们对于(x0,y0)曼哈顿距离相同,随着(x0,y0)右移他们还是会相同的,所以干脆直接数他们到(xm,y0)的曼哈顿距离就行了,xm为x0坐标的最大值。 他们到(xm,y0)距离相同的话,则这些点到任意他们的右侧(x0,y0)距离也肯定相同。

这题两种写法,一种是枚举最小值+线段树单点更新维护可行最大值。 另一种是dp (神仙知道怎么写,我不知道)。这题思路还是比较复杂了,然后HDU的CSY巨巨现场一眼标算,果然神仙和凡人是不能比的。

当我问群巨怎么做时,他们只给我“枚举最小值+线段树维护可行最大值“,这几个关键字,我百思不得其解,终于想了几天后顿悟了。o(╥﹏╥)o

首先。我们考虑一个动态规划问题:给出a个长度为1的区间和b个长度为2区间,每个区间都有权重。从中取出若干个不相交的区间,在满足覆盖满[1,n]情况下,使得【权重最大的区间】的权重最小,要怎么做。

一个显然的想法:令dp[i]代表覆盖满[1,i]的所有方案中,权重的最大值最小为多少。然后按左端点从小到大枚举区间,进行状态转移就行了,复杂度O(a+b)。

我们把n个长度为1的区间和n-1长度为2的区间按权值排序 -枚举最小值 – 将权值小于最小值的区间删去 –

– 然后对剩下的区间做dp,求出可行的【最小的最大值】,计算最大值和当前枚举的最小值之差,并更新答案。

上面那个做法虽然不够优越,但是已经为正确的做法已经铺好了路,因为上面涉及到一个线性dp的单点修改后在查询,套个老掉牙线段树维护dp值不就可以在log(n)的时间内查询到修改后的值了吗。

所以现在我们就有了个nlog(n)做法,核心在于怎么把dp挂到线段树上。不过说起来容易做起来难, 因为你发现如果你要搬到线段树上要维护一坨东西才行,

不过核心思想并不复杂,只是枚举一下树上孩子合并时是否有区间跨过两个孩子就行了,合并操作的具体代码长这样

完整的AC代码如下(我删掉一个区间的方法,是把这个区间权值赋值成无穷大,这样对答案就没有贡献了,话说我居然是跑得最快的╰(*▽*)╯):

好吧,这是一个比较傻吊的组合数学题,但是现场的时候看错条件了,越想越复杂_(3」)_。

首先因为是连通简单环图,所以母图必须只有一个简单环且连通所有结点,在断掉一些边后,必然会变成n-m条链的组合。

现在我们先来考虑一个比较简单的问题:n个结点组成一条链有多少种本质不同的方案

写成ai/(i!) x^i 的指数型生成函数的话(什么你不会指数型生成函数,那还不赶紧去学),就是

则题目想要的答案就是bn/k!。 为啥除k! ? 因为我们的答案是不考虑这k条链出现的先后顺序的。

上面那个多项式我们并不需要真的做多项式的幂运算。首先上面的式子可以拆成这样。

乘k次,就相当于求k次前缀和,求k次前缀和的第m项,想必现在是个人都应该会了。

则我们要求的答案{},随便容斥一下就可展开成如下形式:

这样就转化为只有01的形式,然后用问题的1方式就能计算了,到这问题就解决了吗?然而还有一些计算上的细节问题要解决。

你自行思考一下就会发现,这个{ (i-1个) +×} 不就是等于{i-1个} 吗? 因为这个尾巴上的×,对可选区间数莫有虾米贡献,(因为x是不能选的,挂不挂在尾巴上没差)。

而这个(i-1个) +O}好像不太能转化成和{i-1个}有关形式,因为每种情况的可选区间数,都可以额外增加【最后一个O贡献的可选区间的数】=【右端点为n的可选区间的数量】=【i – 上一个1的位置】。但是这个上一个1的位置,对于不同情况是不一样的。(例如{OO}=3^m 而再加个O话,{OOO}=(3+3)^m ,而对于{O×}=1^m,再加个O,{O×O}=(1+1)^m,)

现在我在来考虑一下dp方程这么转移。我们要加上{(i-1个) +O}的方案数,减掉{i-1个) +×}的方案数,所以有:

到此转移就完成了,然后你会发现,这个算法是n^4。但是常数很小,然后题目有1000组数据,其中包含50组大数据_(3」)_,写挫就可能惨遭卡常。

所以遇到1,因为{(i-1个) +1}={(i-1个) } ,所以连动都不要动,但是注意需要记这个1的位置,因为在计算右端点为n的可选区间的数量会用到。

而遇到0时,所有情况下k那个维度都要加上【i – 上一个1的位置】偏移量,所以要讨论一下这个1是从2变来,还是线,转移是和问题三一样的,只不过也要注意一下,计算偏移量时的这个1是从2变来,还是线就行了

最后,你发现这个毒瘤题还会有爆内存的风险,需要优化掉一维的空间。而且可能还要和卡常斗智斗勇。

所以再仔细观察一下,你发现这两种转移其实就是两种简单的操作:一种是数组下标偏移,一种是求j那维的前缀和。

因此当个二维数组写的时候:遇到1,不做任何操作。遇到0时只累加偏移量。遇到2,枚举j求个前缀和,求玩在计算2带来的偏移量。

for(int j=; ji; j++)///把2当0时累加偏移量。注意这个for是不能和上一个for交换位置,如果写个三维数组的,再改成二维数组就会知道为什么。

ACM ICPC 2018 青岛赛区 部分金牌题题解(K,L,I,G)的更多相关文章

摘要 本文主要列举并求解了2016 ACM/ICPC亚洲区青岛站现场赛的部分真题,着重介绍了各个题目的解题思路,结合详细的AC代码,意在熟悉青岛赛区的出题策略,以备战2018青岛站现场赛. HDU 5 …

ACMICPC 2018亚洲区预选赛北京赛站网络赛D-80 Days——–树状数组

题意就是说1-N个城市为一个环,最开始你手里有C块钱,问从1-N这些城市中,选择任意一个,然后按照顺序绕环一圈,进入每个城市会有a[i]元钱,出来每个城市会有b[i]个城市,问是否能保证经过每 …

ACMICPC 2018亚洲区预选赛北京赛站网络赛 80 Days(尺取)题解

题意:n个城市,初始能量c,进入i城市获得a[i]能量,可能负数,去i+1个城市失去b[i]能量,问你能不能完整走一圈. 思路:也就是走的路上能量不能小于0,尺取维护l,r指针,l代表出发点,r代表当 …