UOJ Logo C_SUNSHINE的博客

博客

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 抱枕一个!

UOJ Round #16 题解

2016-08-28 22:10:07 By C_SUNSHINE

破坏发射台

By NanoApe,题解 By NanoApe

萌萌哒新人来水题大放送啦 >.<

算法一

枚举所有染色方案,一个个看是否符合要求。

复杂度 $O(m^n)$,期望得分 $8$ 分。

算法二

上一个做法太暴力了,我们会发现,第一个格子选第一种颜色的方案数等于第一个格子选第二种颜色的方案数,所以我们可以加点剪枝,利用最小表示法状态去重。

复杂度 $O(n!)$,期望得分 $40$ 分。

算法三

暴力做法已经没有什么可以优化的地方了,我们把它扔进垃鸡嘴里。

$n$ 为奇数的时候,我们设第一格的颜色为 A,然后设个一元二进制状态表示当前格的颜色是否为颜色 A。

设 $F[i][0..1]$ 表示第 $i$ 格的颜色是否为颜色 A 的合法方案数,然后递推一波即可。

复杂度 $O(n)$,期望得分 $32$ 分。

结合算法二,期望得分 $56$ 分。

算法四

算法三的转移可以用个矩阵来表示,然后就是在算法三的基础上套个矩阵快速幂即可。

复杂度 $O(log n)$,期望得分 $40$ 分。

结合算法二,期望得分 $64$ 分。

算法五

$n$ 为偶数的时候,我们设第一格的颜色为 A,设第 $\frac{n}{2}+1$ 格的颜色为 B,然后设个二元三进制状态表示第 i 格和第 $\frac{n}{2}+i$ 格的颜色是否为颜色 A 或颜色 B($1 \leq i \leq \frac{n}{2}$)。

设 $F[i][0..8]$ 表示推到第 $i$ 格的所有二元三进制状态的合法方案数,然后递推一波即可。

复杂度 $O(n)$,期望得分 $48$ 分。

结合算法四,期望得分 $88$ 分。

算法六

和算法四的优化一样,你把转移写成矩阵然后矩阵快速幂即可,转移可以大力讨论。

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

结合算法四,期望得分 $100$ 分。

破坏蛋糕

By MemoriaIgnitus,题解 By C_SUNSHINE

算法一

对于两个特殊的情况($n=3$和所有直线与$L1$或$L2$平行),有限的区域分别是三角形和平行四边形,求出这个三角形和平行四边形,在每一段上选关键点判定即可。

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

算法二

对于每一段,我们取其上一个关键点(例如中点),则问题变成判断一个点所在区域是否为无限。

妈妈我会半平面交!

拉板子,每段$O(n \log n)$,惨啊只能做$n \leq 1000$。

算法三

我们把所有直线按照斜率排好序,排过序之后半平面交就是$O(n)$的了,那么考虑从一段走到下一段,发生了什么变化呢?

有一条直线的方向改变了,而且还是改变了$\pi$,我们把这一条直线拿出来插回去,就做到了每次排序$O(n)$,那么直接套模板似乎就能做$n \leq 5000$了。

然而半平面交有点卡常数?

我们考虑另外一种判定方法,把所有直线面向判定点一侧法向量的斜率拿出来极角排序,如果有两个相邻的法向量,他们的极角转过了超过或等于$\pi$,就说明出现了一个开口。这个区域就是无限的了。

于是判定一下子变得简单很多,$n=5000$就可以轻松做了。

算法四

相信说到极角排序后查看相邻的法向量,很多小朋友已经想到$n \leq 100000$怎么做了。

每次只修改了一个法向量,而且只需要检测相邻的法向量,于是这个事情完全可以用平衡树来做,事实上一个set足矣。写的时候注意转过一圈时的边界情况就好了。

参考代码http://uoj.ac/submission/94838

当然如果你怕被卡精度的话,你可以用向量来表示角度,所有的比较都可以分类讨论+叉积,这样就没有精度误差了。

参考代码http://uoj.ac/submission/94836

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

这是不是近几场UR中最Simple的一个B题了呢?

破坏导蛋

By ftiasch + jiry_2,题解 By jiry_2

算法一

考虑如何方便的判断一个点是否在三角形内。

在三角形内的限制可以看成要求满足与三条直线之间的位置关系,即要满足三个形如 $ax+by+c \leq 0$ 的不等式,分别带入判断一下即可。

对每组询问爆枚每一个点判断是否满足条件,时间复杂度 $O(nm)$,期望得分 $20$ 分。

