温馨提示！由于新浪微博认证机制调整，您的新浪微博帐号绑定已过期，请重新绑定！&&|&&
My name is VFlea King.
LOFTER精选
网易考拉推荐
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
前奏大约4月份的时候，业界毒瘤pyx噔噔噔跑过来说：“酷爱！我YY了一道题！准备当CF的C”我当时就被吓傻了。"Yet another Chinese round?"“区间取模，区间求和”感觉这题还不错？不过pyx嫌水了……好办！当时我刚刚出完动态仙人掌不久，于是一拍脑袋说：把这个问题出到仙人掌上去！当然被pyx鄙视了……后来一直就没啥动静，直到5月底的CTSC。试机的时候pyx给我看了套他出的神题……里面有一道题……我不小心读成了下面这个样子：“给定n个m维的模2意义下的向量，求线性无关组的数目”，然后发现好像不可做……但是我们可以改题目！求基的数目！然后发现好像不可做……但是我们可以改题目！只要知道奇偶性！然后我发现可做了！再加强一下，发现不会做……旅游日那天，pyx给我、lyy、hza、kzf说了下准备出CF的Div.1的题目：A. 随机树链剖分的期望总深度。B. 树上两两点之间RMQ之和。C. 单点修改，区间取模，区间求和D. 布吉岛E. 给定n个模2意义下的向量，求基的个数的奇偶性。……我强烈反对E出成那个鬼样子……太数学化了……然后我说这个A难度比平常的A高，这样不好。于是贡献了个lowbit题……我说：构造一个集合使得lowbit之和等于给定的数sum。每个数小于等于limit。pyx说那就用这个替换原来的A吧！不过D题还是没有着落，囧……时间又过了一天，CTSC结束了。我请大家去餐馆吃饭的路上，pyx把C题中加入了区间赋值。pyx用了个平衡树来解决此题。外国人要在CF上写平衡树了吓傻。无限ym。后来回宾馆，pyx窜入了我的房间，四处寻觅D题。然后我一拍脑袋说：给定一个矩阵，求权值和最大的子矩形（能不连续的那种）。然后发现不会做，讨论了好久，还是不会做。于是我们噔噔噔跑去找hza他们……此时hza、kzf、lyp正在房间里开心地打扑克。花了好长时间，重复了好几遍题目，才把他们的注意力从打牌转移到题目上来。没想到lyp刚听完题面便说：“哦！不可做。XXX研究过的，”……于是灰溜溜地又回到房里构造D题。……印象中pyx就不停地重复两句话：“vfk！D(de,一声)题，D题！快！” & “我觉得那题当E挺好的”。然后我终于又灵机一动想了一道超级无聊的sb题：求简单多边形的三角剖分数目。pyx和ydc表示合适。接着pyx把所有参与出题的人拉到一个讨论组。pyx在讨论组里宣布题目成了下面这个样子：A.&构造一个集合使得lowbit之和等于给定的数sum。每个数小于等于limit。B. 树上两两点之间RMQ之和。C. 区间赋值，区间取模，区间求和D. 求简单多边形的三角剖分数目。E. 给定n个模2意义下的向量，求基的个数的奇偶性。……我仍然强烈反对E出成那个鬼样子……然后就又没啥新动向了……湖南省选之后的某天，pyx突然在讨论组里说：“。。。我又想起来这个讨论组了…”……然后各种毒瘤属性爆发：“谁来造个E吧-_-||……出抽代怎么样-_-||……多项式除法！多项式素性检测！”第二天pyx造了个题：两个人玩游戏，每回合每个人可以选择：攻击，防御，蓄力。蓄力能增加1能量，攻击消耗1能量，攻击时对方蓄力则赢。问K回合内游戏未结束的方案数。然后不会做……于是只好不管了……又过了一天，pyx又跑过来说：“刚才到处拉人气的时候，杜教表示大量E题抛售……”杜教就是不一样！不过把杜教拉过来岂不是变成math round了？结果pyx说：“vfk其实我觉得出纯数学题挺好的嘛！”那我就不客气了！张口就来：从前有一个长度为n的序列a，初始都为1。每次均匀随机出l, r, k，执行a[k] = a[l] + a[r]。问m次操作以后序列a中元素：1.平均值的期望。2.平均值的方差。3.方差的期望。4.方差的方差。然后发现太水了不适合当E……后来又变成了两个随机矩阵的乘积的XXXX。但是这题意义何在……没有任何营养……pyx说：“杜教造了一道题，经过讨论，似乎是陈题。”……于是又不知道出什么E了……接着又过了几天……pyx说我的lowbit太无聊了……准备换一题。我建议pyx搞个20维FFT什么的当E，pyx说不好出。接着说着说着说到多项式开方去了。太神了不会捉啊囧囧囧……诶？好像倍增可搞诶！O(n log n)诶！于是pyx决定拿这个当E。但是总不能出成：给定一个多项式，请开方吧……那样实在是会把人逗笑的……两天后pyx跑过来告诉我换了个A题：给你一个图，删一个点的代价是连接的点的点权和，求最小代价的删除序列。感觉还是不错的。但是lowbit题被换掉了55555……那么E题？我决定在卡特兰上改改：说从前有棵二叉树，二叉树的每个结点都有个权值，权值只能在c_1, c_2, ..., c_m中取c给你了，对于所有1 &= s &= m，求总点权为s的二叉树的个数。然后感觉没啥显而易见的暴力背包。只要坑着大家去写了个FFT我就满足了算你AC了……于是再一次，题目变成了这个样子：A. 给出一张无向图，删去一个点的代价为它连接的所有未删点的点权和，问删去所有点的最小代价。B.&求简单多边形的三角剖分数目。C. 给出一张图，每个点有点权，随即选择两个点，问它们最小的路径上最大点权的期望。D. 区间赋值，区间取模，区间求和E. 求每个结点都有个权值只在c_1, c_2, ..., c_m中取的，总点权为s的二叉树的个数。对于每个1 &= s &= m，输出***。终于，一场CF，有了一个轮廓。联络既然题目基本上定了，那就联系CF吧！pyx说，现在刚结束的一场是Round #248，我们要去抢Round #250！二百五！不过怎么联系呢……幸好我们有前车之鉴：hzc。他们恰好在此时举办了Round #248。无限ym。hzc表示大约要联络一个月才能安排得上。安排的速度要看Gerald的心情。主席也表示申办周期大概要一个月。这是在逗我笑吗……？那岂不是我们能抢到Round #260都已经运气不错了……还Round #250……没戏吧……以及我们Div.2 AB还没有出。不管三七二十一先挤个英文信出来发给Gerald好了。由于我是CF红名狗狗所以被pyx推出去进行联络……555……妈妈呀……要跟外国人交流了真是可怕……pyx说oyqy准备过来出Div.2 AB。于是出题人阵容：pyx，cyb，oyqy，vfk。挤了一会儿牙膏之后得到了成果：Dear Gerald:Hello!I'm vfleaking, a student from China. My friends Picks, delayyy, oyqy and I enjoy Codeforces contests very much.This time, We already have some interesting problems and want to share with others. So we want to hold a contest (Div.1 and Div.2).We want to know some details about how to prepare a contest, would you please give us some instructions?Thanks!VFleaKing我觉得我英语好烂……发出去了之后就切换到坐等“Your English is so poor that I can't read it”的心情 T_T...诶？突然想起来Gerald是俄罗斯人，英语对他来说也是外语？不怕不怕啦……233……此时是5月24日 周六 晚上8点。俄罗斯与中国相差四个小时，此时是俄罗斯时间下午4点。同在一个地球，共有同一个太阳，所处的时间却不一样。仔细想想真是奇妙的感觉。第二天周日，早晨发现信件在凌晨两点的时候被Gerald阅读了。但是Gerald还没回话……我心想他肯定看了之后觉得：“你们这帮中国人又来祸害人！出题太丧心病狂！不许办比赛！”就这样等啊等啊等啊，终于在晚上7点的时候收到了Gerald的回信。拆开一看发现好大一篇英语阅读……Hi, nice to hear that!&This is the standard message to authors.接下来好详细好详细地写了办比赛的过程。新任务get：集齐所有题面题解。等下！我们Div.2 AB还没造出来！囧！于是我建议把lowbit那题变成Div.2 B。于是缺个Div.2 A。接下来pyx各种毒瘤属性爆发，出现了各种神一样的Div.2 B：long long乘long long模long long。（python笑了）给一个置换，问它的几次方是另一个置换。给一个置换，求另一个置换的k次方等于它。给出一个数，求他的最大因子，满足所有质因子指数相同。给一个数，求一个不超过lim的数，使得它们lcm最大。给一个序列，选出k个数，使得gcd最大。给一个图，求最小瓶颈割。………………还让不让打Div.2的人活了……我灰溜溜地滚去写Div.1 E的题面题解。写题解的时候顺手写出：“Recall the algorithm which calculate the inverse of a formal power series F(z)”被pyx吐槽了：“你真的认为人人都会多项式求逆吗………在我的印象中好像是我把这玩意正式引入OI的吧……”T_T……说得太对了，要是没有pyx，我也不知道快速多项式除法咋弄。周一。pyx终于搞了个正常向的Div.2 A：给出数轴上n个点，现在你在a，求遍历所有点的最短时间，每秒只能移动1个单位。于是oyqy也就没来出Div.2 AB。我们最后还是决定交换BC题……把三角剖分计数放到了C。在晚上终于集齐了大家的充满语法错误的题面题解。张口就来：leftest, rightestzero of last digitsa power series which satisfy XXXXXXXXXX, that is, XXXXX修整着修整着，诶！感觉可以发了！等我连邮件的正文一起码完的时候，已经凌晨1点了囧。在邮件里面我留了个PS：We think the number 250 is interesting. Could you please give us a chance to hold Round #250?不过我觉得其实没什么戏……哎……周二。大约下午2点钟的时候收到了Gerald的邮件：I can give such a chance. =) The only question, do you know how to work in Polygon?赞！！！！太神了！！！！二百五不是梦！！！！紧接着Gerald问我：Do you have a GTalk, or Hangouts?有哇有哇！于是赶紧去开gmail。……………………发现我连google都上不去……今天什么情况…………！紧接着突然发现Gerald给我的联系方式中有QQ。跪傻了……企鹅产品居然还真有外国人用。我是很happy地跟Gerald说可以用QQ嘛！我已经加你好友了！接着等了好久也没等到Gerald上线。他表示：“Do you know is there any version of QQ for linux?&I've googled a lot, I find out that there is no QQ international for Linux. I don't know Chinese =(”真是个悲伤的故事……T_T……于是我又说用Web QQ吧……紧接着发现Web&QQ没有国际化……外国人肯定没有办法知道哪个按钮是登陆……= =……于是我们只好去尝试skype。但是布吉岛为什么我下载的skype客户端出了点问题。（还不小心把杜教坑得去下了个skype还注册了个号，T_T……）从Gerald问我的即时通讯工具开始，已经过了一个半小时。我已经快疯了……抱着侥幸心理又试了试gtalk。发现能上啊！！！爽！审题Gerald紧接着给我发了Polygon的说明和CF出题人须知。“How much time do you have in near future? I've planned 250 round either in the end of this week or in the start of the next one.”……感觉时间好紧啊……不过讨论了下大家觉得还是来得及的。于是就把时间定到了周日。“Ok, let start discussing the problems”要审题了好可怕……接着Gerald沉默了。许久之后：“very similar problem was it? at http://codeforces.ru/contest/412/problem/A”……又要滚去再造个Div2.A了囧……真是开门红啊……接着Gerald去看Div.2 B，但是不是很理解啥叫lowbit。直到此时我才发现貌似外国人写树状数组的时候直接x -= x & -x，所以根本不知道lowbit是个啥……那中国OI教学里的lowbit是谁带起来的囧……我很好奇……理解清楚lowbit了之后，Div.2 B，Gerald评价说：nice problem。……呼……幸好没又放个链接说similar problem……接着Gerald去看Div.1 A，然后立刻就评价：Very nice problem div1A不一会儿，Gerald又说：Hey!&Div1B also very NICE!Orzzzzzz……于是到我的Div.1 C了……在纠结了一会儿啥叫三角剖分了之后Gerald说：Good problem.&May be a bit hard to code.&Anyway suitable for div1C.还剩Div.1 D和E。其实我最担心的是E过不过得了审核……然后Gerald沉默了好久，说："I should go in a half a hour.&You can start preparation of the approved problems"所以DE的命运还是个悬念。此时叉姐也被拉入了Tester的队伍。叉姐建议说：*************** （我怀疑叉姐要借某个机会把这题出出来 T_T，我还是隐藏题面吧）…………说好的Div.2 A的普及组难度呢？这时杜教又出来拯救世界了：有n个id。。。然后每个人id是字符串+数字。。。然后按数字排序。。。感觉还是很适合当Div.2 A的嗯……不过感觉略麻烦……这时lyy出来毁三观了：给一个2048的局面。。问是否能一步之内合出2048。。读完游戏的规则就10min过去了吧…… = =……这时叉姐说：给一个pyx，怎么1步之内把他玩坏。超好评！！！这时lyy又出来毁三观了：给一个评测信息。。。判断是怎么错的。。。如果WA要输出WA在第几个点。。。这……………最后还是cyb出来拯救世界了：给一道选择题，三短一长选最长，三长一短选最短，否则选C。2333333……带有中国特色的题目。很快获得了大家的好评。不过Gerald仍处于离开状态没有回音。pyx开始胡死乱想是不是D题被毙了：“肯定是在找一个好听的理由安抚我的幼小心灵QAQ………”hza：话说，我们猜猜E题通不通得过lyy：感觉过不了。。。cyb：→_→ ……这是个严肃的问题hza：你们得写份义正言辞的演说词！说服那个Gerald！首先你们得表现地这题非常简单的样子pyx：是的。题面多简单hza：然后将题解用几句话说完。在他思考前告诉他解法。。这样他就不知道这题难不难了。……哎……不过得赶快开始造题了。只剩寥寥数天，我们却还没开工。由于发现我们运气很好捡了个六一，所以决定主题得跟熊孩子有关。题目背景中得有个人物？我们展开了一系列构想：little delayyy，little ftiasch，super ftiaschDZY LOVES CF！doge！Huang half goddess（黄半仙）！……然后不了了之……我提议，要不大家题面都这么起头吧：A long long time ago, there is a XXX and a child. The child likes playing with the&XXX.&(Why long long ago? because you must use a long long to store the time interval)XXX填跟题目有关的那个东西……比如三角剖分那题就填Polygon然后pyx吐槽说，要是所有题都这么写，Div.2 B就会变成：The child likes playing with the function lowbit()……what the f**k不过最后大家还是决定以这段话起头。于是分头干活去了。转眼到了晚上11点。pyx：genald还没回应吗vfk：没hza：估计被E题吓晕了T_T……555555……突然有点后悔自己为毛线要受pyx蛊惑去出E……感觉考一个根本不普及的算法的拓展版本一点意思都没有……哎……周三。出三角剖分那题的数据把自己出吐了……求造简单多边形的正确姿势……55555……下午3点Gerald终于复活了，并通过了那个选择题作为Div.2 A。接下来他开始审Div.1 D。然后他想了半个小时……终于忍不住去看了题解……然后评价说：Really nice problem.接下来的话就让我们凌乱了……Look, I think your problem D is enough for problem E.It is really nice.If problem E will be as nice and as hard as your DMay be the better decision is to make another D, simpler that yours. And left your E to another round.……这可怎么办才好……等他看了E……就得牺牲掉一题了吧……好想强硬地回答：No！Two E are OK!杜教：Chinese round不需要E。No ! Four problems are enough!pyx：Chinese round only needs four solvable problemsorz…………终于到了E的审判时刻了好激动。但是过了一个小时Gerald也没有任何动静。于是我忍不住去问：Hmm, What about the difficulty of E? Gerald：I am thinking. It seems that it is really hard.T_T……坐等Gerald单手屠E。又过了半个小时gtalk终于又响了。我噔噔噔跑过去看：Hm, it is really hard problem.And it seems that the solution is quite new for me.I didn't have a deal with power series.&I didn't use them in contests.Seems that they are very powerful.……哎……不过像这种题面……很容易让人看完之后一拍大腿：啊哈！上帝终于让你落在我手里了！这种先背包再乘卡特兰的裸题！要是不是对生成函数有特殊爱好怎么会去想着去展开生成函数呢……接着，Gerald又让我们考虑下两道E的不合理之处……May be none of participants will solve at least one of them.&What do you think about my offer?怎么办！！我建议pyx把D题改回原来的单点修改，这样可以不写平衡树。pyx说，这题亮点就在区间赋值啊…………为啥……我一直觉得这题亮点在于取模的神奇性质……在讨论中不知不觉把Gerald晾了5分钟。他一定觉得我们很不友好 T_T……于是他又说了几句：OK. I think for you creating easy problem & D will not so much hard.Of course the next contest may be on the date you want, for example the next next contest. In a month, or in a two weeks.&So, you will have a time to think about new problems.（说实话从这几句话中我完全没感觉到CF的出题人在排队 T_T……）怎么办！到底怎么办！pyx：我觉得D考场上可以A啊……你让gerald再考虑下D的难度……？我说，既然你觉得是区间赋值比较好玩，那我们完全可以把前面的区间取模换成一个更加显然能均摊分析的操作吧，这样能减小难度。比如区间开方？是原题……要不改成单点修改？这样说不定只写个set就能AC了~比如区间除以k并向下取整？可惜| &| &a &| &| & &| &| --- | &| & &| &|_ k _| &| & &| & & &a & & || --------- | &= | &--------- ||_ & &j & &_| & &|_ & j * k &_|所以能标记合并。这时pyx又说，难道不能考平衡树吗？我觉得原题超优美的啊……代码也挺优美的啊……深刻怀疑Gerald没想清。接着我和pyx就“D题到底是不是很简单”进行了一次辩论。突然半路杀出来一个杜教：为啥不换了E？说得好，我也想把这个丧心病狂的E给换掉。我觉得起码要等大家都会多项式除法的时候，出这题才有意义。还不如换E呢……pyx：要么我们下次把E扔TCO/CC啥的……留到这个群里的人都退役后出 CTSC 233于是就这么定了。把D放到E，再造一个D题。没有人反对。所有人一致通过。于是我滚去想个新D题。20分钟后……cyb：翻了一下以前的E，感觉原D当E似乎偏简单了一点……pyx：完了……这下我要修改宣传辞了……1h通ABCDE。于是pyx想反悔了。……其实我也觉得原D当E偏简单了一点……不过怎么跟Gerald说？“You are too weak! D is easy enough!”……显然是不可能的……况且我话已经说出去了，怎么着？瞬间又反悔？一点都不靠谱。这个时候pyx摇身一变谈判专家，啪啪啪列了五条歪理：1. 时间不够2. 对于中国人来说解决D太容易了。3. 会有很多人解决D题。4. E题可以缩小范围，不用FFT。（我们原先以为如果把二叉树可取的点权数量减少能不使用FFT，后来发现sb了……）5. 多项式求逆的算法是已经被人提出的算法。我反对！“对于中国人来说解决D太容易了。”是搞毛线……这是典型的地域岐视……况且况且最可怕的是Gerald根本不是说E题要写FFT所以多么多么困难，他直接说要用幂级数，所以很难。这时pyx为了反驳我又改了口风：幂级数求逆不是人人都会的吗？“Recall the algorithm which calculate the inverse of a formal power series F(z)”T_T……那只是我口误好不好……要不还是别反悔了……要是把那道方差的方差出出来当D题？感觉挺爽的。这个时候叉姐窜出来贡献了一道题：*****************（隐藏题面 T_T）不过当时由于种种原因大家没有深入讨论此题 T_T……哎……后来看看还是很好玩的题……20min后我和pyx讨论出了一种D题改简单的方案：区间除以一个数（四舍五入到整数），单点查询，区间赋值。这样只要会写set就能AC了。那么有没有漏洞可钻呢？比如啥奇葩的线段树维护下水之？其实之前我都想吐槽他们xyz大大在CTSC才讲过的区间覆盖的维护方法，你们接着就拿着考。后来我才知道他们是独立探究出来的，只是xyz在CTSC碰巧提到了。接着仔细一看发现两种维护的方法还不同。一个是平衡树，另一个是线段树。于是pyx跑去研究了下，然后我们趾高气昂地得到结论xyz的方法做不了！但是！突然pyx脑袋一转弯，然后发现居然可以用xyz的方法，用个线段树就行了！无限怨念……煮熟的D题飞了……这下可好……相当于一道大原题……xyz论文的简单应用。于是区间赋值再也没有什么意思了。我只好跑去跟Gerald说：Oh.....we find a simpler solution to problem D....just use segment tree is OK.其实这样也算是个圆满的结局了。D题变水了，于是D题是D题难度，E题是E题难度。什么都不用动，什么都不用改。怎料到Gerald的回话让我们吃了一惊。May be, but the hardest in the problem is to get the solution.It is really not obvious that each element decreases log times.神马？你在逗我笑吗？有效的取模只有log n次难道有E题难度？吓傻了！这岂不是到时候会有100多人过E题吗！我一直以为Gerald觉得是后面的平衡树比较值E题难度 = =……毕竟CF的平衡树出得少。pyx：Gerald的关注点到底在哪，怎么这么畸形啊=_=，他想不出来的地方大家不是5分钟就意识到了吗！这次不好说服？？？我整个人都不干了。担惊受怕了一晚上…………我跟Gerald说：改成单点修改，这样想到那个取模的性质之后就能迅速AC了。pyx：我支持原题面，不跟你们玩了，我深深地怀疑Gerald的水平=_=&深深地，你不用打消我这个疑虑，因为你做不到，cf真坑爹=_=。Gerald：I think yes still difficult.&But why we need to change?&Such a version easier than the initial?现在这题够水了吧！怎么还觉得难啊囧……这也有E题难度？那什么题没有E题难度啊囧……于是我抄起家伙跟Gerald辩论，码了一段说明此题不难的理由发了过去。然后Gerald发了一句：Let me think之后就消失了。pyx：我都没法找到词汇形容他……他认为D太难了…全是因为他没有看出取模的结论…我想用看卓亮的眼光看gerald了……一直等回复直到0点。他终于回复了。但是他仍然认为即使改成单点修改也不超过10个人能解决此题。于是我又码了一段说明此题不难的理由，还附带了若干事例。最后Gerald终于说：Hm. Ok, may be I am wrong. Sometimes this happens.然后说单点修改可以当D题。&于是D题变成了单点修改，E题保持不变，终于皆大欢喜了。在此之前的某个时刻Gerald过来询问我们比赛的时间。问莫斯科18:00行不行。我脑残了半天才裹清楚时差是多少，也就是北京时间22:00。有点晚了……于是我们想定到20:00，但是Gerald说有一个比赛的结束时间离20:00太近了不适合。于是最后时间就变成了21:00。时差真是奇妙。我们完全可以这样造句子：“中国人在睡觉的时候，俄罗斯人还在工作！这就是为什么他们是发达国家！”然后不一会儿CF上就显示出了CF Round #250。看看时间，时间真的不多了。如果不想变成CF史上题面、数据、题解出错最多的一场Round的话，接下来还有大量的工作要做。造题周四。被简单多边形玩傻了……不会造啊……不过最后终于造出来了看起来超级随机的玩意儿：&获得了一个成就。计算几何写挂的人你们受死吧哈哈哈哈………………CF出题要在一个叫做Polygon的平台上进行。为啥呢……因为一场CF是多人协作出的……如果不是用Polygon这个平台，那么如果有人修改了点什么东西，就得抱着QQ把文件传来传去。这样就很麻烦了……Polygon上面每个人都可以编辑题目。不过，你编辑的是副本，编辑的时候会记录下你改动了哪些操作。当你点击Commit Changes这个按钮的时候，就会试图去修改主版本。（如果一不小心与主版本产生了莫名其妙的冲突的话……那么请允许我做一个悲伤的表情……）在Polygon上你可以写题面，提交数据生成器用shell造数据，在Polygon上对拍，在Polygon上卡暴力。总之用起来非常爽……一本满足。对于一道题目，除了要搞题目描述、样例、数据、标程之外，CF还有些其它的东西。1. checker. & CF的所有题目都是special judge。checker用于在评测时检验选手输出是否正确。2. validator. 这东西我还是头一次写。比如要是比赛时，有一个人来hack别人，搞了组数据。但是数据不合法，要是直接扔给标程，标程估计会RE。那么怎么办呢？于是就有了validator，检验别人hack的数据是否符合规范。当然了，这东西还有其它用途，Polygon会自动运行validator来检查生成的tests是否符合规范，以防止坑人。这样就给数据上了一道保险。不过大家想想看写这两个玩意儿的难度。假设我就是读入一个实数，然后判判与标准***的差距。好，那么怎么读呢？这还不简单？scanf("%lf", &a);但是！如果输入数据是"wahahahawobushishishu!!!!"呢？就读入失败了啊……于是你又会说通过scanf的返回值来判断云云……其实CF提供了个很方便的库testlib.h。之前久仰大名，这次终于有机会写写。发现果然好用。不多说了，你可以在上找到这个库。然后我来摘录一下CF出题人的自我修养。感觉CF规定得真是仔细：1. 准备一场CF包括：题目、比赛通知、题解。2. 你的题目必须是独一无二的。你不能从以前用过的题目中抄袭它的想法。PLEASE BE FAIR WITH THE COMMUNITY。（这句英文我觉得我翻译过来就变了味道 T_T……）3. 空间限制必须是256MB，时间限制至少是出题人的java程序运行时间的两倍。（惊呆了！从此没人卡常数！）4. 题面必须清晰好懂，没有语法错误。建议写得短短的……（顿时就想起了某些题目有半个网页的题目描述……）5. 题目背景中不要写数据范围，全部都要写在输入格式里。6. 请参考以前CF的题目描述的格式来写题目描述。如果你不知道怎么清晰地描述输入输出格式，请找与之类似的题目进行仿写。7. 题目描述中的数组下标最好从1开始。（我觉得这是个非常重要的但容易被人忽视的细节问题！T_T……）8. 你必须限制被你提到的所有的变量的范围。如果你提到一个字符串，你必须写明哪些字符可以出现在这个字符串内。（顿时联想起有些OI题就说XXX是个数，连到底是实数还是整数还是正整数还是非负整数都不告诉我！真是捉鸡啊……）9. 题目的tests中必须包括各种各样的数据，而且应该有各种各样的达到最小数据范围的数据和达到最大数据范围的数据。也就是说如果1 &= n &= 100000，那么数据中既应该有n = 1，也应该有n = 100000。（想想我们普通OI题中的数据……由于只有10组经常由于数据水而放过错误的程序……基本上没有什么题会照顾到n = 1最小数据。对于一个完美主义者来说这样的数据显然是不达标的）10. 你应该写个暴力。11. 你应该拿标程与暴力对拍。12. Div.2的题的pretests要很强，能让应该超时的程序在pretests上就TLE掉。但是你可以让这个点毫无意义。比如给n个数排序，你可以用n个1来确保选择排序不能过。13. 确保读错题的人不能过pretests。14. 建议添加极端数据，但是不必是所有极端数据。确保数组开小的人不能过pretests。15. 不要让时间复杂度很高但做了大量常数优化的人AC。16. 每道题至少2个样例。每道Div.2的题目的前两个样例必须有样例解释。17. 如果要使用long long，请确保不开long long的人不能过pretests。周五中午，我的题目大致造好了……不过其它人的貌似还各种缺……到晚上大家题目终于齐了……很遗憾他们没有仔细读须知……我钻进他们的题目中去看发现到处都是问题……把题目的pretests造得超级弱什么的……甚至tests也超级弱……甚至不给样例……还有validator也不写……后来pyx和cyb告诉我是他没来得及造数据之类…… T_T钻进pyx的Div.2 B lowbit那题改了一通题面。往前方一看，距离6月1日只有有限时间，但是要做的工作却是无穷的呢……CF的很多须知没有被执行。Tester也还没开始工作。顿时有种很不好的预感，感觉当天晚上要狂发对于题目描述的修订，狂改数据，发现checker、validator有错……最后变成一场unrated。然后背上"Chinese round, interesting"的千古骂名。也许结局没有我想得那么坏？是该发预告贴的时候了。于是去贴吧发了个预告贴。每次我发预告贴总会想起“只要998！只要998！XXX抱回家！”“你还在等待什么！赶快拿起***拨打XXXXX！”于是就写成和这玩意儿一样的风格的预告贴了233……那么是不是该在CF发announcement了？……可是我们还不知道Tester具体是哪几位……不知道大家有没有时间验题。贴吧上面可以把所有知道题目的人都拉进来称作Tester，但是CF可别乱说吧……而且也不知道score distribution。要跟Gerald讨论一下。所以只好放一放了。周六。起床时发现杜教已经用python水完了Div.2 A,&Div.2 B,&Div.1 A,&Div.1 B。无限仰慕。由于需要Java的标程的时间的两倍来定时限，所以叉姐变成了用Java的Tester~然后叉姐用Java水掉了Div.1 D。昨天晚上hza说分治好像能做Div.1 E。然后我说hza去写一个吧！hza：我坚决不写。我CTSC就是写了个类似的分治然后被卡到死的，已经留下心理阴影了。然后hza已经从阴影中走出来了233……因为他用分治4s水掉了Div.1 E……当然了，我的标程跑的是1.5s。不过我超良心把时限设到了5s。叉姐：加大数据！卡掉愚蠢的O(n log^2 n)！pyx：减小时限！我：就这样吧……让分治过挺合适的……hza：我觉得让分治过不合理。叉姐：我觉得挺好啊，这难度一下子就fair了，像一套简单的可以AK的CF了。我：出0ac的才叫不合理。hza：= =……难度不符合Chinese round传统了pyx：不符合传统+1我：……为啥要符合……我讨厌出0ac的题……考试时和考后都没人看的话……就逗了……dyh：出0AC的心态呢。。。？我觉得让分治过挺好的啊。。。多么的有爱。hza：卡分治说不定会很困难，常数优化空间好像挺大的。。我：别把常数不好的正解卡掉了pyx：好吧……我觉得也行……叉姐：我觉得，如果Java写的都能过，那肯定怎么都卡不掉，我晚上回来写一个。接下来只要Java能2.5s内出解就能安心5s不违反CF规定了啦啦啦……但是这样E就变水了……于是hza说：我还是觉得D题应该加个区间赋值……我觉得这样难度会平衡点……接着赞同声一片。这个时候人群中冲出来一个vfk：我反对！………………囧…………为啥D题改难的建议会被反反复复地提出来……已经是几天前定下来的事情啊……其实单点修改能不放到E已经谢天谢地了……况且马上就要CF了……又改题面？……真是不靠谱……hza：好吧，既然已经说好了就不反悔了。。叉姐：题不要出太难嘛 。难为自己难为别人。。pyx：好……那就这样吧……hza：果然民主投票打不赢vfk的独裁233……因为我垄断了跟Gerald的通讯哇哈哈……得快点了……我们的题面还要翻译成俄文呢……所以先把题面搞OK吧……此时我们的题目的标题全部统一成了The child and XXX，第一句话已经全部统一成了A long long time ago, there is a XXX and a child. The child likes playing with the&XXX.&(Why long long ago? because you must use a long long to store the time interval)XXX分别是homework, set, toy, zoo, polygon, sequence, treehza自愿冲上前线审察题面。果然，hza神勇地像开着轰炸机般地摧毁了好多语法错误以及句子中的歧义。转眼到了下午。hza继续审察题面。pyx：谁帮我造下数据吧…下午要上文化课=_=我：pyx不是要赚美刀吗 T_T！！！！别这样啊！！！！我这怎么忙得过来……pyx：我明天上午造数据。主要是今天上午考试去了=_=我此时已经码好了announcement。顺便赞一下文本编辑器……我在网站的编辑器上写英文我才发现简直太爽……因为要是有个单词拼错了会在下面划红线标出来……对于我这种词汇量捉鸡君简直就是福利。但是用英文怎么吼“只要998”这种句式啊！我忘记我曾经听哪位英语老师说过……能用英语跟别人吵架说明你的英语很厉害了……想了想确实觉得难度不小……哎……我这种英语渣渣……想写一句“让我们在欢乐地解题度过儿童节吧！”都写不出来。求问怎么翻译“欢乐”……翻译成happy就超级没感觉了……抓耳挠腮最后只好作罢……然后在hza的帮助下写个好点的开头，于是就成了这个样子：Happy Children's Day everyone. What should we do to celebrate the special holiday? Of course, another Codeforces Round is your best choice!A long long time ago, there is a child who is our friend. Now he has faced a lot of algorithm problem, could you please help him?We invite you to participate in Codeforces Round #250, which will take place at&. This round will be held in both divisions.&Note that the starting time of this round is quite unusual.Why? Because it's yet another CF Round held by Chinese! We prepared many interesting problems for you.Are you getting excited? Don't miss this round!The problems were prepared by Delayyy, Picks and me. This is our first Codeforces round~~~~.Many thanks to Gerald, who gave us enormous help during the prepara to ftiasch, Kissshot and&3, who are the t and to MikeMirzayanov, who created such a wonderful platform.In Div. 1, scores for each problem will be 500-00-3000.In Div. 2, scores for each problem will be 500-00-2500.Look! Your high rating is waiting for you! What are you waiting for?Just participate in this contest and write code fast and nicely, and you will take the high rating home!Good luck and have fun!还是觉得用中文吼：“rating带回家！rating带回家！”比较带感……然后我问Gerald这个score distribution靠不靠普，Gerald没回话。只好放一放了。然后我注意到Div.1 C还没有人Test……我：@杜教……求Test Div.1 Cdyh：在,b之星ing。。。TAT无限仰慕百度之星爷……然后叉姐3小时前外出了……囧……要做的事情还很多……去补西墙就忘了还要补东墙……于是我列了一个未完成任务列表：（下面标识的ABCDEFG分别按顺序对应Div.2 AB Div.1 ABCDE）To Do List:例行任务：审查每道题的validator、checker和标程(还差E题)。 validator和checker非常重要，特别是AB题，尤其要仔细检查，如果出错被人钻bug可能会导致unrated。A.1. 缺少pretest2. 提交一个把A.、B.这种前缀也算进description长度的程序，确认它不能过pretest。3. 添加一个四个description长度都到达100的数据到pretest中。4. 时限是否应该是1sB.1. 缺少和1 1的数据，要添加到pretest。2. 无解的数据太少。C.1. 时限是否应该是1s2. 缺少pretest3. Test数量过少4. 确认数据里既有连通图也有非连通图。5. 缺少m = 0的数据6. 缺少n = 1的数据7. 最好加个完全图进去。D.1. 时限是否应该是1s2. 缺少样例解释3. 缺少pretest4. 最好放个wiki解释什么是期望。5. 缺少n = 1, m = 0的数据6. 缺少稠密图的数据E.1. 没有人Test2. 需要提交各种写挂的程序F.1. pretest太少2. test太少3. 需要添加n = 1的数据4. 需要添加n = 10^5的数据5. 需要卡到log^2n的数据6. 缺少样例2的解释7. 输出long long要注明%I64d8. 描述区间操作建议不要用[l,r]而改用更清楚的方式表示。G.暂无接着按照列表上的逐个消灭就好啦！开心一刻：我给A题加了个100字数据A.He_nan_de_yang_guang_zhao_yao_zhe_wo_men_mei_guo_ren_lian_shang_dou_xiao_kai_yan_wahaaaaaaaaaaaaaaaaB.Li_bai_li_bai_fei_liu_zhi_xia_san_qian_chi_yi_si_yin_he_luo_jiu_tian_li_bai_li_bai_li_bai_li_bai_shiC.Peng_yu_xiang_shi_zai_tai_shen_le_jian_zhi_jiu_shi_ye_jie_du_liu_a_si_mi_da_zhen_shi_tai_shen_le_a_aD.Wo_huo_le_si_shi_er_nian_zhen_de_shi_cong_lai_ye_mei_you_jian_guo_zhe_me_biao_zhun_de_yi_bai_ge_zi_a你们AC了之后一定没去注意tests里面有这货吧！！2233333……下午4点，hza对题面的大清理活动进行完毕。于是紧接着我让他去test一下Div.1 Chza果然厉害，AC了之后以各种奇葩的写挂方式去test数据是否很强。接着hza发现n^4能过……好吧我去造个凸多边形的数据。晚上8点，Gerald终于回话了。把我的announcement提到了首页。/blog/entry/12490然后说，Google Code Jam之后帮我们审一下题目，并联系翻译。announcement发出去不久，我们就看见了一条评论：cin && A long long time ago, there&is&a child who&is&our friend.cout && A long long time ago, there&was&a child who&was&our friend./*&UPD:&Thanks for the Round :).Good luck and have fun all */吓傻了！！！这可不是小问题！我们所有题面的第一句话都要改！而且要玩a long long time ago的话，整个题面全要换成过去时。……偌大一个出题团队，居然没有一个人发现了这一点…………抢救不回来了……只好把所有的a long long time ago全删掉了……hza：（果然事先不把人设和世界观搞定就很容易出bugcyb：→_→ 唉，当初应该认真做一下人设的。。接着我、hza、cyb按照未完成任务列表上的事情忙成了一团……晚上9点，叉姐归来码Java版Div.1 E。我：谁快来教教我怎么随机生成一个凸多边形……被虐傻了……我只会找个凸函数然后@%￥@%#%……叉姐：随机产生2^n个点，这样就能得到n个点的凸包了。233333……需要有人来test一下Div.1 A的数据强度，于是我去@杜教。dyh：要战GCJ了TAT &尼萌都不战gcj吗？（我发现随口找个比赛就能推掉的感觉太nice了）晚上11点，叉姐写分治+FFT突然觉得身体不适。叉姐：TAT……头晕目眩。窝一定是感冒了……窝正抱着自己瑟瑟发抖QwQ。于是叉姐只好离开了战斗。T_T……momo……转钟时，未完成任务列表所剩无几：To Do List:例行任务：审查每道题的validator、checker和标程(已完结)。 validator和checker非常重要，特别是AB题，尤其要仔细检查，如果出错被人钻bug可能会导致unrated。A.暂无B.暂无C.1. 时限是否应该是1s2. 确认奇怪的贪心WA掉D.1. 缺少稠密图的数据E.暂无F.暂无G.暂无转眼就到六一了呢……周日，凌晨一点，未完成任务列表除了例行任务外只剩了一项：C.1. 确认奇怪的贪心WA掉当然还有其它任务：1. 每个出题人认真检查validator和checker，确保不出错。2. 用latex的格式写一份题解。当然还差Div.1 E的时间限制问题……要等叉姐的程序…… T_T早上八点。叉姐：QwQ 爷挣扎着起来写了。太神了！！！带病写FFT！这是怎样的精神！！！！过了一会儿叉姐表示写完啦！叉姐：进入到紧张地调试阶段。QwQ紧接着发现了另外一件超级神的事情。Gerald在凌晨4点的时候帮我们修改了Div.2 AB Div.1 AB的题面，一直忙碌到现在，还在修改Div.1 C的题面。大概是时差问题？也许俄罗斯那边的时间是大晚上？掐指一算发现对应到俄罗斯是凌晨0点到4点。顿时就被Gerald的敬业精神感动了……我们赶紧去看Gerald修改的内容，发现修改得非常好。大家有时候会抱怨题目太长……但是其实如果你读的是我们未经Gerald修改的题面的话！哇哈哈哈哈！你会觉得Gerald改得好短的！确实删了很多废话……之前pyx的Div.2 B的题目描述，里面包涵了大量熊孩子到pyx家里来捣乱的各种心里活动描写，简直可怕……Gerald改了题面之后顿觉心情舒畅。Gerald还检查了我们的checker和validator……有些题目他貌似觉得这个不满意直接自己重写了一份。八点半之后，Gerald大概是睡觉去了吧……没有任何动静了。九点半，叉姐终于消灭了最后一个错误——一不小心把(-g)当作g的乘法逆……于是叉姐的Div.1 E写好了。果然Java、FFT、分治三个东西结合在一起就是慢……足足跑了7s。这哪成啊……如果时限给成14s我们就能创造历史了。……要么现在把分治都卡掉，只剩多项式开根。……要么把Java的分治都卡掉留下C++的……（叉姐：考虑一下Java的感受好吗！）……要么做足常数优化把Java的时间压下来……怎么常数优化呢？这个时候人群中冲出来一个hza：您一次更新进行了几次fft？叉姐：好多下。有两次卷积，所以是6次？过了几秒钟。叉姐：我觉得应该可以优化！这么一说有希望了啊！！！由于是a * b * c……而数组足够大。所以叉姐丧心病狂优化成了IDFT(DFT(a) * DFT(b) * DFT(c))降到了5s……叉姐突然嘟哝了一声：诶不对啊……之前版本的数组长度好像不够大，我觉得我之前的算法是错的！于是忙活了半天分析原因。结果发现确实是对的。于是数组长度就能除以2了。顿时快了不少。只要3.6s。不过这样的话时限就应该是8s？于是又去@叉姐叉姐说：我觉得我还能优化！接着对着FFT的代码搞了一通。………………用时纹丝不动。…… = =……坑爹……不过还是咬咬牙开7s时限吧……下午本来有湖北省队互测Week 2。由于CF题目中各种问题实在无法三心二意地打比赛，只好中途离场。大约1点半我突然想起个事……Div.1 A还木有人去确认奇怪的贪心会WA掉……全随机数据真的靠谱？……然后我去试了一下按点权 + 度数贪心A掉了！cyb你坑爹呢？赶紧把cyb抓来造数据 = =……一下午在对题目的修修补补中度过。我和pyx码好了题解。pyx一直盯着CF上的情况。“announcement的赞突破250了！”“好多人在comments里说好期待！说是funny round。我觉得他们要大失所望了。”“ACMonster报名了！！”“tourist大爷怎么不来T^T&”“liouzhou101报名了！”下午3点Gerald重新上线。继续帮我们改题面。想想他真是辛苦。这也是很无奈的事了。他要是不审一遍，俄文翻译根本无法开工。转眼间就下午5点了。Gerald发给我了我的那个announcement的俄文版本，要我添加上去。然后我切到俄文版。…………………………神马都看不懂……连发布博客的那个按钮都找不到。在黑暗中摸索了好久总算把俄文版折腾上去了……&俄文的翻译还在一直工作。题目的俄文版一点一点添加了上来。CF的开考钟声马上就要响起。下午6点，还有3小时。hza给山东小朋友讲课讲完了。dyh过完六一儿童节回来了。叉姐外出归来。于是人齐了，大家聚在一起等待。不过待会儿怎么围观比赛？叉姐：我要上帝视角啊！cyb：这就是传说中的上帝视角吗？吓傻了！！！什么时候出现的！！赶紧进去看。发现居然有各种神奇的权限。比如把报名了比赛的人踢出去，让Div.1选手以正式选手身份参加Div.2（计rating）。比较好奇那个“add new problem”按钮……但是没敢点。感觉我连删掉这场比赛的权限都有！爽爽爽爽爽。距离CF 250还有一个半小时。我们还在对部分细节做小小的修饰。pyx继续播报前方情况。“xyz大爷报名了！！！”“7k+报名了！！！！！！！！！！”“Egor报名了……”“国家队就鼎爷没报名了”点赞的人数持续增加。距离CF 250还有一个小时。我们对数据的健壮性做最后一次检查。确认了都包含了最小数据。Gerald还帮我们又加了几组数据。此时，800人报名。距离CF 250还有十五分钟。千万不要有差错。此时我还在和cyb纠结他的题解中的一些问题。pyx：“999人报名了！！！”“鼎爷报名了！国家队爷齐了！”VFleaKing：The contest is approaching. I'm getting excited~~~Gerald：AhaGerald：I am tooGerald：But for me it is usual feelingVFleaKing：Oh? usual feeling?Gerald：I've prepared about 150 CF rounds有种莫名的感动。距离CF 250还有七分钟时，clj报名了。吓傻了！！终于有人肯定能水过Div.1 E了！距离CF 250还有5分钟。报名关闭了。报名人数超过1000了。xiaodao没有报上名。真是个悲伤的故事。安排了一下分工。hza专门盯着hack。pyx专门盯着solution。我和cyb两边都观察。还有5秒。CF网站今天有点卡。还有4秒。这么卡岂不是会让大家比得超级不爽。还有3秒。我们题面够清晰了吗？我们的数据造得够好了吗？还有2秒。大家对于今天的题是否能满意？clj能否成功AK？还有1秒。真的要开始了！！！来吧！！！
阅读(6325)|
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
历史上的今天
loftPermalink:'',
id:'fks_',
blogTitle:'一场CF的台前幕后（上）',
blogAbstract:'等你等了五千年，只为这一刹那的回眸一笑。前奏大约4月份的时候，业界毒瘤pyx噔噔噔跑过来说：“酷爱！我YY了一道题！准备当CF的C”我当时就被吓傻了。\"Yet another Chinese round?\"“区间取模，区间求和”感觉这题还不错？不过pyx嫌水了……好办！当时我刚刚出完动态仙人掌不久，于是一拍脑袋说：把这个问题出到仙人掌上去！当然被pyx鄙视了……后来一直就没啥动静，直到5月底的CTSC。试机的时候pyx给我看了套他出的神题……里面有一道题……我不小心读成了下面这个样子：“给定n个m维的模2意义下的向量，求线性无关组的数目”，然后发现好像不可做……但是我们可以改题目！求基的数目！',
blogTag:'',
blogUrl:'blog/static/',
isPublished:1,
istop:false,
modifyTime:2,
publishTime:7,
permalink:'blog/static/',
commentCount:26,
mainCommentCount:9,
recommendCount:2,
bsrk:-100,
publisherId:0,
recomBlogHome:false,
currentRecomBlog:false,
attachmentsFileIds:[],
groupInfo:{},
friendstatus:'none',
followstatus:'unFollow',
pubSucc:'',
visitorProvince:'',
visitorCity:'',
visitorNewUser:false,
postAddInfo:{},
mset:'000',
remindgoodnightblog:false,
isBlackVisitor:false,
isShowYodaoAd:false,
hostIntro:'My name is VFlea King.',
hmcon:'0',
selfRecomBlogCount:'0',
lofter_single:''
{list a as x}
{if x.moveFrom=='wap'}
{elseif x.moveFrom=='iphone'}
{elseif x.moveFrom=='android'}
{elseif x.moveFrom=='mobile'}
${a.selfIntro|escape}{if great260}${suplement}{/if}
{list a as x}
推荐过这篇日志的人：
{list a as x}
{if !!b&&b.length>0}
他们还推荐了：
{list b as y}
转载记录：
{list d as x}
{list a as x}
{list a as x}
{list a as x}
{list a as x}
{if x_index>4}{break}{/if}
${fn2(x.publishTime,'yyyy-MM-dd HH:mm:ss')}
{list a as x}
{if !!(blogDetail.preBlogPermalink)}
{if !!(blogDetail.nextBlogPermalink)}
{list a as x}
{if defined('newslist')&&newslist.length>0}
{list newslist as x}
{if x_index>7}{break}{/if}
{list a as x}
{var first_option =}
{list x.voteDetailList as voteToOption}
{if voteToOption==1}
{if first_option==false},{/if}&&“${b[voteToOption_index]}”&&
{if (x.role!="-1") },“我是${c[x.role]}”&&{/if}
&&&&&&&&${fn1(x.voteTime)}
{if x.userName==''}{/if}
网易公司版权所有&&
{list x.l as y}
{if defined('wl')}
{list wl as x}{/list}