Picks's Blog

Solutions to TopCoder Open 2012's Hard Problems

| Comments

TCO 2012 Record

做了十几天吧……终于做完了(看题解)。
很多题的思想真心巧妙。相当值得一做。

1A EllysLights

Description

给一些开关一些灯,一个开关能改变一片灯的状态,一个灯至多连在两个开关上,问最少按几个开关关掉所有灯。

Difficulty

★★

Main Algorithm

二分图染色

Complexity

Solution

由于一个灯只有两个开关连接,就比较明显了。
把每个开关当点,一个要改变状态的灯就在两个开关间连权值为'1'的边,否则为'0'的边。
然后二分图染色,边权为'1'的就异色,否则同色。
出现无法染色就无解了。
最后二分图中,任意一边的开关全按一边就能把这一块满足,故只要特判下在其上的必按开关啥的,取个最小的就可以了。

1B FoxAndPhotography

Description

两个数组,要求 ,每次可以交换任意一个数组中相邻两数,问最少交换次数。

Difficulty

★★★

Main Algorithm

状压DP

Complexity

Solution

显然在两个数组里的交换是等价的,所以只要考虑一个就行了。
假设我完成了前K个人,用的是Task这些人,那么接下来的工作相当于两排都只有(n-K)个人的子问题。
那么就有了最优子结构了。设 为前K个人用去了Task的人的最少次数,暴力转移即可。

1C PasswordXPalindrome

Description

给一个串,每个字母最多出现两次,每次可以交换两个字符,问最少多少次交换变为回文串。

Difficulty

Main Algorithm

贪心

Complexity

Solution

……直接贪心吧= =,出现了一次的直接交换到中间,然后从头往后扫,每扫到一个直接将对应字符交换过去……

Notes

完全不知道意义何在= =叉姐做法是同字符就连边然后统计联通块数?……

2A EvenPaths

Description

给出一张拓扑图,其中有一些点可能有障碍,这样的所有可能局面中,从0到1的不同路径有偶数条的局面有多少种。

Difficulty

★★★★★

Main Algorithm

分段
DP
快速沃尔士变换

Complexity

Solution

由于有 个局面,所以需要用一些方法来处理。
我们将拓扑图按一个割分成两部分,每一部分都有 个障碍。
对于一个部分,可以暴力 枚举后DP出从0/1到它的方案数。
这样,关键就是将两半的答案合并。
我们将与0相连的点的贡献(即往连向1的点上应有的转移)处理为一个向量,其中i的权值表示在1集合中障碍点的状态压位后为i的由0集合贡献的方案数。
另一个向量为从1集合对应点到1号点的方案数。
假如两半局面合并了,合法方案为那些临界点的方案数和为偶数的方案。故需要一个合并方法。
可以发现,对应点的合并的结果是将前一半的结果与后一半逻辑与起来。那么其实我们是要算一个卷积:

类似于SRM 518 NIM,我们构造一个变换来加速这个卷积。
由于逻辑与运算是位独立的,不妨设 .
那么 .
可以验证这个变换是可以满足上述卷积的。
其逆显然为 .
故只需要用这个变换就能在 的时间内解决卷积了。

Notes

调了好久好久好久= =

2B SequenceTransmission

Description

给出一个等差序列,将其二进制表示后摆成一行,问有多少相邻两位不相同。

Difficulty

★★★

Main Algorithm

循环

Complexity

Solution

由于a很小b很大……开始乱搞。
首先考虑,由于每个数首位肯定是1,所以数与数之间的贡献只会出现在数是个偶数的时候。
那么只要考虑数的内部了。
怎么弄呢?假设当前我们在考虑第i位。那么第 位和第 位不同的数p就要满足:
.

这样的话,就是要统计:
的x的数量嘛。
由于是等差序列,我们拆成多段,每次都只考虑恰好不跨越m的时候。
那么这样的话,不同起点的位置只有 个,考虑一下循环节即可。

2C FlattenOut

Description

给出一个环,上面的数字有正有负。每一轮操作将所有大于0的项移1到它的下一项。问T轮后的形态。

Difficulty

★★

Main Algorithm

模拟

Complexity

Solution

考虑一段连续的大于0,则操作可看作将第一个搬到最后去填坑。
考虑最后循环时的状态。一共三种情况:全大于0,全小于等于0,只有0,1.
考虑直接模拟。我们每一次操作(合并起来)可以将一个负数变为0、正数变为0、0变为1.
注意到每一个数在某次变为0后不会变为1,每一个数从某时起至多进行 轮后必然变为0.
故实际上只需要 轮,就能达到目标状态了。

