和谐社会模拟赛。。

 额。。这是我第二次办模拟赛~~上次的灰色头像模拟赛参加的人好少囧。。。。。可能是因为时间过于仓促的原因吧。。上次的模拟赛还有一些小bug之类的。。。不过我也吸取教训了。。。经过一些XX的准备。。决定开始办第二场模拟赛。。。时间定在11月12日晚上7点到10点(跟NOIP吧上的通告比。。提前了1小时。。)
题目灰常和谐。。。一共5道题目。。。前4题是算总分的。。跟NOIP差不多~~。。最后一题就不算了。。而且最后一题到晚上12点都可以单独提交。。AC的奖QB10个。。。
前5名奖10QB(贴钱办比赛。。我容易么T_T。。。) 
比赛还是采用邮箱+手测的方式。。届时会在NOIP吧上开贴答疑。。
tieba.baidu.com/noip
邮箱是WJMZBMR@gmail.com 
P.S。。求神犇帮忙审题。。。
剧透:第一题叫“我爸是李刚”

各种悲剧~~

最近悲剧的事情特别多。。首先我的BZOJ帐号被盗了。。。我怎么有种我的过去被人抢走了的感觉。。
好吧。。也许BZOJ是该告一段落了。。正好也是警告我不要为了AC数做题吧。。以后就用小号算了。。
也没神马。。
然后可能就要转这去刷SGU了。。。。
其次我BZOJ 1841看了题目一开始没有想好。。写了个XX的点分治。。细节爆多。。各种恶心。。写到18KB。。结果发现既MLE又TLE。。其实是可以树链剖分的。。我也想到了。。但当时我觉得写了那么长了就放弃太可惜了。。哎。。真悲剧。。
然后HDOJ的比赛又被虐成傻逼。。。半天才过1题。。。
然后昨天CF的比赛的最后一题接近TC原题。。对我这样的TC党本来应该是很happy的事情才对。。
结果我碰巧没有看到那题过。。导致悲剧。。。
我怎么这么背啊。。我怎么这么弱啊。。。
近期要做的事情:
接着看TC。。从头看到尾。。
应付期中考。。
应付NOIP。。
写一堆模板:空间几何、凸包、各种字符串算法、各种网络流、各种平衡树,还有块链。。

A Problem For Fun

A Problem For Fun

Time Limit:50000MS Memory Limit:265536K
Total Submit:7 Accepted:2
Case Time Limit:10000MS

Description

给出一个N个结点的树,每条边有一个正整数权值,定义两个结点的距离为连接这两个结点路径上边权的和。对于每个结点i,它到其他N-1个结点都有一个距 离,将这些距离从小到大排序,输出第K个距离。

Input

输入文件总共N行。第一行有两个正整数N和K。下面N-1行每行描述树的一条边(保证这些边可以构成一棵树),每行三个正整数u、v、w,表示从结点u到 结点v有一条权值为w的边。
输入文件保证:N <= 50000, K < N, u <= N, v <= N, w <= 10000。

Output

输出文件总共N行,每行一个正整数,第i行的数对于结点i的答案。

Sample Input

Sample Output

Source

陶文博

这个题目解法有好多。。真是道好题。。我有时间写个完整一点的解题报告罗列一下解法。。
我写的是边分治。。因为比较好弄。。
首先通过添加辅助点的办法让点的最大度数为3。。
具体的说就是对于每个度数大于3的点。。
比如说度数为d,构造d个点,每个点分到一个边。。同时这d个点用长为0的边连起来。。
然后边分治。。找到分治的边。。
那么一个点出发的所有路径最多出现在LogN个分治中。。
考虑“一个点出发的路径长度<L的有多少个”这样的询问。。
我们可以通过排序的办法在LogN^2回答这个问题。。
然后通过二分来回答K近顶点的话。。
就是LogN^3了。。
N个点就是NLogN^3
好说不好写。。写了9KB+。。
解法2:
这个想法来自twb。。就是dfs一棵树的话。。
用一个数据结构维护树的dfs序列。。
那么一个字树是一个区间。。
注意到我沿着一条边移动。。设从i->j。。
那么j对应的区间到当前点的距离全部降低cost(i->j)
其它的点全部增加cost(i->j)
那么我们要回鹘一个数据结构。。
支持:
给一段数都增加一个值。。
找所有数中的K大。。
这个情况没有办法用神马有效的办法解决。。只能块状了。。
块状的话找K大还是得先二分。。就有个LogN了。。
就是转变成解决询问比一个数小的数有几个这个问题。。
考虑我们把序列分成L块。。
考虑各种复杂度:
为了支持询问我们得给每个块维护一个排过序的数列。。
给一个块部分增加值:
找出那部分,增加,归并,O(L)
给一个块整体增加值:
直接维护一个标记 O(1)
一个块的询问 O(LogL)<O(LogN)(为了方便看成LogN)
所有块的一次询问 (N/L)*LogL< (NLogN)/L
所有块的查询K大 LogN*(NLogN)/L=(NLogN^2)/L
修改一个区间 O(L+N/L) 假设L>N/L。。则为O(L)
我们在dfs的过程中。。
要进行O(N)次询问,O(N)次修改操作。。
所以让这两个操作平衡起来。。
既L=(NLogN^2)/L
解得L=Sqrt(N)LogN
总共就是N*Sqrt(N)LogN了。。
比第一个要好写一点。。速度也差不多。。

