今天regional合肥赛区网络赛
34th ACM/ICPC Asia Regional, Hefei, Preliminary
1116~1123
一共8题…我们队出了7题…最终rank32
出6题的队伍都排到100开外去了…可见这次的题目难度…
上来看了A…游戏厅…一时读不明白…然后E题啪啪啪的一堆人出了…
一看是普通的最长公共上升子序列…可是想不起来怎么做了…
于是继续读A…终于读懂了…是个背包dp…可是脑抽了…居然写了个O(n^3)的出来还浑然不知…结果自然TLE…
于是转向E题…在模板里搜到了…可是完全没印象了…直接贴上去…然后AC了…
然后发现FGH都有一堆人出…于是去看…
F是给定凸多边形和一些点,点在多边形内的算2分,在外面的算1分,求总分…
直接判断点在凸多边形内的模板贴上去…AC…
然后G是高精度比较…一堆数中找最大的10个…想都没想就敲了…敲完AC后才想起来这个为什么不用java呢…
sky提醒了我A题…才想到我干嘛从后往前背包呢…从前往后就直接O(n^2)的嘛…真傻了…于是AC
H题是图上找2个点使得其他点到这两点最短路中短的那个的最大值最小…规模是500…
没什么想法…这时yq过来说…这题时限2秒呢…n^3直接做应该不会超时…
才发现原来这题时限是2秒…于是Floyd+枚举,700多ms搞定了…
接着看B和D…B是判树同构,D是判图同构…
B规模是1000,D规模是25…
于是D就搞了个按度的搜索加上一些剪枝…结果0ms过了…
而B则看了下树的最小表示的做法…然后写了一个半小时…这代码写的真累…但AC了不错…
这时一堆出7题的…但是没有人出C…
然后去干别的事情了…回过神来发现有人8题了…
于是敲了个最普通的搜索剪枝…然后果然TLE了…
后来封board了…
然后搞了些优化…搞了点限制…搞了点随机…最终以39次提交还是没有过收场…
简述:
A: 游戏厅,dp
B: 判树同构,树的最小表示
C: 最大团,乱搞没过…
D: 判图同构,预判+枚举+剪枝
E: 最长公共上升子序列,dp
F: 判点在凸多边形内,计算几何
G: 高精度比较,高精度
H: 医院选址,Floyd+枚举
下面是BD的详述:
tags: acm, ustc author: ben1222 comments: No Comments
终于今年的regional要开始了呢…
合肥赛区网络赛的热身赛
34th ACM/ICPC Asia Regional, Hefei, Warmup
1041~1046
一共6题,三小时…
有不少队都全出了…
当我们队出了4题的时候还排到过rank4…
可惜后面一直没出题…结果掉到rank23
不过是热身赛…RP用完就不好了…
上来看到F题标题是A*B 结果ssjia直接敲java用高精度…然后马上就过了…
不过有十几人更快…
看完A题后有人过了B…一看B题那么长…耐心的看了一遍…一时没什么想法…
于是去做A…去掉某行某列后矩阵的行列式组成的矩阵…这叫啥来着…忘记了…
此时A有很多人交了没过…不知道是不是TLE…于是不敢直接模拟…
搞了个位运算然后dp个256*256的来做…过了
然后做B题…是说有两种恶心的方式,一个是用TLE和WA来判断输入数据的每个位上的值,从而得到输入数据…另一种是枚举2^n种输出
然后要用最少的提交来取得ac…
此时还是没想法…写了个dfs+剪枝…结果TLE了…
然后和ssjia说题意的时候…不自觉的抽象了下题目…就是一堆二元组(ai,bi)要把它们分成两堆,一堆对ai求和,另一堆对bi求和后取2的幂,要求分出的两堆的值的和最小
范围是100组,ai不大于10000,bi不大于20
然后就突然想到了对bi进行背包…
写了个dp[101][32]…因为最坏情况是10000*100,不会超过long,所以第二维给32就够了…爆long的不需要…
然后背包dp[i][j]=用了前i组,bi之和为j的情况下ai之和最小值
接着就AC了…
然后看C题…一堆点找最大的三角形,三角形内或三角形上不能有点,三角形一个顶点是原点,规模500
想啊想,先是对所有点极角排序,然后极角相同的点只保留最接近原点的那个
想啊想,然后枚举三角形第二个顶点b,对每个顶点b顺时针和逆时针分别枚举第三个顶点c,两个方向都是超过或等于180度就停止,然后记录角cba最小值,如果下一个角度更小,则三角形内没有其他点,并且更新最小值,否则的话说明三角形内有其他点
于是O(n^2)的AC了
然后D题疑似求割点,可是始终WA…
E题不明…
果然差距还是很大啊…
简述:
A: 矩阵行列式,dp[256][256],似乎暴力也行?
B: 为了过题不择手段,dp[101][32]
C: 找三角形,O(n^2)枚举+判断
D: 为什么不在B城市上面和左边的格子那里等着,没过
E: 每天换位置,每天交到新朋友,没过
F: 高精度乘法
没有详述和代码
tags: acm, ustc author: ben1222 comments: No Comments