CodeForces Round #581 Div2 题解

/ 0评 / 0

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

C - Anna, Svyatoslav and Maps

Description

（难以描述……）

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.

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

Solution #1

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

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

Code #1

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

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(){
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();
}

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）

Code #2

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

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(){
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();
}

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

• 对于任意 lr1\leq l \leq r\leq n），满足 [l,r] 区间之内两个串的最长非降子序列（LIS）长度相等；
• t 串中 0 尽量多。

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）；

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

Solution #2

（来自 CF 官方 Tutorial）

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

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

Code #2

#include<bits/stdc++.h>

using namespace std;

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

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

Solution

（来自 CF 官方 Tutorial）

- 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) 同理。

- 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

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(){

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


• 默认
• 护眼
• 夜晚
• Serif
• Sans