TCO19 SRM 742 Div1 解题记录

### Easy ResistorFactory
题意：你一开始的产品只有$1$欧姆的电阻
你可以制造一些产品，每个产品都是之前产品的串联或者并联。
现在你要造出$d/10^9$欧姆的等效电阻。$d\in[0,10^{18}]$
不能制造超过$250$个产品。

题解：考虑造出一个$10^{-9}$，我们这样构造。
并联$1-1\to \frac{1}{2}$
并联$\frac{1}{2}-\frac{1}{2}\to \frac{1}{4}$
并联$1-\frac{1}{4}\to \frac{1}{5}$
并联$\frac{1}{5}-\frac{1}{5}\to \frac{1}{10}$
这样用$4$步就能使$\frac{1}{x}\to \frac{1}{10x}$
用$36$步造出$10^{-9}$
接下来直接一位一位填也行，但是更好的方式是填二进制。
考虑到$long long$，最多造$128$个，远远低于要求。

### Medium RandomConcat
题意：你有$n$个字符串$s_1...s_n$，问将它们随意拼接之后，字符串$t$出现次数的期望。$n\le 15,|s_i|,t\le 50$

题解：只考虑原题就是$kmp+DP$入门练习题。记$f(i,mask)$表示用了$mask$中的字符串，匹配到$t$的第$i$个位置。

### Hard Depot
题意：一条直线上分布着$n$个物品，每一个物品可以表示成$D\ I\ M\ S$，表示$D+I,D+2I,D+3I,...,D+(M-1)I$分布着这个物品，且大小为$S$。
现在有两种询问，一种是询问$Q(D, S)$表示询问用$[0,D]$的物品可否凑出$S$。
另一种询问用
$D, S, A_1, B_1, A_2, B_2, N$
表示有$N$个询问，第$i$个是：
$Di = ((D + i*A_1 - 1)\ mod\ B_1 + 1)$
$Si = ((S + i*A_2 - 1)\ mod\ B_2 + 1)$
询问一共$Q$个。
$Q,n\le 20\ D,I,M,A_1,B_1\le 10^9\ S,A_2,B_2\le 3\times 10^5$

题解：设$f(i)$表示$i$被凑出来需要的最小坐标，每一次加入一个新物品$u$。
考虑朴素的转移$f(j)\to f(i)$需要满足$S_u|i-j$，$f(i)=(1+\frac{f(j)-D_u}{I_u})I_u$具有单调性，直接查询满足条件的最小的$f(j)$即可。
直接把条件处理为下标$(mod\ S_u)$的余数分别记录前缀$min$
$O(NS)$

Rockdu's Blog

导航

最近发表

大佬们的友链