UOJ Logo C_SUNSHINE的博客

博客

暂别

2017-07-25 00:00:59 By C_SUNSHINE

七月…… OIer 们夏日里的新年,既是逐梦多年的选手们封神还是退役成败在此一举的时刻,也是层层选拔中登顶的国家队员们大学之前在世界舞台上崭露锋芒的瞬间。

对 UOJ 来说,这意味着管理员的再一次更新换代,来自新集训队乃至国家队的新一代管理员将为 UOJ 注入新的活力,带来新的思维,而对于我来说,参与了两年的 UOJ 管理工作终于告一段落,是时候拥抱新的大学生活了……

过去的一年里,UOJ 主要是由 C_SUNSHINEcymatthew99 负责,当然 SkydecNanoape 也做帮了不少忙。

还要十分感谢叉姐姐 (ftiasch) 的加盟,叉姐姐给 UOJ 贡献了不少有趣的题呢。以及九条可怜老师 jiry_2 虽然已经不再是管理员但依旧活跃在出题造题的第一线,vfk有时也会突然活过来调试评测系统,造造题什么的,可见过去的管理员们在繁忙的大学生活之余依旧在为 UOJ 的发展努力着。

就要卸下管理员的大锅了,有不舍,也有些回忆想和大家说的呢~

首先要向大家道歉,UOJ 从 Goodbye Bingshen 以来只办了一场 UNR,很大程度上是我的锅(当然毛爷和假老师也有),因为我去年九月到今年六月都在美国麻塞诸塞州做交换生,日常学习就有不少的任务,而且我还要学英语,于是花在 OI 上的时间就缩减的很少了,加上时差的原因,即我有时间的晚上是国内的早上,大家都没有兴致所以没法号召起来讨论题目,造成很多给 UOJ 投来的 Idea 一拖再拖。真是非常不好意思,相信下一届管理员会做的更好的!

说来惭愧,给 UOJ 当了两年的管理员,却没有给 UR 出过任何一道题,一来是我平时没有积累 Idea 的习惯,不擅出题,二来觉得自己有时候勉强憋出来的 Idea 没什么质量也就没投 UOJ 官方比赛,也算是对 UOJ 比赛题目质量的一个坚持和保证(虽然这样一来也挺遗憾的)。去年 CTSC 之后渐渐的淡出 OI,反而对 Idea 更敏感了一些,将来如果有好的 Idea 还是会第一时间投 UOJ 的。

质量是 UOJ 一贯的坚持,如果没有好题出那就不出,绝不能因为急着出比赛就不负责任把糟糕的 idea,胡乱拼凑的模型,粗制滥造的数据扔给大家。虽然这一年来管理员很忙,但每一道题的 Idea,标算复杂度,实现细节,部分分设定,我们都尽力调整到最好。但我也知道我们做不到完美,还是出现过几次数据不够严谨的时候,这也和比赛前一天晚上熬夜造题有关,以后的 ddl 还得设置在比赛前两天左右,然而这都是下一代管理员要做的事了(甩锅)。

大概就说这些了吧,想来我长达七年的 OI 生涯就快要结束了,在这里祝愿还在漫漫征途上的 OIer 们都能在 NOI 赛场乃至 IOI 赛场上圆梦。

接下来就到了宣布下一届 UOJ 管理员的时刻了,他们是:

WuHongxunScapeWrongAnswer

虽然说老一代管理员很快或者已经退役了,但我们一直都会支持 UOJ ,只是花的时间会比以前少了,如果有好题或者好的资源一定会第一时间贡献给 UOJ 的,也欢迎现役选手们给 UOJ 贡献新颖,有趣的题目啊。

另外插一句,这两代管理员交接的时刻恰逢 IOI2017,届时 UOJ 将会史无前例的有四位管理员前往参加,他们是当代管理员 matthew99C_SUNSHINEcy,和新一代管理员中的 WrongAnswer,虽然很难但我希望在不远的将来 UOJ 管理组能再次凑齐一个国家队,坚持做中国 OI 的领跑者,也预祝这些 UOJ-IOI 选手(包括我owo),在德黑兰取得好成绩!

愿 UOJ 越来越好!

UOJ NOI Round #2 排行榜

2017-07-15 14:43:13 By C_SUNSHINE

历时两天的UOJ NOI Round #2终于落下帷幕,这里公布最终总成绩排行榜:

