专栏文章

省队集训-0419试机赛

aallenchoi
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip5msu0
此快照首次捕获于
2025/12/03 06:33
3 个月前
此快照最后确认于
2025/12/03 06:33
3 个月前
查看原文

A.石堆分裂

题意：

初始时有一个共 nn 个石子的石堆。给定 mm，一次操作时，假设有 kk 个石堆，大小为 a1...ka_{1...k}，可以指定 b1...kb_{1...k}，满足 0≤bi≤ai,∑bi≤m0\le b_i\le a_i,\sum b_i\le m，然后把第 ii 堆分裂成 bi,ai−bib_i,a_i-b_i 两堆，大小为 00 的当作不存在。求分裂出 nn 个大小为 11 的石堆所需的最小操作次数。
多组测试，T≤103,n≤m≤109T\le10^3,n\le m\le10^9。

Sol：

假设要分裂 xx 次，则相当于要给 nn 个石子都赋一个 [0,2x)[0,2^x) 的编号，每一位表示在这一次操作中这颗石子是分到 bib_i 一堆还是 ai−bia_i-b_i 一堆，要求这些编号两两不同，且每一位 11 的数量都不超过 mm。
考虑二分答案。按照 popcount 贪心，从小到大填入。popcount 相同的数，如果填不够 nn 个，给每一位的贡献都是相同的，即 (x−1i−1)\binom{x-1}{i-1}；否则可以把 11 均摊到每一位，这样一定最优。
复杂度 O(Tlog⁡2n)O(T\log^2n)。

Code：

CPP
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,n,m;
bool check(int x)
{
    ll sum = 0,cnt = 0,c1 = 1,c2 = 1;
    for(int i = 0;i <= x;i++)
    {
        if(i) c1 = c1 * (x - i + 1) / i;
        if(i > 1) c2 = c2 * (x - i + 1) / (i - 1);
        if(sum + c1 >= n) return cnt + (i ? ((n - sum) * i + x - 1) / x : 0) <= m;
        sum += c1,cnt += (i ? c2 : 0);
        if(cnt > m) return false;
    }
    return false;
}
int main()
{
    freopen("split.in","r",stdin);
    freopen("split.out","w",stdout);
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        int l = -1,r = n,mid;
        while(r - l > 1)
        {
            mid = (l + r) / 2;
            if(check(mid)) r = mid;
            else l = mid;
        }
        printf("%d\n",r);
    }
    return 0;
}

白：

题意：

有一个排列，可以执行一次操作：选择若干个不交的区间，然后把区间里的数从小到大排序。也可以选择什么都不做。问可以得到多少本质不同的排列。
n≤2×105,mod=998244353n\le 2\times10^5,mod=998244353。

Sol：

相当于把排列划成若干段，每一段排序。由于要求本质不同，我们要求划出来的区间都是极小的，即每一段都不存在一个分界点，使得左边最大值小于右边最小值。
设 fif_i 表示 [1,i][1,i] 的答案。可以把合法的段都拿出来，然后 O(n2)O(n^2) DP。考虑优化。
设 xx 为 ii 之前最靠后的小于 pip_i 的位置，则 (x,i](x,i] 都可以是 ii 这一段的左端点；yy 为 xx 之前最靠后的大于 pip_i 的位置，则 (y,x](y,x] 处都不能是左端点。
考虑 yy 之前的点作为左端点，充要条件为 [l,y][l,y] 中不存在一个分界点，使得 [l,mid][l,mid] 的最大值小于 (mid,i](mid,i] 的最小值。设 zz 为 [y,x][y,x] 内 pp 最小值的位置，发现 (z,i](z,i] 都大于 pzp_z，所以 ii 的合法左端点对于 zz 而言都是合法的，但反过来不一定，因为 zz 的合法左端点可能会落在 (y,z](y,z] 中。由于 [y,z)[y,z) 都大于 pzp_z，所以可以确定 (y,z](y,z] 都可以转移到 fzf_z。因此我们让 fif_i 加上 fzf_z 再减掉 (y,z](y,z] 处带来的贡献即可。
树状数组维护，单点修改区间和，O(nlog⁡n)O(n\log n)。

Code：

CPP
#include <bits/stdc++.h>
#define lb(x) ((x) & (-(x)))
using namespace std;
const int N = 2e5 + 5,mod = 998244353;
int n,p[N],q[N],f[N],lst1[N],lst2[N],st[N][20];
set <int> s;
set <int> :: iterator it;
bool cmp(int x,int y){return p[x] < p[y];}
struct Bit
{
    int s[N];
    void update(int x,int v){for(int i = x;i <= n;i += lb(i)) s[i] = (s[i] + v) % mod;}
    int query(int x)
    {
        int ret = 0;
        for(int i = x;i;i -= lb(i)) ret = (ret + s[i]) % mod;
        return ret;
    }
} tr;
int main()
{
    freopen("bai.in","r",stdin);
    freopen("bai.out","w",stdout);
    scanf("%d",&n);
    for(int i = 1;i <= n;i++) scanf("%d",&p[i]);
    for(int i = 1;i <= n;i++) q[i] = i;
    sort(q + 1,q + n + 1,cmp);
    for(int i = 1;i <= n;i++)
    {
        it = s.lower_bound(q[i]);
        if(it != s.begin()) lst1[q[i]] = (*prev(it));
        s.insert(q[i]);
    }
    s.clear();
    for(int i = n;i >= 1;i--)
    {
        it = s.lower_bound(lst1[q[i]]);
        if(it != s.begin()) lst2[q[i]] = (*prev(it));
        s.insert(q[i]);
    }
    for(int i = 1;i <= n;i++) st[i][0] = i;
    for(int j = 1;j < 20;j++)
        for(int i = 1,x,y;i + (1 << j) - 1 <= n;i++)
        {
            x = st[i][j - 1],y = st[i + (1 << (j - 1))][j - 1];
            st[i][j] = (p[x] < p[y] ? x : y);
        }
    f[0] = 1;
    tr.update(1,1);
    for(int i = 1;i <= n;i++)
    {
        f[i] = (tr.query(i) - tr.query(lst1[i]) + mod) % mod;
        if(lst2[i])
        {
            int l = lst2[i] + 1,r = lst1[i],t = (int)__lg(r - l + 1),x = st[l][t],y = st[r - (1 << t) + 1][t],m = (p[x] < p[y] ? x : y);
            f[i] = (f[i] + f[m]) % mod;
            f[i] = (f[i] - tr.query(m) + mod) % mod;
            f[i] = (f[i] + tr.query(lst2[i])) % mod;
        }
        tr.update(i + 1,f[i]);
    }
    printf("%d\n",f[n]);
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...