WC 2012

0 在常州混了这么多天,还是挺开心的,很可惜的是没有把到一个妹纸(喝多了无视)。。

1 游乐园玩的真心开心,嗓子都叫哑了。。。

2 讲课中我各种刷存在感,感觉教练印象分提高了很多?

3 我看了一下,我THUSC第四,NOI第四,THU集训第四,作业分第四,WC之前第四,WC分数没有第四(如果这个第四我就做不到总分第四了,所以第四数量是理论最值?),WC之后第四。。。。。

4 不得不说这WC太囧了。。我整个人都考场梦游了。。。。前两题各骗了50分之后。。本来想看看是写第二题的100分呢。。还是做第三题呢。。想先做做第三题搞点分再搞第二题。。。结果写搜索各种跑不出来最后就被坑进去了。。。。。尼玛现在OI是不是就是比谁挂的少啊!!!大家都各种SB错误挂。。。某人文件名打错都不知道怎么吐槽了。。。。。

5 貌似noi前4除了我都跪了?当然fhq不算。。这OI尼玛太凶残了。。。

6 各种搅基啊。。。。欢乐死了。。。。

7 最后上去唱周杰伦的菊花~~台了~~。。虽然我自我感觉良好。。不过貌似声音都被炫教盖没了T_T。。。。

8 尼玛这1.5道提交答案题创纪录了吧!!!!!

9 雅礼神校啊。。。屠场屠的太狠了。。。。。。

10 wc rank1的某人。。。考完还发完挂状态。。。。。。。。。。

11 zrp和某人各种那啥。。大家都懂。。。

WC 讨论资料

那啥由于我讲的这玩意Suffix Automaton的定义和证明之类的东西太多了。。。。。。
不得以就讲的跟堆定义一样。。。。。

时间也非常紧。。。感觉40分钟读一遍定义都差不多了。。讲的太快也请大家见谅T_T。。。

其实ppt做到还是很详细的。。。如果讲的时候没有跟上可以慢慢看ppt。。。。

资料在我的skydrive网盘的OI文件夹的all.rar里

另外我现在对于我的选材感到非常的后悔。。本来我的题目应该是

“根号算法与分块思想”。。。。。。。

WC hf && gl

马上就要WC了,我的OI生涯估计也要结束了(今年要被刷了,明年不想搞了)。。。。
比赛什么的,能觉得尽力了就好了吧。。。

另外我WC的时候会讲点傻逼的东西,大家轻点喷。。。

SGU Volume 5

那啥最近闲的蛋疼。。把SGU的Volume 5 A光了。。(为啥A这个?因为Volume5题目最少。。。。。)

就简单的吐槽一下吧:

500:恶心的计算几何题。。算法很好想就是很恶心。。。由于我写的太烂还被卡常数。。T了无数次。。。

501:很久以前做的了。。这个一看就知道是要用dp做的。。。。慢慢写吧。。。

509:赖神貌似有题解。。不过也不是很难的题目。。自己想也行

516:毫无难度的傻逼模拟题。。。居然只有个位数AC。。。

522:简单的调整就可以构造出答案

526:我感觉我傻逼爆了。。。只会n^2的做法。。大体就是只有O(n)个有用的时间位置组合,然后搞搞求出路径就行了。。。。。

528:比较麻烦的模拟题,理清楚就行了

529:HNOI原题
530:分析一下可以发现有很简单的结论

535:这题其实是傻逼题。。别想复杂了。。。

541:比较麻烦的代码实现题。。。。

 另外我WC打算讲某个神奇数据结构。。。。大家可以做好准备到时候喷我。。

POI18 简要题解

这两天闲的慌把POI18水完了。。。决定发一篇题解以除草。。。。。

Stage I和II似乎发过了。。就发下Stage III的吧。。
Party:每次找到两个不是朋友的人,把他们都删掉,就可以得出结果,为什么很容易证明。
Sticks:我觉得这题有点傻逼。。将所有排序之后,扫描一遍,维护最大且颜色不同的三个即可。

Periodicity:这个题目还是很有意思的,首先这货其实是要求一些长度的前缀和后缀相等,比如1,2,4,10。。那么我们依次构造,比如1,2,4的结果是A,那么可以知道1,2,4,10的结果是A**A。中间当然是能全添0最好,如果不能全添0,把最后一个改成1就行了。如果是1,2,4,7这样的话。直接在A的前面补上一个长度正好的前缀就行了。

Meteors:我们进行分治处理,比如处理到[l,r)这个操作区间,答案在这个区间的国家集合是S,那么我们添加[l,m=(l+r)/2)这些操作,如果一些国家已经够了,那么它的答案就在[l,m)否则就在[m,r),递归处理即可,复杂度是nlogn。

