2023 (ICPC) Jiangxi Provincial Contest -- Official Contest

https://codeforces.com/gym/104385

D. Stack Out

题意

有 $n$ 个数，每次可以将第一个数入栈，或者将栈顶元素出栈。求最大连续出栈次数不小于 $k$ 的方案数。

题解

我们这样考虑，每当一个元素压入栈以后，紧跟着就是出栈操作（可能是 $0$ 次），这样每次可能的出栈操作次数只与当前栈内的元素个数有关，由此可以设计状态进行dp。

设 $f_{i,j,0/1}$ 表示 $i$ 个数入栈，$j$ 个数出栈，不合法/合法的方案数。

当 $j<k$ 时，

$$\begin{aligned} f_{i,j,0}&=\sum_{t=0}^jf_{i-1,t,0}\\ f_{i,j,1}&=0 \end{aligned}$$

当 $j\geq k$ 时，

$$f_{i,j,0}=\sum_{t=j-k+1}^jf_{i-1,t,0}\\ f_{i,j,1}=\sum_{t=0}^{j-k}f_{i-1,t,0}+\sum_{t=0}^jf_{i-1,t,1}$$

可以利用前缀和优化转移。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3005;
const int p=998244353;
ll f[N][N][2];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;cin>>n>>k;
    f[0][0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(j>=k) 
            {
                f[i][j][0]=(f[i-1][j][0]-f[i-1][j-k][0]+p)%p;
                f[i][j][1]=(f[i-1][j-k][0]+f[i-1][j][1])%p;
            }
            else f[i][j][0]=f[i-1][j][0];
        }
        for(int j=1;j<=i;j++) 
        {
            f[i][j][0]=(f[i][j][0]+f[i][j-1][0])%p;
            f[i][j][1]=(f[i][j][1]+f[i][j-1][1])%p;
        }
    }
    cout<<f[n][n][1]<<'\n';
    return 0;
}

F. Cities

题意

有 $n$ 座城市，$n$ 为偶数。现在，要建立 $\dfrac{n}{2}$ 对关系，每对城市只能处在一个关系中。若 $(i,j)$ 建立了关系，则需要在 $(i,i+1),(i+1,i+2),\cdots,(j-1,j)$ 间各铺设一条道路。所有城市处在一条直线上，第 $i$ 个城市在 $x_i$ 处，第 $i$ 个城市和第 $i+1$ 个城市间最多铺设 $s_i$ 条道路。求所有方案的道路长度之和。

题解

考虑dp。设 $f_{i,j}$ 为前 $i$ 个城市中 $j$ 个城市未建立关系的方案数，$g_{i,j}$ 为前 $i$ 个城市中 $j$ 个城市未建立关系的所有方案中前 $i$ 个城市间的总贡献。此时，$s_i$ 就相当于是对 $j$进行了限制。城市 $i$ 与 $i+1$ 间铺设的道路数量同样取决于 $j$。（因为每个未建立关系的城市在与后面的城市建立关系后，铺设的道路一定包含了 $(i,i+1)$。）

转移时考虑第 $i+1$ 个城市，它可能未建立关系，也可能与前面某个未建立关系的城市建立关系。它与不同的城市建立关系，贡献是不同的。但我们的状态考虑的是城市间铺设了多少条道路，这样就可以转移了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2005;
const int p=998244353;
int x[N],s[N];
ll f[N][N],g[N][N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>x[i];
    for(int i=1;i<n;i++) cin>>s[i];
    f[0][0]=1;
    for(int i=0;i<n;i++)
        for(int j=0;j<=s[i];j++)
        {
            if(j+1<=s[i+1]) 
            {
                f[i+1][j+1]=(f[i+1][j+1]+f[i][j])%p;
                g[i+1][j+1]=(g[i+1][j+1]+g[i][j]+f[i][j]*j%p*abs(x[i+1]-x[i]))%p;
            }
            if(j)
            {
                f[i+1][j-1]=(f[i+1][j-1]+f[i][j]*j)%p;
                g[i+1][j-1]=(g[i+1][j-1]+g[i][j]*j+f[i][j]*j%p*j%p*abs(x[i+1]-x[i]))%p;
            }
        }
    cout<<g[n][0]<<'\n';
    return 0;
}

H. Permutation

题意

给定一个长度为 $n$ 的排列，$n$ 为偶数。将前 $\dfrac{n}{2}$ 个数记作序列 $A$，后 $\dfrac{n}{2}$ 个数记作序列 $B$，进行如下操作：

• 若 $A,B$ 均为空，停止操作。
• 若 $A,B$ 中仅有一个非空，将非空序列的第一个元素放入序列 $P$ 的末尾。
• 若 $A,B$ 均非空，将 $A,B$ 的第一个元素中较小的那个放入序列 $P$ 的末尾。

显然，最终得到的 $P$ 也是一个排列。

现在给出一个排列 $P$，问是否存在一个排列，经操作后能够得到排列 $P$。

题解

考虑 $p_i$ 和它后面第一个比它大的数 $p_j$，容易发现 $p_i,p_{i+1},\cdots,p_{j-1}$ 一定是某个序列的连续的一段。我们可以据此将序列 $P$ 划分为若干个段，段内的元素一定同属于一个序列，段与段之间没有限制。我们要判断是否存在一种划分方式，使得两个序列的包含的段长度之和均为 $\dfrac{n}{2}$。

这是一个多重背包问题。需要注意的是，所有段长之和为 $n$，所以本质不同的段长只有 $O(\sqrt{n})$ 个，利用单调队列优化多重背包可以在 $O(n\sqrt{n})$ 时间复杂度内完成。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int p[N],mx[N],a[N],b[N],f[N],g[N],q[N];
map<int,int> mp;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        mp.clear();
        int n;cin>>n;
        for(int i=1;i<=n;i++) cin>>p[i],mx[i]=max(mx[i-1],p[i]);
        vector<int> v;
        for(int i=1;i<=n;i++)
            if(mx[i]==p[i]) v.push_back(i);
        int k=(int)v.size();
        for(int i=0;i<k;i++)
            if(i<k-1) mp[v[i+1]-v[i]]++;
            else mp[n-v[i]+1]++;
        int m=0;
        for(auto i:mp) 
        {
            a[++m]=i.first;
            b[m]=i.second;
        }
        memset(f,0,sizeof(f));
        f[0]=1;
        for(int i=1;i<=m;i++)
        {
            for(int j=0;j<=n;j++) g[j]=f[j];
            for(int j=0;j<a[i];j++)
            {
                int h=0,t=-1;
                for(int k=j;k<=n;k+=a[i])
                {
                    if(h<=t&&q[h]<k-b[i]*a[i]) h++;
                    if(h<=t) f[k]=max(g[k],g[q[h]]);
                    while(h<=t&&g[k]>=g[q[t]]) t--;
                    q[++t]=k;
                }
            }
        }
        cout<<(f[n/2]?"Yes":"No")<<'\n';
    }
    return 0;
}