[破碎的状态] 北大校赛经历
比赛网址:http://poj.openjudge.cn/
Rank : 21
比赛经历(乱说版):
队友ufo首先拿到题目拆了A题..并没有翻译给我就自行拆了..榜上大概过了A和J两题
我翻了一发题,感觉D题题面最短就读D题,然后感觉可做
ufo又把J题给写了,测试,我出了个数据把他hack掉了
ufo改了下,然后拆了J题
我终于找出了D的规律,果断手写高精度拆D
至此,3题
然后我跟榜看G,队友在跟榜走看H
然后..把G读懂发现是个最短路
不过这个最短路是随机图,1e6个点5.5e6个边
目测dijkstra过不了,写了个spfa,因为我sb的写错了交了3次才过
然后我看H,感觉题面给的东西都是没用的啊所以我就默默的给了个思路
然后..不想写矩阵,所以队友帮我写了
我滚去思考I题,那个题是神题..
感觉P很好鉴别,P有个圈别的都没有
K和U不好分,只好用一个奇怪的做法去做
找K或者U所有点的平均点,然后看周围圆心内是否有点就行了
之后就行了..多交了几次,终于过了
最后我强行把C读懂给拆了
=================================================================
比赛经历(正规版)
| 提交人 | 题目 | 结果 | 内存 | 时间 | 代码长度 | 语言 | 提交时间 |
| 有趣的队名 | C | Accepted | 1308kB | 800ms | 3665 B | G++ | 04:50:15 |
| 有趣的队名 | C | Wrong Answer | 1308kB | 530ms | 3637 B | G++ | -1 |
| 有趣的队名 | I | Accepted | 20580kB | 120ms | 5092 B | G++ | 03:59:28 |
| 有趣的队名 | I | Wrong Answer | 19184kB | 100ms | 5066 B | G++ | -4 |
| 有趣的队名 | I | Wrong Answer | 19184kB | 60ms | 5019 B | G++ | -3 |
| 有趣的队名 | I | Wrong Answer | 19184kB | 60ms | 5060 B | G++ | -2 |
| 有趣的队名 | I | Wrong Answer | 19184kB | 100ms | 4998 B | G++ | -1 |
| 有趣的队名 | H | Accepted | 516kB | 170ms | 2791 B | G++ | 02:15:23 |
| 有趣的队名 | G | Accepted | 102768kB | 1810ms | 2253 B | G++ | 01:47:02 |
| 有趣的队名 | G | Wrong Answer | 102768kB | 1200ms | 2252 B | G++ | -3 |
| 有趣的队名 | G | Runtime Error | 173252kB | 650ms | 2274 B | G++ | -2 |
| 有趣的队名 | G | Runtime Error | 173252kB | 690ms | 2259 B | G++ | -1 |
| 有趣的队名 | D | Accepted | 256kB | 0ms | 1421 B | G++ | 00:53:58 |
| 有趣的队名 | J | Accepted | 516kB | 0ms | 1025 B | G++ | 00:28:13 |
| 有趣的队名 | A | Accepted | 252kB | 0ms | 809 B | G++ | 00:09:49 |
开局,我把ufo喊去看A,我自己去乱翻题目..看到D题题意较短
[A是什么题我不知道因为他翻译好了就AC了] 提交,1A(00:09:49)
J题:
给你个序列,问是不是一个树的中序遍历
*如果访问到空,则为'#'
这一题只要是# 数字 # 数字 # .... #即可....
提交,1A(00:28:13)
D题:
你要构造一个数组a,使得数组里所有数字的lcm与它们的和相同
*a数组不允许有重复的数字
*2<=a数组大小<=200,a数组中的数字不得超过100位
(错误解法:构造1 2n-2 2n-2+1 2(2n-2+1) .... )但是会超过100位
这一题是个构造题,我们观察:
1 2 6 18 54 ...这一组序列,恰好能做到前若干项是3的n次方
这时候的lcm是最后一个数
之后,我们取一个3x的形式的数即可,例如样例
1 2 3 或者4
1 2 6 9
这样保证lcm是2*3n-2,和也是2*3n-2
观察得到,这个数字90+位,是可以的
很果断的1A(00:53:58)了
接下来他在看H,我就一个人看G去了
看起来G是个最短路的模版题,给你个随机图生成器,你要求1到n的最短路....
然后想写dijkstra但感觉要TLE
这时候我去看H题,提了个思路在那里,ufo在翻矩阵乘法的模版....
H题:
给你一个球,它在(x,y),第i分钟它会按第ai%m种姿势分裂(当i是m的倍数时取m)
你要求出在n分钟后,所有球的坐标之和%1,000,000,007
姿势分裂都是这样的:每个球在它的上,下,左,右,各复制U,D,L,R个球.(注意不同姿势的值可能不一样)
后来G题写了个spfa,因为我很滞涨的写错了点东西导致了(-3)的罚时
之后还好调对了,1个多小时的时候给AC(01:47:02)(-3)了
他这时候模版已经找到了花了点时间给1A(02:15:23)了(果然我比较弱没法1A)
之后我们看了下,做了5题还有5题
感觉为什么那么多人都过了PKU识别的I题啊,那就去做I题吧
I题:
给你一张图,里面包含P,K和U,例如Sample是这样的..
............................................................ ............................................................ ............................................................ ............................................................ ................................############................ ..................##############################............ ..................################################.......... ..................#################################......... .............................................#######........ ................................................#####....... ..................................................####...... ..................................................####...... ...................................................####..... ....................................................###..... ....................................................###..... ....................................................###..... ....................................................###..... ....................................................####.... ....................................................####.... ..............###########################...........###..... ...........##############################...........###..... .........################################...........###..... ........######################......................###..... .......#######.....................................####..... ......#####.......................................####...... .....#####.......................................#####...... .....####......................................######....... ....####...................................#########........ ....####...........################################......... ....###............###############################.......... ....###............############################............. ....###............##########............................... ....###..................................................... ....###..................................................... ....###..................................................... ....###..................................................... ....####.................................................... .....###.................................................... .....####................................................... .....#####.................................................. ......#####................................................. .......######............................................... ........#################################........##......... .........################################........##......... ..........###############################........##......... .............##########################..........##......... .................................................##......... .................................................##......... .................................................##......... ............................................#######......... ..........................................##.....##......... ......................##..................#......##......... ......................#####..............##......##......... ........................#####............##......##......... ...........................#####.........##......##......... ............................#######......##......##......... .............................##..#####...##......##......... ...........................####.....##....##.....##......... .......................#########............#######......... ....................######....##............................ ...................####........##........................... ................................#........................... ................................##.......................... .................................##......................... .................................##......................... ..................................#......................... ............................................................ ............................................................ ............................................................
嗯
所以你要找有多少个P多少个K多少个U
以及总和,保证数据不会刁难你(比如把字母叠起来,或者字母太小无法辨认,或者字母之间靠的很近)
这一题我又出了个奇怪的思考,那就是把P求出来后,把某个联通分块的点找个平均值,然后取个半径sqrt(点数/5)
如果半径内有点那么这个是K否则是U
看完这题以后交给ufo写了,ufo果然写了好久....预料之中
跟着榜走,下一题是C,读完题去拿东西吃饭了
吃好饭,大致思考了下C
C:有10个机器分别是0~9
有m个规则,每个规则是把颜色为x0的糖果经过i机器颜色改为x
保证对于任意x0,i存在最多一个x
当然,1~9机器还可以做出一个颜色为x的糖果
问你编号在[a,b]中的糖果,每个颜色各有多少个(如果非法则不统计)
(注意如果不存在规则就是非法)(编号就是操作序列)
例如sample吧
2 10 2 5 1 1 2 2 5 2 7 1 9 1 1 1 0 2
一共2种颜色,5个机器可以做糖果(1,7,9号做颜色为1,2,5号做颜色为2)
你可以把一个颜色为1的糖果放在0号机子上,之后它的颜色会成为2
那么制作成1号颜色的编号(也就是操作序列)有:
1 7 9
制作成2号颜色的编号有
2 5 10 70 90
编号在[2,10]之内,颜色1有俩,颜色2有3,故输出2和3
这一题是个dp吧
这时候I题交上去了WA
经过调参数,把半径从2(正方形)改为了sqrt(n/20)(正方形)和sqrt(n/10)(正方形)和sqrt(n/5)(圆形)(-4)
之后突然发现似乎忘记memset了..过了..就这么AC(03:59:28)(-4)了..
之后去dp做C题,dp(i,j,k)表示到第i位的时候,颜色为j,目前和a/b是否相等的操作数
首先a--
然后就转移一下就行...在最后15分钟submit,WA(-1)!
正巧造了个数据cha掉了程序赶紧改过来submit,AC(04:50:15)(-1)!
然后这场比赛就结束了
评论 (0)