[Fortuna OJ]Aug 4th – Group A 解题报告

今天被各路神仙吊打,顺利 gg。

A – Forging 锻造

在考场上我推了个有后效性的 DP,还以为是高斯消元,然后看到数据范围就 GG 了。这道题主要是把一些东西给转换掉了。

首先,对一个概率为\(p\)的事件,它的期望次数是\(\frac{1}{p}\)(参见这里)。然后,考虑一个状态\(dp[i]\)代表合成第\(i\)级武器的期望花费。显然\(dp[0] = a\)。

考虑\(dp[1]\)的求法,首先需要两个级别为\(0\)的武器,然后发现无论失败与否都可以保证至少又一个\(0\)级武器,所以我们只需要注意另外一个武器的花费就可以了:

\[ dp[1] = dp[0] + dp[1] \times \frac{1}{p} \]

继续阅读[Fortuna OJ]Aug 4th – Group A 解题报告

[Fortuna OJ]Jul 8th – Group B 解题报告

今天这几题咋就那么毒瘤呢?

A – String

其实这道题考场上应该能做出来的,是一道很简单的计数问题。在考场上一看到字符串就懵了,不知道为什么我对字符串的字典序有阴影,现在看来就是一道傻逼题。

考虑这样计数:

  1. 枚举一个\(i\),考虑前\(i-1\)个字符与\(T\)串相同,然后第\(i\)个字符小于\(T[i]\),这样可以保证后面怎么放置字母都能满足要求。
  2. 在枚举了\(i\)的情况下,枚举字符\(ch\),范围在\([a, T[i])\),考虑以下两种情况对答案的贡献:
    1. 如果\(ch = S[i]\),那么后面需要变动的字符个数为\(k\)个,对答案的贡献:\[ {n – i \choose k} 25^{k} \]
    2. 如果不等于,那么后面需要变动的字符个数为\(k-1\)个,因为本位占了一个;对答案的贡献:\[ {n – i \choose k – 1} 25^{k – 1} \]
  3. 贡献之后,如果本位\(T[i] \neq S[i]\),那么把\(k–\),代表多固定了一个不同的字符。

继续阅读[Fortuna OJ]Jul 8th – Group B 解题报告

LibreOJ 3096:「SNOI2019」数论题解

解法

首先我们在\(Q\)的剩余系内枚举数\(x_0\),对于此每个数表示成\(x = (x_0 + k * P) \mod Q\),思考一下发现这些数会随着\(k\)变化,且这些数会呈现周期性规律:也就是这些数在一个环上,我们可以考虑记录\(Q\)剩余系中每一个数在\(P\)中的贡献,记录成前缀和,计算答案时比较排名来判断环的方向(长弧或是短弧)。

具体看代码吧,细细品味一下应该就能理解了。

继续阅读LibreOJ 3096:「SNOI2019」数论题解

P1447:[NOI2010]能量采集题解

解法

这道题是一道裸题,考察莫比乌斯反演和 Dirichlet 卷积的知识。

在这里我们规定\(n<m\),这两者调换不会对答案产生影响。然后我们来观察这个计数规律,发现每一个点对答案的贡献至少为\(1\),附加的贡献其实就是当前线段上除了本身的整点(整数坐标点)个数的两倍,换句话说就是:

\[ ans = \sum_{i = 1}^n \sum_{j = 1}^m 1 + 2( gcd(i, j) – 1 ) \]

继续阅读P1447:[NOI2010]能量采集题解

莫比乌斯反演与杜教筛

简述

省选级别以上的 OI 赛事中的数学题,相比于 NOIp 的数学题来说要难很多。这篇文章我来记录学习了莫比乌斯反演和杜教筛之后的一些心得。以下是本文大纲:

继续阅读莫比乌斯反演与杜教筛