CH Round #36 - 三体杯 Round #4

ACM/ICPC - Official

From jx


小时

尚未报名

汉字统计 2/99 From
公共子串 11/27 From
比分问题 37/74 From
选三角 14/73 From
排座位 7/25 From
关键节点 2/18 From

三体杯第4轮比赛圆满结束。

祝贺Stilwell摘得第一涨rating,其他题数并列(按罚时升序排列)的选手如下。

Stilwell
徐先友 
猫小猫、
luoruixuan
zerotrac 

表示下次不出第一题这种大家都不熟悉毫无区分度的题目了。一句话题解明晚(6.3)这里见。

说好的一句话题解:

A、[编码]使用iconv.h(Linux下GCC自带)将UTF-8转成GBK(GBK更好处理,UTF-8的中文字符不定长)。然后中文字符就变成定长的两字节编码,判断是否在某一区间内即可识别出汉字。
B、[字符串]时限10秒,所以可以暴力(我不知道怎么暴力,但有人做到了所以一定可以)。
更快速的做法是使用后缀数组,把N个串用‘#’隔开后连成一个串,处理出按字典序排好的后缀;
再用两个指针扫描一遍,答案+=各区间内的最长公共前缀的长度。
C、[组合数学]这是个很水的题(其实是我出水了,没想到递推这么容易)。
我的做法是直接算一个统计方案总数和A比分始终大于B的方案数,然后一除。
总数=(a+b)!/(a!b!),
A比分始终大于B的方案数=(a+b-1)!/((a-1)!b!) - (a+b-1)!/(a!(b-1)!)
不要问我为什么,自己百度/谷歌/维百/萌百“T路”的各种性质。组合数学的一个小题。
D、[有趣的·水题]我的做法:随便选一个点O开始,找出离它最远的点A,再找离A最远的点B;
不断用OAB的面积更新最大面积,如果足够大就输出吧。
E、[真·水题]随便搞一个排法。然后不断随机两个交换的位置,如果换了更好就换吧。直到噪音够小为止。
F、[POJ3906]第一道非原创的三体杯题目,真是开了个不好的头呢= = 作为补偿,我多搬运几句:
“求出图中的割点,这些割点将图分成了若干个双连通分量,我们把每个双连通分量分开处理,因为不同双连通分量里的点必然不共同属于某个环,不然它们就会在同一个双连通分量里了。
然后在连通分量里找奇环。不难发现:只要连通分量里存在奇环,那么该连通分量中的所有点都在某个奇环中。
找奇环我们用交叉染色法,即开始随意选个点染色,然后不断从一个已染色的节点出发,将与其相邻的节点染成与自己不同的颜色。如果相邻节点已经染过色且颜色与当前节点相同,代表找到奇环。”

------------------------------------华丽丽的分割线------------------------------------

由于CH的输入文件存在数据库里(或者是别的原因),第一题输入数据在CH服务器端不正确。

赛后请大家自助下载数据测试。

由于中途CH不能访问了一段时间,加时30分钟。

题目简洁有趣,难度上下兼顾。
三体杯第4轮已经开幕。
开始猎杀难(水)题吧。

更多信息:3小时6道题(删去了一道有误的题)ACM/ICPC赛制,NOIp提高组难度左右
 

百度贴吧同步链接