2013-team5/南京赛区小结
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
by Dark_sun
这场拆开题后,根据惯例,我从A,B,C开始看
A题是一道大水题,题意是让你算GPA......等级A+对应多少,B-对应多少之类的.
我写完发现对面上交已经过了,一交结果返回了WrongAnswer......
我心里顿时一紧,因为首WA很伤而且影响士气的,还是大水题......
检查了一下没发现什么错误,自己做了组case才发现,原来我一个函数的返回值写成的int,但是绩点是double, 改完就过了, 2Y18min.
之后发现J题有人过了,于是我赶紧过去看J.
J的大意是袋子里有一堆球, 总共有三种颜色, 一开始桌子上没有球, 你需要一个个把球放成一列. 每次放置你可以将当前的球放到该列的任何位置, 同时会产生一个score, 即为原序列中,当前位置之前的球不同颜色数加上原序列中当前位置之后的球的不同颜色数.
这道题也比较简单,和kotomi手算了一下后就发现的规律,就是先将球数按颜色排序, 先放两轮(对于每一轮,每种颜色的球放一个,某种颜色没有则不放), 看看能放多少个球.
这样做的意义实际上是能放多少个不同颜色的球在两侧, 然后其他的球都放中间就行了.
这道题过的速度还行, 1Y43min
写完发现I题有人过了,于是我去看I.
I题的大意是给你N个颜色,每个颜色有一个值.
一个蛋疼的人第i天会从这N个颜色中随便选择i个颜色来混合成一种新颜色,其值为这i个颜色的异或和. 总共有C(N,i)种选法. 问你每一天所有可能选法得到的新颜色的值的和.
一开始感觉没啥思路,想了想之后AI学长果断指出直接每一位分开来处理就好了.
也就是说可以通过DP求出每一天,在某一个数字位会出现多少个1.
于是我赶紧上去写,写完DP后发现结果不对......一开始以为边界错了,于是测试了各种边界还是不对(其中作死浪费了一些时间).
我把代码打印出来debug,同时AI学长上机器写C题.
折腾了半天,我才发现我这题方程的另一种情况写错了.....
因为这类方程一般两种情况都是对称的......但这里是异或!
改了2个字符后,成功过了样例,一交,结果TLE.
因为我dp数组开了很大,每次初始化都memset了整个数组,可能会T.
改完之后一交,结果返回了一个WA......原因是我最后算答案的时候只算了10位的答案,应该是32位......马上改完再交就过了,3Y127min.
这题做得比较伤,debug花了很多时间不说,还因为不应该的错误错了2次.
不过还算好的是这题基本上没有占用机器多少时间.
在AI学长继续写C题的期间,我去看了下B.
B的大意是这样的,给你一个菜价牌,有X和Y两个值,初始为1. X是个数,Y是总价.
你可以按两个按钮,一个是使Y加1,此时该物品的单价也会相应上升.
另一个可以使X加1,同时Y也会增加相应的单价. 但是Y只会显示整数部分.
问你如何按得尽量少的情况下, 使X和Y变成给定的值X'和Y'.
这题想了想,还是很快想到了解法.
因为先把Y弄大的话,单价涨的越快,因为每按一次单价会增加1/X.
但是不能超过最大值(Y'+0.9999)/X'.
所以X每加一,操作Y使单价不断逼近最大值就好了.
代码很快就写完了,因为涉及到浮点数操作就检查了好久没有交. 期间AI学长很扎实地把C过掉了,1Y181min. 我想了想觉得我的代码没问题, 于是交了, 1Y183min.
两分钟内连过两题好像很厉害的样子.
这个时候我们出了5题,此时6题可以冲进前10,此时还剩两个小时,也就是说我们再出一题就能夺金!
后面两小时真是刺激,我们看到K题过得人比较多,于是去想K,想了想还是有点思路. 后来看到2队的学长们1Y过了K,更加坚定了我们合力做K的决心.
我们想到了很多看起来靠谱的做法,有些小激动,但是仔细分析之后发现还是不靠谱......
如此纠结了好久,直到剩下半个小时的时候,还是没有想出靠谱做法.
于是我开始写一个有那么一点点希望过的一个乱搞的算法.
直到还剩10分钟,我发现没过样例,手算样例之后发现,妈呀,我们做的不是同一道题啊!!!
K题大意是这样的,给你一棵树,有N个节点(N<10W),每个节点有个权值,问你能否找到任意一条路径,使该路径上的权值的乘积mod一个大素数后的值恰好为K.
题目是输出该路径的两个端点,使这两个点的字典序最小.
而Kotomi学长直接跟我们说的求一条路径,使字典序最小,没说输出的事情!
妈呀,做了半天做得不是同一道题啊...这完全不一样啊...
后来问学长做法,发现我们第二步都想到了,但是第一步完全没往LCA的方面去想!
因为要保存路径还要保证字典序最小!!!
不过这也不能完全怪Kotomi,我和AI学长还剩两个小时,都没有去算样例,是在是不应该.
但是考虑到当时有点小激动......
最后实际排名是38名,银牌. 上一场也是38,银牌......
真是"沉着应对,稳定发挥"......
虽然拿银牌这种成绩在意料之中,但还是感到有些许遗憾.
因为最后关键的两个小时因为这样的原因打了酱油[del]其实应该直接去吃饭[/del], 再没出过题, 还是感到有些可惜.
不过没有夺金也好[del]虽然不脑残也不一定能蹭上去[/del],不会让自己懈怠,从而让自己更加努力吧.
好好治疗一年,明年再战![del]再脑残就回老家下井挖煤[/del]
}}}by Dark_sun
这场拆开题后,根据惯例,我从A,B,C开始看
A题是一道大水题,题意是让你算GPA......等级A+对应多少,B-对应多少之类的.
我写完发现对面上交已经过了,一交结果返回了WrongAnswer......
我心里顿时一紧,因为首WA很伤而且影响士气的,还是大水题......
检查了一下没发现什么错误,自己做了组case才发现,原来我一个函数的返回值写成的int,但是绩点是double, 改完就过了, 2Y18min.
之后发现J题有人过了,于是我赶紧过去看J.
J的大意是袋子里有一堆球, 总共有三种颜色, 一开始桌子上没有球, 你需要一个个把球放成一列. 每次放置你可以将当前的球放到该列的任何位置, 同时会产生一个score, 即为原序列中,当前位置之前的球不同颜色数加上原序列中当前位置之后的球的不同颜色数.
这道题也比较简单,和kotomi手算了一下后就发现的规律,就是先将球数按颜色排序, 先放两轮(对于每一轮,每种颜色的球放一个,某种颜色没有则不放), 看看能放多少个球.
这样做的意义实际上是能放多少个不同颜色的球在两侧, 然后其他的球都放中间就行了.
这道题过的速度还行, 1Y43min
写完发现I题有人过了,于是我去看I.
I题的大意是给你N个颜色,每个颜色有一个值.
一个蛋疼的人第i天会从这N个颜色中随便选择i个颜色来混合成一种新颜色,其值为这i个颜色的异或和. 总共有C(N,i)种选法. 问你每一天所有可能选法得到的新颜色的值的和.
一开始感觉没啥思路,想了想之后AI学长果断指出直接每一位分开来处理就好了.
也就是说可以通过DP求出每一天,在某一个数字位会出现多少个1.
于是我赶紧上去写,写完DP后发现结果不对......一开始以为边界错了,于是测试了各种边界还是不对(其中作死浪费了一些时间).
我把代码打印出来debug,同时AI学长上机器写C题.
折腾了半天,我才发现我这题方程的另一种情况写错了.....
因为这类方程一般两种情况都是对称的......但这里是异或!
改了2个字符后,成功过了样例,一交,结果TLE.
因为我dp数组开了很大,每次初始化都memset了整个数组,可能会T.
改完之后一交,结果返回了一个WA......原因是我最后算答案的时候只算了10位的答案,应该是32位......马上改完再交就过了,3Y127min.
这题做得比较伤,debug花了很多时间不说,还因为不应该的错误错了2次.
不过还算好的是这题基本上没有占用机器多少时间.
在AI学长继续写C题的期间,我去看了下B.
B的大意是这样的,给你一个菜价牌,有X和Y两个值,初始为1. X是个数,Y是总价.
你可以按两个按钮,一个是使Y加1,此时该物品的单价也会相应上升.
另一个可以使X加1,同时Y也会增加相应的单价. 但是Y只会显示整数部分.
问你如何按得尽量少的情况下, 使X和Y变成给定的值X'和Y'.
这题想了想,还是很快想到了解法.
因为先把Y弄大的话,单价涨的越快,因为每按一次单价会增加1/X.
但是不能超过最大值(Y'+0.9999)/X'.
所以X每加一,操作Y使单价不断逼近最大值就好了.
代码很快就写完了,因为涉及到浮点数操作就检查了好久没有交. 期间AI学长很扎实地把C过掉了,1Y181min. 我想了想觉得我的代码没问题, 于是交了, 1Y183min.
两分钟内连过两题好像很厉害的样子.
这个时候我们出了5题,此时6题可以冲进前10,此时还剩两个小时,也就是说我们再出一题就能夺金!
后面两小时真是刺激,我们看到K题过得人比较多,于是去想K,想了想还是有点思路. 后来看到2队的学长们1Y过了K,更加坚定了我们合力做K的决心.
我们想到了很多看起来靠谱的做法,有些小激动,但是仔细分析之后发现还是不靠谱......
如此纠结了好久,直到剩下半个小时的时候,还是没有想出靠谱做法.
于是我开始写一个有那么一点点希望过的一个乱搞的算法.
直到还剩10分钟,我发现没过样例,手算样例之后发现,妈呀,我们做的不是同一道题啊!!!
K题大意是这样的,给你一棵树,有N个节点(N<10W),每个节点有个权值,问你能否找到任意一条路径,使该路径上的权值的乘积mod一个大素数后的值恰好为K.
题目是输出该路径的两个端点,使这两个点的字典序最小.
而Kotomi学长直接跟我们说的求一条路径,使字典序最小,没说输出的事情!
妈呀,做了半天做得不是同一道题啊...这完全不一样啊...
后来问学长做法,发现我们第二步都想到了,但是第一步完全没往LCA的方面去想!
因为要保存路径还要保证字典序最小!!!
不过这也不能完全怪Kotomi,我和AI学长还剩两个小时,都没有去算样例,是在是不应该.
但是考虑到当时有点小激动......
最后实际排名是38名,银牌. 上一场也是38,银牌......
真是"沉着应对,稳定发挥"......
虽然拿银牌这种成绩在意料之中,但还是感到有些许遗憾.
因为最后关键的两个小时因为这样的原因打了酱油[del]其实应该直接去吃饭[/del], 再没出过题, 还是感到有些可惜.
不过没有夺金也好[del]虽然不脑残也不一定能蹭上去[/del],不会让自己懈怠,从而让自己更加努力吧.
好好治疗一年,明年再战![del]再脑残就回老家下井挖煤[/del]