排名ID笔试Day1.ADay1.BDay1.CDay1Day2.ADay2.BDay2.CDay2总分
金牌($15$人)
1lych_cys99100201002201009772269588
2dwjshift100100404018010010080280560
3yanQval98100401002401000100200538
4Stalker01004010024070100100270510
5ljss9450401001901003089219503
6hanyuu62100010020010010036236498
7tzn991004051451006090250494
8xumingkuan97204010016010030100230487
9blutrex99100201002201001034144463
10PaidySung97100203515510010100210462
11SKE_tlzmybm9910020100220350100135454
12MemoryLimitExceeded10070403014010010100210450
13hzq84621999001001901001046156445
14XuYipei9510003013010010100210435
15hanwenchen9810020301501006025185433
银牌($25$人)
16Kuugo988020401401001080190428
17resuscitated0100404018010010048248428
18jiyutian991000100200100025125424
19bzoj9610020401601001055165421
20peehs_moorhsum991004001401001069179418
21Sky_miner99100603519555062117411
22jinhaonan971000010010010100210407
23TDL5951004040180356034129404
24Miloris971002030150100056156403
25Manchery040209015010050100250400
26liu_runda9910060402005503287386
27xuhaike97202040801006042202379
28goodqt9810010052055501570373
29bright_sun06040401401006069229369
30xiqiao961002020140551067132368
31Amber00_Chen97000010010069269366
32bingshennaive1005020401101001042152362
33hld67890991002030150401059109358
34Cherries010020301501000100200350
35ct123098010020401601001080190350
36WasteRice98800080100066166344
37_Itachi951006051655502479339
38Wuvin0100001001006069229329
39sherc99404030110551052117326
40kqp96100203015040102474320
铜牌($50$人)
41commonc03020100150100069169319
42JOHNKRAM98100201002200000318
43AntiLeaf97604010110551044109316
44YveH97100201513540103282314
45stony97602020100100015115312
46rwy01000010010010100210310
4715013799100030130008080309
48FoolMike98304030100201076106304
49CQzhangyu981000010020080100298
50guoxingzhuo9850203010020080100298
51mcfxmcfx9610040551950000291
52Aralon98602008040069109287
53wangxiuhan9910020651850000284
54jiazihankk05040301201003033163283
55neither01002025145100032132277
56jasonvictoryan9610040401800000276
57orzkpm2964020100160200020276
58xuyixuan01004025165551046111276
59orzfang0100200120100055155275
60guoruihan10010040351750000275
61kito06020301101001055165275
62lhl32296402056555056111272
63orzlxl9810040301700000268
64zhlj02059640204010020301666262
65Leo_h996020301102002444253
66miaom99000070080150249
67LazyJazz99100030130200020249
68frank_c19810020301500000248
69jimmy0526967040401500000246
70xjr97402056540103484246
71lyind9970200904001555244
72bzh986020201002002545243
73111116966040401400000236
74SOLar233339760205852003454236
75__W__1001000351350000235
7600zj948020401400000234
77ceerrep99602015952001535229
78Tachibana_Kanade010020512520106999224
79tqyaaaaang01000251250603898223
80tbw1033987020301200000218
81Ajatar0100040140700070210
82kczno1975020401100000207
83chilling1006020251050000205
84oscar010020512520104878203
85TLEbyc8760201595200020202
86mengbierr986020080002323201
87worse010001002000000200
88mywaythere9130205552003454200
89cuibst994020401000000199
90xmcp98100001000000198
胸牌($??$人)
91llgyc984040201000000198
92liu_cheng_ao974020401000000197
93ztr00000100089189189
94OlRed2017_fan00000100089189189
95f321dd99000055102388187
96thhyj0502057520092112187
97unrtest00000100082182182
98WAAutoMaton9760205850000182
99gls119606020401202004262182
100ShallWe9670015850000181
101zxcvbnm9960200800000179
102liyuankai96202040800000176
103abclzr964020565001515176
104Pepcy_Ch962005252003454175
105lpc024289350205750077175
106Lucius9950205750000174
107icecathy9850205750000173
108TerryHu10050200700000170
109swm_sxt01002020140002525165
110lethalboy0602025105005959164
111chentong99000020103464163
112cloudsky9930205550077161
113la1la1la010020401600000160
114CHNFTQ0000070089159159
115lny00000100055155155
116YxuanwKeith9440200600000154
117Infinity3799202015550000154
118c_2h000001001042152152
119116405651605020351052002747152
120bqsgwys050201585006767152
121CYDIATER91102030600000151
122cnyali_lk94202015550000149
123Owen000001001038148148
124scallop0602015952003252147
125ONCE_AGAIN060205852004262147
126F_Darcy00000100046146146
1276130000055089144144
128wyq2386114864984005450000143
129yangpu9130200500000141
130Todobe0502015854001555140
131fengchanghn865000500000136
132l__ZeRo_t010020151350000135
133liaoliao000001001015125125
134hanchenyu01002051250000125
135qaz050205752003050125
136riteme00000100023123123
137ihopenot990000002323122
138zzyu5ds01002001200000120
139DenyTianly8020200400000120
140lzj209060205852001535120
141st_nec990200200000119
142FYT00000100015115115
143wangyuji03020106020102454114
144zhhx03040070004242112
145Herrwerner920000001515107
146gawyunis0700351050000105
147songyiqun2018842000200000104
148Etienne0802001000000100
149JK770000010000100100
150Ketsui0000010000100100
151YihAN_Z06020080200020100
152afrojack0100001000000100
153ddddddpppppp0100001000000100
154lichang0000010000100100
155BOLALA10000000000100
156Heret1c10000000000100
157hamster10000000000100
158y55354643610000000000100
159Barrin10000000000100
160gyjian10000000000100
161dy_yali990000000099
162stealthassassin030003000696999
163Qizy980000000098
164oveoveove980000000098
165Leefir980000000098
166fcba980000000098
167fjzzq2002980000000098
168GQH123980000000098
169RapionScorbbit980000000098
170xsj980000000098
171KyleYoung980000000098
172Dirak980000000098
173lis980000000098
174huangsi970000000097
175triple_u970000000097
176wchabh970000000097
177Tommy_r7970000000097
178Mcallor970000000097
179shorn1970000000097
180ISA970000000097
181ElevenDimensions970000000097
182crazy_cloud970000000097
183iamgqr900000007797
184cwbc960000000096
185l_garbage960000000096
186ynoi_coder107960000000096
187Drench960000000096
188waz2001960000000096
1891650497621960000000096
190Rapiz950000000095
191DraZxlNDDt950000000095
192zqy1018950000000095
193NORMALone940000000094
194hlscgqz940000000094
195xffyjq940000000094
196WerKeyTom_FTD930000000093
197chad930000000093
198fanzhirui930000000093
199zysgdtc83100010000093
200MintGreen0402056520082893
201Lucida920000000092
202xqmmcqs910000000091
203wearry900000000090
204hanuha900000000090
205scPointer030204090000090
206scarlyw04020157500151590
207lyx_cjz890000000089
208realfan890000000089
209xchzkg5400000010798989
210EtaoinWu0000000898989
211yww880000000088
212Demerzel880000000088
213Thinkwice0500156500232388
214xehoth0202004000454585
215blackjack0402056520002085
216player_lin820000000082
217liujunhao00000400428282
218Lynstery06020080000080
219l1ll5000002010487878
220lzgaoyurui040201575000075
221pks05020575000075
222Rushfinen0300030200244474
223tayloronline04020565007772
224Kanade0202054520072772
22515092000305020070000070
226Oakley05020070000070
227cdzhangjiajie0402006001001070
228skyline040201070000070
229nekosu0302055500151570
230AseanA04020565000065
231zaq000002010336363
232Talyee04020060000060
233ZZRun04020060000060
234ez_zwl0600060000060
235g19zwk04020060000060
236pandajt04020060000060
237qianguch04020060000060
238s_h_y04020060000060
239abyss03020555000055
240liji03020555000055
241EIJ03020050000050
242liujiacong0500050000050
2431172879531010202050000050
244458180000000434343
245LuoJin_IOI_AK00000200234343
246lzr0105060000000424242
247BuLR0000000414141
24815420158002020040000040
2491609400360400040000040
250Acheing02020040000040
251Ignatz0400040000040
252Mengbier0400040000040
253anantheparty0400040000040
254icemage0102003001001040
255ljl0400040000040
256orzNanoApe0000040004040
257oscar_jack0400040000040
258slamacraft02020040000040
259sosusosu0400040000040
260owen_creeper0000000323232
26116093000801020030000030
262DreamAct0300030000030
263H1KHC0300030000030
264L_Si_liang01020030000030
265Trick01020030000030
266Xbonnielass01020030000030
267ZYFoi0300030000030
268ZaiYiOnline0300030000030
269xiejun0300030000030
270DZYO0020525000025
271helloat1230000000232323
272zx20030000000232323
2731509201340020020000020
2741509201410020020000020
2751601WSH010001001001020
2761609200030020020000020
2771609300100020020000020
2781609400020200020000020
279187110039740020020000020
2807267613930200020000020
281Chuaichuai0200020000020
282cyyyy0200020000020
283littleg0020020000020
284luke0020020000020
285s_circle0000020002020
286skydog0200020000020
287ulita0200020000020
288Tmp30000000151515
289Tornadol5590100010000010
290dawny0100010000010
291wawcac0100010000010
292zjm0100010000010
293zcysky0000000888
294zzzzzzzzzy0000000777