算法二

坐标范围很小时,我们可以枚举点的横坐标把二维的限制降至一维,这样询问就变成了询问横坐标等于 $x$ 的点中纵坐标在某一个区间内的点数。对每一个横坐标预处理一下前缀和即可。

时间复杂度 $O(|x||y|+n+m)$,结合算法一期望得分 $40$ 分。

算法三

要同时满足三个 $ax+by+c \leq 0$ 不好处理,可以先只考虑一个限制。即给出限制 $ax+by+c \leq 0$,询问满足条件的点有多少个。

当 $K$ 很小时,可以把所有点按照 $ac+by$ 排序,满足条件的点一定是个前缀,二分一下即可。

现在考虑需要同时满足三个限制,我们可以使用 bitset。即对每一个限制求出每一个点是否满足条件,那么只要把三个 bitset and 起来再求其中 $1$ 的个数就好了。单个限制的时候依然是直接排序,然后维护一下前缀 bitset 即可。

这样的时间复杂度是 $O(Kn \log n+\frac{nm}{w}+m \log n)$ 的,可以接受,然而空间复杂度是 $O(\frac{nm}{w})$ 的,这就太大了。

我们可以对点集进行分块,每一块分别求解,假设块的大小是 $S$,那么时间复杂度是 $O(Kn \log n+\frac{nm \log n}{S}+\frac{nm}{w})$,空间复杂度是 $O(\frac{mS}{w})$ 的,调整一下块大小即可,结合算法一和算法二期望得分 $70$ 分。

算法四

算法三的瓶颈在于讲所有点按照 $ax+by$ 排序,即给出角 $\theta$,把所有点按照 $sin(\theta)x+cos(\theta)y$ 排序。

考虑两个点 $i$ 和 $j$,它们的权值相同时 $\theta$ 有两个取值 $\theta_1$ 和 $\theta_2$,它们把区间 $[-\pi,\pi)$ 分成了三部分 $[-\pi,\theta_1)$,$[\theta_1,\theta_2),[\theta_2,\pi)$。一共有 $n^2$ 对这样的点,所以区间 $[\pi,-\pi)$ 一共被分成了 $O(n^2)$ 段,所以不同的顺序也只有 $n^2$ 种。

把所有关键点排序,从小到大枚举 $\theta$,每一个关键点之后对序列的影响就是交换相邻的两个位置,这样前缀 bitset 还是可以维护的。主要要特判关键点重合(多点共线)的情况。同时离线按照斜率依次处理每一个询问,每一次到了相应的顺序时二分一下就好了。

直接做时间复杂度是 $O(n^2 \log n+m \log n+\frac{nm}{w})$ 的。

依然可以对点集分块,设块的大小是 $S$,那么时间复杂度就是 $O(S^2 \log n+\frac{nm \log n}{S}+\frac{nm}{w})$,期望得分 $100$ 分。

算法五

当然要去掉 bitset 也是可以的,不过细节会多一些。

询问一个三角形内的点数,可以拆成三个询问一条线段下方的点有多少个,这可以看成询问一条直线下方的点中横坐标在一个区间里的有多少个。

可以按照 $x$ 坐标排序然后分块,块内和算法四一样,多余的不超过 $\sqrt n$ 个点直接暴力就好了了。

这样时间复杂度是 $O(S^2 \log n+\frac{nm \log n}{S}+mS)$,期望得分 $100$ 分。

不过在这个数据范围内 bitset 部分只占了很少一部分的运行时间,主要还是在处理每一个块的部分和二分的部分,所以两个算法在运行时间上并差不了多少。

总而言之,这道题主要的思维难度还是在把 $n$ 个点分块上,这题也应该算是一道比较简单的 C 题了吧。

UOJ Round #15

2016-08-10 22:59:08 By C_SUNSHINE

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

这是 UOJ 第十五场 UOJ Round。UOJ Round 还是一如既往的省选及以上难度,欢迎大家来玩 owo

公元 2004 年 8 月 13 日,2004 年雅典奥运会开幕。其实,在遥远的跳蚤大陆,每年也会举办一场跳蚤奥运会。跳蚤奥运会项目虽然众多,但最被跳蚤公民们关注的还是最古老项目——跳高。

十年前,伏特跳蚤国王横空出世,靠着自己高超的跳高技术横扫整个跳蚤跳蚤大陆,一举夺得跳蚤奥运会跳高总冠军,并在之后的九年连续卫冕,跳高这项运动甚至开始变得没有悬念起来。

