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上。。大家可以自己去虐

THU集训吐槽

去这个集训打酱油了。。。。。。

跟超哥住一个房间,超哥每天都说啊,考挂了考挂了,然后他就rank2了。。。

wqs每天都屠狗一样的屠题目。。。总分破天际。。4天有3天rank1。。实在太屌了!!!!!!!!然后在王宏教授讲下次IOI在Italy的时候,wqs果断穿着后面标着大大的Italy的衣服,表示他已经被内定了!!!!!!!!

wqs屠了全场之后还去玩PKU的学姐们,我等屌丝只能给高富帅跪了。。。

第一天我考场犯2。。。。第二天我考场犯2。。。。第三天我考场犯2。。。第四天我考场犯2。。。。。

然后我就回家了。。。。

Ural 上5道hardest problem的题解。。。

好久没发题解了。。除个草。。。

不得不吐槽一下。。。Ural上的所谓hardest problem。。基本上都是糟糕的论文题。。。。

Aztec Treasure 。。。可以搜到公式。。然后直接高精度计算打表。。。可以用Mathmatica。。。

Arrays Printing 。。。感觉看懂题目之后是挺普通的dp啊,直接dp就行了。。。

Dodecahedron。。。首先得搞出所有的置换。。然后就B***定理就行了。。搞置换可以脑补,可以上网搜,可以自己写程序转转看。。
ps,三维旋转真心恶心透了。。

Mnemonics and Palindromes 2。。。打表找规律。。。可以按mod 6给出规律。。。

Expert Flea。。。考虑这个图,把它从0点断开,任何一个这个图上的哈密顿回路,如果把跨越0点的边全部删掉,就会变成一些路径集合,同时只有于0点距离<=3的点才能成为路径集合的端点,用什么状态压缩啦矩阵乘法来把各种路径集合的个数搞出来,再枚举插入跨越0点的边算算就行了。。。

Page 4 of 54« First...23456...102030...Last »