526互联

胡测5 (by gtm1514)

发布时间 2023-04-20 21:04:01作者: KafuuChinocpp

T1 记得对拍

首先有一个结论：如果 \(x\) 在序列中存在一个位置是对拍的，那么 \(x\) 在序列上对应一段连续的区间。

证明：考虑将不在这个区间内对拍的数 \(x\) 插入到区间内，那么这个数的贡献 \(+1\) ，而两边的贡献最多 \(-1\) ，答案不会变劣。

因此每种数字要么全部放在一起对拍，要么每个均不对拍。

可以这样理解，首先将每个数按照从小到大排序，每次可以将一种数字拆成不连续的散点，每个散点插入到两个对拍相等段之间会产生 \(1\) 的贡献，具体的我们从大到小考虑每种数，设当前数出现次数为 \(cnt\) ，当前考虑的数可以作为一段连续的对拍相等段，贡献为 \(cnt-1\) ，可以完全拆掉后插入到不同的对拍相等段之间，贡献为 \(cnt\) ，发现不完全拆掉贡献为 \(cnt-1\) ，一定不优，因此忽略这种情况。

于是现在题目转化为给定一个序列 \(a\) ，从小到大依次遍历每个位置，维护变量 \(x\) ，每次可以选择使得 \(x+1\to x\) ，可以选择 \(x-a_i\to x\) ，但需要保证任意时刻 \(x\ge 0\) ，求解最多减几次，只需要做可反悔贪心即可。

code

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int max1 = 2e6;
const int inf = 0x3f3f3f3f;
int T, n, a[max1 + 5], save[max1 + 5], len;
int bin[max1 + 5];
priority_queue < int, vector <int>, less <int> > que;
void Work ()
{
    scanf("%d", &n);
    for ( int i = 1; i <= n; i ++ )
        scanf("%d", &a[i]), save[i] = a[i];
    sort(save + 1, save + 1 + n);
    len = unique(save + 1, save + 1 + n) - ( save + 1 );
    for ( int i = 1; i <= len + 1; i ++ )
        bin[i] = 0;
    for ( int i = 1; i <= n; i ++ )
        a[i] = lower_bound(save + 1, save + 1 + len, a[i]) - save, ++bin[a[i]];
    while ( !que.empty() )
        que.pop();
    int ans = 0, x = 0;
    for ( int i = len - 1; i >= 1; i -- )
    {
        x -= bin[i];
        que.push(bin[i]);
        ++ans;
        while ( x < 0 && !que.empty() )
        {
            x += que.top() + 1;
            que.pop();
            --ans;
        }
    }
    ans += n - len + 1;
    printf("%d\n", ans);
    return;
}
int main ()
{
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    scanf("%d", &T);
    while ( T -- )
        Work();
    return 0;
}

T2 三好学生

考虑将 \(p<k\) 的情况转化为 \(p\ge k\) 的情况，考虑一个人给对应的学生投票等价于他给其他学生投反票，也就是让其他学生的 \(a_i-1\to a_i\) ，此时每个人有 \(n-k\) 张票，我们令 \(-a_i\to a_i\) ，每次操作仍然令 \(a_i+1\to a_i\) ，取票数最多 \(n-p\) 个学生淘汰，这样转化与原先操作相同，并且相当于 \(n-k\to k,n-p\to p\) ，此时一定有 \(p>k\) ，可以按照 \(p\ge k\) 的情况考虑。

因此我们只考虑 \(p\ge k\) 的情况，发现此时每个人的决策一定是给当前 \(S\) 集合中票数最小的 \(k\) 个人依次投票，容易发现此时判断一个集合 \(S\) 的合法条件：设 \(Min\) 为 \(S\) 集合内的最小值， \(Max\) 为不在 \(S\) 中元素的最大值，当 \(Min+m\ge Max\) 并且 \(\sum_{i\in s}\max(0,Max-a_i)\le mk\) 是当前集合合法。