Inspection:这题貌似没有什么难度。。树形dp出每个子树的大小和结果然后判断一下计算结果就行了。

Dynamite:首先二分答案,然后不难发现一个lighted fuel越靠近根越好,那么我们可以从底向上处理,必须放的时候才放。另外这个idea已经年娇处了吧>_<。。。。

Programming Contest:不难建出费用流模型,但是注意到有些边的代价是二次函数,不过这不影响费用流算法>_<,直接做就行了。同时由于此题的特殊性,可以实现的很简单,比如BZOJ上我就写了800B。

最近水的一些sgu题目。。

由于基本上前人都有题解。。。。。。所以发这篇的单纯是除草。。。。。

由于做的比较多。。就只说说AC数<20的好了。。。

sgu 331:crazyb0y有题解。。没啥好说的。。。

sgu 387:挺傻逼的一题。。令人吐槽不能的是大小可以为0。。。

sgu 450:挺傻逼的模拟题。。

sgu 470:就几行的傻逼构造题。。。

sgu 472:分治一下算出每个点周围的最短路然后dijstra就行了。。。

sgu 474:挺裸的题目。。。。没啥好说的。。。

sgu 498:意外的居然是傻逼题。。。随便算算就能算出来了。。。

 

个人感觉难的题目的话。。ural总体质量比sgu好?当然这跟ural题目比较多也有关系。。不过sgu上好题也是有些的。。。

TopCoder SRM 526.5 题解

250:

做法很多,我用的是最暴力的一种,考虑一个数x,它如果是完全平方数,那么它下一轮就跪了,否则它下一轮的位置是

x-sqrt(x),sqrt(x)取下整。

由于没删掉的数之间的顺序不会变。

我们显然是要找到一个最大的数,它在变成1之前没有跪,那么我们从n到1暴力判断。。。。

这个速度很慢。。Java会T。。改成C++就能卡过。。。

500:

注意到期望的平方不具有可加性,咋办呢。。

注意到Sum(a1+..an) ^2 = Sum(ai*aj){i in [1,n],j in[1,n]}

那么一个点上的和平方的期望,就等于每对个range在这个点上相遇的期望次数的和

后者是可以通过简单的数学计算得出的。

 

1000:

确保你会做http://community.topcoder.com/stat?c=problem_statement&pm=8587这题

SRM396 1000pt

我们要找出一个最大的,独立的子空间,使得Sum(Red)*Sum(Blue)最小

我们考虑所有这些子空间,它们的(sumRed,sumBlue)组成的点集合。

那么我们可以注意到,答案只可能在这个点集合的凸包上!

那么我们来办法搞出凸包上的所有点就行了。。

打个比方说,我们给一个斜率k,然后把所有信封按red*k+blue排序,然后用SRM396 1000pt的做法

我们就能得到一个最大独立子空间,它的k*sumRed+sumBlue最小

这意味这,它就是斜率k的直线,一直往下压所碰到的凸包上的一个点!!!

根据标程我们只要搞出所有有可能成为答案的斜率,计算即可。。

不过我随机了很多斜率。。也过了。。

Ural 上5道hardest problem的题解。。。 第二弹

。。。纯除草。。貌似都是上个月做的题目。。。最近完全在颓废。。。

Goat in the Garden 4 :二分答案之后,我们只需要判断3种点:到两线距离相等的,到两点距离相等的,到一点一线距离相等的即可。

Time Limit Exceeded :模拟题,认真读请题意即可

 

Goat in the Garden 6:跟4一样,只需要考虑几种边界上的情况,全部列出暴力判断即可。

 

Death Star 2:首先考虑一个向量v,一个包含v的向量空间中离某点T最近的点p,p->T这个向量必然于v垂直(为啥你脑补一下就知道了),这样就能算出最近点,然后列出方程,可以将剩下的问题转化成一个2次多变量函数的最小值,就傻逼了。

 

Space Poker 3:枚举所有可能的community cards情况,之后进行dp即可,dp的状态是每个数量的牌种类各有几个。Java需要常数优化才能过

我以前出的一套CTSC模拟题 已传至BZOJ~~

很久以前跟某校一起集训的时候出的。。

当时就说要放上来。。结果忘了。。

那就发一下吧。。

连接发不上来。。。自己去我的skydrive网盘看吧。。叫problems

标程和题解不发,数据太大了懒得传。。就当娱乐看看吧

 

第三题的条件中不是|a-b|而是a-b才对。。打错了

题目相当水。。比赛的时候大家都有200分以上,有3个人AK了

 

题目已经+到BZOJ上。。大家可以自己去虐

Page 5 of 56« First...34567...102030...Last »