日记 - 伊埃斯的博客站

你硕德对，蛋柿现在是日记时间。

洛谷讨论区昨天爆炸了，究其原因是洛谷国际站有人发 nc 内容，直接被罚了 $100$ 万。重要的是：

他的注册资本都才 $200$ 万。

然后今天早上来了一个 综合训练。其实就是 IOI 赛制的模拟赛，只不过有 $6$ 题，从做题的顺序来说吧。

Count The Bits↗

这道题是场切的，就是一道简单的不能再简单的数位 dp。还是说一下。

先想状态。设 $dp_{pos,cnt,p}$ 表示填到了第 $pos$ 位，总共有 $cnt$ 个 $1$ ，这个数 $\mod{k} = p$ 时的方案数。我们直接开始记搜。搜索边界就是当 $pos = b$ 时，如果 $p = 0$ 就 return cnt 否则 return 0。

放一下简单至极的代码：

1
#include<bits/extc++.h>
2
#pragma GCC optimize(2)
3
#pragma GCC target("avx")
4
using namespace std;
5
typedef long long ll;
6
const ll mod = 1000000009;
7
int k,b;
8
ll dp[130][130][1005];
9
ll dfs(int pos,int cnt,int p)
10
{
11
    if (~dp[pos][cnt][p])
12
        return dp[pos][cnt][p];
13
    if (pos == b)
14
        return p == 0 ? cnt : 0;
15
    ll ret = 0;
16
    for (int i = 0; i < 2; i++)
17
        ret = (ret + dfs(pos + 1,cnt + i,(p << 1 | i) % k)) % mod;
18
    return dp[pos][cnt][p] = ret;
19
}
20
signed main()
21
{
22
    scanf("%d%d",&k,&b);
23
    memset(dp,0xff,sizeof dp);
24
    printf("%lld",dfs(0,0,0));
25
    return 0;
26
}

之前考试有一道这样的题，但是那道题的 $k$ 很大，大到 $dp$ 数组存不下的地步，但是我们发现， $k$ 越大暴力越快。当 $dp$ 存不下时，我们就可以直接上暴力了。

Space Station↗

这道题也是一道搜索题。直接上记搜。但是我上午实在是太颓废了导致根本没有想这道题。

其实很简单。我们看 $a_i \le 50$ ，想到用桶。（其实我赛时想到的是 $\sum a_i \le 5 \times 10^6$ ，就存得下 $dp$ 数组，然后就这么的错了） $cnt_i$ 表示 $i$ 的出现次数。对 $cnt$ 算哈希用来记忆化。然后就这么做完了。

放下代码：

1
#include<bits/extc++.h>
2
#define int long long
3
using namespace std;
4
typedef unsigned long long ull;
5
const int maxn = 1e5 + 5;
6
const int mod = 1e9 + 7;
7
const int base = 97;
8
int n;
9
int cnt[55],cnt0,_max;
10
int a[maxn];
11
int fac[maxn];
12
__gnu_pbds::gp_hash_table<ull,int>dp;
13
void init(int up = 1e5)
14
{
15
    fac[0] = 1;
16
    for (int i = 1; i <= up; i++)
17
        fac[i] = fac[i - 1] * i % mod;
18
}
19
inline ull hsh()
20
{
21
    ull ret = 0;
22
    for (int i = 50; i >= 0; i--)
23
        ret = ret * base + cnt[i];
24
    return ret;
25
}
26
int dfs(int sum,int stp)
27
{//sum表示现在数字的和，stp表示还剩多少步
28
    if (!stp)//走完了就直接return
29
        return 1;
30
    if (sum >= _max)//如果现在的和已经大于最大的数了，那么剩下的随便走，有stp的阶乘种情况。
31
        return fac[stp];
32
    ull hs = hsh();//哈希
33
    int ret = 0;
34
    if (dp.find(hs) != dp.end())//如果搜过了
35
        return dp[hs];
36
    for (int i = 1; i <= sum; i++)
37
    {
38
        if (cnt[i])
39
        {
40
            cnt[i]--;
41
            ret = (ret + (cnt[i] + 1) * dfs(min(_max,sum + i),stp - 1) % mod) % mod;
42
            cnt[i]++;
43
        }
44
    }
45
    return dp[hs] = ret;//记忆化
46
}
47
signed main()
48
{
49
    ios::sync_with_stdio(0);
50
    cin.tie(0);
51
    cout.tie(0);
52
    init();
53
    cin >> n >> a[0];
54
    for (int i = 1; i <= n; i++)
55
    {
56
        cin >> a[i];
57
        cnt[a[i]]++;
58
        cnt0 += (a[i] == 0);
59
        _max = max(_max,a[i]);
60
    }
61
    int ans = dfs(a[0],n - cnt0);
62
    for (int i = n; i > n - cnt0; i--)
63
        ans = ans * i % mod;
64
    cout << ans;
65
    return 0;
66
}