UOJ NOI Round #2 题解

2017-07-13 13:39:31 By C_SUNSHINE

先来个小问题?

MysteryMan 是谁呢?

关于这点,我只能告诉你无可奉告,你们不高兴也不行。

好吧其实是一个2009年左右的不愿透露姓名的OI选手……

Day1

UOJ拯救计划

from MysteryMan, 题解 by ydc

大家好,这是 MysteryMan 出的题,题解由失踪多年的ydc来写。

这题说白了就是求解图染色方案数,由于图染色问题是NPC的,因此只要你输出答案模6的值。

对于前$30\%$的数据,我们直接爆搜即可,$O(k^n)$。

对于$4,5$两个测试点,由于$k=1$,我们发现只有当$m=0$时有解(且解为$1$)。当然爆搜也是可以的。

对于$6$号测试点,由于是一棵树,我们可以用组合计数的方法得知答案为$k*(k-1)^{n-1}$

对于满分做法,我们首先可以推导得知答案为$\sum\limits_{i=1}^k A(k,i) \times $恰好用$i$个颜色染色的方案数,A为排列数,然后由于答案要模$6$,因此当$i \ge 3$时,对答案贡献为$6|A(k,i)$。

所以我们唯一要做的就是考虑$i=1,i=2$,当$i=1$的话,只有当$m=0$的时候才有解,所以问题就是只考虑$i=2$了。

