CodeForces Round #581 Div2 题解

/ 0评 / 0

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 k vertexes as good, if v is a subsequence of p, v_1=p_1, v_k=p_m, and p is one of the shortest paths passing through the vertexes v_1 ,\dots, v_k 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]);
}

signed main(){
    n=read();
    memset(dist,0x3f,sizeof(dist));
    for (int i=1;i<=n;i++) dist[i][i]=0;

    char ch=getchar(); while (ch!='0'&&ch!='1') ch=getchar();
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++){
            if (ch=='1') dist[i][j]=1;
            if (i==n&&j==n) continue;
            ch=getchar(); while (ch!='0'&&ch!='1') ch=getchar();
        }
    m=read();
    for (int i=1;i<=m;i++) p[i]=read();

    Floyd();
    int last=-1;
    for (int i=1;i<=m;i++){
        if (i==1 || i==m) {
            ans.push_back(p[i]);last=p[i];
            continue;
        }
        if (dist[last][p[i+1]] == dist[last][p[i]]+dist[p[i]][p[i+1]]){continue;}
        ans.push_back(p[i]);last=p[i];
    }
    printf("%d\n",(int)ans.size());
    for (int i=0;i<(int)ans.size();i++) printf("%d ",ans[i]);
    printf("\n");
    return 0;
}

Solution #2

(来自 CF 官方 Tutorial)

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

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]);
}

signed main(){
    n=read();
    memset(dist,0x3f,sizeof(dist));
    for (int i=1;i<=n;i++) dist[i][i]=0;

    char ch=getchar(); while (ch!='0'&&ch!='1') ch=getchar();
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++){
            if (ch=='1') dist[i][j]=1;
            if (i==n&&j==n) continue;
            ch=getchar(); while (ch!='0'&&ch!='1') ch=getchar();
        }
    m=read();
    for (int i=1;i<=m;i++) p[i]=read();

    Floyd();
    int last,cnt;
    for (int i=1;i<=m;i++){
        cnt++;
        if (i==1) {
            ans.push_back(p[i]);last=p[i];cnt=0;
        } else if (i!=2 && dist[last][p[i]] < cnt){
            ans.push_back(p[i-1]);
            last=p[i-1];cnt=1;
        }
    }
    ans.push_back(p[m]);
    printf("%d\n",(int)ans.size());
    for (int i=0;i<(int)ans.size();i++) printf("%d ",ans[i]);
    printf("\n");
    return 0;
}

D1/D2 - Kirk and a Binary String

Description

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

数据范围:n\leq 2000

Solution #1

(来自 https://blog.csdn.net/nudt_spy/article/details/99940916)

从后向前考虑:

所以只有第(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 串。则有以下几条事实:

(证明可见: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>=1&&s[l-1]=='1' && r+1<=n&&s[r+1]=='0') l--,r++,vis[l]=vis[r]=true;
        for (;;){
            if (l-1>=1 && vis[l-1]){
                while (l-1>=1 && vis[l-1]) l--;
                while (l-1>=1&&s[l-1]=='1' && r+1<=n&&s[r+1]=='0') l--,r++,vis[l]=vis[r]=true;
            } else break;
        }
        i=r;
    }
    for (int i=1;i<=n;i++) if ((!vis[i]) && s[i]=='1') s[i]='0';
    printf("%s\n",s+1);
    return 0;
}

1204E - Natasha, Sasha and the Prefix Sums

Description

给出 nm,对于每个长度为 n+m、包含 n 个 1、m 个 -1 的数列,有其最大的前缀和(如果小于 0 则取 0)。形式化地说,定义 f(a) 为长度为 l 的序列 a_1,\dots,a_l 的最大前缀和,l \geq 0,则:

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,j)=0
- 其他情况:可以从 G(i-1,j) 中转移:直接在最后加上一个 1,原来最大前缀和是 0 的现在还是 0(因为 x\leq y),G(i,j-1) 同理。
所以:G(i,j)=G(i-1,j)+G(i,j-1)
这个数组的构造可以解决 “前缀和小于 0 时取 0” 的问题。

定义 F(i,j) 表示 n=i,m=j 时的答案(最大前缀和之和)。
- i=0 时:显然 F(i,j)=0
- j=0 时:显然 F(i,j)=i
- 考虑对于 (i-1,j) 的数列:在前面加上一个 1 就可以变成 i,j,这样的数列有 {x+y-1 \choose x} 个,则这一部分答案是 {i+j-1 \choose j} + F(x-1,y);同样地,对于 (i,j-1) 的数列有 {i+j-1 \choose i} - G(i,j-1) 个(为 0 的不能再减),每个减去一个 1,这部分答案是 F(i,j-1)-({i+j-1 \choose i} - G(i,j-1))

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 (int j=1;j<i;j++) c[i][j]=(c[i-1][j-1]+c[i-1][j])%tt;
    }
}

signed main(){
    n=read(); m=read();

    for (int i=0;i<=n;i++)
        for (int j=0;j<=m;j++){
            if (i==0) g[i][j]=1; else
            if (i>j) g[i][j]=0; else
            g[i][j]=(g[i-1][j]+g[i][j-1])%tt;
        }

    build_cons();

    for (int i=0;i<=n;i++)
        for (int j=0;j<=m;j++){
            if (i==0) f[i][j]=0; else
            if (j==0) f[i][j]=i; else
            f[i][j]=((c[i+j-1][j]+f[i-1][j])%tt+(f[i][j-1]-(c[i+j-1][i]-g[i][j-1])%tt+tt)%tt)%tt;
        }

    printf("%lld\n",f[n][m]);
    return 0;
}

知识共享许可协议 本文章采用 知识共享署名-非商业性使用-相同方式共享 4.0 许可协议 进行许可。
欢迎转载,如有错误欢迎指出。
本文链接:https://skywt.cn/posts/cf1204/


发表评论

电子邮件地址不会被公开。 必填项已用*标注