AIIO糊做

这个文章是用来总结我做的AIIO(澳洲邀请赛)从10年到17年的题。

AIIO2010

Nomnomnomnom: Can Has Dessert?

给一个序列,求某个l在满足Sum[1,l]=Sum[l+1,l+l]的情况下最大化Sum[1,l]


由于数非负,所以前缀和具有二分性。于是可以二分l进而求的最大的l

Clam Oil

树形无限背包问题。


经典问题,维护每个点到根的路径上的权值和以及重量和,直接做背包DP即可。

Budgie Shots

给定N个区间,选最少数量个点,使得每个区间都至少包含他其中的一个点。


直接贪心即可。我们按照左端点排序,维护一个选择区间,如果下一条线段与当前的选择区间不存在交集,则答案需要增加1,更新选择区间,正确性显然。

AIIO2011

World Bus Driving Championships

N个司机(N一定是2的某个幂次),有若干轮比赛,初始第一轮比赛1司机与2司机比赛,34比赛,类推。第二轮根据第一轮的胜者重新编号,依然按照这个方法比赛。每个司机都有个实力值,较高的人胜出(保证任意两人的实力值不同),现在你想看到某k个给定编号的司机的比赛,那么你最少出席几场比赛呢?


不难注意到这个是满二叉树,根据贪心原则,我们想减少看的比赛次数的话,就得最大化一场比赛能看到所需要看到的司机的个数,因此我们希望在这个司机的最后一场去看他。正确性显然。一个我们想看的司机被ban掉的话,如果是被我们希望看到的司机ban掉,那么正确性OK。如果不是,我们不管是在之前看,还是在现在看,都要有个1的代价,所以正确性依旧OK,故得证。

Kiwileaks

给定若干置换规则,求轮换回原来的序列至少需要几次。无法轮换输出NO


根据置换群,不难发现答案为LCM{g[i]},其中g[i]表示在置换规则图上i所在的环的大小。

若不成环显然是-1

The Terrifying Canary-Bird

给一个网格,一个点能到另外一个点当且仅当他的值比另外一个点的值高,求可行移动序列的个数。


不难注意到这是个DAG,直接做拓扑序DP计数即可。

AIIO2012

Time Warp

你在数轴上,从1走到x,有n个机器,每个机器可以让你往回闪现w_{i}格,然后继续向x走。你走过一个格子的时候,就会获得该格子的分值,闪现回去则不算。你可以不必用完所有机器。最大化分值。格子内的分值可正可负。


不难注意到用一个机器实际上等价于增加了某一区间和。于是直接对每个机器找出他的最大区间值即可。如果是正数,则加入答案,最后别忘了加上整个数轴上的数值。

Hopscootch

数塔问题,不同的是你有K个数,可以用他们去替换数塔中的某些数。每个数只能用一次。最大化分值。数据范围300。


直接DP即可。满分需要滚动一维数组。

Negotiations

N个数,求第k大的子区间和。


二分子区间和,问题转化为判定个数,个数可以通过枚举起点,再二分右端点得到。

AIIO2013

Flatman's Tower

N个正方体,每个正方体有个宽度和高度,你把他们堆成一堆,要求上面的正方体的宽度不能少于下面的正方体的宽度,最大化高度。箱子可以翻转


裸的导弹拦截,直接做DP即可。

Flight Planning II: BASMAS

给定一张无向图,要求删除一些边,使得任意两个城市都可以互相到达,且两个同个国家城市之间不需要经过其他国家的城市。最大化删的边的权值总和。


对每个国家做最大生成树先,然后再对非同国边做贪心即可。

Vitamin D

N分钟,第i分钟沙滩上区间[L[i],R[i]]有阳光,问他最多能坐在某个地方不移动能连续得到多久的阳光。


答案具有二分性,问题转化为判定某个位置是否在某段时间内一直有阳光。时间段可以枚举,判断是否有阳光可以通过判断是否有交集(此处可用ST表优化)

AIIO2014

The Treeless Trees

NOIP2015(?)搭积木原题


作差,直接贪心。

Art, Key, Texture

在网格中构造一个建筑,建筑必须符合现实逻辑(比如说每个选定的块底下的块也一定被选定,建筑不能悬空,建筑之间不能隔空),最大化所选格子的和。


大力DP即可

Memes

给一些字符,一个子串内每个字母不重复出现,则这个子串称为奈斯子串。所有奈斯子串中出现的次数最多的奈斯子串被称为炒鸡子串。有E个修改操作,在修改操作后你要输出奈斯子串的长度,以及最大的奈斯子串连续出现的次数。


对每个字符进行哈希,线段树维护,通过线段树合并,我们可以轻易的求出两个答案。

AIIO2015

Friendly

N个人按顺序来找你,每个人想要某种卡牌,当你给他某种卡牌以后她就会给你另一种卡牌,以及C_{i}块巧克力。你最初可以选择一种卡牌作为开始拥有的卡牌。问最多能获得多少个巧克力,在获得最大数量的巧克力的条件下,你最初可以选哪些卡牌?


为了第二问,倒着DP即可,用set优化。

Going Home

一张无向图,小A从1开始,走到N,小B从2开始,走到N,他们要gay在一起,但他们又都走最短路,问两个人最多能gay多久,要想gay这么久,有多少种方案呢?


分别从1,2开始跑最短路,再从n开始跑最短路,那么只需要考虑dis1[u]+w==disn[v],dis2[u]+w==disn[v]的边即可。对每个点求出从1,2到达他的方案数,再通过特殊边再进行一次DP组合两种方案数。

Riding Jetstreams

题意略

每个时段的对应点之间连边,求最短路即可。连边需要维护一棵线段树用来做RMQ。

AIIO2016&17

AI.io

用线段树维护多项式最小值。再利用set维护有序链表和之间的差值。