我们知道,对于一个联通的二分图,确定了一个点后,其余点的颜色就都确定了。因此,我们判断整张图是否是二分图。如果不是二分图,直接输出$0$,否则统计联通块个数,输出2的联通块个数次方即可。

最后有一个小细节即$m=0$,因为当$m=0$的时候,恰好用两个颜色染色的方案数就不是2的联通块个数次方,而要减去全黑和全白。

这题还有另一个思考的思路,即色数多项式——一张$n$个点图的染色方案是关于$k$的$n$次多项式,记作$f(k)$。我们要想知道$f(k)$模6的值,只要知道$f(k)$模$2,3$的值即可。要想知道$f(k)$模$2,3$的值,只要知道$f(0),f(1),f(2)$模$2,3$的值即可。然后就能得到一个殊途同归的算法。

排兵布阵

from MysteryMan, 题解 by jiry_2

收题的时候我感觉这题应该是 T3 的,但是当了几个月甩手掌柜之后发现这题被放到了 T2..感觉组题的人有点石乐志。

C_SUNSHINE:“行吧我石乐志……”

算法一

直接 $O(n^2)$ 暴力,可以通过第一个数据集。

算法二

没有移动操作,那么可以用处理矩形加,询问矩形信息的数据结构 kd-tree 来做。

时间复杂度 $O(n \sqrt n)$,可以通过第二个数据集。

当然肯定有其他复杂度更低的方法。

算法三

因为这是一道对着 idea 出的题,所以不排除有简单的算法或者复杂度更低的算法,但是这题的 idea 本身还是很妙的。

考虑这么一个数据结构:我们对平面里的每一行统计这一行的点数 $nx_i$,每一列统计这一列的点数 $ny_i$。对于一个点 $(x,y)$,如果 $nx_x \geq ny_y$,那么它就作为 $y$ 列的关键点,否则就作为 $x$ 行的关键点。

不难发现每一行每一列的关键点个数都是严格 $O(\sqrt n)$ 的。

于是思路就是每一个操作,都是关键点上暴力,非关键点打标记,同时对每一行每一列维护非关键点的权值最大值。这样每一次操作都是严格 $O(\sqrt n)$ 的。

只要利用好每一个点要么是行关键点,要么是列关键点,那么每一个操作都可以顺其自然的暴力了。

思路虽然简单但是细节还是比较多的:

维护权值

这个问题的核心在于把横纵的修改和询问联系起来。在刚才那个结构中,可以定义一个行关键点 $(x,y)$ 的权值为它的点权加上列 $y$ 上的非关键点加标记。

这样在行操作的时候,我们把每一个行关键点的点权修改一下,同时更新这个关键点所在列的非关键点最大值。列操作类似。

关于合并

关于合并一个简单的想法是,直接把关键点集合并起来,然后把非关键点最大值取个 $\max$,但是实际上没有那么简单。

首先是标记,在合并两个有标记的行的时候,因为标记是不能下传的(下传要遍历每一个非关键点并修改,复杂度爆炸了)。所以标程的做法是对行和列分别维护一个并查集,同时用类似同态加边判断是否是二分图的方法,在并查集的每一条边上维护儿子和父亲的标记差。

这样对于一个原来坐标是 $(x,y)$ 的点,我们要看它列上的标记,只要在列并查集里求它到根的边权和就可以了。

接着,因为在合并了两行之后,行的点数变多了,所以一些行关键点会变成列关键点。这个时候我们要遍历所有行关键点,然后看关键点是否会跑到另一边去。因为一次合并之后关键点也是 $O(\sqrt n)$ 的,所以这一步也可以暴力。但是要注意的是行关键点变成列关键点后,这个点的点权要根据行列的标记修改一下以满足我们刚才的定义。

关于去重

行列的关键点个数是 $O(\sqrt n)$ 的分析建立在没有重点的基础上,但是合并的过程中会出现重点,这个时候我们需要对关键点去重。

去重的过程相当于把所有相同位置的关键点变成一个点,且权值为这个位置所有关键点的最大值。

如果每一次合并都去重的话,去重的复杂度在瓶颈上,必须要写 hash 之类的方法,常数较大。

实际上可以设一个阈值 $S$,例如 $\frac{3}{2}\sqrt n$,然后在每一次我们要暴力扫关键点集合的时候,如果我们发现关键点数量超过了 $S$,那么就进行一次去重。

因为每一次去重都至少删掉了 $O(\sqrt n)$ 个点,而总点数只有 $n$,所以去重的复杂度不在瓶颈上,可以用 map 暴力。

综上,这个算法的时间复杂度是 $O(n \sqrt n)$ 的,并查集、去重的时间复杂度都不是瓶颈。可以通过后两个数据集。

