「Wdoi」Windy Simple Round 2.5
2021-04-05 18:30:00 ~ 2021-04-05 22:30:00
& \color{#fefef0}\kern{-15pt}\rule{220pt}{40pt} \cr[-45pt]
& \color{#ef2020}\kern{12.4pt}\scriptsize\clubs \cr[-10pt]
& \begin{gathered}
{\mathbf{\color{#407000}\huge\Bbb S\textbf{\i} mple\ \Bbb R\Large{\Theta}\huge und }} \quad
{\large\color{#006070}\texttt{ver2.5}} \cr[-5pt]
\underline{\color{#606060} \textsf{---Powered by }
\color{#808080}\pmb{\mathfrak{Windy\ OI}}
\color{#606060} \textsf{---}}
\end{gathered}\cr
\end{aligned}
赛时公告
赛时更新。在比赛期间会被移至本界面的顶端。比赛期间的一些重要改动将会放置在此处，请参赛选手实时关注。
比赛描述
- 本场比赛题目难度较低，低于 $\text{SR1/SR2}$ 大概是普及组模拟赛，所以请各位巨佬酌情参加。同时为了还原真实的做题场景，因而采用了非常惊险刺激的 $\small\colorbox{#f39c11}{\color{white}\textsf{OI赛制}}$ 。也就是说，选手只有在比赛结束时才能看到自己题目的得分，以及最终的榜单。每题得分以最后一次提交的得分为准。
- 本比赛一共有 $4$ 条题目，时间为 $\xcancel 54 $ 小时。尽管题目难度基本按照题目顺序递增排列，但仍请选手**合理安排做题顺序**以及时间。
可公开的信息：
- 题目难度较低，依旧介于 $\text{CSP}$ 入门组与提高组之间。因此可能 $\text{AK}$ 人数非常多（
- 部分题目码量略大（ $2\text{KB}$ 左右，但保证不是大模拟题贡献的码量，请放心 ），不过仍在一般普及选手可以接受的范围内。
- 每条题目都有下发大样例，帮助选手调试。
- 空间限制不小于标准程序使用的空间的 $2$ 倍；时间限制不小于标准程序使用的时间的 $1.5$ 倍。因而，选手拥有充足的时间/空间。大可不必担心被卡常。
[$\small\textsf{比赛系列题单}$](https://www.luogu.com.cn/training/7672)
[$\small\textsf{知乎评价通道}$](https://www.zhihu.com/question/452818940)
[$\small\textsf{答疑贴}$](https://www.luogu.com.cn/discuss/show/309103)
[$\small\textsf{赛后总结贴}$](https://www.luogu.com.cn/discuss/show/309275)
## 题目安排
本次比赛题目组成/出题人/验题人相关情况如下：
$$\def\arraystretch{1.5}\begin{array}{|c|c|c|c|c|}\hline
\textbf{编号} & \textbf{题目名} & \textbf{出题(第一背锅)} & \textbf{造数据(第二背锅)} & \textbf{验题(第三背锅)} \cr\hline
\textbf{A} & \color{#daaa10}\textbf{\textsf{小小的埴轮兵团}} & \text{Leasier*} & \text{离散小波变换°} &
\begin{gathered}\text{chenxinyang2006}\cr\text{Leasier}\cr\text{CSP\_Sept}\cr\text{NaOH\_Frog}\end{gathered}\cr\hline
\textbf{B} & \color{#3ea0ff}\textbf{\textsf{琪露诺的算数游戏}} & \text{离散小波变换°} & \text{离散小波变换°} & \begin{gathered}\text{NaOH\_Frog}\cr\text{chenxinyang2006}\cr\text{诱宵美⑨}\end{gathered}\cr\hline
\textbf{C} & \color{#5dbf2f}\textbf{\textsf{未来水妖集市}} & \text{离散小波变换°} & \text{离散小波变换°} & \text{24KH}\cr\hline
\textbf{D} & \color{#a3a3a3}\textbf{\textsf{第二次月面战争}} & \text{离散小波变换°} & \text{离散小波变换°} & \text{chenxinyang2006} \cr\hline
\end{array}$$
$*:$ 第一题的原 $\text{idea}$ 为该出题人所出，但是由于短时间联系不上原出题人，所以目前由 @离散小波变换° 代理。
比赛考察的知识点大致与 $\text{CSP}$ 入门组相似。保证不会考查冷门算法，也不会考察诸如结论题之类的偏门题目，请各位选手放心享用。
$$\def\arraystretch{2}\begin{array}{|c|c|c|c|c|} \hline
\textbf{题目编号} &\textbf{A} & \textbf{B} & \textbf{C} & \textbf{D} \cr\hline
\textbf{总分值} & 100 &100 &100 &100 \cr\hline
\textbf{测试点数目} & 20 & 20 & 20 & 20 \cr\hline
\textbf{时间限制} & \text{1.0 秒} & \text{1.0 秒} & \text{1.5 秒} & \text{0.75 秒} \cr\hline
\textbf{空间限制} & \text{128MB} & \text{128MB} & \text{128MB} & \text{128MB} \cr\hline
\textbf{题目类型} & \text{传统题} & \text{传统题} & \text{传统题} & \text{传统题} \cr\hline
\textbf{比较方式} & \text{全文比较} & \text{全文比较} & \text{全文比较} & \text{全文比较} \cr\hline
\textbf{是否开启O2} & \text{否} & \text{否} & \text{是} & \text{是} \cr\hline
\end{array}$$
## 题解
- [$\color{#daaa10}\underline{\verb![!\textbf{\textsf{A. 小小的埴轮兵团}}\verb!]!}$](https://www.luogu.com.cn/blog/over-knee-socks/solution-Wdsr2o5-T1)
- [$\color{#3ea0ff}\underline{\verb![!\textbf{\textsf{B. 琪露诺的算数游戏}}\verb!]!}$](https://www.luogu.com.cn/blog/over-knee-socks/solution-Wdsr2o5-T2)
- [$\color{#5dbf2f}\underline{\verb![!\textbf{\textsf{C. 未来水妖集市}}\verb!]!}$](https://www.luogu.com.cn/blog/over-knee-socks/solution-Wdsr2o5-T3)
- [$\color{#a3a3a3}\underline{\verb![!\textbf{\textsf{D. 第二次月面战争}}\verb!]!}$](https://www.luogu.com.cn/blog/over-knee-socks/solution-Wdsr2o5-T4)
## 奖励
由于 $\text{SR}$ 将可能获得神秘人员的资金资助，因而打算对参赛人员进行一定的奖励活动。一共会发放 $10\text{RMB}$ 作为该比赛的奖励。
### 琪露诺奖
对于首杀，以及 $\text{rank 1}$ ，将会获得如下奖励：
$$\begin{matrix}
\textsf{\textbf{第一题}}& \textsf{\textbf{第二题}}& \textsf{\textbf{第三题}}& \textsf{\textbf{第四题}}&\textsf{\textbf{第一名}} \cr[10pt]
\text{1 RMB} & \text{1.5 RMB} & \text{2 RMB} & \text{2 RMB} & \text{1.5RMB}
\end{matrix}$$
### 因幡奖
对于剩下来的金额，将会通过抽奖函数在**得分选手**中随机抽取若干名幸运观众进行分配。
```cpp
#include<bits/stdc++.h>
const unsigned N = , LastId = ;
const double Money = ;
const char W[] = "";
double P[N+3], Q[N+3], s, d, m, r, w; unsigned h, l; bool V[N+3];
int main(){
P[1] = 1,Q[1] = 1,s = 1,m = Money, l = strlen(W);
for(int i = 2;i <= N;++ i) P[i] = 1 / log(i),s += P[i]; d = 1.0 / ( s - 1 );
for(int i = 2;i <= N;++ i) Q[i] = Q[i - 1] - P[ i ] * d;
while(m > 1e-9) {
h ^= LastId , h ^= N , w = 0;
for(int i = 1;i <= l;++ i) {
h = h * 13331 + W[i - 1]; h = h << 13 | h >> 19;
}
w = fmod(h , s);
for(int i = 1;i <= N;++ i) if(w < Q[i] && !V[i]) {
printf("Number = [%d] ,money = [%.2lf]\n" , i, std::min(1.0 , m));
m -= 1.0 , V[i] = true; break;
} else w -= Q[i];
}
return 0;
}
```
其中， $N$ 表示参加比赛并得分的人数， $\mathit{ LastId}$ 是**本场比赛最后一次提交**的提交记录 $\text{id}$ ，$\mathit{Money}$ 是当前抽奖奖池内的钱数（如果某题目无人通过，奖金将会流入抽奖池内）。抽奖串 $W$ 由两部分组成，一是已经设定好的固定串，二是**在答疑贴里收集**，即每个用户都有更改 $W$ 的能力。具体如下：
- 用户可以发送形如 $\verb![abc123ABC]!$ 的字符串，满足它除去括号后仅由大小写字母、数字、空格组成，长度不超过 $20$。它会被拼接在 $W$ 的最后面。
- 初始时 $W$ 的值同样是一个合法的字符串。
比如甲乙丙三个用户，按照时间顺序分别发送了 $\verb![114514]!$ 、 $\verb![you ak SR]!$ 、 $\verb![www]!$ ，同时 $W$ 初始为 $\verb!windy round!$ ，那么最终 $W=\underline{\verb!windy round114514you ak SRwww!}$ 。
此外，可以证明，每个人的获奖权重是一个单调递减的函数，满足第一个人的权重为 $1$ ，最后一个人的权重为 $0$ 。你可以理解为，排名越靠前，越有可能获得奖金。
$W$ 初始串的长度为 $64$ ，其 $\text{SHA256}$ 值为：
$$\verb!9C6480AEDB950F150FFD19BB465385DF3570916035E54CCE5DDE3BF85F497AAD!$$
$\verb!upd 16.57:!$ 由于出题组的疏忽，透露了初始串，所以现在重新生成了一个 $\text{orz}$ 。保证不会再出锅了。
赛后会公布初始串，以及抽奖结果。有资格领取奖金的请在 $3$ 日内私信 @囧仙。
请以下排名的选手及时私信 @囧仙。由于囧仙账号不一定任何时候都有人在线，所以可能会延误一会儿……
```plain
Number = [29] ,money = [1.00]
Number = [12] ,money = [1.00]
Number = [19] ,money = [1.00]
Number = [8] ,money = [1.00]
Number = [9] ,money = [1.00]
Number = [21] ,money = [1.00]
Number = [7] ,money = [1.00]
Number = [39] ,money = [0.50]
```
## 鸣谢
感谢以下用户对本比赛的支持。顺序不分先后。
$$\begin{aligned}
\textbf{离散小波变换°} & : \text{本场比赛的主催，最大背锅人。} \cr
\textbf{Leasier} & : \text{出题人，出的题目迷之被选入了比赛。} \cr
\textbf{chenxinyang2006} & : \text{验题人，橄榄了原 std，然后被某题橄榄了。} \cr
\textbf{CSP\_Sept} & : \text{验题人。} \cr
\textbf{诱宵美⑨} & : \text{验题人。} \cr
\textbf{24KH} & : \text{验题人。} \cr
\textbf{NaOH\_Frog} & : \text{验题人，差点被橄榄了。} \cr
\textbf{cmdysj} & : \text{为本比赛提供了精神支持。}\cr
\textbf{囧仙} & : \text{东方大手子，为车万活动提供了很多帮助。}
\end{aligned}$$