3A CowsMooing

Description

N头牛,每头牛按一个周期moo。问1~50!时间内恰有i头牛moo的时间总数。

Difficulty

★★★★

Main Algorithm

数论

Complexity

Solution

由于50!约数足够多了,所以不会出现什么循环节溢出去的情况。
相当于给出一大堆同余方程,问恰好满足i个(一个即一组同模数的方程,任意满足一组中的一个就好)同余方程的 个数。
考虑一个简单的情况。假如所有周期互质,那么,他们的lcm即为他们的乘积。
这样有什么好处呢?那就是他们的乘积以内的每一个数,在方程组中对应了唯一的一组位置。每一组位置,也对应了一个数。
那么便不用考虑这些数有什么区别了,只要每一个方程来贡献答案就好。设f_i为i头牛同时moo的时间总数,然后随便转移下。
但是关键就是不互质的时候,并不一定每一组位置对应一个数。有的位置组是没有对应数的(即方程无解)。这东西很难处理。
怎么办?我们分类讨论。注意到周期最多50,,那么只要我们能把2,3,5,7带来的不冲突影响去掉,就能视作是一大堆互质的数在玩了。
那么我们就把最终的lcm扩长!给最后的lcm再与 取lcm。
将每一个周期带来的贡献展开到C上,这时的新周期就是
那么就变为了对于模C的每一个剩余系单独考虑贡献。这时候所有周期都是互质的了,用简单的方法就能处理了。
但是这样会T = =。
解决办法是,考虑到会与7产生冲突的只有49,那就直接把新周期为7的扩展7倍,变为49去处理就好……那么 ,这样就能跑出来了……

Notes

这题简直恶心啊= = 。简直恶心啊= = 。简直恶心啊= = 。
基本上是把std抄了一遍= = 。

3B PQHulls

Description

给出平面上N个三点不共线的点,问有多少个子点集的凸包覆盖了P,Q两个点。

Difficulty

★★★★

Main Algorithm

计算几何
容斥原理

Complexity

Solution

这题思路略强……不过好难写= = 。
首先考虑一个简单的情况,只有一个点P。
这种情况下,计算覆盖了P的子集数还是不方便,于是考虑计算未覆盖P的子集数。
假如一个子集没有覆盖P,则子集中的点必在某个过P的直线的一侧。
那么就在扫到这个子集中极角序最小的点的时候把这个子集判掉吧。
把所有点关于P极角排序,两个指针维护一个180度(这里简直细节多出翔啊= =),统计一下指针间的点数就好。
那么覆盖了P的点集中,那些没有覆盖Q的点集是不合法的。我们要把它们删掉。
考虑枚举一个点,以该点和Q的连线作为凸包的切线,计算不跨过这条切线的覆盖了P的点集的数目。直接调用上面那个算法就好。

Notes

调到哭

Semifinal 1 YetAnotherNim

Description

现在有一个博弈游戏。
有n堆石子,每堆石子的数量在 之间,其中 .
先手先从中选出连续K堆石子,删掉其他的所有堆。
后手接着删去任意堆石子,可以不删,但是不能全删。
然后两人开始玩NIM游戏。
求后手必胜的初始局面数量。

Difficulty

★★★

Main Algorithm

DP 矩乘加速
线性代数
博弈论

Complexity

Solution

挺有意思的。
我们发现关键是后手删去任意堆石子后,剩下的石子异或和为0.
即先手取了任意连续K堆石子后,都存在一组数使得异或和为0.
那么就继续用线性代数来描述。题目变为求长度为n,每个数均在1~m之间,任意连续K个数线性相关的序列个数。
显然的当 的时候,任意K个数必然是线性相关的,那么答案就是
的时候,直接做似乎不好做,线性相关这个东西看上去并不容易压入状态。
那么补集转化为求存在某K个数线性无关的序列个数。
这样,对线性无关的讨论似乎更方便,因为线性无关组中一个数所控制的位仅一位。
表示考虑了前i个数,且恰好后j个数线性无关的序列个数。
考虑新加入一个数。
假如这个数与后j个数都线性无关,那么除了只在这j位为1的数之外,都可以选。
.
假如这个数与后v个数线性无关,但是与后v+1个数线性相关:
那么这个数在从后数第v+1个数控制的位上是1,除了后v+1个数控制的位,别的都不能为1(若在除了这v+1位上有1,则会导致这个数对于后v+1个数线性无关)。
.
不能往别的状态上转移了,但i后面的数就能任取了。其对答案的贡献为 .
考虑用矩阵乘法加速。
前面的那一大堆的系数都是常数。唯有向答案贡献的地方乘的是 。怎么办呢?考虑最后的答案是个关于m的多项式,每个系数就是 ,那么用秦九韶算法展开后,所有系数便都变为常数了。