第三个数据集的用意是避免掉合并操作时标记合并的一些细节。当然可能存在着一些针对性的算法。

个人感觉这题的 idea 还是挺不错的,但是好的 idea 到好的题目的过程还是有点难.. 之前思考熊那题就是这么翻车的。这题虽然有 $6$ 个操作但是因为横竖是对应的如果写的好的话应该可以只写 $3$ 个操作,或者竖的部分可以从横的部分贴过来改一下。因此代码量虽然略大但是应该还是在 OI 比赛可接受范围内,当个 T3 挺合适的。

(不过 UNR 传统是 T2 最难?)

C_SUNSHINE:“Exactly!”

黎明前的巧克力

from sevenkplus, 题解 by C_SUNSHINE

题解很啰嗦,觉得想的差不多的可以直接看算法七。

算法一

我们可以 $3^n$ 直接枚举每个巧克力是在 Evan 的集合 $A$ 里还是 Lyra 的集合 $B$ 里,并判断异或值是否相等,时间复杂度$O(3^n)$,期望得分 5 分。

算法二

我们重新考虑算法一,我们可以先枚举一个巧克力是否在 $A + B$ 里,再考虑是再谁的集合里,由于两个集合的异或值相等,$A + B$ 的异或值一定为 $0$,接着观察可以发现, Evan 可以选择 $A + B$的任何一个子集作为 $A$,Lyra 只要选择其补集即可,所以我们只要对于所有异或和为 $0$ 的集合 $S$,把 $2^{|S|}$ 加到答案里去就好了,最后别忘了 $-1$ 去掉 $S$ 为空集的情况。

如果我们枚举所有可能的 $S$ 集合,我们的算法复杂度就是$O(2^n)$,期望得分 15 分。

算法三

当$a_i$的值域不大的时候,显然这个东西我们是可以DP的,定义一个集合 $S$ 的权值为 $2^{|S|}$。我们可以用 $f_{i,j}$ 表示,前 $i$ 个数,异或和为 $j$ 集合的权值和。那么转移时枚举当前数选不选:

$f_{i-1,j} \rightarrow f_{i,j}$

$f_{i-1,j}\times 2 \rightarrow f_{i,j~xor~a_i}$

用 $m$ 表示最小的 $k$ 满足所有 $a_i$ 都小于 $2^k$,这个做法的时间复杂度是$O(n2^m)$的,结合前面的算法,期望得分 30 分。

算法四

注意到有部分数据不同的数字种类数不算多,我们可以发现一个数字选奇数个对异或和的贡献都是一样的,于是我们用组合数预处理每个数选奇数个/偶数个的权值和,再按数字DP,每次枚举当前数字是选择奇数个还是偶数个进行转移即可,转移方法类似算法三。

假设有 $D$ 个不同的数字,时间复杂度是 $O(D2^m)$,期望得分 40 分。

算法五

继续观察算法三,可以发现每次转移相当于是原数组和当前数组 $F_{a_i}$ 做了一个 $XOR$ 卷积,当前数组 $F_{a_i}$ 满足 $F_{a_i}(0)=1$,$F_{a_i}(a_i)=2$,其他位置上都是 $0$,那我们考虑使用快速沃尔什变换(FWT)来优化这个位运算卷积。

对每一个数 $a_i$ ,都求出 $FWT(F_{a_i})$,然后把这些变换之后的数组乘起来,在逆变换回去得到 $G$,最后输出 $G(0)$ 即可。

这样,你就可以获得…… 0 分了,可以发现这算法的复杂度是 $O(nm2^m)$ 的,会全部TLE。

算法六

作为新时代的OI少年,我们一定要把这个FWT优化到极致,继续观察这个FWT的性质,可以发现 $F_{a_i}$ 只有两个位置上有值,那不妨把 FWT 的结果打印出来观察一下——

可以发现每个位置都是 $-1$ 或者 $3$。

由于FWT是线性变换,即$FWT(F_1+F_2) = FWT(F_1)+FWT(F_2)$,所以若第 $a_i$ 位上的 $2$ 对 $x$ 位置贡献了一个 $+2$ 则第 $x$ 位上是 $3$,反之贡献了 $-2$ 导致 $x$ 位置上是 $-1$。

接着观察可以发现,当 $x~and~a_i$ 的二进制中有偶数个 $1$ 时,贡献为 $+2$,否则贡献为 $-2$。

为什么呢?

不妨采用高维FFT理解FWT来证明一下,我们把数字 $x$ 二进制下的第 $k$ 位用 $x_k$ 表示,则FWT可以写成:

$$FWT(F)(n) = \sum_{k=0}^{2^m-1} \left(F(k) \prod_{j=0}^{m-1}(-1)^{n_jk_j}\right)$$

由于 $01$ 变量的乘法可以看成 $and$,令 $bitcount(x)$ 表示 $x$ 二进制中 $1$ 的数目,则:

