UOJ Logo WuHongxun的博客

博客

UER#8 A 的最优复杂度

2019-01-31 14:46:49 By WuHongxun

UER8的那天,uoj管理员群里突然出现一个神圣跳蚤君主国国王!

vfk:我证明了UER 8A的lower bound是1.206n,有没有人给一个match的upper bound啊?

众人:[惊呆]

然后我跑到vfk的寝室,看vfk表演了怎么得出这个lower bound和对应的upper bound。

whx:Orz 在uoj blog里写下这个做法吧!

vfk:太忙了,咕咕咕。

于是只有辣鸡whx来复读一遍了。

Lower bound

首先,我们考虑单轮交互的情况,也就是Bob先发一个信息$x$给Alice,然后Alice发一个信息$y$给Bob。

假设$|x| \leq m, |y| \leq m$,由于$x$只有$2^m$种,那么至少有$\frac{\binom{2n}{n}}{2^m}$个下标集合$I$会导致相同的$x$。

那么Alice要发给Bob这些集合的并,但是Alice发过去的集合最多覆盖$\binom{m}{n}$个集合。

为了解$\frac{\binom{2n}{n}}{2^m} \leq \binom{m}{n}$,我们设$m = n/r$,那么$\binom{m}{n} =\binom{m}{rm}=2^{m(H(r) + o(1))} $,其中$H(p) =plog_2\frac{1}{p}+(1-p)\log_2\frac{1}{1 - p}$是大家熟悉的信息熵。

所以$\frac{2^{2mr}}{2^m \sqrt{2mr}} \leq 2^{mH(r)}$,两边同时取$log$得:$2mr - log(mr) \leq m(H(r) + 1)$

因为我们只关心乘在$n$上的系数,不妨舍去log项,从而得到$2r \leq H(r) + 1$, 如果召唤mathematica,我们很快就知道$m = n / r =1.206n$

这个Bound同样适用于多轮的情况,不严谨的说,因为在多轮交互中,Alice发给Bob的信息只能依赖于Bob之前发过来的信息,以及Alice自己的串,从而在给出了Bob之前发来的串之后,对Bob手里的集合$I$信息量为0。(有人有兴趣用conditional mutual information严谨的证一下吗)所以最后Alice发给Bob的还是至少是$\frac{\binom{2n}{n}}{2^m}$个集合的并。

另外,这个Bound也一样适用于高概率正确的随机化算法,因为它要在趋近于1的比例的下标集合$I$上合法,就必须

Upper bound

Shannon在证明存在一种编码方式可以达到信道容量的时候,所用的方法就是给每个元素随机编码,我们也用一样的思路。

Bob要发给Alice的其实是$I$的一个超集,所以我们现在的问题其实是,我们要从$N=\binom{2n}{m} = \binom{2mr}{m} = 2^{2mr\left(H\left(\frac{1}{2r}\right)+o(1)\right)}$个大小为$m$的集合中,选出不超过$M=2^m$个,使得每个可能的下标集合$I$都是某个集合的子集,我们不妨随机选这$2^m$个集合。

因为一共有$K=\binom{n}{m-n} = \binom{mr}{m(1-r)}=2^{rm(H(\frac{1-r}{r})+o(1))}$个集合覆盖了$I$,其中一个集合都没被选的概率就是: $$ p=\frac{\binom{N-K}{M}}{\binom{N}{M}}=\frac{(N-K)^{\underline M}}{N^{\underline M}}\leq\left(1-\frac{K}N{}\right)^M=(1-2^{rm(H(\frac{1-r}{r})-2H(\frac{1}{2r})+o(1))})^{2^m} $$ 我们做一些简单的计算:

\begin{equation}\begin{split} &H\left(\frac{1-r}{r}\right)-2H\left(\frac{1}{2r}\right)\\ &= \frac{1-r}{r} log\left(\frac{r}{1-r}\right)+\left(1-\frac{1-r}{r}\right)log\left(\frac{1}{1-\frac{1-r}{r}}\right)-2\left(\frac{1}{2r}log\left(\frac{1}{2r}\right)+\left(1-\frac{1}{2r}\right)log\left(\frac{1}{1-\frac{1}{2r}}\right)\right) \\ &=\frac{1-r}{r}(log(r) - log(1-r))+\left(1-\frac{1-r}{r}\right)(log(r) -log(2r-1))+\frac{1}{r}(log(r)+1)-\left(2+\frac{1}{r}\right)(log(r)+1-log(2r-1)) \\ &=\left(\frac{1-r}{r}+1-\frac{1-r}{r}+\frac{1}{r}-2-\frac{1}{r}\right)log(r)-\frac{1-r}{r}log(1-r)+\left( \frac{1-r}{r}-1 +2-\frac{1}{r}\right)log(2r-1)+\frac{1}{r}-2-\frac{1}{r} \\ &=log\left(\frac{1}{r}\right)+\frac{1-r}{r}log(1-r)-2 \\ &=\frac{H(r)-2r}{r} \end{split}\end{equation}

也就有 $$ p \leq (1-2^{m(H(r)-2r)})^{2^m} $$ 因为$H(r)+1-2r\rightarrow 0$,所以$H(r)-2r<0$, $2^{m(H(r)-2r)}\rightarrow 0$,从而 $$ p \leq (1-2^{m(H(r)-2r)})^{2^m} =(1-2^{m(H(r)-2r)})^{2^{m(2r-H(r))+(H(r)-2r+1)m}}=e^{-2^{(H(r)+1-2r)m}} $$ 我们取$H(r)+1-2r> \varepsilon$,那么在$m \rightarrow \infty$的时候,$p \rightarrow 0$,不难发现$\binom{2n}{n}p\rightarrow 0$,我们随机选的集合大概率能覆盖所有这样的$I$。结论就是,我们可以任意逼近我们之前推出的lower bound。

Remark

这道题如果优化的目标,变成二者所发信息的和,那么就是一个典型的”通信复杂度“的问题了,但是那样的话,我们的方案$2.412n$还不如直接把整个串发给Bob。事实上直接把整个串发给Bob也最优的复杂度了,因为Bob可以计算出两个串对应的集合有没有交,也就是Set disjointness上。

同时这个方法因为需要uniform的随机取$2^m$个大小为$m$的集合,不能直接用于这道题。有没有同学试一试不严格的随机方法能不能通过?

暂别

2018-09-16 21:24:53 By WuHongxun

紧张的二招结束了,难熬的军训过去了,一转眼已经到了开学的季节,也是一年一度uoj传(diu)承(guo)的季节了呢。

我们(WuHongxunScapeWrongAnswer),在过去的一年里负(gu)责(gu)了uoj的题目和比赛。这一年里,在叉姐ftiasch、毛爷爷matthew99 、吉老师jiry_2 等等的大力帮助,以及正在读这篇post的你的支持之下,办出了一些质量让人满意的比赛,其中大部分题目都是我愿意推荐给别人的好题。

但是与此同时,在这一年里,一方面因为我们能(tai)力(ge)有(le)限,导致比赛场次和频率非常少。比如UNR差点变成Uoj No Round。另外一方面我们不(tai)够(lan)勤(le)奋,导致比较枯燥的传题任务有许多没有完成。非常惭愧,今天中午在宿舍遇到vfk的时候,vfk说还以为uoj快要凉了,我们没有称职地完成任务,十分对不起大家。在新的一届里,我们吸取了之前的教训。将会分设传题组和比赛组,分别负责比赛和传题的工作。每组会由三名活跃的OIer/ACMer构成,将会按照新任管理员的意愿进行分组。希望新的改变可以带来新的生机与活力。

下面就宣布新的管理员队伍。

出题组:AwDwhzztztr

传题组:nike0gooddiamond_dukeLazyJazz

会由朱老大whzzt来负责联络和给大家分锅。

再说一点题外话吧。

虽然很长一段时间,我都没有把自己当做一个“典型”的OIer。但当进入了大学,就突然发现自己被打上了OIer的标签,面对问题时的思维方式和习惯都带上了OI的烙印。再回头看去,才发现OI成为了自己重要的一部分,而OI也不断塑造着一批批的OIer。希望在这个进程中,新的管理员能让uoj成为一盏明灯。对新OIer而言,能照亮OI里最有趣的那些部分,对老OIer而言,就像家中的灯光一样,回首就能感到它的温暖。

愿UOJ和OI的明天更加光明,祝新的管理员们一切顺利!

UOJ NOI Round #3 排行榜

