Codeforces Round #581 (Div. 2) 比赛链接：LInk

C - Anna, Svyatoslav and Maps

Description

给出一张有向图，每条边的边权都是 1。给出一个 m 个点的路径序列 $\{p_i \}$，表示依次经过这 m 个点的路径。路径序列中相邻元素之间有边相连。
现在需要你找出这个序列的一个最短的子序列 $\{v_i \}$，长度为 k，使得经过这 k 个点的路径也经过 $\{p_i \}$ 中所有点。

（难以描述……）

Define the sequence $v_1,v_2,\dots,v_k$ of vertexes as good, if is a subsequence of , , , and is one of the shortest paths passing through the vertexes in that order.

（题目里说是无环的，但是给出数据包括样例都是有环的……没搞懂……）

数据范围：$2\leq n\leq 100, 2\leq m\leq 10^6$。

Solution #1

VP 的时候写出来的，但是数组开小了 qwq 一直显示 WA 但是一直找不到错……

翻译一下题意无非就是让我们找“不必要的点”，即在路径中删除之后根据之前和之后的点能推断出的点。既然走的是最短路，能删除的点自然是在最短路径上的点。
看到百级的数据肯定先跑 Floyd，然后遍历题中的路径。答案序列初始只有 p[1]，记答案序列最后一个元素是 last，则对于每个元素只要判断是否在最短路上即可：

$dist(last,p_{i+1}) == dist(last,p_i) + dist(p_i,p_{i+1})$

Code #1

#include<bits/stdc++.h>
using namespace std;
 
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
 
const int INF=0x3f3f3f3f;
 
const int maxn=105;
const int maxm=1000005;
 
int n,m;
int dist[maxn][maxn];
 
int p[maxm];
vector<int> ans;
 
void Floyd(){
    for (int k=1;k<=n;k++)
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
}
 
{
    n=();
    (dist,,(dist));
     ( i=;i<=n;i++) dist[i][i]=;
    
     ch=();  (ch!=&&ch!=) ch=();
     ( i=;i<=n;i++)
         ( j=;j<=n;j++){
             (ch==) dist[i][j]=;
             (i==n&&j==n) ;
            ch=();  (ch!=&&ch!=) ch=();
        }
    m=();
     ( i=;i<=m;i++) p[i]=();
 
    ();
     last=;
     ( i=;i<=m;i++){
         (i== || i==m) {
            ans.(p[i]);last=p[i];
            ;
        }
         (dist[last][p[i]] == dist[last][p[i]]+dist[p[i]][p[i]]){;}
        ans.(p[i]);last=p[i];
    }
    (,()ans.());
     ( i=;i<()ans.();i++) (,ans[i]);
    ();
     ;
}

Solution #2

（来自 CF 官方 Tutorial）

先跑 Floyd（或者 DFS……），一样先把 $p_1$ 加入答案，然后遍历 $p$ 路径时记录 last 到当前的路径长度（因为题目中保证 $p$ 的相邻元素之间有边），如果 $dist(last,p_i)$ 小于记录的路径长度，说明 last 到这个点有其他更短的路径，则必须在答案序列加入 以确保沿 路径走。

Code #2

#include<bits/stdc++.h>
using namespace std;

inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}

const int INF=0x3f3f3f3f;

const int maxn=105;
const int maxm=1e6+5;

int n,m;
int dist[maxn][maxn];

int p[maxm];
vector<int> ans;

void Floyd(){
    for (int k=1;k<=n;k++)
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
}

{
    n=();
    (dist,,(dist));
     ( i=;i<=n;i++) dist[i][i]=;
    
     ch=();  (ch!=&&ch!=) ch=();
     ( i=;i<=n;i++)
         ( j=;j<=n;j++){
             (ch==) dist[i][j]=;
             (i==n&&j==n) ;
            ch=();  (ch!=&&ch!=) ch=();
        }
    m=();
     ( i=;i<=m;i++) p[i]=();

    ();
     last,cnt;
     ( i=;i<=m;i++){
        cnt++;
         (i==) {
            ans.(p[i]);last=p[i];cnt=;
        }   (i!= && dist[last][p[i]] < cnt){
            ans.(p[i]);
            last=p[i];cnt=;
        }
    }
    ans.(p[m]);
    (,()ans.());
     ( i=;i<()ans.();i++) (,ans[i]);
    ();
     ;
}

D1/D2 - Kirk and a Binary String

Description

给出一个长度为 n 的 0/1 串 s，你需要找出一个长度相同的 0/1 串 t，满足：

• 对于任意 $l$ 和 $r$（$1\leq l \leq r\leq n$），满足 $[l,r]$ 区间之内两个串的最长非降子序列（LIS）长度相等；

数据范围：$n\leq 2000$。

Solution #1

（来自 https://blog.csdn.net/nudt_spy/article/details/99940916）

从后向前考虑：