然而就在前不久,跳蚤大陆东南部一个人口不足跳蚤大陆总人口 5% 的省份,一位被称为“最强跳蚤”的跳高选手突然跃入跳蚤们的视线。靠着自己的绝技“最强跳蚤跳跳跳”,最强跳蚤一路过关斩将,轻易进入了跳高国家队,大有与伏特跳蚤国王一战的趋势。

一边是经验丰富的跳高界泰斗,一边是初生牛犊不怕虎的天才跳高小将,这一场史诗级较量究竟谁能取得最后的胜利呢?

这一场比赛将围绕这这一次较量展开。

出题人:qmqmqm, ftiasch, ppfdd

这场成绩将计入 rating。

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

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

UPD: 比赛已经结束!

echo -n A题没有AC的人中排名最高的 | md5sum
0dd1e3fdc9a4b50ac3e718a89cba15be

恭喜获得前 5 名的选手!

  1. WrongAnswer
  2. yanQval
  3. jasonvictoryan
  4. philipsweng
  5. OhWeOnFire

恭喜 swm_sxt 获得 UOJ 抱枕一个!

UOJ NOI Round #1 排行榜

2016-07-18 18:58:42 By C_SUNSHINE

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

排名ID笔试Day1.ADay1.BDay1.CDay1Day2.ADay2.BDay2.CDay2总分
金牌($15$人)
1WuHongxun99100972622310010080280602
2xumingkuan97100606222210015100215534
3WrongAnswer9710060902501003050180527
4masanzhou9990602817810015100215492
5JOHNKRAM1001006024184100080180464
6srwudi9890100382282015100135461
7worse991006018178100080180457
8wzj991006021181701580165445
9scPointer9910080252051015100125429
10Hentai010097019710030100230427
11immortalCO991006047207106050120426
12bright_sun1001006039199403050120419
13wangyisong19969810060281881015100125411
14fateice0908058228701590175403
15chenqihang969030381581001530145399
银牌($25$人)
16yanQval969030351551001530145396
17Groot100100801219220080100392
18lis10010060351953006090385
19TDL7090601816810015100215383
20abcd1927981000941942007090382
21lzr010506961003025155100030130381
22shadow100100304417420155085359
23wusongyin99100301714740070110356
24hzt110010060251852005070355
25carlyu0100061161100090190351
26liaoliao97100601917930153075351
27huhanwen100100302015020080100350
28tzn100100018118100030130348
29TDL9100100303816830153075343
30chrysanthemum9810004814810157095341
31Under_Taker10010005515540153085340
32laonahongchen9910002812830080110337
33AHWHRKY100100022122015100115337
34Orz__Orz__Orz981000571571006070325
35smallling10010002112110000100321
36kj99070310010030281583003060318
37aufeas10010002212210157095317
38OnlyaDouBi10010001611670030100316
39EZ_zby10010030401700153045315
40fjzzq2002100100039139700070309
铜牌($50$人)
41nlj1999981000291293005080307
42Fancy1006001575100030130305
43x56ngy4nfan991003037167300030296
44lbn1879900001001580195294
45jhr1006004110140153085286
46Thaddeus10010030521820000282
47lcr88888801003022152100030130282
48dwjshift010080151950157085280
49assassain9910000100008080279
50Ele_Ele971000201202004060277
51maijing100100001002005070270
52qzqzgfy971000610620153065268
53pedrolee100100018118005050268
54Manchery1001000010020153065265
55ct1230989960306962005070265
56tomjerry2131006030291190153045264
57zhouzixuan100100029129003030259
58liujunhao9690010100006060256
59SCaffrey97100028128003030255
60cyand1317995030251052003050254
613zwyh010030301602007090250
62zhouyidong991000491490000248
63lvzijian100100031131015015246
64new99100011010153045245
65shpgy99100001000153045244
66chaiyt_is_pig010004914910157095244
67jianglin33208002110150090140241
68indakaru981000371370000235
69thomount1001000351350000235
70sui090027117101590115232
71function21001003001300000230
72diaosipan10010000100003030230
73875951000301300000225
74109317324999603016106200020225
75massimodong991000261260000225
76la1la1la09060351851003040225
77AliceWang97600161006060218
7832151001000151150000215
79zyb990000100150115214
80pyz57151001000141140000214
81ScarletMoon991000151150000214
82yusitong991000101100000209
83Austin_Griffin100800291090000209
84y7070951000111110000206
85schronuman996001373003030202
86FTYYY01006011171003030201
87Stalker100100001000000200
88liguanglin100100001000000200
89Horizon99100001000000199
90qj01009701970000197
胸牌($??$人)
91AwD0100065165003030195
92icecathy9830021510153045194
93zxcvbnm1004002363003030193
94Cicada0100061161003030191
95dongchen01000451450153045190
96xia_xue_QAQ9900007002090189
97HXLLL969000900000186
98sunzeyu1003002252003030182
99q707185547010000100008080180
100frank_c10100001005003080180
101stiger100001003038168001010178
102SnowSword1003001646003030176
103Ciki99600060015015174
104chenguanting01000491491015025174
105czllgzmzl01000391392015035174
106copyright982003858015015171
107Ryan100300434003030164
108wwwzbwcom883000300153045163
109chestnut9930032620000161
110whzzt0100031131003030161
111D04241297300030003030157
112cjsoft090016106005050156
113cyd123180600491093015045154
114ljslkdllf9930021510000150
115swm_sxt0100019119003030149
116qiuwowpijiahuanhua01000231231015025148
117SAI92000010153055147
118FizzyDavid000001001530145145
119llgyc9530019490000144
120Yukimai1000044440000144
121sixer826000600000142
122chilling0100011111003030141
123WYMTF09001910153045136
124Manu_Zhu0700118110153055136
125sdhyabc993003330000132
126esto953006360000131
127szzq00000100030130130
128sxysxy933000300000123
129Onlynagesha903000300000120
130orzkpm20900090003030120
131wangnick1999990021210000120
132dlhham0900291190000119
133li20082008li01000161160000116
134lzoi_zzq853000300000115
135dram940021210000115
136zkx061110500611110000111
137GaoQiuYang0600501100000110
138SKE_tlzmybm00000101580105105
139Zvezda0900121020000102
140201507060100001000000100
141Wuvin0000010000100100
142i0100001000000100
143rainbow9790100001000000100
144sunsiyu0100001000000100
145yashen0100001000000100
146zxozxo10000000000100
147kblack10000000000100
148hcpxej10000000000100
149subconscious10000000000100
150philipsweng10000000000100
151LucasSkipper10000000000100
152____________________10000000000100
153Ketsui10000000000100
154yts199910000000000100
155Rivendell10000000000100
156Simple10000000000100
157mxh199910000000000100
15861310000000000100
159jinlifu199910000000000100
160excited10000000000100
161131131yhx10000000000100
162heheda10000000000100
16396468533110000000000100
164sky4626210000000000100
165st_nec10000000000100
166gstggsstt10000000000100
167zhangzj10000000000100
168dingzijun199910000000000100
169DoubleLyra0000020080100100
170sentews3990000000099
171resuscitated990000000099
172xiqiao990000000099
173Prime990000000099
174ymx990000000099
175ws_fqk990000000099
176Fuxey990000000099
177dogther990000000099
178stdafx990000000099
179fnoi06bxthang990000000099
180Amber00_Chen990000000099
181zhourunlong990000000099
182Oxer990000000099
183ahaloer990000000099
184qiaoranliqu990000000099
185oijwei990000000099
186goodqt990000000099
187LLX990000000099
188jiazihankk990000000099
189yxr0105990000000099
190lcr88888990000000099
191CMSwift980000000098
192Sengxian980000000098
193PaidySung980000000098
194lcomyn980000000098
195NanoApe980000000098
196EatenBagpipe980000000098
197cdefgkill0970097000097
198dflasher970000000097
199Evenstar970000000097
200lzx970000000097
201BillXu2000970000000097
202luhan970000000097
203RAcceleratorPlus970000000097
204shanquan233970000000097
205czgj970000000097
206Clare970000000097
207QTQT960000000096
20820140355960000000096
209zms_950000000095
210Atlantis940000000094
211nacisey314940000000094
212uesama940000000094
213chongjg940000000094
214jasonvictoryan930000000093
215RicardoWang920000000092
216alps03001747015304592
217qq253115001900000000090
218xjr0600565101502590
219ksyx880000000088
220davidxu880000000088
221jkxing880000000088
222CtrlCV880000000088
223cxzxxjd0600187810001088
224hld67890870000000087
225lxtx76100010000086
226yang1999422850000000085
227teachk03001545100304085
228yyjxx2010xyu840000000084
229ws_yzy780000000078
230Okami770000000077
231WasteRice000003015307575
232lzr156000252550005075
233superguymj660000000066
234RatingBooster00000015506565
235chengzhiyan620000000062
236DERIT0300174701501562
237zyh3838438zyh0600161000061
238lzoi_lxy030003000303060
239Aralon030003000303060
240wxm157wxm000323200202052
241jxrjxrjxr03002151000051
242zhangyiding00000200305050
243cloudsky03001646000046
244zzh000151500303045
245Livf0400141000041
246Ironk0300030000030
247MedalPluS0300030000030
248acm_Lh0300030000030
249liuyiluxun0300030000030
250woshiyzr0300030000030
251y5535464360300030000030
252ALXPCUN00000100203030
253nevernow0002929000029
254snakes0002525000025
255Burst_Zero0000020002020
256invoid0000001501515
257myhuib0000001501515
25817486992790000000101010