$$FWT(F)(n) = \sum_{k=0}^{2^m-1} F(k) (-1)^{bitcount(n_j~and~k_j)}$$

那么这个式子怎么算呢?

不妨考虑枚举 $t=n_j~and~k_j$,在枚举 $s$ 是 $t$ 的超集即$s~and~t = t$,则能收到 $s$ 的贡献的位置 $x$ 满足的条件是,$t$ 的超集集合中,除了 $t$ 为 $1$ 的那几位之外,与 $s$ 没有交集的 $x$。只考虑 $t$ 之外的位,可以发现 $s$ 的贡献其实是针对一个子集的,所以我们只要对子集打上标记,最后补集转化后做子集和变换就可求得贡献和了。

现在我们会求所有元素的贡献和了,可我们要的不是贡献和啊,我们要的是贡献积,这怎么办呢?

假设对于某一个贡献和为 $s$ 位置,$x$ 个数贡献了 $-1$,那么就有 $n-x$ 个数贡献了 $3$,于是列出方程 $3(n-x)-x=s$,可以解得 $x=\frac{3n-s}{4}$。

解出 $x$ 之后,贡献积就是 $(-1)^x \times 3^{n-x}$了,用快速幂计算即可,之后逆FWT回来输出 $G(0)$ 就可以了。

由于要枚举集合和超集,还要做子集和变换,时间复杂度是 $O(n+m3^m)$,结合前面算法期望得分 65 分。

算法七

之前提到过,对于贡献和为 $s$ 位置,设$x$ 个数贡献了 $-1$,列出方程 $3(n-x)-x=s$,可以解得 $x=\frac{3n-s}{4}$,接着贡献积是 $(-1)^x \times 3^{n-x}$了,用快速幂计算即可。

那么观察算法六我们的推导过程,可以发现我们对FWT做了细致的解析,然而既然我们知道他是FWT,其实完全可以不做这个解析,直接用FWT计算贡献和即可。

简单来说我们直接把每一个数的数组 $F_{a_i}$ 加起来,然后做FWT,通过贡献和求出贡献积,在逆FWT回去就能求出答案数组了。

只需要使用 $FWT$ 和快速幂,时间复杂度 $O(n +m2^m)$,期望得分 100 分。

算法八

$$FWT(F)(n) = \sum_{k=0}^{2^m-1} \left(F(k) \prod_{j=0}^{m-1}(-1)^{n_jk_j}\right)$$

这个式子,其实是可以DP计算的,令 $dp_{i,j}$ 表示前 $i$ 位任意,后 $m-i$ 位和 $j$ 相等的数,乘以 $(-1)^{|t|}$ ($t$ 是前 $i$ 位与 $j$ 的交集)的总和。

转移时只用枚举当前位变为前 $i$ 位是,是变成 $1$ 还是变成 $0$,如果第 $i$ 位变成 $1$ 还要考虑当前数字在第 $i$ 位是否为 $1$ 以决定是否要乘以 $-1$.

这个 $DP$ 的复杂度是 $O(m2^m)$的……

不过,明眼人一下子就看出来了,这个DP其实就是一个按位分层求FWT的东西……

除此之外还有一个优化,在做逆FWT的时候,由于我们只要求 $G(0)$,可以发现 $G(0)$ 就是逆变换前数组中所有的元素之和,再乘以 $2^m$ 的逆元,所以直接扫一遍求和即可,不用逆FWT,这样常数可以减小很多。

这样FWT就完全被(或者假装被)省略了……

一个用FWT推完的题代码里没有FWT也是一件有趣的事呢?

时间复杂度$O(n+m2^m)$,期望得分 100 分。

Day2

积劳成疾

from MysteryMan, 题解 by C_SUNSHINE

算法

介于除了最基本的 20 分部分分,其他部分分似乎都比std难写……

于是我们直接说std做法吧!

令 $f_{m,n}$ 表示最大值不超过 $m$,长度为 $n$ 的序列的劳累度之和。

那么首先对最大值是否等于 $m$ 分类,若最大值不为 $m$ 则可以直接加上$f_{m-1,n}$。

接着考虑最大值为 $m$ 的情况,我们不妨枚举最大值第一次出现的位置 $p$,即 $a_p = m; a_{i} < m (1 \leq i \leq p-1); a_{j} \leq m (p+1 \leq j \leq n)$

可以发现,所有包含位置 $p$ 的若干个区间的劳累度都确定了(不妨即为 $c$ 个),为 $w_k$,除了这些区间,$p$ 把整个序列分成了互相独立的两个部分,根据期望线性性,这个序列的劳累度期望为左侧序列劳累度期望乘以 $m^c$ 再乘以右侧序列劳累度的期望,于是就可以 $O(n)$ 转移了。

即 $f_{m,n} \leftarrow \sum_{p=1}^{n} f_{m-1,p-1} \times m^c \times f_{m,n-p}$

时间复杂度 $O(n^3)$,期望得分 100 分。

梦中的题面

La tâche est écrite par ftiasch,

et la solution est écrite par matthew99

