2015 北京现场赛4题
Xiongnu’s Land
题意与题解
这一题是第一题,算是个签到题吧,题目大意是一个(R,R)的地图上有若干个小矩形,让你画一条\(x=n\)的线,使得左边包含的矩形面积必须大于右边,且左边的土地面积要尽量大。数据中两两矩形不相交。
可以看到矩形两两不相交,我们直接从左到右扫描就行了,找到第一个面积合法的位置,然后尽量右移得到答案。
代码
Mysterious Antiques in Sackler Museum
题意与题解
这一题也很简单,给你4个小矩形,问你是否可以选取其中3个组成一个大矩形。对于这题我们枚举所有情况即可。
代码
Osu! Master
题意与题解
这一题题意大概是有一个游戏,分为三个element. C,B,和S,C和B有标号,S没有标号,顺序标号的C和B为一个组,S单独为一个组,问你在给定序列中总共有几组。
直接按照顺序模拟下来就行了。
代码
Snake Carpet
题目大意
给你n条蛇,第i条蛇长度为i,现在要你设计一个矩形,把这n条蛇全部放在矩形上,要求蛇身不能相交。(每条蛇自己的身子也不能和自己相交)除此以外,奇数长度的蛇必须有正奇数个转点,偶数长度的蛇必须有正偶数个转点。要求输出这个矩形。
题解
题目虽然说如果有解才输出,但是稍微分析一下可以发现这个题其实我们是可以构造出来的。
首先可以根据蛇的数量确定矩形的长和宽。
对于奇数蛇,我们考虑矩形的右上角,依次放1,然后围绕着1填上3,再围绕着3填上5….这样一直下去,我们可以得到一个奇数的正方阵。
我们在总的矩形中把这个矩形剪掉,我们发现还剩下一个\(n(n+1)\)的矩形,这个矩形我们需要填上偶数,我们假设在第一行的1,2列填上2;对于4,我们在当前矩形的2下面填上4个4(2*2);对于6,我们在当前矩形的右边填上6个6(2*3)….这样依次下去,我们可以完全得到偶数的构造方式。
我们得到奇数和偶数的构造方式以后,我们就可以输出了,不过偶数的阵有时候需要旋转一下,因为剪掉之后的矩形可能较长的边在左边,而我们构造的偶数阵是\(n(n+1)\)的。