Luogu P4616 [COCI2017-2018#5] Pictionary

1 题意

在第 $i$ 天,如果 $\gcd(a,b) = m – i + 1$,那么 $a,b$ 之间会建立一条边

给定 $a,b$,求 $a,b$ 最早什么时候连通

多组询问,离线

$1 \leq n ,q \leq 10^5, 1 \leq m \leq n, 1 \leq a, b \leq n$

$n,m,q,a,b \in \mathbb{Z}$

Continue reading “Luogu P4616 [COCI2017-2018#5] Pictionary”

中山纪念中学 Day 4 2019.08.04 解题报告 & 题解

T1 锻造 Forging

1 记录

考场上的时候总觉得题目非常的奇妙

因为一直循环下去不就完了吗?

直到后来我的同桌给我指点,原来把 DP 式子当方程解可以了

还是太菜啊

Continue reading “中山纪念中学 Day 4 2019.08.04 解题报告 & 题解”

Luogu P2624 [HNOI2008]明明的烦恼

题目链接: https://www.luogu.org/problemnew/show/P2624

0 前置技能

1 推式子时间

这个题目很像 Luogu P2290

但是问题在于,这个里面具有不确定的度数

经过简单的思考,我们可以得出以下式子
$$
C_{n – 2}^{cnt} \times \frac{sum!}{\prod_{i = 1}^{cnt} (d_i – 1)!} \times (n – cnt) ^{n – sum – 2}
$$
其中

  • $sum$ 为已知总度数
  • $cnt$ 为已知点数
Continue reading “Luogu P2624 [HNOI2008]明明的烦恼”

可重组合与不相邻组合

可重组合

从 ${1, 2, 3 \cdots, n – 1, n}$ 中选出 $m$ 个元素,可以重复,有多少个不同的组合?

答案 $C_{n + m – 1}^{m}$

证明

显然,问题可以转换为 $m$ 个球放入 $n$ 个盒子,可以放无数个或者不放

即插入 $n – 1$ 个隔板,然后求全排列 $(m + n – 1)!$

但是隔板和球的顺序是无效的所以除去 $m! \times (n-1)!$


$$
\frac{(m + n – 1)!}{m! \times (n – 1)!} = C_{n + m -1}^m
$$

Continue reading “可重组合与不相邻组合”

「BJOI2019」光线

题目链接: https://oj.woshiluo.site/problem/2055 / https://www.luogu.org/problemnew/show/P5323

我看到题目的一瞬间

我是在学 oi 还是在学物理?

然后我仔细思考了一下,这两个镜子来回反射,您这是要求极限?

然后我仔细思考了一下

设 $f_i$ 为从 $1$ 到 $i$ 的透光率,$g_i$ 为从 $i$ 到 $1$ 的反光率

Continue reading “「BJOI2019」光线”