算法一

枚举前$m - 1$个数,算出第$m$个数的可能数量,期望得分10分。

算法二

考虑容斥,枚举有哪些数超过了限制,然后使用可重组合数算出方案数,时间复杂度为$O(2 ^ m m)$,期望得分30分。

算法三:

考虑数位DP,记录当前每一个数与限制的大小关系,然后枚举下一位的值,如果使用二进制并采用逐位逐数转移的话,时间复杂度为$O(2 ^ m m ^ 2 \log {b})$,期望得分30分。

算法四:

考虑$c = 1$,如果我们在b进制下进行数位DP,那么我们发现对于从第$x$低位,恰好有$m - x + 1$个数可以取任意$0$到$b - 1$之间的值,剩下的$x - 1$个数只能是0。首先求出$a$个取$0$到$b - 1$的数和恰好为$b$的方案数$\text{ways}_{a, b}$,考虑从低位开始进行DP,维护$sum{x_i} - n$的值,通过记录当前位的进位(或者退位)数,通过前面求出的$\text{ways}$我们很容易进行转移。由于$sum{x_i} < n$,因此最后必须退一位(也可以看成进位为-1),于是我们也很容易求出答案。

时间复杂度为$O(m ^ 2b ^ 2)$,期望得分60分。

算法五:

考虑$c = 0$,那么无非就是有一些$x_k$可以取恰好$b ^ {k + 1}$,也就是,它在前$k$位都必须取0,第$k + 1$位取1,我们很容易通过给DP加一维来实现转移,也就是记录当前有多少数必须取0,那么最开始显然这个数的数量可以任意(因为可以有任意个$x_k$恰好取了$b ^ {k + 1}$),转移就是对于第$k$位枚举$x_k$是否取了$b ^ {k + 1}$,如果取了的话,它本来就必须取0,于是必须取0的数数量不变,否则取0的数个数需要加一。

时间复杂度为$O(m ^ 3b ^ 2)$,期望得分100分。

算法六:

我们考虑从高位往低位进行数位DP,那么取0的个数最开始是$n$,这一维的转移也很好转移。

这个时候我们就不能记录进位了,我们记录从第$k + 1$位开始往后,$n - sum{x_i}$的值,如果这个值大于$m$,那么就是前面所有$x_l$全取$b ^ {l + 1}$也不可能使这个值小于等于0,于是我们只要在0到$m$中枚举,同理,我们也只要考虑这一位之后$n - sum{x_i}$在0到$m$的情况,于是我们枚举这个值,这样我们可以将复杂度降到$O(m ^ 2b ^ 2)$,期望得分100分。

解开尘封的仪式

from sqc, 题解 by sqc

sqc太菜了,他的提答被A穿了,就当送分好了……

炸弹熊

这种不是NPC问题的求最优解的东西果然不适合造提答……数据太难造了QAQ (出题人尽力克制数据包不太大结果出锅了QAQ)

这次提答不良心都是我的锅QAQ

下面说一下每个点的解法吧(当然还有其他做法吧):

测试点1

哇,这是一条链!我会Manacher或回文树!时间复杂度 $O(n)$ 。

测试点2

这个点字符全是 $a$ 啊,拓扑排序找最长路就没了啊。时间复杂 $O(n+m)$。

测试点3

这个点是由 $1 \rightarrow 2,1 \rightarrow 3,2 \rightarrow 4,3 \rightarrow 4$ 这样的基本单位组成的。

枚举中点,暴力向两边拓展即可。

测试点4

一个比较小的一般的DAG。

考虑 $f[k][u][v]$ 表示是否存在长度为k的路径,起点是u,终点是v,然后存一下正图和反图,转移一下。

测试点5

这个图是由一堆链构成的,且链以随机为主。

由于分支路径不太多,所以可以每条路径搞出来然后回文树或Manacher解决。

测试点6

这个图是一个分块图,块间有连边。

观察可以发现块间连边是一个块的某个入度为 $0$ 的点连向另一个块的出度为 $0$ 的点。

所以这个块间连边不影响答案。

对每块用测试点4的方法做就好啦!

测试点7

哇,这是一颗树!数据范围还那么小!

这个点可以随便搞过去。

测试点8

这个点……似乎没什么特殊的性质?

那就……很尴尬了啊……

我们回头看下第7个点?

测试点7(解法2)

诶?这个字符序列……有点奇妙啊……

发现这是个由后缀组成的Trie?

找出最长链然后跑Manacher就好了吧。

测试点8

发现这个点是由一个后缀Trie+一条链+一个前缀Trie组成的。

然后就很好做了。

