2020-2021:teams:alchemist:2020_self_training_1

差别

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

到此差别页面的链接

--- 2020-2021:teams:alchemist:2020_self_training_1 [2020/07/23 21:44]
mountvoom 创建
+++ 2020-2021:teams:alchemist:2020_self_training_1 [2020/07/24 10:38] (当前版本)
hardict [lpy]
@@ 行 8: / 行 8: @@
 ===== cmx  =====
 ===== lpy  =====
+网络流多组数据初始化时得多加注意
 ===== xsy  =====
+总体还行，不过签到题因为数组开小和没开long long -2多少带点脑瘫。
 ====== 题解  ======
+===== A - Xiongnu's Land =====
+签到题，可以利用差分维护一下一块土地对某个位置的贡献。
+最后把得到的数组求两次前缀和就能得到在某处划线以后得到的左边土地面积，扫一遍即可。
+by MountVoom
+===== C - Today Is a Rainy Day =====
+我们是先进行2操作再进行1操作一定是最优的，因为先进行1操作可能会被2操作修改导致浪费，如果没有被修改那么后进行1操作也是可以的。
+不管2操作进行了多少步，最终得到的状态只有$6^6$种，即记录这6个数最终变成了哪个数。
+这样对于每个状态，我们只要求出从初始状态1 2 3 4 5 6转移到它的最小步数再加上最终和目标串不同的位置的个数即可。
+至于到某个状态的最小步数，可以直接从初始状态进行Bfs，转移就暴力枚举是把某个数变成另一个数就好了。
+by MountVoom
+===== D - Kejin Game =====
+一个网络流题目，建图方式和最大权闭合图有点像
+$source \rightarrow i$流量为正常学习花费
+$i \rightarrow i'$流量为氪金学习花费
+$i' \rightarrow j$流量为删除$j$对$i$依赖价值
+而最关键的是$target \rightarrow sink$为一条$\infty$的边
+则原图每个**有限**割都对应一种学习发案，求最小花费就是求最小割
+by Hardict
+===== G - Mysterious Antiques in Sackler Museum =====
+$4$个矩形，判断能否选$3$个出来拼接为一个更大的矩形
+暴力枚举即可，可以利用$next_permutation$减少码量
+by Hardict
+===== I - Snake Carpet =====
+构造题。当时手动构造出来了(震惊)，当时发现奇数能很好的堆成一个块，然后发现偶数又能恰好在旁边堆上2333。
+<code c>
+5554466
+3354466
+1352266
+7777666
+5557666
+3357244
+1357244
+777766688
+555766688
+335724488
+135724488
+</code>
+看了这个表就很清晰了，如果$n$是偶数考虑$n - 1$最后再加两列$n$即可。
+构造奇数时发现$n$可以很容易的由$n - 4$转移过来，于是问题就解决啦。
+by MountVoom
+===== K - A Math Problem =====
+打表发现$f(2x)=3f(x),f(2x+1)=3f(x)+1$
+然后可以发现$f(x)$的$3$进制表示数值上等于$x$的$2$进制表示
+其实就是个取模带余数的数位$dp$
+by Hardict

2020-2021/teams/alchemist/2020_self_training_1.1595511870.txt.gz · 最后更改: 2020/07/23 21:44 由 mountvoom