2018-07-14 15:52:03 By WuHongxun
排名ID笔试Day1.ADay1.BDay1.CDay1Day2.ADay2.BDay2.CDay2总分总罚时
**金牌($15$人)**
1wangxiuhan98100100100300100208120159972579
2fjzzq200298100100100300100106917957768202
3kczno19645100100245501006221255361751
4tqyaaaaang9910010010030050306214254180554
5orbitingflea9910010010030050206213253178486
6zhangzy9910010010030003010013052957963
7smallfat9910010010030030108112152085509
8666sb666100701001002707004511548568418
9peehs_moorhsum1001010010021001002812843858276
10xuyixuan1007066100236020678742372090
11YMDragon010100100210100208820841881263
12cxt045100100245100204516541075875
13F_Darcy9635100100235020527240369138
14yww100106010017070105213240266613
**银牌($25$人)**
15cwystc_fan10010010002000010010040029696
16mayaohua045661002117010019189400102391
17sshockwave10010661001765006211238850353
18laofu01010010021070208117138174628
19Marco_L_Tsien10010100100210020517138179313
20mcfxmcfx01006010026001010011037074038
21CYDIATER1007066100236010223236871281
2200zj10035661002011520225735882567
23langsike991010010021004084835779309
24ljt121381001001005205010415135679983
25nqiiii6310100100210020628235562030
26dcy11011951066651415006911935581563
27xjzjohn9135100100235151032835476034
28LazyJazz01001003523570103611635176939
29wzf200001006610026600818134741096
30l__ZeRo_t010061002060608114134751986
31atempuser0451001002450010010034549475
32beginend1001010010021000333334336024
33cwystc010010010030030083833867387
34ClssWer98010010020000363633451074
35ez_zwl1001066100176010485833464728
36qiqi2002102698451003518000505032851992
37Starria10020100100220008832857878
38asd123www89100100020003033332246293
39un26259496101005016000626231851713
**铜牌($50$人)**
40cdsfcesf97106007070305015031774983
41zx2003982066100186010223231676070
42applese9501006516500545431433240
43supy100100601060100810831472104
44duweihua90100651115006211231360524
45AChen142857070100352050100810831368086
46ugly23339410100100210008831259104
47zht111_98101003514500676731047738
48Magolor1002010035155010445430981772
49KEKE_046100106007001003813830867284
50Icyfox100701000170010273730757922
51litble992010051253010397930369583
52dy060702010010022000818130169193
53liu_cheng_ao0100100100300000030040030
54xjr100101006517501081829367721
55jhr10010666514100515129247078
56Tommy_r799101005016000333329250600
57Timsei98101006517515031829180143
58Blue233333997010020190000028928521
59izumihanako9951003514000505028958252
60TLEbyc1001010051153020227228779122
61Kirin9220100512500696928664522
62DZYO97706100176000027332780
63Spylft10060010016001031327345428
64jhdjames3710020610012600454527152038
65ez_zjt035361001710307010027162411
66YuHaoXiang96100660166000026224502
67oscar100101000110150334825867852
68Sdchr961060070700198925545796
69LadyLex100206035115020204025583475
70bulijiojiodibulido00000701008325325332097
71wxgwxg1001010035145008825360420
72igronemyk99106635111010334325374942
73lichangdongtw10020300507030310325391429
74vera990100010000515125031455
75Cyanic8910000100300316125044744
76Ivan9945665116010253525070481
77yzx_H2O100151000115010223224750624
78zhangyiding04010051455005210224773583
79superguymj10010100011000333324341174
80Ra1nbow9910010011000333324245858
81noi2018test1000100010000414124128048
82zhouyuyang961010035145000024142866
83infinityedge9820662010600343423856998
84wdyhy92206620106020193923748980
85Hzoi_joker9910100011000272723654904
86SHENZHEBEI901010035145000023528829
87shixinyi93351000135000022813533
88deadecho01010010021001081822842926
89wbyyui9920365010600202022551241
**胸牌($??$人)**
90NaVi_Awson995100010500191922325923
91Anoxia100201000120000022031871
92Narcissus9635363510601081822064335
93wangyuji01066100176301034321987876
94Lin1043990100010000191921815769
95KingSann99151000115003321718284
96kyr1no980100010000191921722104
97Sinogi970100010000191921620319
98zP1nG98101000110008821627958
99hycc10070360106008821438035
100Anoxx1001063551300336321469032
101qq81553615410051000105008821334663
102GQH1231000100010001031321341589
103WinXP99101000110003321239660
104cloudsky100101000110000021019619
105cuking100101000110000021023401
106iot010100100210000021029908
107__stdcall10001000100008820830222
108ldxxx9710060106003320640661
109irides10051000105000020519598
110wangzhongtao97560065301034320564506
111zhouyi9901000100003320211962
112Iscream01001000200000020023921
113Primy990100010000001998528
114_rqy980100010000001989151
115pb02079620653100696919652756
116miaom941000010000001944974
117Never_See940100010000001948724
118Ebola9606606615082318543235
119wh200199100354500393918346275
120wyc188521001036206601031317960358
121wangxh93100010020557517852795
122xxyj0101003514503033317878411
123zhaimingshuzms010666514100363617751154
124qxj010666514100363617764300
125zhoutb951066076003317420212
126TS_Hugh930651170007017446912
127Treeloveswater912060080000017121841
128fpdqwq97000070007016719028
129lumingqi99100010300275716635037
130scallop901036046010192916559918
131Turkey0101003514501081816371085
132dian_di001000100010485815841213
133helehan0101003514501031315854765
134newbie314159020010012000363615628784
135huangsi02010035155000015538166
136Hunter_Will8806606600001546215
137ksyx8356607100001547091
138WildRage95106016010334315455271
139jjikkollp1001036551000015129461
140Rebirth_A010100511500363615151638
141Deluxurous010100511500363615155235
142XYZinc981036046000014422345
143mengbierr010100011000333314350372
144JackBai9920002000222214137049
145tianfuzhen056635106010253514169123
146ridiculos75103604600191914043126
147Samsara_Karma921003545000013733357
148AloNE97036036003313625191
149shjzhqm0351000135000013514534
150qwecjiwjd95036036003313416197
151lujiaju00100010000333313325570
152Duan2baka9815602100141413340447
153I_Love_Minions000007006213213236642
15415810698439503603600001314782
155Aqua100206026003312929395
156hhzzkk010100511500141412938842
157Acheing010100011000191912952923
158whitesola01066581150334812967624
159NORMALone010100011015031812848024
160linly8713100000000252512514820
161foreverlasting00100010000191911915063
162nansns00100010000191911919083
163Apocrypha0101000110008811825845
164wxs6666660101000110008811835953
165rootnode98106016003311751057
166l1ll5100106016000011619935
167Jiangkangping98000015031811636580
168wjh_082311179956011003311325547
169Mr_Spade9610601600001128087
170blackjack97150015000011216555
171LZHlzh0101000110000011022727
172thchuan20010066066301034310973121
173liujun390598000000331015175
174VisJiao980000003310115072
175temp6965005000010117859
1760_25100000000001000
177Cai100000000001000
178Coding_Farmer100000000001000
179Isrothy100000000001000
180RabbitHu100000000001000
181Saramanda100000000001000
182Xeonacid100000000001000
183cyl100000000001000
184ljs_yali100000000001000
185luyouqi233100000000001000
186wdmmsyfsyf100000000001000
187zlt100000000001000
188cc12332100100010000001007804
18943423850400000001001001008799
1903215010000100000010010192
191Dilhao001000100000010013577
192richway2001000100000010017560
193bestFy01066076010142410047504
194CRITICAL_PROCESS9900000000990
195File_saver9900000000990
196dlqqq1239900000000990
197lzq_9900000000990
198q234rty9900000000990
199wy16279900000000990
200xy201306309900000000990
201yyc9900000000990
202137shoebills9800000000980
203Umbrella9800000000980
204XHRlyb9800000000980
205liumy20109800000000980
206xlj9800000000980
207Pickupwin9700000000970
208rabbit_lb056006501022329756461
209Chuzyh0103655101036469772778
210hypnotic9600000000960
211zyyorz9600000000960
212ShichengXiao9500000000950
213hanghang07029500000000950
214lastans79500000000950
215miaowey9500000000950
216zhangenming9400000000940
217Mogician9300000000930
218Ice_teapoy9200000000920
219huhao9200000000920
220shadowsocks9100000000910
221crazy_cloud9000000000900
222permui8900000000890
223MiracleEEEE8800000000880
224WAAutoMaton8800000000880
225fakeac8700000000870
226Amphetamine06060660019198534278
2277707800790000015069848431131
228Imperfect0106607600888453122
229shuiyuhan7900000000790
230qaz00600600019197927063
231Gunbuster010650660103137968603
232lonelysniper0106607600007623508
233bzh0106607600007634207
234star_magic_young056607100337448533
235wjy017200000000720
236Demerzel000000069696911987
237dsgsjk006606600336912066
238Senji006606600336935094
239pinkex02065310036366746195
240Hallmeow056006500006535465
241ywt_16300000000630
242zhouzhendong0000030031616137006
243pizzaking00600600000605749
244233sb233000005003535319079
245yhgalaxy00360360103134934046
246justahuman0000001036464633669
247liji010001015019344446219
248Js2xxx053003500333829484
249hercier0000001028383833205
250fengchanghn00360360000364542
251feng_chengjie003603600003611446
252OhWeOnFire000000036363618287
253chenjiyuan30000001019292933604
254zj_yuneng0000001019292933681
255dsl200201000100017172713150
256orzzz015652600002637086
257elijahqi010601600882445959
258functionendless010601600331925810
259ARiAkari010001000881829335
260RedKiller23300000001717177477
2611124828077000000016161611181
262Tachibana_Kanade010601600001615930
263Zhang_RQ015001500001512513
264zlh1000000014141410503
265ax7e010001000331314579
266SirKnight000000103131334173
267whcyz010001000001013180
268onlysky010001000001013531
269xuzhouzi010001000001017919
270orzljr00000008884646
271zhoushuyu00000008886154
272Mychael000000088814114
273WeaponMasterOri000000088814681
274ratingunderflow000000088814705
275wuenze000000088817645
2762000F11Y10M123006060000613233
277112122011005005000053957
278jamiechoi05005000058080
279Notseefire00000005559339
280hfctf021000000003331335
281attack00000003331665
282was_n00000003333170
283hychyc00000003333816
284xiaohao23300000003334259
285Kukoc00000003334628
286lzgaoyurui00000003336377
287yczddgj00000003337788
288miaokehao00000003337941
289mjt00000003338060
290tlyangwj00000003338307
291lzoilixy000000033312412
292WAAutoMata000000033314549
293evangelion13000000033315333
294CleverLarry000000033316447
295HeroOfJustice000000033318548
296waiwaibi000000033319179
297122333abcd00000000000
298123456700000000000
2991999214700000000000
3002017thx00000000000
301AnzheWang00000000000
302CHNFTQ00000000000
303Cansult00000000000
304DXC00000000000
305DawnMint00000000000
306Devil_Gary00000000000
307Diogenes00000000000
308DolaBMOon00000000000
309DraZxlNDDt00000000000
310EdwardFrog00000000000
311GOOD00000000000
312HailJedi00000000000
313HenryLi00000000000
314IONKAYXC00000000000
315JYYHH00000000000
316LanrTabe00000000000
317NicoDafaGood00000000000
318Oktavia00000000000
319OrangeLee00000000000
320Rye_Catcher00000000000
321Sigmoid00000000000
322Silver_Sink00000000000
323Stan_Chou00000000000
324TonyZhao00000000000
325VCode00000000000
326Xe0nacid00000000000
327Xin_Time00000000000
328YGGGAY00000000000
329YuXiaoze00000000000
330alex_china00000000000
331bennyJBC00000000000
332caiB_Oier00000000000
333camouflager00000000000
334cdzhangjiajie00000000000
335chenye_202400000000000
336chuhan00000000000
337cjj66666600000000000
338cqz21083154900000000000
339cyhzz00000000000
340cyz66600000000000
341dengdengdeng12300000000000
342dlzzq200200000000000
343fzjjq200200000000000
344fzyz_duke00000000000
345goldgenius00000000000
346highplay12100000000000
347jah_melon00000000000
348jmsyzsfq00000000000
349kevinshuai00000000000
350kuangshouren00000000000
351larryzhongcn00000000000
352lijinnn00000000000
353orzyxq00000000000
354pbreader00000000000
355pbvrvnq00000000000
356rt00000000000
357sdfzchy00000000000
358spicy_chicken00000000000
359u3330400000000000
360ubospica00000000000
361vanilla00000000000
362whzxp00000000000
363wjxandmk00000000000
364ws_zzyer00000000000
365wsmrxc00000000000
366xdll_xc00000000000
367xht1312700000000000
368xinyue00000000000
369ywx00000000000
370zbw00100000000000
371zenmeshuone00000000000
372zerolt00000000000

UOJ NOI Round #3 Day2 题解

2018-07-14 15:46:20 By WuHongxun

白鸽

from matthew99, 题解 by matthew99

出题经历——为什么这会是A题?

这个题本来idea几乎就一个——射线法的应用,但是我逐渐发现不管怎么出题,都没区分掉依赖于角度的做法(比如说,如果换成小范围的哈密顿路径,实际上对于每个点可能的角度个数也是$O(n)$的,当时这个题说的时候差不多是这个版本然后我也没意识到不用射线法也能做,所以感觉能做A)。但是这个题A题的位置已经占了,到后面为了保证不成为导致这场比赛鸽掉的千古罪人,也因为deadline临近没时间重新再想一个题了,只好抱着“孩子再丑也要生下来”的心态把这个题出完了。当然,这个题出A题,我也不喜欢(其实这个题变成这个样子我也不喜欢了),要是准备更充分应该把这个题和昨天B交换的。如果你们是抱着做好题的心态来做UNR却被这个题翔了一脸我只能真心说声抱歉了。

