TCO19 SRM 748 Div1 解题记录

### Easy EraseToGCD
题意：$n$个数$a_i$，删除一些数使得$gcd$为给定值$t$，问有多少种删除方法。$n\le 500,a_i\le 1000$

题解：不知什么时候，动态规划入门题目也可以出进$div1$了。$f(i,j)$表示前$i$个$gcd$为$j$的方案数，特别的，定义$f(i,\infty)=1,gcd(x,\infty)=x$。$O(na)$

$EX$题意：$n$个数$a_i$，删除一些数使得$gcd$为给定值$t$，问有多少种删除方法。$n\le 10^5,a_i\le 10^6$

题解：考虑进一步分析性质，我们可以删除$t|a_i$的所有$a_i$。对答案没有影响，因为选择了这类$a_i$一定不能得到答案。
问题变成了将剩余的$a_i$除以$t$，问选出一些数来$gcd$为$1$的方案数是多少。
考虑枚举倍数，可以对所有$x$求出$x|gcd(a_i)$的方案数。使用朴素容斥。加上枚举倍数，总复杂度$O(a\log a+n)$

### Medium UnreliableRover
题意：你在火星上发射了一个探测器，火星表面布满了$1\times 1$的网格。你的探测器会发回信息，信息总长为$n$，每一条用移动方向和格数表示一次移动。具体来说，每一步方向会是东南西北或者'?'，'?'表示方向不定，一共有$m$个。格数会写成$[min,max]$，表示最少走$min$格最多走$max$格，有'?'的格子$min$一定是$0$。问探测器最后可能在多少个格子。$min\le max\le 10^7,m\le 20,n\le 50$

题解：显然的性质是改变操作的前后顺序和结果无关。考虑把所有确定的操作放在前面，最后一定得到一个矩形。
那么剩下的就是对一个矩形做很多操作，每次对每个块向外扩展$x$格问最终图形的面积。
题解给出的解法是规规矩矩枚举$2^m$种情况，看每次是横着还是竖着，这样每次移出来都是矩形，而我们就是取这些矩形的并集。
但是我自己一开始想的是一个很魔幻的做法：
发现最终的图形的四个角都是相同的，我们考虑一个角落的情况。不难发现，一个角落一定可以表示成这样：一个大正方形扣除对角线重合的一些小正方形后形状的一半。我们能不能维护这些小正方形都是些什么呢。
如下图，是$1-3-3$操作的过程
![图片标题](https://leanote.com/api/file/getImage?fileId=5c6fae18ab6441369300182c)
![图片标题](https://leanote.com/api/file/getImage?fileId=5c6fae22ab6441369300182d)
![图片标题](https://leanote.com/api/file/getImage?fileId=5c6fae29ab6441369300182f)
问题在于怎么维护正方形，嗯……
发现断点等价于背包……
呃，还是$O(2^n)$的……

### Hard Rectoggle

哪个毒瘤出题人出的$Nim$积……
~~泄！做不来，告辞~~

Rockdu's Blog

导航

最近发表

大佬们的友链