日记 - 伊埃斯的博客站

这个人因为获得了 $30$ 的性质分乐惨了。

上午

考 NOIp day2。

T1

一道绿的概率论，蛋柿没做出来。只打了 $30$ 的性质分，因此乐坏了，因为暴力都只有 $20$ 分。

T2

本来有很简单的 $O(nm \log n)$ 做法，蛋柿我没写，痛失 $30$ 分。

T3

打了 $30$ 分的暴力。

每道题都没有人打正解。总结：不会骗分。别人都骗分上 $100$ 了我还只有 $60$ 分。

下午

改题。

T1

首先，根据期望的线性性（没学过），有 $E(x) = \sum\limits_{i = 2}^n P_i + 1$ 。其中 $P_i$ 表示第 $i$ 堆棋子在第一堆之前取走的概率。经过一番推导，我们发现 $P_i$ 跟别的没关系，只跟 $a_i$ 和 $a_1$ 有关系，具体来说 $P_i = \frac{a_i}{a_1 + a_i}$ 。

T2

$O(nm \log n)$ 做法：循环每个 $x$ ，二分它的答案。如何把他变成正解：随机化。我们用随机的顺序遍历每个 $x \in [0,mod - 1]$ ，设 $F(x)$ 是 $x$ 的最优解。那么 $F(x)$ 比 $ans$ 小的 $x$ 的个数的期望是 $\sum\frac{1}{i} = \ln n$ 。那么每次循环到一个新的 $x$ ，就在 $x$ 的情况下 check(ans)。如果不行就 continue，可以就往下二分。时间复杂度 $O(nm + n \ln n \log n)$ 。

1
#include<bits/extc++.h>
2
#define inf 0x3f3f3f3f
3
using namespace std;
4
const int maxn = 1e5 + 5;
5
int n,mod,k;
6
int a[maxn],b[maxn],val[maxn];
7
bool apr[1005];
8
random_device seed;
9
inline void read(int &x)
10
{
11
    x = 0; int f = 1;
12
    char ch = getchar();
13
    while (!isdigit(ch)){f = ch == '-' ? -1 : 1; ch = getchar();}
14
    while (isdigit(ch)){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
15
    x *= f;
16
}
17
inline bool check(int mid)
18
{
19
    int sum = 0,cnt = 1;
20
    for (int i = 1; i <= n; i++)
21
    {
22
        if (b[i] > mid)
23
            return 0;
24
        sum += b[i];
25
        if (sum > mid)
26
        {
27
            cnt++;
28
            sum = b[i];
29
        }
30
    }
31
    return cnt <= k;
32
}
33
inline void cpy(int x)
34
{
35
    for (int i = 1; i <= n; i++)
36
        b[i] = (a[i] + x) % mod;
37
}
38
inline int bin()
39
{
40
    int l = 0,r = n * mod,mid,ret = inf;
41
    while (l <= r)
42
    {
43
        mid = (l + r) >> 1;
44
        if (check(mid))
45
        {
46
            ret = min(ret,mid);
47
            r = mid - 1;
48
        }
49
        else
50
            l = mid + 1;
51
    }
52
    return ret;
53
}
54
signed main()
55
{
56
    srand(seed());
57
    read(n),read(mod),read(k);
58
    for (int i = 1; i <= n; i++)
59
        read(a[i]);
60
    iota(val,val + mod,0);
61
    random_shuffle(val,val + mod);
62
    cpy(val[0]);
63
    int ans = bin();
64
    for (int i = 1; i < mod; i++)
65
    {
66
        cpy(val[i]);
67
        if (!check(ans - 1))
68
            continue;
69
        ans = min(ans,bin());
70
    }
71
    printf("%lld",ans);
72
    return 0;
73
}

吐槽：为啥模拟赛里会有随机化？？！

T3

没改，赛场上尝试想出正解，明显是不可能的。

祝老说了，如果能在这学期内，把 NOIp 的得分率稳定在 $60\%$ 以上，下学期就可以考省选了。~~感觉离退役不远了啊~~。

不管了，有紧迫感是好事。这学期才刚开始，好好努力。

Thanks for reading!

日记

周四 2月 20 2025

665 字 · 5 分钟

life 日记