如果你们有兴趣读完这篇题解,那么你会发现我最后区分掉(或者一定程度上区分掉,取决于是否还有不用射线法的做法存在)直接用角度的做法的方法就是利用费用流的代价只有0或者1的性质,而当出题走到这一步的时候,除了出一个看起来玄学的复杂度然,写一个长得荒唐的高效费用流并使用非常复杂的方法证明一个丑陋的复杂度下界,没有任何别的路可走了。

总之,在出题方面这个题的教训还是很多的,首先最显然的是一定要趁早,如果比赛临近了还在准备题目再发下出各种问题,那么很可能要么只能鸽(显然,UNR不能再往后拖任何一天),要么最后出出来的题变成怪胎。其次就是,我出题的习惯一般是想到一个题目再想做法,而不是想到一个做法再去强行凑题。这个题刚开始还是先想到的题,而不是先想到的做法,但是我后面发现我非常喜欢这个射线法的思路(其实这个思路非常显然,只是自己卡了很久就觉得很神奇),于是走上了对着做法凑题的弯路。

当然,可喜之处是这个题最后还是没有出很基础的问题的,差评是可以预料的,好评才反而是奇迹,哪怕换做我是考试选手我也会想差评的,这个题的档次也完全不及我以前出的任何一个题。但是怎么说呢,这场UNR办的非常紧急(这个当然也有我自己的责任),差评题也胜过没有题。说不定你们NOI还会遇到更奇怪的题?

角度法

容易发现,顺时针方向走过的圈数可以通过将每次走的边的极角加起来再除以$2\pi$,即180°,得到。

射线法

容易发现,如果从原点任意引出一条射线,你所找出的欧拉回路在顺时针方向经过这条射线的次数减去逆时针方向的次数是一个常量,这个常量就是顺时针方向绕原点旋转的次数。

subtask1

这一个subtask就是直接暴力,枚举边的访问顺序并计算答案。时间复杂度是$O(m!poly(n, m))$。

subtask2

这一个subtask的做法是基于状态压缩的动态规划,记录一下当前已经访问的边和当前所在点,以及当前走过的角度和,或者当前顺时针时间方向经过射线的次数减去逆时针方向的次数,如果你使用射线法的话。复杂度是$O(2 ^ mn)$。注意不要记录当前所在边因为这将使时间复杂度退化为$O(2 ^ mn ^ 2)$(当然你很可能也能通过这个subtask)

判断一个图是否存在欧拉回路

这一步相信大家都会做,每个点的度数必须是偶数。且每一条边都必须和$1$号点连通。注意孤立点可以不与$1$号点连通。

subtask3

这个subtask就是最基础的费用流,同时也是给基于角度法的算法的。我们可以将原图转化为一个可以跑费用流的图:首先任意找一条欧拉回路然后计算答案,然后对于每一条边我们可以将其反向,我们可以反向连两条边,流量均为1,费用为角度或者顺时针穿过射线的次数。然而,直接连两条边会存在一个问题,你有可能只增广了一条边而没有增广另一条,这种情况下你相当于一条边没有经过。解决方案是将两条边合成一条流量和费用一样的边,然后将答案乘以二。由于原图存在负权,这个时候你只能用消圈做法,这大概没法过后面两个subtask。

另外一个思路是先任意定向并贡献答案,,新建源和汇,然后对于入度大于出度的点,从源向它连一条流量为入度减去出度的边;对于出度大于入度的点,从它向汇连一条流量为出度减去入度的边。由于前面我们将整张图的流量和会用都除以了$2$,这些流量也要除以$2$。容易发现如果存在欧拉回路的话,这些流量都是偶数,所以这个操作不会导致非整数的出现。然而这样建成的图还是有负权,这意味着我们必须用Bellman-Ford或者SPFA来做最短路,这个算法是平方级别的,乘上线性的增广的次数,总时间复杂度是$O(n ^ 2(n + m))$难以通过subtask4。

subtask4

接下来的算法都基于射线法。

对于一条权值为负数的边,我们可以通过将其反向来干掉负权。这样的话,开始的图不会有负权,我们可以用Dijkstra算法计算最短路,由于路径长度是$O(n)$以内的整数,可以用桶做到线性。

对于后面的图,负权边是难免的。考虑在做Dijkstra的时候每次选距离增加量最小的点而不是距离最小的点,可以证明基于增加量的图是没有负权的,于是我们可以在线性时间内更新最短路。

总时间复杂度为$O(n(n + m))$。

subtask5

在每次做完最短路之后,我们可以用dinic算法来增广掉当前残余网络上所有的流量。可以证明这样最短路长度将会增大。

容易证明在单位容量网络上做dinic的复杂度是$O((n + m)\sqrt{n})$的。

对于长度不超过$O(n ^ {\frac{1}{4}})$的最短路,做dinic的总时间复杂度为$O(n ^ {\frac{3}{4}}(n + m))$;由于答案不超过$O(n)$,长度超过这个值的最短路不超过$O(n ^ {\frac{3}{4}})$条,总时间复杂度也是$O(n ^ {\frac{3}{4}}(n + m))$。因此总时间复杂度不超过$O(n ^ {\frac{3}{4}}(n + m))$,可以通过本题。当然这个界感觉还是有点松,如果你发现了更优秀的下界请告诉我。

如果你常逛炉石相关论坛,你可能会遇到一些和这题模型一致的问题,如火山喷发概率求解

网友们往往给出一些错误解法(如算法零)、多次随机模拟法(在这题中没有用)或是复杂度为指数级的解法(如算法一),然而事实上是可以在多项式时间内求出精确解的。

百鸽笼

from ztr, 题解 by ztr

算法零

每个鸽笼空着的概率相等,所以每列有空鸽笼的概率和这列的鸽笼数成正比(雾),且总和为$1$,容易求解。

期望得分:$0$。

算法一

我们令$m=max\{a_i\}$,并在接下来的算法描述中都有这个约定。

状态压缩DP,考虑计算每列鸽笼最后有空鸽笼的概率,记录每列鸽笼还剩余几个空鸽笼为状态,并枚举转移,复杂度$O((m+1)^nn^2)$。

期望得分:$10$。

算法二

注意到如果只是交换两列鸽笼的空鸽笼数量,得到的状态是等价的。对状态进行去重,复杂度$O(C_{n+m}^nn^2)$。

期望得分:$20$。

算法三

前面的算法已经没有什么优化的余地了。

我们可以考虑有$N$个管理员要住,每列鸽笼最后一个住满的概率。

最后一个住满就是在其他$n-1$列鸽笼住满后住满,考虑容斥,通过计算要在某些列鸽笼住满前住满的概率(其他列鸽笼先后任意)来求得答案。

假设选定了要在某$m$列鸽笼住满前住满,其余$n-m-1$列鸽笼什么时候有管理员进对你要算的概率已经没有影响了,于是考虑$m+1$列有关鸽笼的进入序列(每个管理员依次进入哪列)。

这个序列应当包含$a_i$个$i$(第$i$列是被计算概率的一列),少于$a_j$个$j$(第$j$列在选定的$m$列中),且以$i$结尾,且若其长度为$L$,则会产生$(\frac{1}{m+1})^L$的贡献。

这部分很容易使用背包DP来完成,记录用了前几个有关列和当前的总长度是多少为状态,枚举这一列要用掉多少个来转移,复杂度$O(n^2m^2)$。

由于拼在一起后可以任意排列,用掉$L_0$个的贡献要附带系数$\frac{1}{L_0!}$,最后长度为$L$的贡献要附带$L!$。

算上枚举容斥,总复杂度$O(2^nn^2m^2)$。

期望得分:$30$。

算法四

判断数据范围,结合算法二和算法三。

期望得分:$40$。

算法五

我在浏览选手代码时还发现了一种玄妙的DP(其中之一),大概是记录已进入管理员总数和那些列仍有空鸽笼(而没有记录每列具体空鸽笼数量),就能直接转移,复杂度$O(2^nn^2m)$。

期望得分:$30$

算法六

观察算法三的容斥过程,发现一个进入序列的贡献只和$L与m$有关,因此可以加一维状态表示当前选定的有关列数量,枚举这一列要不要被选定与如果要选定的话用掉多少个,这样就能去掉指数上的$n$,复杂度$O(n^3m^2)$。

由于每个都要算一遍,总复杂度$O(n^4m^2)$。

期望得分:$60-100$。

算法七

最后这步其实挺没意思的,算法五仍然是一个背包状DP,算第$i$列的答案的复杂度瓶颈是在把其他$n-1$个东西卷在一起,如果先全部卷起来然后每次退掉一个,复杂度即可优化到$O(n^3m^2)$。

期望得分:$100$。

算法八

事实上指数型生成函数爆推也是可以的。

首先参照PKUSC2018 狼人杀,可以认为已满的鸽笼列照样可以塞管理员(只是不产生效果),那么同样考虑入住序列,应当包含$a_i$个$i$(第$i$列是被计算概率的一列)和不少于$a_j$个$j$(第$j$列是其他列),且以$i$结尾,且若其长度为$L$,则会产生$(\frac{1}{n})^L$的贡献。

从指数型生成函数的角度来思考,对于单列鸽笼,如果其可以被入住$t$次,应当有$G(t)=\frac{x^t}{n^tt!}$的贡献。每列鸽笼可以被入住那些次数是独立的,因此目标函数$F(i)=\frac{G(a_i-1)}{n}\prod_{j\neq i}\sum_{t\geq a_j}G(t)$,且若$F=\sum c_ix^i$,则该列答案$Ans(i)=\sum c_ii!$。

又注意到$\sum_{t\geq 0}G(t)=e^{\frac{x}{n}}$,故若设$S(t)=\sum_{0\leq s\leq t}G(s)$,则$F(i)=\frac{G(a_i-1)}{n}\prod_{j\neq i}(e^{\frac{x}{n}}-S(a_i-1))$

考虑展开后每个$e^{\frac{mx}{n}}x^t=\sum_{s\geq0}\frac{m^s}{n^ss!}x^{t+s}$,现欲求其贡献$\sum_{s\geq0}(\frac{m}{n})^s\times\frac{(t+s)!}{s!}$,容易化得此式为$(\frac{n}{n-m})^{t+1}t!$。

因此只需要求出这些可能展开项的系数即可,不难发现在代码实现上,该做法与容斥做法几乎完全一致。

鸽举选仕

from whzzt, 题解 by whzzt 首先作为出题人给大家道个歉……准备时间有点紧张,没有来得及对每个子任务进行认真的检查和加强,对UOJ系统不熟悉、赛中又出了若干口大小不等的锅,实在是有点难受啊……都怪*鸽普太鸽了(甩锅)

今天这题的源代码已经提供给选手了,因此卡这些乱搞就会显得容易很多。出这题也算是让大家感受一下出题人的不易?

子任务一

我们观察一下下发的代码:

#include <stdio.h>
int a, b;
int ADD(int a, int b){ return (a ^ b) | (a & b) << 1; }
int main(){
    scanf("%d%d", &a, &b);
    printf("%d\n", ADD(a ^ b, (a & b) << 1));
    return 0;
}

