====== 2019 Multi-University Training Contest 2 ======
Virtual Participated on Aug 17, 2020.
====== Results ======
===== Summary =====
* Solved 8 out of 12 problems
* Solved 8 out of 12 afterwards
===== Virtual Participation =====
===== Submit Distribution in Members =====
^ Solved ^ A ^ B ^ C ^ D ^ E ^ F ^ G ^ H ^ I ^ J ^ K ^ L ^
| Pantw | | | | | √ | | | | | √ | | √ |
| Withinlover | | √ | | | | | | √ | | | √ | |
| Gary | | | | | | √ | | | √ | | | |
(√ for solved during VP, ○ for after VP, - for tried but not solved)
----
====== Solutions ======
===== B ======
首先,字典序最小的答案可以倒着预处理一下然后贪心求出来。
然后字典序最大的猜了一手,把数组倒过来做了一遍。然后就A掉了。
===== E ======
这个题看起来很诡异但其实所有东西都是随机且相互独立的,可以全部分开计算。
简单推推式子就完了。
===== F ======
FWT裸题
===== J =====
签到题
===== H ======
网络流板子题(雾)
考虑最小割,一个点与S相连表示染成黑色,与T相连表示染成白色。
然后把一条边拆成6条连上去,满足题目中的(a, b, c)三元组的条件,这个拿张草稿纸手算一下就行
找一个合适的板子套上去就好了。
===== I ======
建立回文自动机 直接判断自动机上每个节点是不是满足条件的回文串,我写的manacher,哈希好像更方便点
===== K ======
主席树板子题(雾)
看上去很难,但其实可以暴力找,找出最大的区间内最大的三个看是否满足条件,然后再找第二第三第四大的$\cdots$
不难发现在数据范围内,任取44个数字一定存在3个数字可以组成三角形,加上这个题有3s的时限,加上n只有1e5。这个做法其实卡不掉(
===== L ======
从前往后枚举区间左端点,对每个值在线段树上维护可行区间。
----
====== Comments ======
ptw:
* 我决起而飞,抢榆枋而止
Gary:
* 加油加油
Withinlover:
* 发挥好不稳定啊(