2020-2021:teams:tle233:taibei2019

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:tle233:taibei2019 [2020/05/21 16:25]
marvolo [题解]
+++ 2020-2021:teams:tle233:taibei2019 [2020/05/21 16:28] (当前版本)
marvolo
@@ 行 23: / 行 23: @@
 中间加了一些奇奇怪怪的剪枝,同时用了一个感觉不怎么靠谱的Hash函数来记忆化棋盘,没想到居然过了.
+===== [C] Are They All Integers? =====
+==== 题意&题解 ====
+签到题
+===== [D] Tapioka =====
+==== 题意&题解 ====
+签到题
+===== [E] The League of Sequence Designers =====
+==== 题意 ====
+给出一段长度为$n$的整数序列,$1 \leq n <2000$.并给出了一段求$(r-l+1)\sum_{i=l}^{r}a_{i}$的最大值的贪心代码.现在要求构造出一段这样的序列,要求正确的最大值比给出代码求出的最大值恰好大$k$.输出任意一种方案.
+==== 题解 ====
+简单构造.
+直接构造长度为1999的序列.令序列的第一位为$-1$,后面全都是非负数.这样贪心找到的子序列长度就是1998,正解找到的子序列长度是1999.设后面这些数的和为$x$.可以得到如下方程:
+$$1999(x-1)-1998x=k$$
+化简得,$x=k+1999$
+然后把$x$随便填充到后面的空位中即可.
+===== [H] Mining a =====
+==== 题意 ====
+给出一个数$n$.求最大的$a$,使得存在$b$,满足$\frac{1}{n}=\frac{1}{a \oplus b}+\frac{1}{b}$.中间的运算符为异或.
+==== 题解 ====
+有趣的结论题.$b=n+1$.然后反解出$a$就行了.
+<del>但是并不会证明</del>
+===== [J] Automatic Control Machine =====
+==== 题意 ====
+给出$m$个集合,每个集合中有一些正整数.现在求它的一个最小的集合子集,使得这些集合的并集中恰好包含了$n$个数.
+==== 题解 ====
+二进制暴力枚举,拿Bitset直接通过或运算来计算并集的情况.实际运行的速度快的飞起.
+===== [K] Length of Bundle Rope =====
+==== 题意&题解 ====
+签到题
+===== [L] Largest Quadrilateral =====
+==== 题意 ====
+给出平面上的一堆点,要求从其中找出四个点,使得这四个点围成的多边形的面积最大.(可能有重合的情况)
+==== 题解 ====
+旋转卡壳+枚举
+构造出凸包后,枚举这个四边形的一条直径,然后类似旋转卡壳那样找面积最大的情况.需要卡一下常数.
+===== 总结 =====
+整场比赛发挥还可以,智商基本上持续在线.比如H题直接猜出了结论节省了很多时间.当然中间还是犯了一些错误,M题开场读完后以为是一个广义Lucas定理,甩给队友持续研究了半天.到最后快结束的时候才发现题目中的取模是重新定义过的,并不是板子题.导致前期开题时人手有些不够,切签到题的速度有些慢.中间推E题构造式子的时候也有些慢.A题在RE了一发之后,一直以为是递归崩栈了,改了几次无果之后才发现是数组越界,多吃了很多次罚时.最后的时间全部用来推F题,感觉是一个SPFA实数费用流模型,但是直到最后也没有完成对模型的修正,正好回头找一队问一下做法.
+<del>别人的520用来秀恩爱,我的520用来训练,我们都度过了充实的一天</del>

2020-2021/teams/tle233/taibei2019.1590049517.txt.gz · 最后更改: 2020/05/21 16:25 由 marvolo