伊埃斯的小站
日记

日记

Thu Feb 20 2025
5 分钟
life 日记
697 字

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

上午#

考 NOIp day2。

T1#

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

T2#

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

T3#

打了 3030 分的暴力。

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

下午#

改题。

T1#

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

T2#

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

CPP
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/extc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 1e5 + 5;
int n,mod,k;
int a[maxn],b[maxn],val[maxn];
bool apr[1005];
random_device seed;
inline void read(int &x)
{
    x = 0; int f = 1;
    char ch = getchar();
    while (!isdigit(ch)){f = ch == '-' ? -1 : 1; ch = getchar();}
    while (isdigit(ch)){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
    x *= f;
}
inline bool check(int mid)
{
    int sum = 0,cnt = 1;
    for (int i = 1; i <= n; i++)
    {
        if (b[i] > mid)
            return 0;
        sum += b[i];
        if (sum > mid)
        {
            cnt++;
            sum = b[i];
        }
    }
    return cnt <= k;
}
inline void cpy(int x)
{
    for (int i = 1; i <= n; i++)
        b[i] = (a[i] + x) % mod;
}
inline int bin()
{
    int l = 0,r = n * mod,mid,ret = inf;
    while (l <= r)
    {
        mid = (l + r) >> 1;
        if (check(mid))
        {
            ret = min(ret,mid);
            r = mid - 1;
        }
        else
            l = mid + 1;
    }
    return ret;
}
signed main()
{
    srand(seed());
    read(n),read(mod),read(k);
    for (int i = 1; i <= n; i++)
        read(a[i]);
    iota(val,val + mod,0);
    random_shuffle(val,val + mod);
    cpy(val[0]);
    int ans = bin();
    for (int i = 1; i < mod; i++)
    {
        cpy(val[i]);
        if (!check(ans - 1))
            continue;
        ans = min(ans,bin());
    }
    printf("%lld",ans);
    return 0;
}

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

T3#

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

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

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