2022.8.12牛客小白补题

B-Gaming_牛客小白月赛54 (nowcoder.com)

先把所有区间的权值加起来，考虑从覆盖住的区间中找一个不被覆盖的点，可以枚举删掉哪个点，删掉这个点造成的权值损失可以通过差分前缀和来得到。

const int N=1e6+5;
typedef long long ll;
int n,m;
ll s[N];
ll tot;

int main(){
	scanf("%d%d",&n,&m);
	int l,r,c;
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&l,&r,&c);
		s[l]+=c; s[r+1]-=c;
		tot+=c;
	}
	
	for(int i=1;i<=m;i++)s[i]+=s[i-1];
	ll res=0;
	for(int i=1;i<=m;i++){
		res=max(res,tot-s[i]);	
	}
	cout<<res<<endl;
	return 0;
}

C-School_牛客小白月赛54 (nowcoder.com)

把时间全部转化成分钟的形式，然后对所有时间段排序再区间合并。对于每一个询问t，二分查找小于等于它的第一个左端点，判断这个左端点所在的区间是否包含t即可。

const int N=1e3+5,Q=2e6+5;
typedef long long ll;
typedef pair<ll,ll>PII;
int n,h,m,q;
vector<PII>rg;
PII e[N];

int main(){
	scanf("%d%d%d%d",&n,&h,&m,&q);
	int x,y,a,b;
	for(int i=1;i<=n;i++){
		scanf("%d%d%d%d",&x,&y,&a,&b);
		e[i].l=(ll)x*m+y; e[i].r=(ll)a*m+b;
		//printf("%d %d\n",e[i].l,e[i].r);
	}
	sort(e+1,e+n+1);
	
	//区间合并
	ll st=e[1].l, ed=e[1].r;
	for(int i=2;i<=n;i++){
		if(e[i].l<=ed)ed=max(e[i].r,ed);
		else{
			rg.push_back({st,ed});
			st=e[i].l, ed=e[i].r;
		}
	}
	rg.push_back({st,ed});
	
	for(int i=1;i<=q;i++){
		scanf("%d%d",&x,&y);
		ll t=(ll)x*m+y;
		
		int l=0, r=rg.size()-1;
		while(l<r){
			int mid=(l+r+1)>>1;
			if(rg[mid].l<=t)l=mid;
			else r=mid-1;
		}
		if(rg[l].l<=t && rg[l].r>=t)printf("No\n");
		else printf("Yes\n");
	}
	return 0;
}

D-Word_牛客小白月赛54 (nowcoder.com)

两个可以互相转化的字符串之间连一条无向边，最后跑一遍bfs最短路即可。两个完全一样的字符串也要建立一条边，这是为了处理起点和终点相同的情况。

可以从终点往起点搜，这样方便求路径。

const int N=2005,M=2*N*N,INF=0x3f3f3f3f;
char s[N][24];
int n,m;
int e[M],ne[M];
int h[N],idx;
int pre[N],dis[N],vis[N];
queue<int>q;

void adde(int x,int y){
	e[idx]=y; ne[idx]=h[x]; h[x]=idx++;
}

void bfs(int st,int ed){
	memset(dis,0x3f,sizeof(dis));
	q.push(st); vis[st]=1;
 	dis[st]=0;
 	
 	while(!q.empty()){
 		int u=q.front();
 		q.pop();
 		for(int i=h[u];~i;i=ne[i]){
 			int v=e[i];
 			if(vis[v])continue;
 			if(dis[v]>dis[u]+1){
 				dis[v]=dis[u]+1;
 				vis[v]=1; pre[v]=u;
 				q.push(v);
 			}
 		}
 	}
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
	scanf("%s",s[0]+1); scanf("%s",s[n+1]+1);
	memset(h,-1,sizeof(h));
	for(int i=0;i<=n+1;i++){
		for(int j=i+1;j<=n+1;j++){
			int cnt=0;
			for(int t=1;t<=m;t++){
				if(s[i][t]!=s[j][t])cnt++;
			}
			if(cnt==1 || cnt==0)adde(i,j),adde(j,i);
		}
	}
	
	bfs(n+1,0);
	
	if(dis[0]!=INF){
		printf("%d\n",dis[0]-1);
		int now=0;
		while(now!=n+1){
			printf("%s\n",s[now]+1);
			now=pre[now];
		}
		printf("%s\n",s[n+1]+1);
	}
	else printf("-1\n");
	return 0;
}

E-Slash_牛客小白月赛54 (nowcoder.com)

线性dp。

设f[i][j][k]表示当前正在考虑第\((i,j)\)个字符，同时最新已经匹配到了t串的第k位的所有方案。

如果\(s[i][j]==t[k]\)，说明可以从原来状态上接上去这个字符形成更长的匹配，即f[i][j][k] = max(f[i-1][j][k-1],f[i][j-1][k-1])。

如果匹配满了，我们要把它“进位”，即f[i][j][0]=f[i][j][len(t)]+1

最后还需要考虑\(s[i][j]!=t[k]\)时的失配状态，失配之后，状态立刻变成\(f[i][j][0]\)。因为\(f[i][j][0]\)对答案的贡献一定不比\(f[i][j][k],k>0\)要好，所以我们可以简单粗暴地转移，不管前一个位置匹配了多少，全部都转移到失配的位置上，即f[i][j][0]=max(f[i][j][0],max(f[i-1][j][k],f[i][j-1][k]))。

const int N=105;
int f[N][N][N];
int n,m,p;
char s[N][N],t[N];

int main(){
	scanf("%d%d",&n,&m);
	scanf("%s",t+1);
	p=strlen(t+1);
	for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
	
	memset(f,-0x3f,sizeof(f));
	f[1][0][0]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int k=1;k<=p;k++){
				if(s[i][j]==t[k])f[i][j][k]=max(f[i-1][j][k-1],f[i][j-1][k-1]);
			}
			
			f[i][j][0]=f[i][j][p]+1;
			
			for(int k=0;k<=p;k++){
				f[i][j][0]=max(f[i][j][0],max(f[i-1][j][k],f[i][j-1][k]));
			}
		}
	}
	
	int ans=0;
	for(int i=0;i<p;i++)ans=max(ans,f[n][m][i]);
	cout<<ans<<endl;
	return 0;
}