- Vijos
-
Towerlight LV 10 @ 2014-10-01 22:44:12
时间定在10-2…………决定的有点仓促……不过就这样了。
既然国庆放假欢迎大家来虐场。
难度不做任何宣传，觉得题目弱的欢迎来喷。
比赛的主要目的是为了来找虐。
大概就是这样了。
祝虐场愉快。
Le vent se lève, il faut tenter de vivre.
//以下时间是东京时区懒得改了…………
(doc:) 已修改
Upd(18:04): 比赛开始了…………但是三四题标程还是RE的…………不过别担心爆栈的程序会予以手动重测…………
Upd(20:49): Arietta 时间限制调整为每个测试点 2s 。
Upd(21:06): Arietta 中某句话更改为 "如果Arietta 融合出来的光束能量为C中的某个数" 。
(doc:) Upd(22:12): 比赛结束, 题解参见http://pan.baidu.com/s/1gd27e3x
(doc:) Upd(次日20:43): 比赛已经重测, 修正了第三题的数据错误. 恭喜 小岛 以300分的绝对优势 获得冠军!
结束啦。
这场比赛对于你来说意味着什么呢……？（笑……
或许有些人只着眼于他认为看不懂的题面上吧。我也无法下更多的评论。
我只想到NOI 2014前的为数不多的安详的日子。嗯，所以就是这样了。
悲切的事情暂时过去了，前方还会有一片凄风苦雨。
最后致敬，至少对一切可能的付出与回忆致敬。 空の向こうに
http://www.xiami.com/song/3444294?spm=a1z1s.6659513.0.0.UolcIB
愿诸君度过一个愉快的夜。
ありがとう
19 条评论
-
liyinghaowei LV 10 @ 2014-10-04 13:26:57
vijos又屌了
[Vijos] 恭喜您AC了题目P1294 - 拯救OIBH总部
今天上邮箱，发现了这个-
@ 2014-10-04 15:07:27
我也收到了 吊炸天
-
@ 2014-10-04 15:12:06
一定是twd2干的
-
@ 2014-10-04 16:17:09
能不能把以前的补发
那样就能把代码存下来了 -
@ 2014-10-04 22:09:53
补发的话工程很大啊QAQ
-
-
@ 2014-10-03 11:32:28
简直是狠 这么仓促 昨晚我还在写作业呢 要是提早知道我去网吧都要参加啊- -
-
@ 2014-10-03 14:23:55
没事哒, 4道数据结构题, 你有空补一下就可以.
-
@ 2014-10-04 15:08:19
话说回来这真的是NOI的难度么 怎么觉得不像
-
@ 2014-10-04 15:09:34
当然不像啦……因为是NOIP PJ难度啊……
-
@ 2014-10-04 16:16:16
pj？？？？？？？？？？？出题人220？
-
@ 2014-10-04 17:31:45
我不是出题人呀...我之前连题目都不知道的, 是和你们同时开始做题的.
还有我是300不是220. 重测过. -
@ 2014-10-05 11:11:49
OTZ...OTZ...OTZ...OTZ........
-
-
@ 2014-10-03 07:52:40
NOIP出的题比这个难多少呢
-
@ 2014-10-03 00:03:43
这就是传说中的PJ难度，话说T1贪心不可以吗，一个节点的最大流=MIN ( cost [ i -> fa [i] ] , sigma ( cost [son[i] -> i ] ) )
-
@ 2014-10-03 01:42:01
贪心可以，因为叶子到根就一条路径
-
@ 2014-10-03 01:42:16
用树剖维护路径流量即可
-
@ 2014-10-03 11:35:49
纯贪心是不行的…………乃可以简单想想反例大概还是很好构造的…………
-
@ 2014-10-03 13:59:50
能不能公开一两个小数据
-
@ 2014-10-03 14:14:25
-
@ 2014-10-03 14:24:30
谁和你说是普及组难度的啦=_= 10-5的比赛才是普及组难度的.
-
@ 2014-10-04 00:18:57
数据一样吗，我在ch上交了，多过了一个点，而且两次分别对的点完全不同
-
@ 2014-10-04 10:19:27
首先CH的测试点排列似乎是随机的…………多过了一个点是因为在Vijos上我把部分分调成了10分……所以数据不大一样…………
-
-
@ 2014-10-02 23:20:57
能不能详细说下T2在异或情况的处理方法（就是那个FWT什么的）
顺便求下T2数据，加法部分的FFT不知道在哪里跪了..ORZT1数组开小改完10->100我也是醉了..以后再也不能犯这样的错了T_T..
-
@ 2014-10-02 23:42:06
T2 是 离散Haar小波变换. 还需要如何细说?
-
@ 2014-10-03 11:35:07
-
@ 2014-10-03 13:21:42
哦是这样啊 就是不知道什么是FWT，有资料就好办了，谢谢啦
-
@ 2014-10-03 15:49:49
ORZ Towerlight和doc..
我看了那个链接里的介绍，但不是很明白，只觉得和FFT很相似..
A=(A0,A1)是不是指A是由当前位是0的A（就是A0）和当前位是1的A（就是A1）组成？
还有能不能给一下XOR时的变换tf的tf(A)=(tf(A0)+tf(A1),tf(A0)-tf(A1))的证明？ -
@ 2014-10-03 16:44:08
你需要知道tf(A)是什么,tf(A)=H*A可以看作是作用在A上的线性变换.H是Hadamard矩阵,如果这一点你知道了,应该不难证明之后的结论.
-
@ 2014-10-03 17:15:32
额额额吓傻了..百度上的哈达玛矩阵的介绍好少，如何确切知道h[i][j]（哈达玛矩阵的i行j列）是多少？
还有我对A=(A0,A1)的理解是正确的吗？小岛大神求教..ORZ.. -
@ 2014-10-03 17:39:38
Hadamard矩阵的定义是递归定义,你去wiki上看一下就了解了.
-
@ 2014-10-04 13:08:27
ORZ..我实在是太弱了..等我再研究研究..（能不能说一下要证明那些东西要用到这个矩阵的哪些性质？）
还有对于特别对于小岛大神的，今年中秋节您举办的那场比赛的T3的神一般的动态规划+组合数学，我正处于半昏半醒的状态，能不能一起探讨一下..
-
@ 2014-10-04 15:30:33
你只要知道Hadamard矩阵是什么东西,就可以自己证出来了.
上次T3没有什么想多说的,比较直接的思路. -
@ 2014-10-04 15:52:22
ORZ...对于T3当时我就又疑惑但正好vijos挂了，然后就一直拖着，然后就忘了...
上次T3的题解我在挖出来：第三题,你所提到的0010200和0010020都被看作是状态<2,2>因为都是2个人, 当前是2个团体, 你可以思考这样一个问题:"给定N个座位围一圈, K个人坐上去了, 它们是按照顺序的, [也就是第一个人的右边是第二个人(有可能存在些许间隔), 第二个人右边是第三个人, ... , 第K个人右边是第一个人] 形成了G个团体的方案, 是多少?" 这个答案只与N, K, G有关. 那么类似的, 我给定任何一个K个人的全排列 (记为t1...tk) 并要求它们按照这个全排列的顺序去座位 (允许相邻两个人中间有间隙, 且桌子是圆形的), 满足的答案个数总是一样的. 所以我们可以不要考虑最后的间距是多少, 也不用管每一个人坐在哪里, 只要最终的排列确定下来了, 总方案就确定了. 那么到底有多少可行的最终的排列呢?(实际上是有多少可行的圆排列?) 就需要递推算出来.
我想问：f[i][j]代表的是前i个人j个团体的可行方案数还是可行排列数？
我当时理解：因为"给定N个座位围一圈, K个人坐上去了, 它们是按照顺序的, [也就是第一个人的右边是第二个人(有可能存在些许间隔), 第二个人右边是第三个人, ... , 第K个人右边是第一个人] 形成了G个团体的方案, 是多少?"的答案只与N、K、G有关，所以这个答案乘以最终的可行排列数就是最终可行方案数的答案？
但是比如N=7 K=4 G=3的情况下，似乎有些问题..
对于f[4][2],1234这个排列与1342这个排列都是可行排列（1234自不用说，134.2..也是合法的）
但这两个可行排列的方案数并不一样，1234比1324多，因为1.234..可行但1.342..不可行
所以我理解的不对？请小岛大神指教..ORZ.. -
@ 2014-10-04 17:44:19
虽然你写了很多, 但是很抱歉我并没有理解你要说什么.
或许你可以这样来思考: 我们把问题修改一下,
1) 如果说两种座位方案, 可以通过对其中一个方案旋转, 得到另外一个方案, 那么我们认为这两个方案是相同的.
2) 如果说两种座位方案, 可以通过调整相邻两个团体之间空位的个数(但是认为要保证是两个团体,也就是说至少要有一个空位子), 得到另外一个, 就也认为这两个方案是相同的.对于这个简化的问题,你考虑F[i][j]表示前i个人组成j个团体的方案. 就可以理解F的转移关系了.
下面的事情是. 回到原问题, 新问题中的一个方案对应了原问题中的多个方案, 那么究竟对应了原问题中多少个方案呢? 这个是可以算出来的. -
@ 2014-10-07 15:41:53
我的表达能力确实很捉鸡..
现在确实明白了，真的很感谢小岛大神..
-
-
@ 2014-10-02 22:13:00
比赛结束. 题解请参见: http://pan.baidu.com/s/1gd27e3x
-
@ 2014-10-02 22:59:12
这部科学额..
为什么我第一题写的树链剖分WA掉了都？
第二题的只有加的部分的裸卷积FFT也写了额..
最不能忍的是那10分暴力也写错了？ -
@ 2014-10-02 23:00:54
有题解真是极好的！业界良心哇。。大赞！！
-
@ 2014-10-02 23:05:06
题解里第二题的题解能不能详细说一下额.
异或部分要怎么处理，那个FWT是个什么东西，百度不到额. -
@ 2014-10-02 23:11:47
第二题第二部分, 需要用到 离散 Haar 小波 变换.
FWT 应该是指: Fast Wavelet Transform -
@ 2014-10-02 23:17:41
我了个擦..T1数组开小了..线段树应该至少开2倍的节点结果只开了1倍..改了瞬间AC了..
-
-
@ 2014-10-02 21:46:04
谁来安抚下我悲伤的心情。。TT
-
@ 2014-10-02 22:33:00
你为何悲伤?
-
@ 2014-10-02 22:53:21
我因为思考不出。。人从哪里来又往哪里去而悲伤。。
-
-
@ 2014-10-02 21:11:43
求diff
-
@ 2014-10-02 21:07:40
题目做了两处修改，如果有理解错误的我感到十分抱歉……请注意查看……
-
@ 2014-10-02 19:51:32
t3的花费只算那两个节点吗，还是从两个节点到lca的所有点权
-
@ 2014-10-02 20:01:03
是只算那两个节点的。
-
-
@ 2014-10-02 18:46:41
小岛最笨了. doc快来养我!
-
@ 2014-10-02 18:42:30
吓尿了。。我都不敢去参加noip提高组比赛了=。=你确定网络流真的是noip提高组难度及其以下？。。。
-
@ 2014-10-02 18:46:17
网络流当然是普及组难度啦. 不过第一题似乎不是简单的网络流哦.... 您别想错了.... 我继续写程序去=_=
-
@ 2014-10-02 18:49:26
OTZ.............
-
@ 2014-10-02 18:57:55
话说。。上次中秋节模拟赛的题目是您出的嘛？。。这次我得好好膜拜膜拜。。沾点大神的气息。。OTZ..OTZ..OTZ..OTZ..OTZ..OTZ..OTZ..OTZ..OTZ..OTZ..OTZ..OTZ..OTZ..OTZ..OTZ..OTZ..
-
@ 2014-10-02 22:00:35
不是小岛出的, 上次那套水题是从别的地方找的.
-
@ 2014-10-02 22:54:28
噗。。。。
-
-
@ 2014-10-02 18:27:23
抱歉要离开1h。有什么问题doc会负责回答的…………QAQ
-
@ 2014-10-04 15:31:58
你若累坏了doc, 我要你命!
-
-
@ 2014-10-02 18:16:12
t4那个x到底是什么
-
@ 2014-10-02 18:18:55
T是一个字符串集合，x是一个给定的要操作的字符串的下标。
Tx是T集合中的一个元素，是一个字符串。
-
-
@ 2014-10-02 18:09:45
看不懂题，，，，看不懂题。。。看不懂题QAQ。。。。OTL
-
@ 2014-10-02 18:12:22
哪道题看不懂呢。。QAQ
-
-
@ 2014-10-02 17:05:47
orz
-
@ 2014-10-02 15:36:50
膜拜Towerlight
-
@ 2014-10-02 15:32:20
膜拜Towerlight
-
@ 2014-10-02 15:05:18
水题赛高! 好棒好棒!
- 1