显然将函数 $ \texttt{ADD} $ 中的 $ \texttt{|} $ 改为 $ \texttt{+} $ 就是正确的,否则错误率有点高。

所以我们随便手输几组 $ a, b $ 就好啦!

子任务二

我们可以发现这位选手的代码中分成了两个部分:当边数 $ m $ 很少时跑 $ O(m) $ 的暴力,边数较多时跑 $ O(n^2) $ 的 BFS。

在小数据的时候显然这份代码不会超时,所以我们可以先拿出 $ 10^3 $ 左右个节点连成一个完全图,然后再挂出去一条链,每次询问链的端点到图上一点即可。

代码:

#include<stdio.h>
int main(){
    int i;
    puts("5000 10000");
    for(i=2;i<=1000;i++)printf("1 1 %d\n",i);
    puts("1 1000 5000");
    for(i=4999;i>=1001;i--)printf("1 %d %d\n",i+1,i);
    for(i=1;i<=5001;i++)printf("2 %d %d\n",i%1000+1,1001+i/1000);
}

子任务三

咦这个乱搞怎么似曾相识?这么困难,怎么做?

我们考虑我们的目标是什么:不妨考虑构造两棵形态相同的树,假设答案点对为 $ (x, y) $,那么最终的答案就是 $ d_1(x) + d_1(y) - d_1(lca(x,y)) - d_2(lca(x, y)) $。

我们想要钦定一对这样的 $ x $ 和 $ y $,那么什么能够让我们完成这个任务?当然是让 $ d_2(lca(x, y)) $ 尽量小,同时不存在其他点对 $ p, q $ 使得 $ lca(p, q) = lca(x, y) $。

这显然是不可能的,例如 $ p = lca(x, y) $ 时只需选择一个子树中的点。但是我们可以钦定 $ d_1(lca(x, y)) $ 也很小,这样我们就不能选择 $ lca(x, y) $ 这个点啦。

如此一来我们保证了答案的唯一性,并且在过程中只用了 $ 3 $ 个节点,接下来的任务就是使得在迭代过程中如果碰到的不是 $ x, y, lca(x, y) $,就一定无法迭代到最优解。

这就非常容易了,因为点 $ x $ 和点 $ y $ 间存在一个 % d_2(lca(x, y)) 的天然优势,接下来我们只要用另外的一些点引诱你过去就可以了。

鼓掌熊

一种构造大致如下:

#include<bits/stdc++.h>
using namespace std;
int rnd(){return rand()<<15|rand();}
int rnd(int l,int r){return rnd()%(r-l+1)+l;}
const int N=100005,inf=2e9;
int n=100000,m,p[N],fa[N],fd1[N],fd2[N];
int main(){
    int i;
    for(i=1;i<=n;i++)p[i]=i;
    for(i=1;i<=n;i++)swap(p[i],p[rnd(i,n)]);
    m=n-100;
    for(i=2;i<=m;i++)fa[i]=rnd(1,i-1),fd1[i]=rnd(-10,10),fd2[i]=rnd(-10,10);
    fa[m+1]=1;fd1[m+1]=-inf;fd2[m+1]=-inf;
    fa[m+2]=m+1;fd1[m+2]=inf;fd2[m+2]=rnd(1,10);
    fa[m+3]=m+1;fd1[m+3]=inf;fd2[m+3]=rnd(1,10);
    fa[m+4]=m;fd1[m+4]=-inf;fd2[m+4]=-inf;
    for(i=m+5;i<=n;i++)fa[i]=i-1,fd1[i]=-inf+rnd(-10,10),fd2[i]=-inf+rnd(-10,10);
    //best solution: m+2, m+3
    printf("%d\n",n);
    for(i=2;i<=n;i++)printf("%d %d %d\n",p[fa[i]],p[i],fd1[i]);
    for(i=2;i<=n;i++)printf("%d %d %d\n",p[fa[i]],p[i],fd2[i]);
}

好像因为时限太小大大降低了难度。

子任务四

感谢@Foolmike提供该子任务。

???

咦这个子任务真的错了吗?

思考熊

撕烤一下我们可以发现,这份代码的主要思想是维护 $ f_i = \max(f_j + \max(w_{j + 1} \ldots w_i)) $ 的最大的 $ j $,并使用单调队列维护。但是我们可以发现可行的 $ j $ 并不是单调的。

因此我们只要随便手动构造一下就可以得到这个子任务的分数啦,怎么样,是不是很开心呢!

示例:

12 4
0 0 0 70 80 90 1000 1000 1000 200 180 199

子任务五

题面中忘记写 $ k \ge 2 $ 了嘤嘤嘤。

容易发现只有 $ k = 2 $ 时有用,正确的做法是将点拆成两边表示成矩形面积的形式,这样有决策单调性。

咦这个做法怎么有三个错误做法套在一起还加了卡时?这一看就卡不掉嘛。

容易发现第一个随机两个产生贡献就是来搞笑的,有用的只有后面两个做法。

后面的两个做法实际上是套在一起的,你只需要保证最优解的两个区间一定不在 $ 1 $ 中最大的若干个即可。

这就非常容易啦!我们只要硬点最优解是选择第 $ n - 1 $ 个区间和第 $ n $ 个区间,然后在前面安排 $ 99990 $ 个区间理性愉悦一下就好啦!

#include<bits/stdc++.h>
using namespace std;
const int N=100005,B=1e7,Q=1e8,R=Q-1,inf=1e9;
int n=100000,m=99990,l[N],r[N];
int main(){
    int i;
    for(i=1;i<=m;i++)l[i]=i,r[i]=i+R;
    l[n]=inf-Q;r[n]=inf;l[n-1]=inf-Q-1;r[n-1]=inf-1;
    for(i=m+1;i<=n-2;i++)l[i]=l[n]-B*(n-i),r[i]=l[n]+i;
    printf("%d\n",n);
    for(i=1;i<=n;i++)printf("%d %d\n",l[i],r[i]);
    return 0;
}

子任务六

老师,我的旋转卡壳就是这么写的!我觉得这份代码没有问题!

我们重新审视一下这样写旋转卡壳为什么会GG,容易证明对于一个凸包上的一个点来说,最远点在凸包上是决策单调的。那么这个做法的唯一问题就在于距离函数不一定是单峰的。

hack

如上图所示,我们只有恰好走到两端才能使得被困住的铁蹄继续前进,这种情况下上述算法显然是错误的。

这份代码好像写错了一点啊,如果j > n 本应该更新 ret[j - n] 的。

子任务七

分值这么小一定是送分点!

可以发现这份代码实际上就是将相同的数缩起来,并且实现也非常普通。

因此随便随一组只有区间加没有区间覆盖数据就可以过惹!这告诉我们出数据结构题数据不能在不同操作间均匀随机。

实现比较简单就不贴了。

子任务八

无论是观察代码还是观察题面都可以发现,只有最小生成树上的边有用!因此我们只要求平面欧几里得最小生成树就好啦!

可以发现这份代码是将点在 $ x $ 轴和 $ y $ 轴上分别投影,找到最近的若干个点并连边。

那么我们只要让两个必连的点连不上就好啦!

构造实现比较简单,代码略去。

思考:如何卡掉在更多条过原点的随机直线上投影的算法?

感谢@vfleaking提供该subtask的std。

UOJ NOI Round #3 Day1 题解

2018-07-13 13:50:00 By WuHongxun

鸽子固定器

from AprilGrimoire, 题解 by AprilGrimoire

这次的题目顺序真是十分抱歉QwQ A题可能是三道题中AC人数最少的了……

然而这题std才50行,放B和C显得不太合适哇QwQ

子任务一

$n$的范围只有$10$,所以随便怎么暴力都可以哇QwQ

时间复杂度:$\Omega(poly(n))$

期望得分:$5$

子任务二

容易发现,如果我们确定了选择的固定器大小的范围,那么一定会选择这些固定器中牢固度最大的至多$m$个。所以我们可以把固定器按大小排序,枚举选择的右端点,然后将左端点向左扫一遍。在扫的过程中,用一个小根堆来维护选择的固定器的牢固度。

时间复杂度:$O(n^2 log m)$

期望得分:$10$

子任务三

当$d_s=d_v=1$的时候,首先把鸽子固定器按照大小排序。设$f_{i,j}$表示在前$i$个固定器中选择$j$个,且必须选择第$j$个的价值的最大值。则 $$f_{i,1}=v_i$$ $$f_{i,j}=\max\limits_{1 \leq k < j}f_{k,j-1}-(s_i-s_k)+v_i\\=v_i-s_i+\max\limits_{1 \leq k < j}f_{k,j-1} + s_k$$ 只要记录前缀最大值进行DP,就可以在$O(nm)$的时间内解决子任务三。

时间复杂度:$O(nm)$

期望得分:$10$

结合子任务二的做法可以获得$20$分。

子任务四

考虑子任务二的一个优化:在扫描过程中,如果发现右端点被出堆了就终止扫描。这样做显然是对的,因为右端点被出堆后的方案可以通过简单地左移右端点来使答案变优,一定不是最优值。然而,对于构造的数据,这个优化可能并没有什么用:

200000 50 2 2
1 1
2 2
3 3
...

对于这样的数据,这个优化并没有什么用。然而对于随机数据,它还是跑得挺快的。让我们进行一波有理有据的分析:对于第$i$大的固定器,随机找另一个固定器,有大约$\frac{i}{n}$的概率找到一个比它大的固定器。也就是说,期望扫描$\frac{n * m}{i}$个固定器,它就会被出堆。对于所有固定器,扫描所需要的总期望时间是 $$\sum\limits_{i=1}^{n}\frac{n * m}{i} = O(nm\log{n})$$

时间复杂度:$O(nm\log{n})$

期望得分:$25$

结合前三个子任务的做法可以获得$45$分。

子任务五

假设以$i$为右端点向左扫描时,$j$号点始终没有被入堆,那么以$i+1$为右端点时,它肯定也不会被入堆。这启示我们大胆猜想:对于右端点来说,左端点有决策单调性!取区间上前m大的点可以用主席树在$O(\log n)$的时间内完成,再算上决策单调性二分的$O(\log n)$,我们就可以在$O(n\log^2n)$的时间内解决

.

.

.

$d_v \neq 2$的情况。为什么当$d_v = 2$时没有决策单调性呢?考虑这样的数据:

200000 50 2 2
1 5000
2 1
3 1
...
199999 1
200000 10000000

对于中间的大部分点,最优决策都是选连续的$m$个固定器。而对于最后一个点,最优策略是选择最后一个点,第一个点和中间任意48个点。非线性的东西往往能够破坏决策单调性。

这个做法实际上可以通过前五个子任务,因为小数据不太好卡,对于随机数据正确性又很高。

实际上冷静一下就能发现决策单调性是假的:如果复杂度和$m$无关,为啥$m$这么小呢?

时间复杂度:$O(n \log^2 n)$

期望得分:$70$

子任务六

考虑优化子任务四的做法。这个做法会被价值递增的数据给卡掉。那么,如果我们二分ST表来找下一个会被入堆的点呢?事实上,这个算法是能通过全部数据的。

