无论哪个学科，最难的部分永远是数学
题目I——集合均值(mos)
MOS=Mean Of Set
一道完美的数学题，指不推公式你完全不知道它居然求的是**（暂且保密）。
因为每一次都需要从B中随机一个数，那么第一次取到了 $a_i$ 的话，求到的 $ans$ 应该加上 $\frac{a_i}{2}$ ，以此类推，当第二次取到了 $a_j$ 的时候，求到了 $ans$ 就取到 $\frac{a_i+a_j}{3}$ ，然后继续计算，我们会发现 $B$ 中的所有数对最终答案的贡献系数都是一样的，并且其贡献系数与其在 $B$ 中的位置没有关系，只会和 $B$ 的大小有关系，然后继续推算，答案就显而易见了：
$ans=f(|B|)\sum_{x\in B}{a_x}$
那么现在的问题就在于求出 $f(i)$ 了，我们可以模拟从 $B$ 移动到 $A$ 的过程，花费 $\mathcal O(m)$ 的时间，这也是 $40pt$ 的做法。然而这道题的关键在于：我们最后求出的期望值是一个有理数 $frac{a}{b}$ ，所以我们需要进行有理数取余，而进行逆元操作。（逆元便是这道题的正解）
怎么想到使用逆元的
首先，我们已经推出了 $ans=f(|B|)\sum_{x\in B}{a}$ ，设 $i$ 为当前 $A$ ，即已经已过去了的数的个数，那么 $|B|=\frac{i-1}{i}$ 了。我们需要在计算的过程中取模，也就自然想到使用逆元了。（虽然考的时候完全没有想到）
具体来说：
- 暴力模拟求逆元可得 $70pt$
- 线性求逆元可得 $100pt$
- 事实上，我们需要的也是这些逆元的和即可，根据原作者的话来说，会有一种
强力的的多项式高科技能使求逆元的复杂度达到 $O(\sqrt{nm}\log{nm})$ 。但在这道题来说($n\times m \leq 2\times10^7$)，线性求逆元已经完全足够了。
Task One Ac Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define underMax(x,y) ((x)>(y)?(x):(y))
#define underMin(x,y) ((x)<(y)?(x):(y))
typedef long long ll;
using namespace std;
const int MAXN=2e7+1;
const ll Mod=998244353;
template<class T>
inline void underRead(T &x)
{
x=0;
char ch=gh(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
if(t) x=-x;
}
ll n,m,x,Num[MAXN],Sum,Inv[MAXN];
int main()
{
freopen("mos.in","r",stdin);
freopen("mos.out","w",stdout);
underRead(n),underRead(m);
for(int i=1;i<=n;++i) underRead(Num[i]),Sum+=Num[i];
Sum%=Mod;
Sum=(Sum*m)%Mod;
Inv[1]=1;
for(int i=2;i<=n*m+1;++i)
{
Inv[i]=(Mod-Mod/i)*Inv[Mod%i]%Mod;
x=(x+(i-1)*Inv[i])%Mod;
}
x=(x*Inv[n*m])%Mod;
printf("%lld",Sum*x%Mod);
return 0;
}
|
题目II——聚烷撑乙二醇(pag)
PAG=Play A Game
做题最大的收获是知道了 $PAG$ 是聚烷撑乙二醇的意思
题目含义
鲁迅曾经说过，要多去尝试，才能最终发现最优的答案。
鲁迅也还说过，要珍惜当下，把握住眼前的机会。
有 $n$ 个随机数生成器，第 $i$ 个生成器可以均匀随机地生成 $[L_i,R_i]$ 内的一个实数。
现在你要玩个游戏，从第 $1$ 个生成器到第 $n$ 个生成器，每次当前生成器会生成一个数，你需要选择：
求使用使得期望答案最大的策略时，期望答案是多少。
很玄学的题意和标题
思路详解
其实想明白后十分简单，主要是想到这道题到底是怎样操作的。假设现在我们到了第 $i$ 的随机数生成器，第二个生成器产生的数的期望是 $Y=\frac{L_{i+1}+R_{i+1}}{2}$ 。如果第 $i$ 个生成器产生了 $X$ ，当 $X<Y$ 时，我们当然放弃 $X$ 更优，反之则取出 $X$ 。
那我们将 $i$ 与 $i+1$ 扩展到 $1$ 到 $n$ 的思路。对于每一组来说，我们都这样来扩展答案，就可以得到下面的算式：
当 $ans<L_i$ 时 $ans=\frac{L_i+R_i}{2}$
当 $L_i<ans<R_i$ 时 $ans=\frac{ans\times(ans-L_i)+\frac{ans+R_i}{2}\times(R_i-ans)}{R_i-L_i}$
否则， $ans=ans$ ，当然，这步不用在代码里体现。
明白这件事之后，还有一个需要注意的，那就是：
我们在扩展答案是应该从 $N$ 到 $1$ 扩展：
因为我们只有在知道了 $i+1$ 的区间之后才能知道第 $i$ 个到底取不取。
Task Two Ac Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define underMax(x,y) ((x)>(y)?(x):(y))
#define underMin(x,y) ((x)<(y)?(x):(y))
typedef long long ll;
typedef long double ld;
using namespace std;
const int MAXN=1e6+1;
template<class T>
inline void underRead(T &x)
{
x=0;
char ch=gh(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
if(t) x=-x;
}
int n,l[MAXN],r[MAXN];
int main()
{
freopen("pag.in","r",stdin);
freopen("pag.out","w",stdout);
underRead(n);
for(int i=1;i<=n;++i) scanf("%d%d",&l[i],&r[i]);
ld ans=0;
for(int i=n;i>0;--i)
{
int L=l[i],R=r[i];
if(ans<L) ans=ld(L+R)/2;
else if(ans<R) ans=(ans*(ans-L)+(R+ans)/2*(R-ans))/(R-L);
}
printf("%.5Lf",ans);
return 0;
}
|