(泥萌怎么都会这个点啊捂脸熊

测试点9

这个点是性质是一个有向的有根树。

那……试试回文树?

诶?怎么跑半天跑不出来啊,怕是不对?

现在考虑回文树为什么跑不出来。

直接回文树做的话,是均摊复杂度的。如果一条全 $a$ 链后接一个全 $a$ 的菊花就会导致复杂度退化成 $O(n^2)$ ,所以跑不出来。

我们可以考虑把均摊复杂度搞成严格复杂度的。

考虑可持久化KMP的做法。

我们像可持久化KMP一样做,每个转移记录一下trans,然后就是$O(n)$了。

可以参考某篇论文。

(为了减小数据包的大小,删了一些点,这个点出锅了,被乱搞搞过去了啊

UOJ NOI Round #2

2017-07-05 19:39:45 By C_SUNSHINE

UOJ NOI Round #2 将于 7 月 11 日至 7 月 15 日举行。这是 UOJ 第二场 UOJ NOI Round。

UOJ 半年没有动静,丁酉年至今未办UR,UOJ 群世风日下,OI 界甚至产生了 UOJ 已死的不良传言。

就在 UOJ 生死存亡之际,NOI 的到来使得世界各地的 UOJ 管理员们再度集合起来,筹备一场 UNR 帮助大家备战 NOI。

本次 UNR 将以 OI 为主题!

比赛时间

笔试模拟将于 7 月 11 日晚 19 点开始,将进行半个小时。

Day 1 的比赛将于 7 月 13 日上午 8 点半开始,将进行五个小时,共三道题。

Day 2 的比赛将于 7 月 15 日上午 8 点半开始,将进行五个小时,共三道题。

出题阵容

这次比赛的大部分题目来自于 UOJ 管理员,出题人有:

MysteryManftiaschsevenkplussqc

这场比赛除笔试外将计入rating.

比赛难度

比赛的难度将与 NOI2014 相近,相信对绝大部分选手来说题目是具有一定的挑战性的。

同时我们尽力确保了较多的部分分、较好的区分度以及考察内容的全面性,题目中还有着一道提交答案题,大家可以放心食用。

比赛奖励

这次比赛将会根据三次比赛的总分进行排序(如果存在同分将以两天的罚时总和作为第二关键字),其中比赛的前五名将成为这次训练的金牌得主,第六名到第十五名将获得银牌,第十六名到第三十名将获得铜牌。(得奖人数将根据参赛人数进行调整)

总分前三名将获得 UOJ 萌萌哒的撕烤熊抱枕一只。

另外,参加本次比赛将有机会获得 UOJ 抱枕!d72746ef33403997547e50af13c27ddd 是获奖条件的 md5 码。比赛结束后将公布条件。

UPD:比赛已经结束!

echo -n 笔试不是满分的选手中排名最靠前的 | md5sum
d72746ef33403997547e50af13c27ddd

总排名见 http://c-sunshine.blog.uoj.ac/blog/2826

由于前三名已经钦定了抱枕,就从第四名之后开始算啦。恰好第四名 Stalker 又是笔试没获得满分,于是就发给他了!

UOJ Easy Round #7

2016-10-07 11:06:43 By C_SUNSHINE

UOJ Easy Round #7 将于 10 月 16 日星期日晚上 19:00 举行!比赛将进行 3 个小时,共三道题。

这是 UOJ 第七场 UOJ Easy Round。NOIP马上就到了,来一场UOJ Easy Round给NOIP选手们热热身!

公元 1939 年 10 月 16 日,德国纳粹空军轰炸英国领土,二战首次在英国本土打响。

2016 年 10 月 16 日,跳蚤国的死对头跳晚国由于无法忍受跳蚤们每天早上起床早操的行为,跳晚国国王一声令下,率领着他的跳晚们驾驶战机轰炸跳蚤国,一时间跳蚤国硝烟四起,跳蚤们四散奔逃。跳蚤国王十分愤怒,号召全体跳蚤拿起武器,保卫家园!

然而,跳晚们是有备而来,就在不久前,他们一起研制出了新型炸弹——三星note7。这种新型炸弹威力无穷,可以瞬间炸平一个操场。跳晚们立刻加急生产投入到了对跳蚤国的空袭中。纵然跳蚤军队拥有极高的战斗素质,有的跳蚤甚至能直接跳到天上把飞机拉下来,但在跳晚们不分昼夜的狂轰滥炸中,跳蚤国处于十分不利的状态,甚至跳蚤政府都不得不转入地下工作。

这场比赛将围绕跳晚国的侵略战争展开。

出题人:matthew99, vfleaking, zhj, matthew99

(你猜哪些人出了哪些题?)

这场成绩将计入 rating。

参加本次比赛将有机会获得 UOJ 抱枕!e633bc492aea4d52c67d1653e8bbb018 是获奖条件的 md5 码。比赛结束后将公布条件。

再次提醒大家比赛中途只测样例,最后会进行最终测试,把所有提交记录重测。

UPD: 比赛已经结束!

echo -n 第一次参加UOJ比赛的选手中排名最靠前的 | md5sum
e633bc492aea4d52c67d1653e8bbb018

恭喜获得前 5 名的选手!

  1. dwjshift
  2. AmberFrame
  3. lis
  4. zms_
  5. goodqt

恭喜 WoShiShaBi 获得 UOJ 抱枕一个!

C_SUNSHINE Avatar