证明:假设在以$i$为右端点向左扫描时$j$被入堆了,就记录有序对$(j, i)$。我们把有序对$(a, b)$分成两类:$v_b \geq v_a$的叫做第一类有序对,$v_b < v_a$的叫做第二类有序对。 1. 对于第一类有序对$(a, b)$,一个$b$最多对应$m$个$a$。(否则$b$会被出堆) 2. 对于第二类有序对$(a, b)$,一个$a$最多对应$m$个$b$。(否则在扫描到$a$的时候,堆里至少有$m$个比$a$大的数,也就是说,$a$不会被入堆)

入堆操作最多会被执行$O(nm)$次,每次需要$\log n$的时间来二分ST表和$\log m$的时间来入堆,因此,这个做法能够在$nm \log n$的时间内通过所有子任务。

时间复杂度:$O(nm \log n)$

期望得分:$100$

神奇的做法

在比赛时,发现了这样一种神奇的做法: 按照坚固度从小到大考虑所有固定器。 1. 如果当前固定器被选中了,那么选中的固定器集合一定是一个区间。(否则可以把当前固定器换掉来获得更优的答案。) 2. 如果当前固定器没被选中,我们可以把它删掉。

用链表维护剩下的固定器。包含当前最小固定器的区间最多只有$m$个,所以这个算法的复杂度是$O(nm)$的。

子任务六的两个优化

  1. 用链表维护当前可能被入堆的点集。如果在从右往左扫的过程中一个点没有被入堆,那么我们可以把它从点集里删掉,因为它以后也永远不会入堆。这样就能避免二分ST表,只有$O(nm \log m)$的复杂度。($\log m$是因为需要用堆维护当前被选的固定器。)
  2. 堆也不是必要的,因为每次可能入堆的点只会增加一个,所以可以线性维护当前被选中的点集。这样就能做到$O(nm)$。

To Do Tree

对于大多数OIer来说,这题应该是个大胆猜结论题。

算法零:构造

看过题的同学就知道,subtask3就是送分的,每星期只能肝一个ddl,搞什么都行嘛……只要输出格式没有问题,大家应该都能得到这$6$分。

算法一:搜索

直接枚举每星期肝的ddl集合搜索,期望得分$30$,可以通过subtask1。

结合算法零可以得到$36$分。

算法二:子集dp

设$dp_{S}$表示肝掉集合$S$中的所有ddl所需要的最少的时间,然后枚举下一次肝的集合转移即可。

时间复杂度$O(3^{n})$,期望得分$60$分,可以通过subtask1,subtask2。

结合算法零可以得到$66$分。

算法三:构造

这个题看起来不可做又看起来很可做,有哪些选手能证明一下自己的算法是最优的呢?

先说出题人Mike给出的一种构造算法和证明。

首先对把依赖关系翻转一下,对于任意一个任务$i$,执行$i$之前必须先完成$i$的所有子节点。这个问题的最优解把执行顺序反转一下就是原问题的最优解了。

直接说结论:每次选择最深的叶节点执行,若有多个则随意执行一个即可。

证明如下:

考虑答案的两个显然的下界,$t \geq max_{i \in T}(dep_{i})$,$t \geq \frac{n}{m}$。

显然前面那个是机器数较多的情况,后面那个是机器数较少的情况。

然后将节点按深度分两块,任取一个深度$\alpha$,有

$$t \geq \alpha - 1 + \frac{\sum_{i = \alpha}^{n}p_{i}}{m}$$

显然最早在时刻$\frac{\sum_{i = \alpha}^{n}p_{i}}{m}$时深度不小于$\alpha$的节点才能被处理完,此时至少会剩下一个深度为$\alpha - 1$的节点,至少还需要$\alpha - 1$时间才能完成,因此这是总用时的一个下界。(显然对于$\alpha = 1$时也成立,但上面的叙述有问题)

下面证明$t \geq max_{\alpha}(\alpha - 1 + \frac{\sum_{i = \alpha}^{n}p_{i}}{m})$是一个紧下界。

考虑最大值时$\alpha$取到的$\beta$,如果有多个则取最小的,则有

$$\forall d < \beta, \frac{\sum_{i=d}^{\beta - 1}p_{i}}{\beta - d} < m$$

上式显然成立,否则$\alpha$取$d$的函数值不比$\alpha$取$\beta$时小。

根据当前树的深度是否小于$\beta$,我们按时间序将算法分为前半部分和后半部分。

下面证明,假设深度不小于$\beta$的节点全部被完成后,剩下的节点只需要$\beta - 1$时间就能完成。

首先归纳证明,算法执行过程中,任意时刻树中深度最大的任意$k$层节点,每层的节点均值都小于$m$。

形式化的表述是,设树的深度为$h$,则有$\frac{\sum_{i = d}^{h}p_{i}}{h - d + 1} < m$。$(1)$

也就是和上面一样的形式。

采用归纳法,反证,假设经过了$1$时间后深度至少为$d$的部分不满足条件,取最大的$d$。

根据假设,显然有$p_{d} \geq m$,否则深度至少为$d + 1$的部分也满足条件,与$d$最大矛盾。

考虑此时深度为$d$的这些点构成的子树,显然每个子树至少有一个叶节点,因此当前深度不小于$d$的叶节点有至少$m$个。

删掉一个节点后,深度不小于$d$的节点个数单调不减,因此上一次深度不小于$d$的叶节点个数不小于$m$,根据算法流程可知上次删掉的节点深度至少为$d$。

则上次深度不小于$d$的节点有$\sum_{i = d}^{h}p_{i} + m$个,$h$是当前树的深度,$p_{i}$是当前树中深度为$i$的节点个数。

$$\sum_{i = d}^{h}p_{i} \geq m(h - d + 1)$$

$$\sum_{i = d}^{h}p_{i} + m \geq m(h - d + 2)$$

即上次深度不小于$d$的部分也不满足条件,与归纳条件矛盾,因此命题$(1)$得证。

由命题$(1)$可得,算法执行后半部分的任意时刻,深度最大的节点个数不超过$m$,因此只需要树的深度时间就能够执行完所有深度小于$\beta$的节点。

下面证明删掉深度不小于$\beta$的节点只需要$\lceil \frac{\sum_{i = \beta}^{n}p_{i}}{m} \rceil$时间。

由$\beta$的定义,可以得到如下结论:

$$\forall d \geq \beta, \frac{\sum_{i = \beta}^{d}p_{i}}{d - \beta + 1} \geq m$$

否则$\alpha$取$d$的函数值比$\alpha$取$\beta$时大。

下面证明,算法执行前半部分的任意时刻,设当前树的高度为$h$,深度为$i$的节点有$p_{i}$个,则对于任意的$\beta \leq d < h$,满足上述条件

$$\forall \beta \leq d < h \frac{\sum_{i = \beta}^{d}p_{i}}{d - \beta + 1} \geq m(2)$$

使用归纳法,反证,假设经过$1$时间后深度为$\beta$到$d$的部分不满足条件,取满足条件最小的$d$。

这个单位时间内显然删掉了至少一个深度为$d$的节点。(上一时刻时这一部分还满足条件)

这说明之前深度大于$d$的部分叶节点不足$m$个。

若$d \geq h$,则当前的$d$不在定义域中,自然不影响成立性。

若$d < h$,则此时这一时刻内一定删掉了所有深度为$h + 1$的点。

由于深度大于$d$的叶节点个数随时间单调不减,且上一时刻深度大于$d$叶节点个数不足$m$,所以只需要$h - d$时间就能将所有深度大于$d$的部分删去,因此在上一时刻有

$$\sum_{i = \beta}^{d}p_{i} < (d - \beta + 1)m + D$$

其中$D$为删掉的深度为$d$的节点个数。

深度不少于$d + 1$的叶节点至少有$p_{d + 1}$个,因此$D \leq m - p_{d + 1}$。

因此得到

$$\sum_{i = \beta}^{d + 1}p_{i} < (d - \beta + 2)m$$

又$d < h$,因此上一时刻取$d = d + 1$时条件不满足,与归纳基础矛盾,因此命题$(2)$得证。

因此当深度大于$\beta$时恒有$p_{\beta} \geq m$,即深度不小于$\beta$的叶节点个数$\geq m$,每次都能取满$m$个。在深度为$\beta$处至多一次取不满$m$,因此前半部分可以在$\lceil \frac{\sum_{i = \beta}^{n}p_{i}}{m} \rceil$内完成。

综上,算法正确性和用时下界都得到了证明。

这个算法可以做到$O(n)$的,想必大家都会,也不是重点,于是就没设分。

按深度贪心也是正确的,证明主要思路采用调整法;按大小贪心也是正确的,证明主要思路采用反证法。证明繁杂赛后我在uoj博客发一下证明。

配对树

from C_SUNSHINE, 题解 by C_SUNSHINE

子任务 1

我们可以暴力枚举ddl区间,然后在树上做树形DP来计算最小匹配的大小,如何DP呢?

令 $f_{i,j}$ 表示 $i$ 的子树内还有 $j$ 个点没匹配的匹配大小,然后计算转移边需要被覆盖几次。这个想法明显太傻了,我们不可能让子树内的点拉到子树外面配对的,如果存在两个点 $x, y$ 他们在子树内都没有配对,那么假设他们分别和 $x', y'$ 配对,显然 改为 $x, y$ 配对 $x', y'$ 配对更优,所以 $j$ 只能是 $0$ 或1。

接着发现其实 $j$ 的奇偶性和子树内ddl数目的奇偶性相同,于是直接dp即可。

时间复杂度 $O(m^2n)$。

子任务 2

我们接着观察,对于一个确定的ddl区间,一条树边被匹配包含了当且仅当把它删去后树被分成两个包含奇数个ddl的块。若我们令 $1$ 为根做dfs,则一个非根点父向边被包含当且仅当其子树内有奇数个ddl。

我们可以换一种方式思考,计算一条树边被多少个偶区间覆盖。

枚举一条树边,把它子树内的ddl全部在序列上标为 $1$ 其余标为 $0$,来把序列转成 $01$ 串,于是问题变成了统计 $01$ 串中包含偶数个 $1$ 的子串数目。

对 $01$ 串做前缀和得到 $s_i$,则一个区间 $[l,r]$ 要被统计当且仅当 $s_r-s_{l-1} \equiv 1 \pmod 2$ 由于 $l-1 \equiv r \pmod 2$,我们可以对 $s_i(0 \leq i \leq m)$ 按照下标奇偶性分别维护,维护对 $i \mod 2 = k = 0$ 或 $1$ 分别计算 $s_i$ 中奇数的数目 $cnt_{k,1}$ 和偶数的数目 $cnt_{k,0}$。那么包含这条树边的区间数目就是 $cnt_{0,0} \cdot cnt_{0,1} + cnt_{1,0} \cdot cnt_{1,1}$。

把序列转化成 $01$ 串需要 $n+m$ 的时间,统计 $cnt$ 需要 $O(m)$ 的时间,于是时间复杂度为 $O(n^2+nm)$。

子任务 3