UOJ NOI Round #1 题解

2016-07-18 14:13:21 By C_SUNSHINE

Day1

争夺圣杯

By YJMWOI,题解 By C_SUNSHINE

算法一

$n \leq 100$的部分,当然可以写一个simple的暴力啦,我们枚举所有区间,然后对每个区间求出最大值,再计算答案。

这个复杂度是$O(n^3)$的,期望得分$10$分。

算法二

上一个做法太暴力了,可以发现$\max \{a_l,a_{l+1},\cdots,a_r\} = \max \{\max \{a_l,a_{l+1},\cdots,a_{r-1}\},a_r\}$,于是我们先枚举$l$,然后升序枚举$r$每次更新最大值就好了。

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

算法三

暴力做法已经没有什么可以优化的地方了,我们把它扔进垃圾桶。

考虑一个元素$a_x$,在哪些区间中它会成为最大值。

找到$a_x$之前第一个比$a_x$大的元素$a_L$,若没有则$L=0$,再找到$a_x$之后第一个比$a_x$大的元素$a_R$,若没有则$R=n+1$。

设$p=x-L,q=R-x$,则以$a_x$为最大值的区间一共有$pq$个(左端点在$[L+1,x]$,右端点在$[x,R-1]$)。

接着观察这些区间的长度分布,不妨设$p \leq q$,考虑长度$len$