4
6
4
7
5
6

6 3
1 2 2
1 3 4
1 4 3
3 5 1
3 6 2

SRM 486

熬夜参加。。。
压力很大。。。
第一题有点压力。。写的时候比较小心。。所以就写慢了。。
然后还犯了个SB错误。。看了半天T_T。。
第二题直接裸map了。。写的还挺快囧。。
第三题想到算法但是现场写凸包压力很大就上网找模板。。
。。。最后还是fst了。。
最后Rank 60多。。真囧。。

网络游戏

网络游戏

Time Limit:40000MS  Memory Limit:65536K
Total Submit:11 Accepted:3
Case Time Limit:3000MS

Description

TT是个富甲一方的大富豪。作为一个富有激情和创造力的新时代青年,他早做腻了一般的买卖,决定顺应时代潮流,开一家网络公司。由于他从小就热爱网络游 戏,所以TT决定把网络游戏作为他的第一个经营项目。
由于TT的制作团队相当强大,所以TT很快就开发出了一个绝对能盖过暴雪出的一堆游戏的的超牛B网络游戏,一夜之间风靡全球,TT也再次发了一笔 财。当然TT对钱并不感兴趣,他更感兴趣的是游戏本身。
TT的网络游戏会根据玩家的各方面给玩家一个实力积分。TT最喜欢的做的事情是选出一些有代表性的玩家,然后按一种特别的顺序排成一个序列,然后 调查连续的一段中积分不超过V的玩家有多少个,以得知这一片玩家是否实力太弱。当然这个序列是会经常改变的,TT经常会把看不顺眼的玩家T掉、在中间加入 一个玩家。并且,玩家的积分也是经常会变的。
刚开始的时候,由于TT选的人不多,这个序列用他的开发团队写的一个简单程序还可以勉强维护。但人一多起来,TT就有些觉得不爽了,所以他决定请 你给他写个牛B的程序来解决这个问题。

Input

输入文件的第一行包含两个整数n和Q,n代表一开始TT所选玩家个数,Q表示TT的操作数。
接下来一行包含n个整数,表示一开始TT选的各个玩家的积分。
接下来的Q行,每行第一个整数o表示本次的操作类型:
若o=0,则接下来三个整数a,b,c表示TT询问第a个人到第b个人之间积分不超过c的有多少个。
若o=1,则接下来两个整数p,v表示TT在第p个人后面插入了一个积分为v的玩家。若p=0,则表示将该玩家插在序列开头。
若o=2,则接下来一个整数p表示TT将第p个人从序列中删除。
若o=3,则接下来两个整数p,v表示TT将第p个玩家的积分更新为v。

Output

对于每个o=0的操作,输出一行包含一个整数,表示该问题的答案。

Sample Input

5 8
10 2 6 1 5
1 1 7
3 5 5
2 5
0 3 5 8
1 2 7
0 2 5 10
0 3 6 2
2 3

Sample Output

3
4
1

Hint

对于20%的数据 n < =10000,Q < =10000
对于100%的数据 n < =100000,Q < =100000,所有输入整数在maxlongint以内。

Source

2008湖南省队集训By刘鹰
嘿嘿。。让我来给出一个(N+Q)LogN+QLogN^2的算法。。。
首先用Splay或者神马平衡树把最终的序列求出来的。。
然后把还没有插入的数看成maxlongint。。不影响结果。。
然后用线段数套平衡树硬搞就可以了。。。
擦~~写了10KB。。怎么一点都不给力啊。。。还没块状链块。。。

CF。。。

被虐的好惨啊好惨啊好惨啊好惨啊好惨啊好惨啊好惨啊
我好弱啊好弱啊好弱啊好弱啊好弱啊好弱啊好弱啊好弱啊

最近各种比赛。。。
早上那个愿望群的模拟赛题目有点意思。。就是第三题是原题然后第二题想出来但没时间写了。。
然后下午去参加CF的那个神马Team Contest的。。

被虐的好惨啊好惨啊好惨啊好惨啊好惨啊好惨啊好惨啊
我好弱啊好弱啊好弱啊好弱啊好弱啊好弱啊好弱啊好弱啊

Page 1 of 41234