这个直接把不超过 $100$ 个点的虚树建出来之后暴力即可。

子任务 4

我们可以考虑使用线段树来维护序列转化成的 $01$ 串,可以发现,我们只需要在线段树区间上维护区间内的 $cnt_{k,0/1}$,通过左半边内 $1$ 的数目来决定是否对右边进行反转,就可以 $O(1)$ 时间合并左右区间,最终需要的 $cnt$ 的值会统计在根节点上。

既然单次修改 $01$ 序列是 $O(\log m)$ 的,我们可以枚举每条边,然后只加入其子树,总修改次数为 $O(n^2)$,于是复杂度为 $O(n^2 \log m)$。

子任务 5

这条件其实没什么特别的用处,只是让点的分步均匀一些。

子任务 6

树是随机的,我们依旧暴力枚举树边然后只添加子树,可以发现每个点会被添加恰好深度次,而深度的期望是 $O(\log n)$ 的,所以总修改次数的期望也是 $O(m \log n)$ 的,总复杂度就是 $O(m \log n \log m)$ 的。

子任务 7

在本来的做法中,我们对子树做完后,清空线段树再吧子树内的 ddl 重新加入,可以发现这个过程中有重复计算。考虑对于每个点 $x$ 我们在 dfs 完其最后一个孩子之后,不清空 dfs 时的修改,而是把其他孩子子树内的 ddl 直接补上,令 $x$ 的最后一个孩子为 $son_x$, $x$ 到 $son_x$ 的边称为特殊边,可以发现,一个 ddl 被添加次数为其到跟的路径上非特殊边的数目。

到这里其实算法已经很显然了,对树轻重链剖分,$son_x$ 就是 $x$ 的重孩子,一个 ddl 被添加的次数就是其到根的路径上轻边的数目是 $O(\log n)$ 的,采用线段树维护的话复杂度就是 $O(m \log n \log m)$,这个算法可以通过本题。提交记录点这里

因为NOI之前信心赛大家开心就好,所以两个 $\log$ 是可以通过的。

这题我本来出出来准备当个前两题的难度的,但不知道哪个管理员就把它挂到 C 题上了,我给他题解的时候还把这段话删了,所以两个 $\log$ 是可以通过的。

想到用线段树维护后,本题有个较为直接的做法即采用线段树合并,每个点的线段树可以看成其所有子树并起来再插入其上的 ddl,我们知道 $m$ 个只有一个元素的线段树合并的复杂度为 $m \log m$,所以直接采用线段树合并可以做到 $O(n + m \log m)$ 的复杂度,只不过空间是 $\Theta(m \log m)$ 的。提交记录点这里 不过采用 Splay 做合并的话,空间可以做到 $O(n)$。