Sum of Numbers↗

我们先感性理解，每一段肯定是长度差不多的。设 $len = \lfloor \frac{n}{k + 1} \rfloor$ ，那么每一段的长度肯定不会超过 $len$ ，我们就可以按照这个来 dp 了。

code:

1
#include<bits/extc++.h>
2
#pragma GCC optimize(2)
3
#pragma GCC optimize(3)
4
#pragma GCC target("avx")
5
#define int long long
6
using namespace std;
7
const int maxn = 2e5 + 5;//数组开小调了一下午
8
int n,k,len;
9
bool vis[maxn];
10
string s;
11
struct long_int//这个高精度真的写死人了
12
{
13
    static const int base = 1e18;
14
    static const int wid = 18;
15
    vector<int>val;
16
    long_int(int len = 0){val.resize(len,0);}
17
    long_int(const string &s)
18
    {
19
        int it = s.size();
20
        while ((it - wid) >= 0)
21
            val.push_back(stoll(s.substr(it -= wid,wid)));
22
        if (it > 0)
23
            val.push_back(stoll(s.substr(0,it)));
24
    }
25
    friend ostream &operator<<(ostream &out,const long_int &x)
26
    {
27
        if (x.val.empty())
28
            return out << '0';
29
        out << x.val.back();
30
        for (int i = x.val.size() - 2; i >= 0; i--)
31
            out << setw(wid) << setfill('0') << x.val[i];
32
        return out;
33
    }
34
    friend long_int operator+(const long_int &x,const long_int &y)
35
    {
36
        long_int ret(max(x.val.size(),y.val.size()));
37
        int f = 0,len = ret.val.size(),lenx = x.val.size(),leny = y.val.size();
38
        for (int i = 0; i < len; i++)
39
        {
40
            if (i >= lenx)
41
                ret.val[i] = y.val[i] + f;
42
            else if (i >= leny)
43
                ret.val[i] = x.val[i] + f;
44
            else
45
                ret.val[i] = x.val[i] + y.val[i] + f;
46
            if (ret.val[i] >= base)
47
            {
48
                f = ret.val[i] / base;
49
                ret.val[i] %= base;
50
            }
51
            else
52
                f = 0;
53
        }
54
        if (f)
55
            ret.val.push_back(f);
56
        return ret;
57
    }
58
    friend bool operator<(const long_int &x,const long_int &y)
59
    {
60
        if (x.val.size() ^ y.val.size())
61
            return x.val.size() < y.val.size();
62
        for (int i = x.val.size() - 1; i >= 0; i--)
63
            if (x.val[i] ^ y.val[i])
64
                return x.val[i] < y.val[i];
65
        return 0;
66
    }
67
}dp[maxn];
68
void solve()
69
{
70
    cin >> n >> k >> s;
71
    fill(vis + 1,vis + n + 1,0);
72
    len = n / (k + 1) + 2;
73
    for (int x = 0; x <= k; x++)
74
    {
75
        for (int i = n; i >= max(1ll,n - len * (k - x)); i--)
76
        {
77
            for (int j = max(0ll,i - len); j <= min(x * len,i - 1); j++)
78
            {
79
                if (!j || vis[j])
80
                {
81
                    long_int tmp = dp[j] + s.substr(j,i - j);
82
                    if (!vis[i] || tmp < dp[i])
83
                    {
84
                        dp[i] = tmp;
85
                        vis[i] = 1;
86
                    }
87
                }
88
            }
89
        }
90
    }
91
    cout << dp[n] << '\n';
92
}
93
signed main()
94
{
95
    ios::sync_with_stdio(0);
96
    cin.tie(0);
97
    cout.tie(0);
98
    int t;
99
    cin >> t;
100
    while (t--)
101
        solve();
102
    return 0;
103
}

然后颓废的一天就这么的结束了。今天晚上好像高三的返校，而我们比他们早一天返校，我们还跟他们一起放假。

比高三的放的还短，这辈子有了

Thanks for reading!

日记

周日 2月 09 2025

1266 字 · 10 分钟

life 日记