Semifinal 2 TheAnimalProgrammingCompetitions

Description

有N个四人队伍,每个队伍有 个礼品,礼品两两不同,人两两不同。
每个队伍要把自己队伍的礼品送给别的队伍,且每一个人最多获得一个礼品。
求方案数。

Difficulty

★★★

Main Algorithm

DP
组合

Complexity

O(4^3 n^2)

Solution

一个简单明了的状态,表示前i个队伍,还有j个礼品没有送出,还有k个人没有收到礼品。由于都是四人队伍,所以k是没有意义的,当然保留着也行,反正N不大。
考虑枚举当前这个队伍往之前贡献了u个礼品,前面的队伍向当前队伍贡献了v个礼品。则:

直接DP就好。

Notes

坑爹呢?模数是1234567891?两个数加起来就会爆int?
简直不敢相信= =。

Wildcard StringSequence

Description

给出两个串A,B。每次可以往A中插入一个字符。
将每次操作后的A串记为一个序列。
求从A串变为B串的不同序列数量。

Difficulty

★★★★

Main Algorithm

DP

Complexity

Solution

不妨先考虑一个简单的情况,即A为空串。
即每次插入一个字符,得到B串,这样的序列数量的统计。
考虑如何去重。什么情况下会有重复串呢?只有在B串出现了连续相同字符的时候,这时候插入这些字符的先后顺序是没有影响的。
为了去掉这一点的影响,不妨规定往连续相同字符中插入时只能插入到这一段的开头。
表示得到 这一段的方案数。如何在转移时将上述规定表述出来?
不妨设第一个插入的字符是 ,那么
故转移就可得了:.
接下来考虑怎么处理A不为空。试图将B拆成很多段,有的段与A中的一部分匹配,别的我们就可以视作是从空->有的利用上述算法得到。
表示A串匹配到了i,B串匹配到了j的方案数。
枚举 匹配到了 ,需要满足 .
.
这样,问题就成功解决了。

Championship DistanceGraph

Description

给出一个M个点的无向联通图,要给所有顶点标号,任意两个顶点标号不同。
要求原图中每条边连接的两点标号差不超过D,补图中每条边连接的两点标号差大于D。
问标号方案数。

Difficulty

★★★★★

Main Algorithm

状压DP
图论

Complexity

Solution

这题屌炸天。
假设我们已经得到了一个合法的标号方案,我们将所有点按标号大小排序,那么每个点连向的点必然是序列中一段连续区间(包含它自己)。
并且,由于题目中的限制,这些区间的左端点、右端点都是单调递增的。否则就会出现标号递减的三点a,b,c,a连向c,a连向b,b不连向c的情况。
那么我们假设已经得到了序列的前K项,现在要找出K+1项。怎么找呢?
假如现在有两个点,他们连接的点中在前K项中的分别有 个。
,那么 中更小的对应的点肯定不能放在K+1项上。因为一旦放了的话,就会出现左端点不递增的情况。
,那我们再比较连接的点中不在前K项中的,设有 .
,那么 中更大的对应的点肯定不能放在K+1项上。因为一旦放了的话,就会出现右端点不递增的情况。
否则,这两个点对应的区间要么是相同的,要么是不可能的。
不可能的情况可以轻易判掉,相同的话,会发现K+1项放谁都可以,那么只要把这个序列产生的贡献乘这样的点的个数,然后任取一个放上就好。
那么,我们就成功地将图论问题转成了序列问题。
现在问题是这样的,给出一个区间序列,左、右端点递增,给他们打递增的标号,使得一个点与它覆盖的区间内的所有点标号差不超过D,不覆盖的点标号差大于D。
表示标号不超过i,已标了前j个,前D个标号是否出现在序列中的情况k。
然后普通地状压DP就好。

Notes

看别人的AC程序看了好久……最后给他们跪……这谁想得出来?

Comments

comments powered by Disqus