当$1 \leq len \leq p$时,长度为$len$的区间共有$len$个($[x-len+1,x],[x-len+2,x+1],\cdots,[x,x+len-1]$)

当$p < len \leq q$时,长度为$len$的区间共有$p$个($[x-p+1,x-p+len],[x-p+2,x-p+len+1],\cdots,[x,x+len-1]$)

当$q < x \leq p+q-1$时,长度为$len$的区间共有$p+q-len$个($[x-p+1,x-p+len],[x-p+2,x-p+len+1],\cdots,[x+q-len,x+q-1]$)

注意到这三段都是关于$len$的等差数列。

所以相当于给一个数组加上若干等差数列,只要求最后每个位置的答案。对于这个问题,我们直接在这个数组的一阶和二阶差分上进行修改,最后从前往后扫一遍求出原数组即可。

使用倍增RMQ建出笛卡尔树来计算$L,R$的复杂度是$O(n \log n)$的,统计答案是$O(n)$的,期望得分$90 \sim 100$分。

算法四

注意到我们并不需要建出笛卡尔树,只要使用两个单调队列从前往后和从后往前分别扫一遍,就能对每个位置求出对应的$L,R$了。

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

合唱队形

By jiry_2

嗯..slyvia 是一个萌萌哒的妹子。

算法一

$n=m$ 的时候终止状态只有一个,其中每一个人都必须学会一个特定的音。

所以就相当于有 $n$ 个数,每一次等概率看一个数再放回去,问期望多少步看到特定的 $k$ 个数。

考虑从看过 $i$ 个经过若干次观看到达看过 $i+1$ 个,那么每一次看一个数都有 $\frac{k-i}{n}$ 的概率完成转移,因此这一步的期望步数就是 $\frac{n}{k-i}$。

那么答案就是 $\sum_{i=1}^k \frac{n}{k-i+1}$。

期望得分 $30$ 分。

算法二

这种情况下总的状态数不超过 $2^{15}$ 种,然而直接列方程高斯消元求答案的时间复杂度还是是无法接受。

考虑每一个点出发的转移,可以发现每一个点能转移到自己或者多一个已完成课程的状态,因此转移是一个套上自环的 DAG,于是就可以按照拓扑序进行 DP,对每一个点解一个一元一次方程就能得到答案了。

期望得分 $30$ 分。

