首页 > 其他分享 >CF1876D Lexichromatography

CF1876D Lexichromatography

时间:2024-01-13 18:34:56浏览次数:32  
标签:pos CF1876D Lexichromatography vec 权值 序列 size 字典

CF1876D Lexichromatography

Luogu CF1876D

题目描述

给定一个长为 \(n\) 的序列 \(a\),你需要对这个序列进行红蓝染色。染色有如下要求:

  1. 每个位置恰好染上其中一种颜色。
  2. 对于所有的值 \(k\),在这个序列的任意子区间 \([l,r]\) 中,值为 \(k\) 且为红色的位置数 减去 值为 \(k\) 且为蓝色的位置数 的绝对值不超过 1。
  3. 如果按照位置顺序将所有红色的数排成序列 \(p\),蓝色的数排成序列 \(q\),那么 \(p\) 的字典序必须 严格大于 \(q\) 的字典序。

统计所有的合法染色方案数。对 998244353 取模。

\(1\le n,a_i\le 2\times 10^5\)。

Solution

不妨先看看每个条件等价于什么。对于条件 \(2\),将所有位置按照权值分类后,不难发现,同一颜色下的所有位置一定是两种颜色交替出现,否则一定不满足条件 \(2\)。对于条件 \(3\),先不管先后顺序,很明显可以先把两种颜色的序列找出来后比较字典序,根据字典序大小来确定颜色。那么条件 \(3\) 中的字典序严格大于即可转化为两个序列字典序不同。

考虑计数两个序列字典序相同的情况。显然如果有一个颜色出现次数为奇数就是不存在字典序相同的情况。否则考虑每种权值,将 \([p_{2i-1},p_{2i}]\) 看作一个区间(即第奇数个出现的位置和第偶数个出现的位置),那么可以得到若干个区间。考虑两个区间,如果两个区间存在包含关系,那么也一定不会存在字典序相同的情况,否则如果两个区间有交,那么这两个区间对应的权值的颜色方案就一定是确定的,所以使用并查集维护所有染色方案确定的权值,假设最后存在 \(\operatorname{cnt}\) 个连通块,那么答案就为 \(2^{\operatorname{cnt}}\)。

时间复杂度 \(\mathcal O(n\alpha(n))\)。

Code
int N, A[_N], maxn = 0, fa[_N], pw[_N];
int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
vector<int> pos[_N];
vector<pii> vec;
signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> N; pw[0] = 1;
    For(i, 1, N) {
        pw[i] = pw[i-1] * 2ll % mod;
        cin >> A[i];
        pos[A[i]].emplace_back(i);
        Max(maxn, A[i]);
    }
    bool flag = 0;
    int ans = 0;
    For(i, 1, maxn) if (!pos[i].empty()) {
        ++ans;
        flag |= pos[i].size() & 1;
        for (size_t j = 0; j < pos[i].size(); j += 2)
            vec.emplace_back(pos[i][j], pos[i][j+1]);
    }
    sort(vec.begin(), vec.end());
    for (size_t i = 1; i < vec.size(); ++i)
        if (vec[i].second < vec[i-1].second)
            flag = 1;
    if (flag) return cout << pw[ans-1] % mod << '\n', 0;
    int cnt = ans;
    iota(fa + 1, fa + maxn + 1, 1);
    for (size_t i = 1; i < vec.size(); ++i)
        if (vec[i].first < vec[i-1].second) {
            int fx = find(A[vec[i].first]), fy = find(A[vec[i-1].second]);
            if (fx == fy) continue;
            fa[fx] = fy, --cnt;
        }
    cout << (pw[ans-1] - pw[cnt-1] + mod) % mod << '\n';
}

标签:pos,CF1876D,Lexichromatography,vec,权值,序列,size,字典
From: https://www.cnblogs.com/hanx16msgr/p/17962714

相关文章

  • CF1876D Lexichromatography记录
    CF1876DLexichromatography题目链接:https://codeforces.com/problemset/problem/1876/D题意给一个$n$个数的数组$a$染色,每个元素被染为红色或蓝色。求满足下面两个条件的染色方案数:将蓝色和红色的数分别取出成为两个数列,则蓝色序列字典序小于红色序列。任意一个子数组......
  • CF1877F Lexichromatography
    题中的约束可以描述为:红的字典序比蓝大。对于每个数值,必然是红蓝交替涂色。设总共出现了\(c\)个颜色,总涂色方案数就是\(2^c\)种,其中字典序情况包含大于,小于,相等,且前两者方案数相同。所以不妨选取更简单的部分相等进行处理,设相等的方案数为\(x\),则答案就为\(\frac{1}......
  • CodeForces 1876D Lexichromatography
    洛谷传送门CF传送门这说明你的能力还不足以维持IM。显然balanced的充要条件是,对于每个值,染色一定是RB交替。然后一种值只会有先染红或先染蓝两种情况。然后还剩下字典序严格小于的条件。我场上的想法是枚举\(\text{LCP}\),然后推出来一个巨大麻烦做法,根本写不出来。但......