你要问我为啥就是个 Splay 合并却写这么长题解,我只能说……既然管理员钦点了,得装的像个 C 题的样子(逃

UOJ NOI Round #3

2018-07-11 20:48:43 By WuHongxun

转眼间又是一年NOI了,为了帮大家备战NOI,延续UOJ的传统保留项目,UOJ NOI Round #3 将在7月12号到7月14号举行!

因为管理员比较鸽时间比较紧迫,公告发的有些迟了,还请参加NOI的大家奔走相告。

这次的UNR将以鸽子作为主题!

比赛时间

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

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

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

出题人

这次拯救UNR于危急存亡之中的出题人有:

FoolMike,AprilGrimoire, whzzt,C_SUNSHINE, matthew99,ztr

比赛奖项

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

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

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

UPD:比赛结束

恭喜比赛的前五名:

1.wangxiuhan

2.fjzzq2002

3.kczno1

4.tqyaaaaang

5.orbitingflea

抱枕条件是

echo "Day1和Day2都有分的选手中两天分差最小的选手,如果 有并列取排名最高,如果还有并列取罚时最小" | md5
bbd3d0574b7ec5dce3b1d4d8aff97e38

恭喜duweihua 以Day1获得$111$分,Day2获得$112$分,分差仅为$1$的绝对优势,击败了分差为$2$的YMDragonsupy夺得抱枕!

同时也祝贺我们的总分前三名wangxiuhanfjzzq2002kczno1获得抱枕!

UOJ Round #17 题解

2018-03-18 22:58:56 By WuHongxun

滑稽树上滑稽果

By jiry_2,数据、题解By WuHongxun

写题解之前,我们先来回顾一下上次比赛的A题题解:

这道题可能并没有那么有趣..本来有一道很棒的 A,但是比赛前突然被发现是个假题..然后就临时出了这么个题..感觉送送分还是不错的。

emm 懂我意思吧?

如果看到题面里大大的滑稽还没有察觉事情不太对...请允悲...

子任务一

既然 $n$ 那么小,我们直接枚举每个点的父亲!

时间复杂度 $O(n^n)$。

子任务二

保证是一条链了,我们就只要枚举排列了!

冷静一下马上就会意识到,答案一定是一条链。这个部分分肯定是出题人用来提示大家冷静一下的!

时间复杂度 $O(n!)$。

子任务三

保证滑稽值的字典序最小?那就等于是每次枚举一个和当前的滑稽值and起来最小的值,然后把他加到后面。

时间复杂度 $O(n^2)$。

子任务四

把相同的位拿出来,这些位要么一定是每次没贡献,要么一定是每次有贡献。

那么剩下的位,每次一定会减去一位,从而最多只会用$O(log a)$次就减到0了,每次暴力找最小的就好了。

时间复杂度 $O(n log a)$。

子任务五

chat

出题人给了一个部分分是这个贪心的过程,我们睿(ruo)智(zhi)的分析一下,这个做法一定是错的!

事实上的确是希望考验大家独立思考、小心求证的能力。

我们一样先把每个数都一样的那些位拿出来,剩下的位我们等于是希望尽快把他们变成$0$。

这可以用一个dp来实现,$f[S]$表示$S$集合内的位为1的时候,想要变成$0$还需要多少代价。

dp转移就是每次枚举一个$a[i]$,$f[S] = min(f[S], f[S \& a[i]] + (S \& a[i]))$。

时间复杂度 $O(na)$。

子任务六

我们可以每次不枚举一个$a[i]$,而是枚举一个子集$T$,强制把这个子集$T$变成$0$。

现在的问题就是,判断有没有一个数他和$T$,and起来是0。

这非常好做,只需要每次$cnt[i] |= cnt[i | (2^j)]$,从每个比$i$多一个$0$的位置转移就好了。

事实上dp的时候,我们可以用贪心得到的解来进行剪枝,所以是不卡常数的。

时间复杂度 $O(a^{log_2 3}) = O(a^{1.58})$

滑稽树下你和我

By picks,数据、题解By Scape

算法一

直接输出两起始点距离即可。

期望得分$5$分。

算法二

考虑"保证存在最优方案,在任意时刻至少有一端点位于树的某结点上"这个性质。

我们先考虑二分答案,显然可以设计一个dp即为$f[i][j]$表示是否存在某种方案使得最终一个点在点$i$,一个点在点$j$。直接按照定义转移即可,时间复杂度$O(n^2logn)$

期望得分$15$分。结合算法一可获得$20$分。

算法三

同样我们先考虑二分答案,看答案是否能$\le v$。

我们考虑一条这样的性质。对于两个状态,两个点所在的边都相同,并且两个状态的两点间距离是$\le v$的,那么这两个状态是两两可达的。因为我们考虑是把其中某一条直线摆平,那么另外一条直线肯定是单调的。

那么我们就可以依此设计状态,令$f[i][j]$表示是否存在某种方案使得一个点在点$i$上,一个点在边$j$上距离点$i$最近的那个点上。那么$f[i][j]$为$1$当且仅当点$i$到边$j$的最短距离$\le v$且存在某个$f[k][x]$为$1$,其中$k$是$j$的某个端点,$x$是某个以$i$为端点的边,或存在某个$f[t][j]$为$1$,其中$t$与$i$有边相连。直接BFS转移就可以了。

因为我写完这个东西已经是早上凌晨三点了,所以我当时就认为这个算法是$O(n^3logn)$的,这就是$n\le 200$这个Subtask的由来。(笑

我们仔细分析一下,$f[i][j]$的转移复杂度显然是$O(i的度数)$的。那么加起来的转移复杂度总和显然是$O(n^2)$的,所以整个算法复杂度是$O(n^2logn)$的,你也可以选择不二分答案而是类似最短路那样去做,但还是要sort或者用堆维护,复杂度不变。

期望得分$100$分。

滑稽树前做游戏

By jiry_2

算法一

如果你做过 这个题,你就肯定知道菊花树的情况下答案就是 $\frac{1}{2} + \frac{n-1}{n}$。用快速幂求个逆元就可以了。

期望得分 $10$ 分。

算法二

$n = 4$ 的本质不同的图只有 $11$ 种,如果你有高超的手算水平,相信你可以算出所有 $n \leq 4$ 的图的答案,然后打表。

结合算法一期望得分 $30$ 分。

算法三

这题据我所知有很多种复杂度较高的 DP 算法可以通过 $n \leq 10$ 的数据,但是都没有标算简洁优美,这儿就不进行介绍了。

和大部分期望题一样,令 $g(t) = Pr[f(x) \leq t]$,那么答案显然就是 $2 - \int_{0}^2 g(t) \text{d}t$,因此我们只需要求出函数 $g(t)$,并做一次积分即可。

我们把题目的输入看做一张 $n$ 个点 $m$ 条边的无向图 $G$,那么 $g(t)$ 是一个关于 $G$ 的函数。

定义函数 $h(G,y,t)$,表示在无向图 $G$ 中,所有顶点权值的最大值小于等于 $y$,答案小于等于 $t$ 的概率,并且我们限制这个函数的定义域为 $\frac{t}{2} \leq y \leq \min(1,t)$。现在我们来考虑如何计算得到 $h(G,y,t)$:

  1. 如果所有点的权值都小于等于 $\frac{t}{2}$,那么必定满足顶点权值最大值小于等于 $y$,因此此时的概率为 $(\frac{t}{2})^n$(令 $G$ 的顶点个数为 $n$)。

  2. 如果至少有一个点的权值大于 $\frac{t}{2}$,我们枚举权值最大的点 $i$,设它的权值为 $w$。考虑所有与 $i$ 相邻的点 $j$,所有 $j$ 的出边中,权值最大的就是边 $(i,j)$ 了,因此 $j$ 的权值应当小于等于 $t-w$(又 $w>\frac{t}{2}$,因此不会和其他限制导出矛盾)。我们删去第 $i$ 个点和所有相邻点,得到了图 $G_i$,那么 $G_i$ 中的点应当满足点权小于等于 $w$ 且答案不超过 $t$,即概率为 $h(G_i,w,t)$。

因此,我们得到了关于函数 $h(G,y,t)$ 的递推式:

$$ h(G,y,t) = (\frac{t}{2})^n + \sum_{i=1}^n \int_{\frac{t}{2}}^{y}h(G_i,w,t)\text{d}w $$

显然有 $h(G,y,t)$ 是关于 $y$ 和 $t$ 的 $n$ 次其次多项式,于是我们对 $G$ 进行状压,可以在 $O(2^nn^3)$ 得到 $h(G_0,y,t)$,其中 $G_0$ 为输入的图。那么这时 $g(t) = h(G_0,\min(1,t),t)$,直接积分就可得到答案。

时间复杂度 $O(2^n \times n^3)$,结合算法一可以得到 $70$ 分。

算法四

怎么在算法三种作优化呢,我们发现算法三的复杂度的一个上界是子图个数,但是很多时候又不慢,比如在图是一个团的时候,$G_i$ 均为空,会计算的子图只有 $O(n)$ 个。

那是不是算法三可以直接跑过 $25$ 呢,遗憾的是并不是。不难发现在输入是一棵菊花的时候,算法三就会跑慢 $2^n \times n^3$。但是其中大部分的子图都是不连通的。

不难发现对于一张不连通的图 $G$,它的联通块分别为 $G_1,...,G_m$,那么 $h(G,y,t) = \prod_{i=1}^m h(G_i,y,t)$,因此对于不连通的图,我们可以直接拆分成更小的子问题,而不是和算法三一样递归的搜索。

时间复杂度未知,可以得到满分。

虽然我不会分析复杂度,但是实际上对于所有我能构造的 $n=30$ 的图,这个算法都可以在 $0.2s$ 内出解。于是冷静了一下就把 $n$ 开到 $25$ 出了出来。

这一题目前一共有 $157$ 个测试数据,std 一共只需要跑 $160ms$,所以应该是不存在卡常数的可能性的。

UOJ Round #17

2018-03-17 22:15:32 By WuHongxun

非常抱歉由于这次准备比较仓促,现在才发公告,希望大家帮忙互相转告,谢谢

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

Q & A

Q: 为什么之前咕了呢?

A: 因为之前一直没有B题,直到Picks贡献了一个idea拯救世界!

Q: 为什么现在才发公告呢?

A: 因为发了公告就不能咕咕咕了。因为之前大家还在努力出题,idea验证是否合理也需要时间。

Q: 为什么这场UR办的这么滑稽呢?

A: emm这次题目简单,风格清新,是您涨Rating的最佳选择!

比赛信息

本场比赛将以

滑稽

作为主题。

出题人 : jiry_2Picksjiry_2

本场成绩将计入Rating。

参加本场比赛有机会获得uoj抱枕!49850781c2939981efaa3d3dd5202cc7是获奖条件的md5码。

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

比赛结束啦,恭喜前5名的选手:

  1. wangxiuhan

  2. yfzcsc

  3. dreamoon

  4. djq_cpp

  5. F_Darcy

 echo "三道题都得分,并且三题得分倒数的平均数和平均数的倒数的差最大的选手"| md5
49850781c2939981efaa3d3dd5202cc7

恭喜dreamoondjq_cpp获得uoj抱枕!(开销 x2...555)

非常抱歉,我们鸽了

2018-03-10 11:06:46 By WuHongxun

非常抱歉,这次的ur需要推迟了。

事情要从在上一场Goodbye Round结束之后说起。我们惊讶的发现,手里有了两道没有选在Goodbye里的题目,这样一来,只要再出一道题,就可以办出一场ur啦!

于是大家就抱着飞龙骑脸的自信,加了一场半个月之后的比赛。

我首先需要承认,这半个月里,我因为种种个人的私事,没有把精力投入到出题上来。虽然现役管理员Scape这半个月一来一直在努力的思考,想要出一道好题,但是结果也完全不够理想。

结果到了比赛前的最后几天,这道题目的空缺还是没有办法填上,无奈之下只好延迟ur了。

很对不起腾出时间来参加ur,信任我们的同学,这次的ur只能推迟到有合适的题目为止了。

当然如果大家有好的idea,也请多多投题。

Goodbye Dingyou题解

2018-02-18 18:10:43 By WuHongxun

祝大家新年快乐,场场ak!

新年的XOR

出题人 jiry_2

数据和题解 jiry_2

这道题可能并没有那么有趣..本来有一道很棒的 A,但是比赛前突然被发现是个假题..然后就临时出了这么个题..感觉送送分还是不错的。

算法一

既然 $n$ 那么小,相信 $L$ 和 $R$ 肯定也不是很大,直接枚举 $L$ 和 $R$ 然后暴力算异或和!

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

算法二

暴力算异或和太蠢了,直接预处理个前缀异或和 $w_n$ 然后 $O(1)$ 用 $w_{l-1} \oplus w_{r}$ 算,岂不美哉。

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

算法三

好像预处理完前缀异或和之后左端点都不用枚举了,直接枚举右端点然后查表看看有没有能用的左端点就好了。

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

算法四

好像所有合法的区间左端点都很小。那么就在 $[n-100,n+100]$ 枚举右端点,然后在 $[1,100]$ 枚举左端点试试。

怎么算前缀异或和呢?不难发现 $2i \oplus (2i+1) = 1$,所以如果 $n$ 为奇数,那么 $w_n$ 就是 $\frac{n+1}{2} \mod 2$,如果 $n$ 为偶数,那么 $w_n$ 就是 $n + (\frac{n+1}{2} \mod 2)$。

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

算法五

诶好像算法四直接 A 掉了。不难发现 $w_n \oplus n \in [0,1]$,而 $w_0=0,w_1=1$,所以只要取 $l \in [1,2]$ 来微调一下个位就可以啦。

因为要求区间的两端都是正数以及区间长度大于 $1$,所以对于 $n=0,1,2$ 要特判一下。

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

新年的叶子

出题人 liu_runda

数据和题解 Scape

算法一

我们先来考虑一下有关直径的一些性质。

我们这里定义直径的长度是直径上边的条数。

显然一棵树可能会有多条直径,但是这些直径的中点显然应该是重合(对于直径长度是偶数)或者相邻(对于直径长度是奇数)。

否则的话我们可以从直径的一个端点出发,走到直径的中点,再走到另一条直径的中点后走到另直径的一个端点,这样可以得到一个更长的直径。

所以我们可以找到任意一条直径的中点,然后把所有叶子按照它位于这个中点的哪个儿子的子树中分成若干个集合,并且以该中点为根计算出每个叶子的深度。

令叶子的深度最大值是$Max$。

对于直径长度为偶数的情况,直径会变小 当且仅当 所有没有被染黑的且深度为$Max$的叶子 都在同一个集合里。

对于直径长度为奇数的情况,直径会变小 当且仅当 深度为$Max$的叶子都被染黑 或者 深度为$Max-1$的叶子都被染黑。那么我们把深度为$Max-1$的叶子全部放在同一个集合里,奇数的情况就变成了和偶数一样。我们可以一起解决。

接下来我们就要考虑这样一个问题,我们有若干个集合,每个集合里都有若干个叶子。我们每次会随机染黑一个叶子,问期望多久后只剩下一个集合里的叶子不是全黑。

令叶子总数是$m$。

我们可以先转化一下,把“每次随机染黑一个叶子(可能会重复染黑)”改成“每次随机染黑一个还没有被染黑的叶子”。这样转化后,假设还剩下$k$个叶子没有被染黑,那么要染黑一个还没有被染黑的叶子的代价就是$\frac{m}{k}$。

接下来我们只要暴力枚举删除叶子的顺序,就可以计算了。

时间复杂度$O(n!)$。期望得到$12$分。

算法二

我们考虑枚举哪个集合最终剩下了。

令$f[i][j]$表示当且集合还剩下$i$个,其他集合还剩下$j$个时期望的删除时间。直接按照定义转移就可以了。

时间复杂度$O(n^2)$。期望得到$30$分。

算法三

我们考虑枚举哪个集合最终剩下了,设当前集合大小为$k$。

设所有集合大小的和为$n$。

我们枚举当其他所有集合都染黑时,当前集合还剩下$i$个没有被染黑,那么这样的情况对答案的贡献为

$$\frac{\binom{k}{i}\times \binom{n-i-1}{n-k-1}\times \binom{n-k}{1}\times(k-i)!\times(n-k-1)!\times (i)!}{n!}\times (\sum_{j=i+1}^{n}\frac{m}{j})$$

线性预处理阶乘,阶乘逆元与逆元的前缀和就可以做到$O(n)$的时间复杂度。

算法四

from WuHongxun

什么,那么上面复杂的贡献你不知道怎么回事?不要急,这个题之所以在B题而不是C题,就是因为有算法四。

心里有数

考虑我们每次枚举一个集合$x$,然后不管它,计算剩下的集合被全部染黑所需要的期望时间,然后把这些时间加起来。

这个期望时间当然非常好算,如果一共有$n$个叶子,我们关心的有$m$个叶子,那么我们第一步需要期望$\frac{n}{m}$步染黑一个关心的叶子,显然答案就是$\sum_{i=1}^m \frac{n}{i}$,只要预处理$h_n = \sum_i \frac{1}{i}$就可以$O(1)$计算了。

算出来这个有什么用呢?

考虑任何一个方案里我们染黑到所有集合都变黑了为止,它对答案的贡献是多少呢?如果$x$是这个方案里最后被染黑的集合,那么是倒数第二个被染黑的时间,反之则是最后一个集合被染黑的时间,假设有$L$个集合,那么全部染黑被算了恰好$L - 1$次。

所以只要每次枚举一个集合,算剩下集合全部染黑的期望时间加到答案中,最后在答案里扣掉$L - 1$倍把所有集合全部染黑的期望时间,就可以啦!

是不是非常简单呢?

新年的五维几何

出题人 ftiasch

数据和题解 WrongAnswer

算法一

当 $n=1$ 时,满足约束的条件是 $x_1-x_1\ge a_{1,1}$ 即 $a_{1,1}\le 0$,因此当 $a_{1,1}\le 0$ 时输出 $1$,当 $a_{1,1} > 0$ 时输出 $0$。

可以通过子任务1,期望得分5分。

算法二

注意到如果有一个 $a_{i,i} > 0$,答案一定是 $0$,否则不用考虑 $a_{i,i}$ 的约束。以下算法均假设所有 $a_{i,i}\le 0$。

当 $n=2$ 且 $l_1=r_1$ 时,恒有 $x_1=l_1$,实际上只有 $x_2$ 一个变量。

若 $l_2=r_2$,仿照算法一判断四个约束是否同时满足即可,同时满足则输出 $1$,否则输出 $0$。

若 $l_2 < r_2$,则约束 $x_1-x_2\ge a_{1,2}$ 等价于 $x_2\le l_1-a_{1,2}$,约束 $x_2-x_1\ge a_{2,1}$ 等价于 $x_2\ge l_1+a_{2,1}$,求出两个约束和 $l_2\le x_2\le r_2$ 的交集长度,除以 $r_2-l_2$ 就是答案。

结合上述算法,可以通过子任务1,2,期望得分15分。

算法三

当 $n=2$ 时,如果 $l_2=r_2$,交换两个变量即可用算法二解决,故以下假设 $l_1 < r_1$ 且 $l_2 < r_2$。

用 $x,y$ 表示变量 $x_1,x_2$,则在平面直角坐标系 $xOy$ 中,变量的定义域是一个矩形 $l_1\le x\le r_1$,$l_2\le y\le r_2$,而约束的区域是该矩形和半平面 $x-y\ge a_{1,2}$ 及 $y-x\ge a_{2,1}$ 的交集。

考虑只有一个约束 $x-y\ge a_{1,2}$,则约束对应的区域为矩形位于直线 $y=x-a_{1,2}$ 下方的部分。当直线不穿过矩形时,答案为 $0$ 或 $1$,否则该区域可能是直角三角形、直角梯形或者矩形去掉一个直角三角形,根据点 $(l_1,r_1),(l_2,r_2)$ 在直线的上、下方分四类情况讨论计算区域面积即可,答案为该区域面积除以矩形面积 $(r_1-l_1)(r_2-l_2)$。

当有两个约束 $x-y\ge a_{1,2}$ 和 $y-x\ge a_{2,1}$ 时,将 $y-x\ge a_{2,1}$ 变形为 $x-y\le-a_{2,1}$,可得答案为约束 $x-y\ge a_{1,2}$ 的答案与约束 $x-y\ge-a_{2,1}$ 的答案之差(如果差为负数,答案为 $0$)。

结合上述算法,可以通过子任务1,2,3,4,期望得分50分。如果你只考虑了 $a_{1,2}$ 一个约束,则只能得到35分。

算法四

对于当 $j\ne i+1$ 时 $a_{i,j}=-10$ 的子任务,只需考虑相邻变量的约束。

设 $f_i(x)$ 为变量 $x_i,x_{i+1},\cdots,x_n$ 满足约束且 $x_i\le x$ 的概率,显然 $f_{n+1}(x)=1$。

当 $x < l_i$ 时,有 $f_i(x)=0$;当 $x > r_i$ 时,有 $f_i(x)=f_i(r_i)$。

否则,因为 $x_i-x_{i+1}\ge a_{i,i+1}$ 等价于 $x_{i+1}\le x_i-a_{i,i+1}$,所以当 $x_i=x$($x\in[l_i,r_i]$)时,$x_i,x_{i+1},\cdots,x_n$ 满足约束的概率为 $f_{i+1}(x-a_{i,i+1})$,于是,当 $l_i=r_i$ 时,有$$f_i(x)=f_{i+1}(l_i-a_{i,i+1})$$

当 $l_i < r_i$ 时,有$$f_i(x)={1\over r_i-l_i}\int_{l_i}^xf_{i+1}(y-a_{i,i+1})\mathrm{d}y$$

注意到 $f_i(x)$ 是一个段数 $O(n)$ 的分段多项式,维护每个分段多项式,用定积分进行转移即可。

结合上述算法,可以通过子任务1,2,3,4,7,期望得分70分。

算法五

注意到 $l_i,r_i,a_{i,j}$ 都是整数且 $l_i,r_i$ 范围很小,不妨枚举每个 $x_i$ 的整数部分。

当 $l_i=r_i$ 时,$x_i$ 是确定的,无需枚举;否则,记 $x_i=p_i+q_i$,其中 $p_i$ 在 $[l_i,r_i)$ 的整数中均匀随机,$q_i$ 在 $[0,1)$ 的实数中均匀随机,我们枚举每个 $p_i$,计算随机生成 $q_i$ 有多少的概率满足所有约束,每组 $p_i$ 下概率的平均值就是答案。

因为 $x_i-x_j\ge a_{i,j}$ 等价于 $q_i-q_j\ge a_{i,j}+p_j-p_i$:

  1. 当 $a_{i,j}+p_j-p_i\le -1$ 时,约束总能满足,不考虑该约束;
  2. 当 $a_{i,j}+p_j-p_i\ge 1$ 时,约束不可能满足,该情况的概率直接返回 $0$;
  3. 当 $a_{i,j}+p_j-p_i=0$ 时,约束等价于 $q_i\ge q_j$。

现在只要考虑若干个形如 $q_i\ge q_j$ 的约束同时被满足的条件。

注意到如果所有的 $q_i$ 均匀随机生成,那么有两个 $q_i$ 相等的概率为 $0$,$q_i$ 可能出现的 $n!$ 大小顺序是等概率的,每种的概率均为 ${1\over n!}$。因此对每个 $l_i < r_i$ 的变量建一个点 $i$,每个约束 $q_i\ge q_j$ 连一条边 $j\rightarrow i$,设该图的拓扑序有 $T$ 个,则满足所有约束的概率为 ${T\over n!}$。

直接枚举排列或者状压DP均可计算拓扑序个数。

时间复杂度 $O((r_i-l_i)^nn!\cdot n)$ 或 $O([2(r_i-l_i)]^nn)$,期望得分100分。

新年的代码

出题人 Glaceon08, worse

数据 worse

题解 WuHongxun

算法一

$n \leq 10$?

当然是$O(3^n)$状压爆搜啦!

算法二

我们大力猜结论!

evil

每个位置只会不连续的变化两段!

dp就只需要$f_{i,j,k}$表示前$i$位处理完了,第$i$位先变成$j$让我们来继续操作后面的位,然后操作完后面的位之后我们把第$i$位从$S_i$变成了$k$,我们再回来用前面的位把它变成$T_i$的最小步数。

交一发,100分。 bomb

其实是有道理的啦...

myy(matthew99)丢给了我一个他猜完结论后的这题代码,虽然我没看懂https://paste.ubuntu.com/p/6P7XZ6zT2W/

算法三

我们任意给$R,G,B$编号$0, 1, 2$,考虑我们每次操作,其实每次都是给相邻两位在模$3$意义下,一个$+1$,一个$-1$。(当然反过来不是每个$+1$,$-1$都能对应到我们的操作)

我们定义$sa_i = sa_{i - 1} + a_i, sb_i = sb_{i - 1} + b_i$,然后按照$sa_i = sb_i$的每个位置分段,那么每段在$mod 3$意义下相等。

首先长度为$n$的每个段,至少需要$n - 1$步操作才能完成,因为每个中间位置我们都需要把它左边和右边移成一样。

事实上我们可以构造出一个只需要$n$步的方案。考虑每次都至少复原一个字母,如果$S$开头两个是$GG$,那么无论$T$开头是$G$(第一个字母直接一样了),还是开头是$R,B$(一步操作之后可以复原第一个字母),显然都可以递归下去。

否则不妨假设$S$开头是$RG$,那么如果$T$第一个字母是$B$,那么一步操作即可。如果$T$的第一个字母是$R$可以直接递归下去。

于是剩下的唯一问题就是$T$的第一个字母是$G$的情况了,如果是$GR$,那么两步复原两个字母递归下去即可。

如果是$GG$,我们考虑处理剩下的位的时候把第二位变成$B$,然后前两位就是$RB$,最后一步变成$GG$

如果是$GB$,我们处理剩下的位的时候把第二位变成$R$,前两位就是$RR$,最后一步变成$GB$

这样我们就构造出了一段只需要$n$步的方案。

excite

我们还需要证明两端之间是独立的,在上一个结论的基础上,这也不难。我们考虑每次在两端之间操作一下,相当于合并了两端。

假如本来两端长度是$a, b$,需要的次数在$[a + b - 2, a + b]$之中,那么现在长度是$a + b$,至少需要$1 + a + b - 1 = a + b$次,不会变成更优。

合并多段的情况一样可以这么证明。

接下来只需要检查$n - 1$步是否合法了,因为这里每个位置都不会被操作超过两次,我们可以这么dp:

$f_{i,a,b}$表示dp完了前$i$个位置,在操作$i..n$位的过程中,需要第$i$个位置从$a$变成$b$的最小步数。

对于长度为$n$的段,如果这么dp之后存在一个答案为$n - 1$的解,那么就加上$n - 1$,否则加上$n$即可。

这样就可以有理有据的获得100分啦。

good

新年的投票

出题人 WuHongxun

数据和题解 WuHongxun

算法一

老师,我会爆搜!

先假设所有人不带标号,然后所有决策一共有$O(2^n)$种,爆搜每种情况,暴力取最好的情况,就会发现自己得了22分!

这是什么道理呢,如果所有人不带标号,那么我们可以这么构造:

如果多数掌握在$1$的人手里,所有人都应该投看到的奇偶性取反。

如果多数掌握在$0$的人手里,所有人都应该投看到的奇偶性。

唯一的问题是如果看到的$0$和$1$一样多怎么投,这时候可以按照多数是0投。

这样一来只有$\frac{n+1}{2}$的时候会导致错误,由斯特林公式易得总的正确率是$1 - O(\frac{1}{\sqrt{n}})$

这样就可以过任务一啦!

此时得分$22$分。

算法二

如果不带编号的爆搜少女已经gg了...

伤心地吃着咸鱼

那么我们就一定要利用上标号才行,任务二太难不会,任务三分数最低肯定最简单,我们先来看看任务三吧。

第$i$个人看看自己前面如果有人头上是$1$那么就投$0$票,否则就假设自己头上是$1$,然后投$2^i$票。

既然前面加起来只有$2^i - 1$票,显然只有最后一个投的人有效。

这样就有$1 - O(2^{-n})$的正确率了。

任务三就轻易解决了,果然是个送分提答呀

此时得分$40$分。

算法三

我们再回头看看任务二。

我们把它所有人分成$1, 2, 4, ... , 2^{k - 1}$的k组

从第一组开始,如果他之前没有$xor = 1$的组,就按照自己$xor = 1$来投。

如果前面有$xor = 1$的组,就一半投0一半投1,把自己抵消掉。

这样只有全部xor = 1的时候会gg,这样的概率是$2^{-logn} = O(\frac{1}{n})$

所以做到了$1 - O(\frac{1}{n})$的正确率。棒

此时得分$64$分。

算法四

现在就只剩下任务四了,看起来应该是需要一个对于任意的$k$都成立的做法。

每个人可以看到一个$(x_1, x_2, ..., x_k)$的向量,那么他投票方案可以写成一个$k$次多项式,他在$(1-y_1, 1-y_2, ... ,1-y_k)$的投票方案是$a_i$。那么这一项就是$(-1)^{\sum y_i}a_i(x_1 - y_1)(x_2 - y_2)...(x_k - y_k)$。

所有人的策略加起来也是一个k次多项式,最后的结果就是这个多项式带$x$进去之后值的符号。

反过来如果有一个k次多项式,那么我们把它的每一项分配给对应的人作为他们的投票策略,也是可行的策略。所以这两个问题完全等价。

我们如何找到一个这样的$k$次多项式呢?如果有$s$个1,由于$s$符合二项分布,我们可以试着把$[\frac{n - k}{2}, \frac{n + k}{2}]$这个区间做对。(方便起见假设$n$和$k$同奇偶)

设$sgn(x) = -1 / 0 / 1$表示$x$的符号,$sgn(x + 1/2 - s) = (-1)^{[s > x]}$,所以用总的多项式取$p(s) = (-1)^{\frac{n - k}{2}} \prod_{i=0}^{k-1} (\frac{n - k}{2} + i + \frac{1}{2} - s)$即可

显然把$\sum x_i$带入$s$之后是一个$k$次多项式。这个策略在$[\frac{n - k}{2}, \frac{n + k}{2}]$的区间内完全正确,在区间外也有一半的正确率。

此时得分$100$分。

共 15 篇博客