算法三

令 $f_i$ 为第 $i$ 时刻还没有停止的概率,那么答案就是 $\sum_{t=0}^\infty f_i$。

考虑算 $f_t$,这时我们可以进行容斥,枚举哪些位置已经完成了对给定串的匹配,来容斥出每一个位置都不匹配的概率。

所以可以先 $2^n$ 枚举每一个位置往后是否可以匹配给定串,那么就得到了一些小学生必须要会哪些音,这就相当于有 $n$ 个数,每次等概率模出来一个数看一下再放回去,有 $k$ 个特殊数,问 $t$ 时刻后所有特殊数都被看过的方案数。

这个也是可以容斥的,我们枚举有多少个特殊数没有被看过,那么就变成了有 $k$ 个数不能被看的概率,这个是非常好算的,就是 $(\frac{n-k}{n})^t$。

容斥的过程中,我们把若干个 $1^t$ 和若干个小于 $1$ 的分数的 $t$ 次加加减减,但是可以发现所有 $1^t$ 是完全抵消的,因为 $\sum_{i=0}^n \binom{n}{i}(-1)^i=(1-1)^n=0$。所以我们可以不管所有 $1^t$ 项,只考虑哪些小于 $1$ 的分数的 $t$ 次项。

将里层的式子拆开,就相当于对很多个真分数 $k$,求 $\sum_{i=0}^\infty k^i=\frac{1}{1-k}$。

所以在容斥的过程中出现的每一个分数 $k$ 的 $t$ 次项对答案的贡献就是 $\frac{1}{1-k}$。

于是枚举位置容斥的时候把贡献累加起来就好了,时间复杂度 $O(2^nn)$,期望得分 $50$ 分。

算法四

不难发现算法三的复杂度其实是 $O(2^{n-m}n)$,因此当 $n$ 和 $m$ 非常接近时,是可以使用算法三的。

考虑当 $m$ 比较小的时候怎么进行容斥。因为两个方案,如果它们必须要选的教程数目是相同的,那么它们在容斥的时候对答案的贡献的绝对值也是相同。

所以可以令 $dp_{i,j,k}$ 表示当前考虑到了第 $i$ 个位置,$i$ 往前 $m$ 个位置匹配给定串的情况是 $j$,当前有 $k$ 个教程必须进行的方案数(实际上是偶数个位置匹配的方案数减去奇数个位置匹配的方案数)。因为只有往前 $m$ 个位置对 $i$ 有影响,所以再往前的就可以不记录了,每一次枚举当前位置选还是不选然后统计答案。

预处理一下后这一部分的时间复杂度是 $O(2^mn^2)$ 的。

均衡两部分的时间复杂度后可以得到一个 $O(2^{\frac{n}{2}}n^2)$ 复杂度的算法,期望得分 $100$ 分。

果冻运输

By xllend3

算法零

手玩了两个点心力憔悴,我还是让出题人感受我的哲♂学吧。

期望得分$0$分,成功成为全场唯一爆零选手。

提交记录:http://uoj.ac/submission/84215

算法一

辣鸡出题人居然搞了个这么长的题面我看都懒得看。直接点下提交爽一爽吧。

期望得分$1$分。

算法二

手玩!

根据手玩技巧和花的时间不等可以获得$6 \sim 50$分。

算法三

我发现这游戏我玩过http://qrostar.skr.jp/index.cgi?page=jelly&lang=en

看我轻松手玩每个点至少$2$分。

但是由于部分分给的特别少,而且大多数的点和原游戏有一些细微的差别并不能直接照抄,又因为一旦步数超的太多就$2$分了,这么做效率比较低。

验题组手玩取$\min$之后获得的分数是$84$分。

考场上单挑$5$小时大概能拿$50 \sim 70$分。

算法四

搜搜搜!根据搜的技巧不同能获得$0 \sim 100$分。

详细搜法见immortalCO博客,我就不详细讲了。

为什么checker给源码呢

虽然checker半个多钟头肯定也能写出来了,但是这样的话我就会变成辣鸡模拟题出题人,所以就直接给源码了。我才不会告诉你其实是因为懒得check每个平台下的问题呢,哼

为什么数据和游戏有点不一样呢

其实原来是照抄游戏的,但是由于是NOI膜你赛,VFK要求最高分达到250,于是就把每个点压缩了几列让比较弱的搜索多拿点分,然后删了几个点,最后成功完成控分。 要是这题考场上有人A了就可以全真模拟题题有人A但是没人AK的情况了

