列表

详情


NC204121. 牛牛的01限定串

描述

对于一个长度为n的字符串S,我们称字符串S_0S_1S_2...S_i为字符串的一个前缀,称字符串为字符串的一个后缀。

我们称两个字符串是相似的,当且仅当它们的成分相同,并且组成各成分出现的数目相同。例如字符串"abbcdf"与字符串"bcfdab"就是相似的,而"abbcdf"与"abcdf"不相似,因为它们虽然成分相同,但是各成分出现的次数不同。

牛牛本来有两个长度均为n的01字符串s,t,但是t串由于数据损坏,导致一些位置不确定到底是0还是1,不过好在,牛牛清楚的记得t串中有cnt_0个0与cnt_1个1。

接下来牛牛要还原损坏的t串。

s串和t串每有一个非空前缀相似,就得到的得分,(不一定是一个正数,当它的值为负时表示失去的得分)

s串和t串每有一个非空后缀相似,就得到的得分,(不一定是一个正数,当它的值为负时表示失去的得分)

牛牛想要知道它能够还原的t串中的最小得分与最大得分。

输入描述

第一行输入五个整数n,cnt_0,cnt_1,, 。且保证

接下来输入两行表示字符串s,t,|s|=|t|=n

其中,s串完全由'0','1'组成,t串完全由'0','1','?'组成。

?表示损坏的部分,也就是需要你还原的部分。

输入数据保证t串中0的数目,1的数目,也就是至少存在一种合法填充t串中?的方案。

输出描述

请输出两个整数,表示还原后的最小得分与最高得分。

示例1

输入:

8 6 2 1 1
10110011
????????

输出:

0 4

说明:

可以构造01串t="00011000"达到最小得分(与s串没有相似的前缀与后缀)

可以构造01串t="00000011"(4个相似的后缀)达到最大得分。

示例2

输入:

20 1 19 55 97
11111010101111111111
1?????1?1?1????????1

输出:

566 1439

说明:

最小:"11111111111111111101"
最大:"11111111101111111111"

示例3

输入:

1 0 1 -999 1000
0
?

输出:

0 0

说明:

因为限制条件为必须有1个1,所以?处只能填1

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 13ms, 内存消耗: 8300K, 提交时间: 2020-05-08 23:49:58

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;
char s[maxn],t[maxn];
int mi[maxn][maxn],mx[maxn][maxn],sum[maxn];
int n,c0,c1,vp,vs;
signed main(){
    scanf("%d%d%d%d%d",&n,&c0,&c1,&vp,&vs);
    scanf("%s%s",s+1,t+1);
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+s[i]-'0';
    memset(mi,0x3f,sizeof(mi)); memset(mx,-0x3f,sizeof(mx));
    mi[0][0] = mx[0][0] = 0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=c1;j++){
            if(t[i]!='1'){
                mi[i][j]=min(mi[i][j],mi[i-1][j]+vp*(sum[i]==j)+vs*(sum[n]-sum[i]==c1-j));
                mx[i][j]=max(mx[i][j],mx[i-1][j]+vp*(sum[i]==j)+vs*(sum[n]-sum[i]==c1-j));
            }
            if(t[i]!='0' && j>0){
                mi[i][j]=min(mi[i][j],mi[i-1][j-1]+vp*(sum[i]==j)+vs*(sum[n]-sum[i]==c1-j));
                mx[i][j]=max(mx[i][j],mx[i-1][j-1]+vp*(sum[i]==j)+vs*(sum[n]-sum[i]==c1-j));
            }
        }
    }
    if(sum[n]!=c1){ mi[n][c1]-=vs; mx[n][c1]-=vs; }
    cout<<mi[n][c1]<<' '<<mx[n][c1]<<endl;
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 18ms, 内存消耗: 18524K, 提交时间: 2020-05-09 20:59:27

#include<bits/stdc++.h>
using namespace std;
int n,n0,n1,u,v;
char s[1005],t[1005];
long long a[1005][1005],mi[1005][1005],mx[1005][1005];
bool ck(int &x,int &y){
	if(x<0||x>n0||y<0||y>n1)return 0;
	return 1;
}
int main(){
	scanf("%d%d%d%d%d",&n,&n0,&n1,&u,&v);
	scanf("%s%s",s,t);
	memset(mi,127,sizeof mi);
	memset(mx,-127,sizeof mx);
	int x=0,y=0;
	for(int i=0;i<n;++i){
		if(s[i]=='0')++x;
		else ++y;
		if(ck(x,y))a[x][y]+=u;
	}
	x=n0,y=n1;
	for(int i=n-1;~i;--i){
		if(s[i]=='0')--x;
		else --y;
		if(ck(x,y))a[x][y]+=v;
	}
	mi[n0][n1+1]=0,mx[n0][n1+1]=0;
	for(int i=n0;~i;--i)
		for(int j=n1;~j;--j){
			if(t[i+j]=='?'){
				mi[i][j]=min(mi[i+1][j],mi[i][j+1])+a[i][j];
				mx[i][j]=max(mx[i+1][j],mx[i][j+1])+a[i][j];
			}
			else if(t[i+j]=='0'){
				mi[i][j]=mi[i+1][j]+a[i][j];
				mx[i][j]=mx[i+1][j]+a[i][j];
			}
			else{
				mi[i][j]=mi[i][j+1]+a[i][j];
				mx[i][j]=mx[i][j+1]+a[i][j];
			}
		}
	printf("%lld %lld",mi[0][0],mx[0][0]);
	return 0; 
}

上一题