考虑枚举不在 \(S\) 中元素的最大值 \(Max\) ，那么对于所有大于 \(Max\) 的元素，一定在 \(S\) 集合中并且不需要接受投票，对于值域位于 \([Max-m,Max]\) 的数，我们需要求解数组 \(f_{i,j}\) 表示总共选择了 \(i\) 个数， \(i\) 个数的和为 \(j\) 的方案数，发现这是一个简单的背包 dp ，由于 dp 可以支持插入和删除，因此可以从小到大枚举 \(Max\) 并用单调指针维护值域位于 \([Max-m,Max]\) 的数所对应的 \(f\) ，通过 \(f\) ，我们可以解决集合大小 \(p\ge k\) 和 \(\sum_{i\in s}\max(0,Max-a_i)\le mk\) 的限制，时间复杂度为 \(O(n^2\sum a_i)\) 。

code

#include <cstdio>
#include <algorithm>
using namespace std;
const int max1 = 200;
const int mod = 998244353;
int n, m, k, lim, bin[max1 + 5];
int cnt, sum, f[max1 + 5][max1 * max1 + 5];
void Add ( int &x, int y )
{
    x = x + y;
    if ( x >= mod )
        x = x - mod;
    return;
}
void Insert ( int x )
{
    for ( int i = cnt; i >= 0; i -- )
        for ( int j = 0; j <= sum; j ++ )
            Add(f[i + 1][j + x], f[i][j]);
    ++cnt;
    sum += x;
    return;
}
void Delete ( int x )
{
    --cnt;
    sum -= x;
    for ( int i = 0; i <= cnt; i ++ )
        for ( int j = 0; j <= sum; j ++ )
            Add(f[i + 1][j + x], mod - f[i][j]);
    return;
}
int Solve ( int Max, int lim )
{
    int res = 0;
    for ( int i = lim; i <= cnt; i ++ )
    {
        int down = max(0, Max * i - m * k);
        for ( int k = down; k <= sum; k ++ )
            Add(res, f[i][k]);
    }
    return res;
}
int main ()
{
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &k);
    for ( int i = 1, val; i <= n; i ++ )
        scanf("%d", &val), ++bin[val];
    lim = 0;
    for ( int i = 1; i <= max1; i ++ )
        lim += i * bin[i];
    for ( int i = 0; i <= n; i ++ )
        for ( int j = 0; j <= lim; j ++ )
            f[i][j] = 0;
    cnt = sum = 0;
    f[0][0] = 1;
    int L = 1, ans = 0;
    for ( int Max = 1; Max <= max1; Max ++ )
    {
        while ( L < Max - m )
        {
            for ( int i = 1; i <= bin[L]; i ++ )
                Delete(L);
            ++L;
        }
        int base = 0;
        for ( int i = Max + 1; i <= max1; i ++ )
            base += bin[i];
        for ( int i = 1; i <= bin[Max]; i ++ )
        {
            ans = ( ans + Solve(Max, max(0, k - ( bin[Max] - i + base ))) ) % mod;
            Insert(Max);
        }
    }
    for ( int i = 1; i <= max1 >> 1; i ++ )
        swap(bin[i], bin[max1 - i + 1]);
    k = n - k;
    lim = 0;
    for ( int i = 1; i <= max1; i ++ )
        lim += i * bin[i];
    for ( int i = 0; i <= n; i ++ )
        for ( int j = 0; j <= lim; j ++ )
            f[i][j] = 0;
    cnt = sum = 0;
    f[0][0] = 1;
    L = 1;
    for ( int Max = 1; Max <= max1; Max ++ )
    {
        while ( L < Max - m )
        {
            for ( int i = 1; i <= bin[L]; i ++ )
                Delete(L);
            ++L;
        }
        int base = 0;
        for ( int i = Max + 1; i <= max1; i ++ )
            base += bin[i];
        for ( int i = 1; i <= bin[Max]; i ++ )
        {
            ans = ( ans + Solve(Max, max(0, k + 1 - ( bin[Max] - i + base ))) ) % mod;
            Insert(Max);
        }
    }
    ans = ( ans + 1 ) % mod;
    printf("%d\n", ans);
    return 0;
}

T3 括号序列

