Difference between revisions of "ICPC 2019 Nanchang Online Contest"

From EOJ Wiki
Jump to navigation Jump to search
 
(2 intermediate revisions by one other user not shown)
Line 41: Line 41:
 
题意:给出 $n$ 个物品,第 $i$ 个物品的价值是 $w_i$,从中选出 $k$ 个,每种选择提供的价值是 $\frac{a^{sum}-1}{a-1}$,其中 $sum$ 是所有选中物品的价值和,求所有选择求出的总价值。
 
题意:给出 $n$ 个物品,第 $i$ 个物品的价值是 $w_i$,从中选出 $k$ 个,每种选择提供的价值是 $\frac{a^{sum}-1}{a-1}$,其中 $sum$ 是所有选中物品的价值和,求所有选择求出的总价值。
  
题解:生成函数,若只求 $a^{sum}$ 的部分,$ans(k)$ 是 $\prod_{i=1}^n 1+w_i\cdot x$ 中 $x^k$ 的系数。做一些变换就能得到答案。
+
题解:生成函数,若只求 $a^{sum}$ 的部分,$ans(k)$ 是 $\prod_{i=1}^n (w_i\cdot x+1)$ 中 $x^k$ 的系数。做一些变换就能得到答案。
  
 
== Problem E ==
 
== Problem E ==
Line 66: Line 66:
  
 
Solved by Weaver_zhu. 01:34 (+)
 
Solved by Weaver_zhu. 01:34 (+)
 +
 +
题意:给个线性递推式和一个好的模数,求一堆第 n 项
 +
 +
题解:矩阵快速幂被卡了,考虑通项公式和二次剩余,在好的模数下就变成快速幂问题了。底数只有两个,类似bsgs分块就能 O(1)求第n项了
  
 
== Problem I ==
 
== Problem I ==
  
 
Unsolved.
 
Unsolved.

Latest revision as of 02:12, 12 September 2019

Problem A

Solved by Kilo_5723. 02:26 (+1)

题意:给出一段长度为 $100$ 的数列,判断其是否为 $\varphi(i)$ 中的连续一段。

题解:通过实验可以发现,$\phi(i)$ 的序列在 $[1,1.5\cdot 10^8)$ 中不存在 $\varphi(i)=\varphi(j),\varphi(i+23)=\varphi(j+23),\varphi(i+46)=\varphi(j+46),\varphi(i+69)=(j+69),i\neq j$。因此,预处理每个 $(\varphi(23\cdot k),\varphi(23\cdot (k+1)),\varphi(23\cdot (k+2)),\varphi(23\cdot(k+3))$,其中 $\varphi(23*p)$ 可以从 $phi(p)$ $O(1)$ 得到,因此可以线性筛出 $phi(i)(i \in [1,7 \cdot 10^6])$,再以此推出所有需要的 $\phi(23*p)$。

接下里,只要枚举数列中第一个是 $23$ 倍数的位置,寻找是否出现预处理过的四元组。如果出现,就找到了它在 $\varphi(i)$ 中的位置,用区间筛判断是否合法。如果没有出现这种四元组,那么它必定不是 $\varphi(i)$ 中的一段。

Problem B

Solved by Xiejiadong. 01:06 (+)

题意:求一个点到其他点的最大距离 $/C$ 和好多个点到其他所有点最大距离比较。

题解:多源最短路,合并路径 max 即可。

注意不要去除 $C$ ,会发生各种问题,用多个点的距离乘 $C$ 即可。

Problem C

Solved by Xiejiadong. 04:52 (+)

题意:求删掉最小的字符,使得包含子串 $9102$ 而不包含子串 $8102$ 。

题解:倒过来处理比较方便处理末位的情况。

维护每一个区间内的转移。区间内的转移为 $f[i][j]$ ,表示状态 $i$ 到状态 $j$ 所需要删除的最少字符数量。

状态一共五个,分别是空和依次 $2$ 、 $20$ 、 $201$ 、 $2019$ 。

用线段树维护区间,每次合并区间的时候,可以发现是矩阵乘法。

线段树支持区间查询即可。

Problem D

Solved by Weaver_zhu && Kilo_5723. 04:25 (+2)

题意:给出 $n$ 个物品,第 $i$ 个物品的价值是 $w_i$,从中选出 $k$ 个,每种选择提供的价值是 $\frac{a^{sum}-1}{a-1}$,其中 $sum$ 是所有选中物品的价值和,求所有选择求出的总价值。

题解:生成函数,若只求 $a^{sum}$ 的部分,$ans(k)$ 是 $\prod_{i=1}^n (w_i\cdot x+1)$ 中 $x^k$ 的系数。做一些变换就能得到答案。

Problem E

Solved by Xiejiadong && Kilo_5723. 02:33 (+)

题意:反向约瑟夫问题,询问一个位置第几个被删除。

题解:大力模拟的复杂度是 $n+\frac{9}{10}n+\frac{81}{100}n+\cdots =10n$ 。

直接用数组模拟即可。内存可能不够开三个数组,直接复用当前数组即可。

Problem F

Unsolved.

Problem G

Solved by Xiejiadong. 00:06 (+)

温暖的签到。

Problem H

Solved by Weaver_zhu. 01:34 (+)

题意:给个线性递推式和一个好的模数,求一堆第 n 项

题解:矩阵快速幂被卡了,考虑通项公式和二次剩余,在好的模数下就变成快速幂问题了。底数只有两个,类似bsgs分块就能 O(1)求第n项了

Problem I

Unsolved.