• 对于 0：必然是某个 LIS 的一部分，如果改为 1，必然会缩短 LIS 的长度（1）；
• 对于 1：
  • 如果以它为起点的区间的 LIS 包含它（显然这个区间的 LIS 全是 1），则把它修改为 0 没有变化（2）；
  • 如果以它为起点的区间的 LIS 不包含它，则把它改为 0 会增加 LIS 长度（3）；

所以只有第（2）种情况可以修改。如果某个区间的 LIS 全是 1，则这个区间必然是 1 的数量大于 0 的数量，并且 1 开头。所以只要从后往前统计，如果 1 的数量大于等于 0 的数量，则允许将 1 改为 0。

（为什么不考虑形如 10001111 的数列？（这个数列里 LIS 似乎并不是第二种情况）在从后向前处理时，后面的 1 都会被搞成 0，换句话说最终 LIS 全是 0 或者全是 1）

Solution #2

（来自 CF 官方 Tutorial）

如果对于一个 0/1 串 $p$，没有串与它满足条件一，则称这个串为 fixed 串。则有以下几条事实：

• 10 是 fixed 的；
• 如果 $p$ 和 $q$ 都是 fixed 的，则 $pq$ 也是 fixed 的；
• 如果 $p$ 是 fixed 的，那么 $1p0$ 也是 fixed 的；
• 每个 fixed 串的 0 和 1 数量相等；
• 每个 fixed 串的 LIS 长度都是其一半，并且只包含 0 或者只包含 1；

（证明可见：https://www.cnblogs.com/yyf0309/p/11389504.html）

那么对于题目中所给的 s，其中的若干 fixed 串是不能改变的，可以不考虑；
则剩下的部分都是一段段 LIS（否则就会有 10 即 fixed string）。所以只要剩下的部分把 1 改成 0，各个 LIS 都不会改变。

Code #2

#include<bits/stdc++.h>

using namespace std;

inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}

const int maxn=100005;

int n;
char s[maxn];
bool vis[maxn];

signed main(){
    scanf("%s",s+1); n=strlen(s+1);
    for (int i=1;i<=n;i++) if (i!=1 && s[i-1]=='1' && s[i]=='0'){
        int l=i-1,r=i; vis[l]=vis[r]=true;
        while (l-1>=&&s[l]== && r<=n&&s[r]==) l--,r++,vis[l]=vis[r]=;
         (;;){
             (l>= && vis[l]){
                 (l>= && vis[l]) l--;
                 (l>=&&s[l]== && r<=n&&s[r]==) l--,r++,vis[l]=vis[r]=;
            }  ;
        }
        i=r;
    }
     ( i=;i<=n;i++)  ((!vis[i]) && s[i]==) s[i]=;
    (,s);
     ;
}

1204E - Natasha, Sasha and the Prefix Sums

Description

给出 $n$ 和 $m$，对于每个长度为 $n+m$、包含 $n$ 个 1、$m$ 个 -1 的数列，有其最大的前缀和（如果小于 0 则取 0）。形式化地说，定义 $f(a)$ 为长度为 的序列 的最大前缀和，，则：

$f(a) = \max (0, \smash{\displaystyle\max_{1 \leq i \leq l}} \sum_{j=1}^{i} a_j )$

需要求出对于所有这样的数列，最大前缀和之和。模 998244853。

数据范围：$0\leq n,m\leq 2000$。

Solution

（来自 CF 官方 Tutorial）

首先构造一个 DP 数组 $G(i,j)$，表示 $n-i,m=j$ 时最大前缀和是 0 的数组数量。

• $i=0$ 时：显然 $G(i,j)=1$；
• $i>j$ 时：$G(i,$；

定义 $F(i,j)$ 表示 $n=i,m=j$ 时的答案（最大前缀和之和）。

• $i=0$ 时：显然 $F(i,j)=0$；
• $j=0$ 时：显然 $F(i,$；

$F(i,j)={i+j-1 \choose j} + F(x-1,y) + F(i,j-1)-({i+j-1 \choose i} - G(i,j-1))$

Code

#include<bits/stdc++.h>
using namespace std;

#define int long long

inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}

const int tt=998244853;
const int maxn=2005;

int n,m;
int f[maxn][maxn],g[maxn][maxn];
int c[maxn*2][maxn*2];

void build_cons(){
    c[1][0]=c[1][1]=1;
    for (int i=2;i<=n+m;i++){
        c[i][0]=c[i][i]=1;
        for ( j=;j<i;j++) c[i][j]=(c[i][j]+c[i][j])%tt;
    }
}

{
    n=(); m=();

     ( i=;i<=n;i++)
         ( j=;j<=m;j++){
             (i==) g[i][j]=; 
             (i>j) g[i][j]=; 
            g[i][j]=(g[i][j]+g[i][j])%tt;
        }

    ();
    
     ( i=;i<=n;i++)
         ( j=;j<=m;j++){
             (i==) f[i][j]=; 
             (j==) f[i][j]=i; 
            f[i][j]=((c[i+j][j]+f[i][j])%tt+(f[i][j]-(c[i+j][i]-g[i][j])%tt+tt)%tt)%tt;
        }

    (,f[n][m]);
     ;
}