Day2

Jakarta Skyscrapers

By qmqmqm

以下复杂度中的$n$为$\max(a,b)$。

算法一

每次暴力枚举得到消息的两个doge,看他们能不能使一个之前没有得到过消息的doge得到消息,直到不能操作为止。时间复杂度$O(n^3)$,操作次数$n$,可以通过第一个subtask,期望得分$10$分。

算法二

对于$b=1$的情况,明显如果$c>a$则无解。

否则,我们可以采用类似这种方式:

$a~~~~~~~~~~~~ \ 1$

$a-1~~~~~~1$

$a~~~~~~~~~~ \ a-2$

$a-2~~~~~~2$

$a~~~~~~~~~~ \ a-4$

$a-4~~~~~~4$

…………

在$2 \log(a)$次操作内得到所有不超过$a$的$2$的幂,进而可以通过二进制分解在$3 \log(a)$次操作内得到所有不超过$a$的数。

可以通过第二个subtask,期望得分$20$分。

算法三

对于$c=1$的情况,明显如果$gcd(a,b)>1$则无解。

否则,我们可以采用辗转相除的方法得到1。每次计算$x \bmod y=x-(x/y)*y$时,采用类似算法二的做法得到$(x/y)*y$。

这样看起来是$3 \log^2(n)$次的,但其实每次的$x/y$的乘积不会超过$n$,所以这些$3 \log(x/y)$之和也不会超过$3 \log(n)$。

可以通过第三个subtask,期望得分$20$分。

算法四

特判$c> \max(a,b)$和$c \bmod gcd(a,b) \neq 0$的两种无解情况。

将算法二和算法三结合,先通过算法二得到$gcd(a,b)$,再通过算法三得到$c$。

操作次数不超过$6 \log(n)$。

可以通过所有数据,期望得分$100$分。

如果你的做法常数过大,可以通过前四个subtask得到70分。

奇怪的线段树

By jiry_2

算法一

一共有 $2n-1$ 个节点,可以直接状压这些节点的颜色,每一次枚举一个区间放上去进行转移。

时间复杂度为 $O(2^{2n-1}n^2)$。

算法二

不难发现无解当且仅当存在一个节点它的孩子中有黑色节点但它自己却是白色的。这样显然是无解的,而只要不存在这样的情况,我们可以直接找出所有是黑色但是孩子都不是黑色的节点,仅对这些节点的区间单独操作,这样就得到了一个可行解,因此这个条件是充分必要的。

于是我们就不用状压全部节点了,只需要考虑所有是黑色但是孩子不是黑色的节点的染色情况就行了,这样状态数就减少到了 $O(2^n)$,实际上算法一种的有用状态也就只有这么多。

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

算法三

命题一:一次覆盖时最终定位的点的区间一定是连续的,而且一定是连续的一段右儿子加上连续的一段左儿子(从左到右)。

证明:考虑反证法,如果存在从左到右连续的左儿子和右儿子,那么它们一定是同一个节点的两个孩子,这时在定位的时候我们取得一定是它们的父亲而不是它们本身,矛盾。

命题二:每一段连续的右儿子加连续的左儿子这样的序列一定可以通过一次定位得到。

证明:首先,我们证明一个引理,就是线段树上的所有右儿子对应的区间的右端点是互不相同的,所有左儿子对应的区间的左端点是互不相同的。

考虑反证法,假设存在,那么这两个右儿子一定是祖先关系,因为他们的区间相交了,令深度较浅的是 $a$,深度较深的是 $b$,那么考虑 $b$ 的父亲 $c$,$c$ 一定是 $a$ 或者 $a$ 的后代,因此 $c$ 的区间一定被 $a$ 包含。然而 $c$ 还存在一个非空的左儿子,因此 $c$ 的右端点要大于 $a$ 的右端点,矛盾。

通过这个命题,我们得到的信息是,对于一个右儿子,往右和它相邻的右儿子恰好只有一个,因此确定了出发点后不停的走连续的右儿子的路径只有一条,左儿子同理。

因此一个左侧的右儿子和一个右侧的左儿子之间至多只存在一条满足条件的路径。

我们来考虑路径最多有多少条,假设每一个左侧的右儿子都可以和一个右侧的左儿子组成路径,每一个左儿子一定可以和它每一个祖先的左儿子组成路径,每一个右儿子一定可以和它的每一个祖先的右儿子组成路径,这样计算出来的路径条数一定不小于真实的路径条数。

