absi2011's Blog & Daily Life.

全新的开始       我要省选翻盘       I wanna AK in 高考\化学       自此,生无可恋
[破碎的状态] JSOI Round 2 Day 2 滚粗记
APIO游记[总]

[破碎的状态] 北大校赛经历

absi2011 posted @ May 09, 2016 04:30:50 PM in OI系列 with tags acm pku 小高考 , 399 阅读

比赛网址: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)!

然后这场比赛就结束了


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter