八月 30th, 2009 () ZJU, acm › ben1222 › No Comments
今天的浙大月赛…
这回只出了4题…第一名有8题…
最后rank36
感觉退步了很多…这样下去会悲剧的…
一开始从A开始看,直到看到C感觉有点想法,因为感觉做过类似的,容斥原理
于是就开始敲,这时听到sky在说D题可以凸包再凸包不断做就可以知道层数
心想这不是很简单嘛…直接上模板,改改弄弄,交之,AC
此时BCD都有人过…
继续敲C…开始用的是枚举二进制位,最后弄好交上去,TLE了…我汗…
改成dfs版本就AC了…
此时很搞笑…overmind和我们都是37分时过了D,然后overmind在67分时过了B,我们在67分时过了C…真巧啊…
看到他们过了B,于是在想B,想来想去没什么好方法…
于是看看别的题,看了G,信号与系统,感觉是高斯消元,H,圆周和矩形交,感觉不难的计算几何
但是心里在想着B,所以也就没有心思敲G和H
过了很久,感觉B还是没想法,于是先敲了个G的高斯消元
因为输出的是小数点后第一个非零位…输出处理有点麻烦…
不过不管怎样,怎么改都是WA…没信心了…
sky说B可以先缩点,缩成一个点的那些点可以用一个环也就是这些点数相当的边留下,剩下的感觉是最终可以表示成一棵树,所以算下有多少个不相连的部分就能算
写之,交之,WA了…后来发现反例…于是又搁置了
我则是看这标题不爽,说不是floyd我偏用floyd来做,把i->k->j的i->j边认为可以删除
结果WA了几次还TLE了几次…
无奈放在一边…去敲H题计算几何
慢慢来,然后AC了…此时已经是258分了…
然后看这个B…突然想到,缩点和floyd合起来用怎么样呢…写之,交了一次不过,又随便改了点,抱着继续WA的心态交了…当看见AC的时候还觉得是不是看错了…
总之就这么莫名其妙的过了
E题也有很多人过,二段跳,就是抛物线…ssjia推了公式好不容易出了样例结果WA掉了…改了精度还是WA…郁闷…
然后郁闷到结束
简述:
A: 苹果树,最小费用搬运苹果使得每个节点苹果数方差最小,网络流?
B: 给一张floyd完的有向图,求保留最少边使得可以floyd出这张图,缩点+floyd
C: 幸运数字,容斥原理
D: 层层警戒,层层凸包
E: 二段跳,推公式
F: 四面体魔方?
G: 信号与系统,高斯消元?
H: 圆周和矩形交的长度,计算几何
I: 做个简单的shell…就是目录的一些功能,没看也没想
BCDH的详述
八月 29th, 2009 () PKU, acm › ben1222 › 1 Comment
军训提前结束了…因为流感暴发…几百人倒下了…我也是其中一个…
高烧39度以上…现在已经好的差不多了…
话说我发烧那天正好是pku月赛…
看到某人说B很简单,后来他又总超时过不了…于是来做了下这道题…
顺便说下,pku上消失了一道题,题号是3698,因为我写的一个pku上拉下每个volume页面里的数据的程序在vol27就停住了…然后answer发现少了这题…
说了这么多无关的…下面开始正文
3741 Number System Converter
题意是有两个进制转换器,其中P可以把数字当作P进制转换成10进制,不过不会检查输入数据的有效性,另一个是Q,可以把10进制数转换成Q进制
给定初始值N0,依次进入P,Q,P,Q,…如此循环,直到最后这两者输出的都是相同的数字…
1<P<Q<37
N0不超过5,000,000位
其实中间不应该是10进制,而是大于等于Q的进制,否则不会一定有解了…
因为十进制比较好理解,所以用十进制当作中间量了吧…
可以改一下描述,变成一个转换器,是把P进制转换成Q进制,然后不断自己输出给自己输入直到数字不变
不过还是采用原先的描述吧,无视那个恶心的地方…
当测试了几组小数据后可以发现一个规律…虽然没有证明…
考察做了第一步转换后得到的数字N1
我把N1当作起点,因为十进制比较好处理
让N1按递增顺序给出[1,2,3,...],可以看到答案是一个[1,...,P,...,Q-1,P,...,Q-1,P,...]
后半部分就一直循环下去,类似无限循环小数的样子
于是就好办了,先把输入数据转换成十进制数,再对循环节取余得到正确的数字
不过位数太长的话会很慢,所以只对<P的数进行转换,大的数直接做转换后的取余值,这样就不需要高精度作为中间变量了
下面是我的代码:
八月 18th, 2009 () Project Euler › ben1222 › No Comments
明天就要回学校了…后天开始军训…不知军训多少天…
啊…还有篇课程论文没写好…形势与政策…上学期期末爽了但是暑假结束时好不爽…
Project Euler
61:C++
62:C++
63:Windows计算器,人
64:C++
65:数列搜索
下面是详细内容:
八月 15th, 2009 () HDU, acm › ben1222 › No Comments
组队赛第三场,在杭电上做
Ecust 2009 ICPC Team Practice 3
题目是2006年西安赛区的现场赛
Asia Regional Contest 2006 Xi-An
uva的链接
这次题目难度就上去了…
44分钟才有第一个队伍提交…
这次只过了3题…火柴棍,睡觉,叠纸片
一开始看题…这次看题真一个郁闷…看一道没想法一道…
好容易读到一道看起来可以做的题…肚子痛了…上了个厕所回来…
看完题…睡觉那题…感觉和以前做过的一道美术馆喷泉的题目有点像…而且这次似乎还简单一点…
说是上课…学生们很困…睡b分钟会醒来a分钟,过了a分钟后会看看睡觉的人数是不是比醒着的人多,是的话就又睡b分钟,否则就一直醒着了…
题意貌似是说否则就再过a分钟后继续观察…不过发生这种情况的话不可能会有人又去睡觉的吧…
a和b都小于等于5分钟,且是整数
于是取所有(a+b)的最小公倍数c,那么只要模拟c*2次看有没有全醒就行了…
敲之…对面的人ac了这题…10分钟后我们也ac了这题…
这时已经快一小时了…
继续看题…sky和我说了最后一题…就是纸片覆盖那题…
4*4的区域用2*2的纸片覆盖,顶点只能在整数点上,按顺序放,给出最后从上往下看到的形态,问能否用6枚以内的纸片完成这种形状
我想了一下,很迷茫…sky和我说…预处理下,打个表,才9^6那么多状态…
我想也是…sky又说…火柴棍那题可以dp,我说要高精度太麻烦…于是先敲叠纸片…
先粗略的估算了下空间,觉得每个状态用5*9的字符串表示太浪费也太大了…
于是想了个压缩方案…每列压成1字节,总共压成9字节的字符串…然后用set来判断
敲完ac了…
然后让sky去敲火柴那题…我继续看别的题…
火柴这题是给你n个火柴,要你拼出最大的可以被m整除的数…sky用dp[用i个火柴][除m余数为j]=最大的数字
和ssjia讨论了一些题…但是仍没什么想法…
其中有题音阶的…有点后悔没仔细看题…
后来sky敲好了,不过程序速度有点慢…极限数据要数秒,时限是5秒…试着交了下tle了…
似乎比较高精度数字大小慢了点,因为是记录前驱,所以每次比较的时候就要把双方的高精度数值都搞出来然后比较…
我说…弄个double预判一下吧…如果double值接近就再用高精度判断一下
改之…然后发现一些数据先前的结果不对…但是现在的结果是对的…也没管,就交了…结果wa了…
想到先前的结果不对应该是高精度比较函数写错了…检查了下…最终发现问题所在…高位在前还是在后搞混了…
改之ac…
然后我去写箱子…无奈wa到结束…
简述:
A: 棍子…上上下下来来回回的感觉要考虑很多,没想法…
B: 火柴…dp
C: 宝箱…二分,计算几何?不确定,没过…
D: 生成填数字的谜题…呃…没什么想法…
E: 睡觉…最小公倍数,模拟
F: 精灵…三维计算几何?这题搞成2维的都挺难的…
G: 水流…网络流..吧?带上下界的有权的…
H: 音阶…仔细看题…角度是整数,所以枚举下应该可以…计算几何
I: 冰人…横版过关游戏…恶心的…搜索?
J: 叠纸片…预处理
下面这段是关于宝箱的那题,可以无视,因为这题最终还是没做出来…因此下面这段可能是错误的思路
八月 14th, 2009 () acm, hnu › ben1222 › No Comments
这次是在hnu的oj上做
2009暑期培训练习赛七(组队赛)
用的是Arab and North Africa 2007的题目
在pku上也有
Arab and North Africa 2007
话说hnu这次比赛太不厚道了…居然比赛到一半挂了…
到比赛结束后很久才恢复过来
有一阵子没切题了…不知是不是这个原因…今天错了好多次…
首先是A题…平均数…很水,直接A了
然后是E题…[L,U]内质数个数和可以表示成平方和的质数的个数
不难…可是敲完交上去居然…wa了…严重莫名…
让sky重写一个…结果re了…汗…这代码TLE都没到就RE了…不过也明白了…题目里有恶心的输入…
因为题目只说L<=U<1,000,000…没有定下限…判断了一下输入有负数的情况后ac了…
然后是B题…电话号码…题意很简单,某人把电话号码加密了…加密方法是*11然后删掉前面超出的位数,要你求原来的电话号码…
不过话说电话号码会有1,000,000那么多位吗?…打宙际长途?
解密也简单,枚举添加0~10在前面,然后看能不能被11除尽…
不过又wa了…十分莫名…
这时候ssjia去敲D题…貌似是麻烦的字符串处理…我和sky继续想电话号码…
后来想到可能电话号码没有0开头的…就改了下…结果又wa了…
这时候ssjia把D给过了…好稳…
重新看题…突然发现输出的格式里面…那个点后面有个空格…囧…
恶心的hnu的网页排版…空格距离和点的直径差不多…让人以为是点后面自带的空隙…
改回来后先用可能带前置0的方案交了下…又WA…再用不带前置0的方案交了下…终于AC…
然后看F题…求最多点共线…很简单,枚举每个点,然后把以这个点为一端的线段按斜率排序,然后找重复最多的
可是又wa了…这回真是我犯了低级错误…改好后ac了…
然后做C题…转矩阵…N*N的矩阵,一圈圈的,每圈都能转,那种转一格的转,不是转90度的转…问有没有可能转成排序完成的矩阵…
也很简单,一层层check就行了…总算1A了…
然后oj挂了…还剩3个小时
发现pku上也有,于是转移阵地去pku上继续做…
然后做G题…看电影…有单人票和家庭票,家庭票只能一个家长和他的孩子,孩子的孩子不能算…问怎么买票才能花钱最少…
不过为什么可以表示成树的结构…直属子节点还会有1000个之多…这难道是无性繁殖…单细胞么?
就树dp而言并不难…对大量的名字而言,会map也不难…可是这读入…恶心到一种境界了…
然后做…第一次re了…因为vector忘记清空…
第二次wa了…因为描述没有自己看一遍…一个人可以被2张家庭票覆盖…描述里有写…讲题的时候没说…
第三次ac了…
然后还剩3题…也就最后一题J过的人比较多…做做看…
最终没有在比赛结束前ac…赛后ac掉了…不过是很险的过了…
简述:
A: 平均数,大水
B: 宙际电话,高精度
C: 转矩阵,模拟
D: 没看,字符串处理
E: 筛质数和4n+1的质数
F: 最多点共线,斜率排序
G: 单细胞看电影,树dp,hash/map,恶心读入处理
H: 推荐作者,感觉很麻烦…
I: 没看…
J: 256个数字连加的感受,dp之有多少优化全都给我搬上来
ABCEFG看上面流水帐…
J详述和代码:
八月 13th, 2009 () 图片 › ben1222 › No Comments
一个有趣的网站
用函数画图,绘制(-10,-10)-(10,10)范围的图像,由你给定f(x,y,r,g,b)来画图
给人感觉是f(x,y,1,0,0)作为R分量,f(x,y,0,1,0)作为G分量,f(x,y,0,0,1)作为B分量来绘制的
返回值颜色变化在(-1,1)之间,-1最暗,1最亮,小于-1和-1一样,大于1和1一样
乘幂用**
貌似这是python的…
所以可以用逻辑运算…可以用某些特有的语法…比如lambda什么的…
画了个简单的精灵球…
((x**2+y**2)<100)*((x**2+(y-2.4)**2)>=9)*(((x**2+(y+20)**2)<500)*(r-g-b)-((x**2+(y+20)**2)>=500)+((x**2+(y+20)**2)>=510)*2)+((x**2+(y-2.4)**2)<9)*(((x**2+(y-2.4)**2)<1.9)-((x**2+(y-2.4)**2)>=1.9)+((x**2+(y-2.4)**2)>=2.2)*2-((x**2+(y-2.4)**2)>=7.8)*2)+(((x+5)*cos(-pi/4)+(y+4)*sin(-pi/4))**2/9+(-(x+5)*sin(-pi/4)+(y+4)*cos(-pi/4))**2/4<1)+((x+1)**2+(y+7)**2<3)
RSS订阅