考虑如何让选出的位置尽量多，发现答案的上解为 \(n\) ，考虑构造这样一组解，假设当前括号序列最外层只有一个括号匹配，那么当前括号匹配可以选择左括号或右括号，发现确定当前选择的方向后，括号匹配内部的所有括号匹配均可以选择并且方案唯一，简单推广，设当前最外层括号匹配的个数为 \(cnt\) ，那么当前括号序列的权值为 \(cnt+1\) ，因此可以用线段树简单维护，复杂度 \(O(nlogn)\) 。

code

#include <cstdio>
#include <algorithm>
using namespace std;
const int max1 = 1e6;
const int mod = 998244353;
int n, q;
char bracket[max1 + 5];
struct Data
{
    int cntL, cntR, sum;
    Data () {}
    Data ( int __cntL, int __cntR, int __sum )
        { cntL = __cntL, cntR = __cntR, sum = __sum; }
    Data operator + ( const Data &A ) const
    {
        Data res;
        res = Data(0, 0, 0);
        res.cntL = cntL;
        res.cntR = A.cntR;
        if ( cntR && A.cntL )
        {
            if ( cntR < A.cntL )
            {
                res.cntL += A.cntL - cntR;
                res.sum = A.sum;
            }
            else if ( cntR > A.cntL )
            {
                res.cntR += cntR - A.cntL;
                res.sum = sum;
            }
            else
            {
                res.sum = sum + A.sum + 1;
            }
        }
        else if ( cntR && !A.cntL )
        {
            res.cntR += cntR;
            res.sum = sum;
        }
        else if ( !cntR && A.cntL )
        {
            res.cntL += A.cntL;
            res.sum = A.sum;
        }
        else
            res.sum = sum + A.sum;
        return res;
    }
};
struct Segment_Tree
{
    #define lson(now) ( now << 1 )
    #define rson(now) ( now << 1 | 1 )
    struct Struct_Segment_Tree
        { Data val[2]; bool rev; } tree[max1 * 4 + 5];
    void Push_Up ( int now )
    {
        tree[now].val[0] = tree[lson(now)].val[0] + tree[rson(now)].val[0];
        tree[now].val[1] = tree[lson(now)].val[1] + tree[rson(now)].val[1];
        return;
    }
    void Update ( int now )
    {
        swap(tree[now].val[0], tree[now].val[1]);
        tree[now].rev ^= 1;
        return;
    }
    void Push_Down ( int now )
    {
        if ( tree[now].rev )
        {
            Update(lson(now));
            Update(rson(now));
            tree[now].rev = false;
        }
        return;
    }
    void Build ( int now, int L, int R )
    {
        tree[now].rev = false;
        if ( L == R )
        {
            if ( bracket[L] == '(' )
            {
                tree[now].val[0] = Data(0, 1, 0);
                tree[now].val[1] = Data(1, 0, 0);
            }
            else
            {
                tree[now].val[0] = Data(1, 0, 0);
                tree[now].val[1] = Data(0, 1, 0);
            }
            return;
        }
        int mid = L + R >> 1;
        Build(lson(now), L, mid);
        Build(rson(now), mid + 1, R);
        Push_Up(now);
        return;
    }
    void Insert ( int now, int L, int R, int ql, int qr )
    {
        if ( L >= ql && R <= qr )
            return Update(now);
        Push_Down(now);
        int mid = L + R >> 1;
        if ( ql <= mid )
            Insert(lson(now), L, mid, ql, qr);
        if ( qr > mid )
            Insert(rson(now), mid + 1, R, ql, qr);
        Push_Up(now);
        return;
    }
    int Query ()
    {
        if ( !tree[1].val[0].cntL && !tree[1].val[0].cntR )
            return tree[1].val[0].sum + 1;
        return 114514;
    }
}Tree;
int main ()
{
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    scanf("%d%d%s", &n, &q, bracket + 1);
    n = n << 1;
    Tree.Build(1, 1, n);
    int L, R, ans;
    ans = 1;
    while ( q -- )
    {
        scanf("%d%d", &L, &R);
        Tree.Insert(1, 1, n, L, R);
        ans = 1LL * ans * Tree.Query() % mod;
    }
    printf("%d\n", ans);
    return 0;
}