令 $w[i]$ 为长度为 $i$ 的线段树中用这种方式计算出来的路径条数,只要证明 $w[i]=\frac{i(i+1)}{2}$,那么路径和区间就是一一对应的。

考虑归纳法:等于 $1$ 的时候显然。

假设把 $n$ 拆成长度为 $m$ 和 $n-m$ 的区间,那么就有式子:

$w[n]=w[m]+w[n-m]+(m-1)(n-m-1)+(m-1)+(n-m-1)+1=\frac{n(n+1)}{2}$

因此每一个区间和每一条这样的线段树上的路径都是一一对应的。

于是我们可以把每一次覆盖拆成两部分,分别为连续的一段右儿子和连续的一段左儿子,并在两条链的 LCA 处统计它们。

令 $f[i][j][k]$ 表示 $i$ 为根的子树,子树中延伸出去要在外面合并的右儿子链有 $j$ 条,左儿子链有 $k$ 条时已合并链数的最小值,暴力转移合并即可。

这个算法的时间复杂度非常高,不过 $n \leq 50$ 的部分分应该还是可以过的。

算法四

在算法三中,我们已经发现连续的一段右儿子加连续的一段左儿子的路径与序列中的区间是一一对应的。

考虑把每一个点的后继都连出来,对于每一个右儿子 $i$,它能走到所有 $l_j=r_i+1$ 的节点;而对于每一个左儿子 $i$,它能走到所有的 $l_j=r_i+1$ 的左儿子。

我们把这张图建出来,不难发现我们得到了一个 DAG,因为我们每走一步所在节点的左端点都是增加的。

同时不难发现这个 DAG 上的每一条路径都是合法的,即都是满足由连续的一段右儿子和连续的一段左儿子组成的。因此这个 DAG 上的每一条路径,我们都可以通过一次操作进行覆盖。

于是就变成了给出一个 DAG,其中有一些点至少经过一次,有一些点不能经过,问最少多少条路径能满足条件。

这是一个裸的下界最小流问题。

点数 $O(n)$,边数 $O(n^2)$,因为流量是 $O(n)$ 的,所以时间复杂度是 $O(n^3)$。

算法五

考虑优化连边,连边的瓶颈在于对每一个右儿子都连一条边指向与它相邻的节点,这部分是可以优化的。

我们新建 $n$ 个辅助节点,对于每一个右儿子 $[l_i,r_i]$,都连一条边指向第 $r_i+1$ 个辅助节点。

同时对每一个线段树节点 $[l_i,r_i]$,都从第 $l_i$ 个辅助节点连一条边回来。

这样边数就优化到了 $O(n)$,时间复杂度为 $O(n^2)$。

在出题的时候我一直觉得这道题是可以线性贪心的,但是因为 ddl 实在太多一时间又有点想不清楚(实际上是不会证明),所以还是放 $4000$ 的良心范围娱乐大众吧。

如果大家想出了贪心的算法欢迎和我讨论。

火车管理

By SkyDec

这是一道十分清真的小清新数据结构题

首先题目可以转化为,有$n$个栈,区间压数,单点弹栈,求区间栈顶和。

算法一

我们可以直接用$\texttt{vector}$模拟栈。

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

空间复杂度 $O(n^2)$

期望得分:$30$分

算法二

考虑一种比较简单粗暴的做法

我们以铁路的编号为下标建立一颗线段树。

则对应的操作就是区间压一个数,单点弹一个数,区间求栈顶之和。

我们可以在线段树上用可持久化treap作为标记,压数和弹数就便成了treap的合并与分裂。标记的下传合并也可以在$O( \log n)$的时间内完成

由于可持久了treap,所以时间复杂度和空间复杂度也相当正确。

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

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

期望得分:$30$分$\sim 100$分

算法三

我们可以建立一颗可持久化线段树,维护每个铁路每个时间的栈顶的吨位和栈顶火车的入栈时间。

我们再维护一颗线段树用来统计答案。

于是操作就显得很简单了:

区间询问:直接在答案线段树里询问即可。

区间压数:在可持久化线段树上进行区间覆盖,这个是十分基础的数据结构技巧,然后在答案线段树上修改一下。

区间弹数:由于我们记录了入栈时间,所以我们删完后用可持久化线段树查出当前入栈之前的栈顶的信息即可,然后在答案线段树上和可持久化线段树上修改一下。

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

空间复杂度 $O(n \log n)$

期望得分:$100$分

C_SUNSHINE Avatar