AtCoder Beginner Contest 214

https://atcoder.jp/contests/abc214

E - Packing Under Range Regulations

题意

有 $10^9$ 个盒子，每个盒子可以放一个小球。现在要求将 $n$ 个球放入盒子内，第 $i$ 个球要放在 $l_i$ 到 $r_i$ 个盒子内。要求判断是否可行。

数据范围：$1\leq n\leq 2\times10^5$。

题解

先考虑朴素的做法：枚举每个盒子 $i$，将左端点为 $i$ 的球加入候选列表中，将候选列表中右端点最小的球放入该盒子，判断此时列表中右端点最小的是否仍大于 $i$，若满足则枚举下一个盒子，否则无解。

候选列表可以用优先队列维护。在枚举时，每当优先队列为空，可以从 $i$ 直接跳到下一个球的左端点，这样时间复杂度就对了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        set<int> s;
        priority_queue<int,vector<int>,greater<int>> pq;
        map<int,vector<int>> mp;
        int n;cin>>n;
        for(int i=1;i<=n;i++)
        {
            int l,r;cin>>l>>r;
            s.insert(l);
            mp[l].push_back(r);
        }
        s.insert(1000000001);
        int i=(*s.begin());
        while(i<=1000000000)
        {
            if(mp.count(i))
            {
                for(auto j:mp[i]) pq.push(j);
            }
            pq.pop();
            if(pq.empty()) i=(*s.upper_bound(i));
            else 
            {
                if(pq.top()<=i) break;
                else i++;
            }
        }
        cout<<(pq.empty()?"Yes":"No")<<'\n';
    }
    return 0;
}

F - Substrings

题意

给定一个字符串 $s$，现在可以删除一些不相邻的位置，求可能得到的本质不同字符串的数量。答案对 $10^9+7$ 取模。

数据范围：$1\leq |s|\leq 2\times10^5$。

题解

考虑一个经典问题：求一个字符串的本质不同子序列的个数。记 $f_i$ 表示前 $i$ 个字符，第 $i$ 个字符必须选的方案数。那么有

$$f_i=\sum_{j=0}^{i-1}f_j$$

但这样会有重复。记 $k$ 为第 $i$ 个字符前一次出现的位置，则

$$f_i=\sum_{j=k}^{i-1}f_j$$

这就没有问题了，因为 $k$ 以前的位置添加 $s_i$ 和添加 $s_k$ 是一致的，这些方案已经在 $f_k$ 中了。使用前缀和优化可以做到 $O(n)$。然后稍微修改一下转移方程就可以通过本题。

不过也有一种不需要前缀和优化的做法，以本题为例：记 $f_{i,j}$ 表示考虑前 $i$ 个位置，最后一个字符为 $j$ 的方案数。那么有

$$f_{i,j}= \begin{cases} f_{i-1,j} &s_i\neq j\\ \sum f_{i-2,k}+1 &s_i=j \end{cases}$$

即每次转移时，我们只使用每个字符最后一次出现的位置，这显然也是不会重复的。时间复杂度为 $O(26n)$。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int p=1e9+7;
int f[N][26];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;cin>>s;
    int n=(int)s.size();
    f[0][s[0]-'a']=1;
    for(int i=1;i<n;i++)
        for(int j=0;j<26;j++)
            if((int)(s[i]-'a')==j) 
            {
                f[i][j]++;
                if(i>1) 
                {
                    for(int k=0;k<26;k++) f[i][j]=(f[i][j]+f[i-2][k])%p;
                }
            }
            else f[i][j]=f[i-1][j];
    int ans=0;
    for(int i=0;i<26;i++) ans=(ans+f[n-1][i])%p;
    cout<<ans<<'\n';
    return 0;
}

G - Three Permutations

题意

给定两个长度为 $n$ 的排列 $p$ 和 $q$，求满足条件的排列 $r$ 的数量：$\forall i\in [1,n],r_i\neq p_i,r_i\neq q_i$。

数据范围：$1\leq n\leq 3000$。

题解

首先考虑容斥，即计算 $f_i$ 为钦定 $i$ 个位置不符合条件的方案数，那么剩余的位置可以任意填，则最终的答案为

$$\sum_{i=0}^n(-1)^if_i(n-i)!$$

考虑计算 $f_i$，我们将每对 $p_i,q_i$ 连一条边，那么就得到了一些环，显然可以逐个环进行考虑。

我们考虑对于一个大小为 $n$ 的环，钦定 $k$ 个位置不符合条件的方案数。在图上，钦定一个位置不符合条件即选择一条边并选择这条边的一个端点。我们可以将一条边拆成两条边 $(u,w),(w,v)$ 选择 $(u,w)$ 即代表选择了边 $(u,v)$ 并选择了点 $u$，后者也是同理。那么问题就变成了有 $2n$ 个物品呈环形排列，选择不相邻的 $k$ 个，求方案数。

考虑 $m$ 个物品排成一条链时选择不相邻的 $k$ 个，这是一个经典问题，可以用插板法解决，答案是 $\dbinom{m-k+1}{k}$。那么回到上面的问题，若选择第一个物品，则第二个和最后一个不能选，剩下 $2n-3$ 个物品排成一条链选择 $k-1$ 个，方案数为 $\dbinom{2n-k-1}{k-1}$；若不选择第一个物品，则剩下 $2n-1$ 个物品排成一条链选择 $k$ 个，方案数为 $\dbinom{2n-k}{k}$。所以最终的方案数为 $\dbinom{2n-k}{k}+\dbinom{2n-k-1}{k-1}$。注意大小为 $1$ 的环方案数为 $1$。

于是我们依次枚举每个环，利用它更新总的方案数就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=6005;
const int p=1e9+7;
ll fac[N],ifac[N];
void init()
{
    fac[0]=ifac[0]=ifac[1]=1;
    for(int i=1;i<N;i++) fac[i]=i*fac[i-1]%p;
    for(int i=2;i<N;i++) ifac[i]=(p-p/i)*ifac[p%i]%p;
    for(int i=2;i<N;i++) ifac[i]=ifac[i]*ifac[i-1]%p;
}
ll C(ll n,ll m)
{
    if(n<m) return 0;
    return fac[n]*ifac[m]%p*ifac[n-m]%p;
}
int a[N],b[N],fa[N],siz[N];
int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int x,int y)
{
    x=find(x),y=find(y);
    if(x==y) return;
    fa[x]=y;
    siz[y]+=siz[x];
}
ll f[N];
ll solve(int n,int k)
{
    if(n==1) return 1;
    return (C(2*n-k,k)+C(2*n-k-1,k-1))%p;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1;
    for(int i=1;i<=n;i++) merge(a[i],b[i]);
    f[0]=1;
    for(int i=1;i<=n;i++)
        if(i==find(i))
        {
            for(int j=n-1;j>=0;j--)
                for(int k=1;k<=min(siz[i],n-j);k++) f[j+k]=(f[j+k]+f[j]*solve(siz[i],k))%p;
        }
    int op=1;
    ll ans=0;
    for(int i=0;i<=n;i++) 
    {
        ans=(ans+op*f[i]*fac[n-i]%p+p)%p;
        op*=-1;
    }
    cout<<ans<<'\n';
    return 0;
}