竞赛讨论区 > 【题解】牛客小白月赛34
头像
213dd
编辑于 2021-06-01 11:48
+ 关注

【题解】牛客小白月赛34

A dd爱科学1.0
两种解法
1、最长上升子序列
二分+单调队列维护,复杂度
#include<bits/stdc++.h>
using namespace std;
char a[1000005],q[1000005];
int n,tail;
int find(char x){
	int l,r,mid;
	l=1;r=tail;int s=-1;
	while (l<=r){
		mid=(l+r)/2;
		if (x>=q[mid-1]&&x<=q[mid])s=max(s,mid);
		if (x>=q[mid])l=mid+1;
		else r=mid-1;
	}
	return s;
}
int main(){
	scanf("%d",&n);
	scanf("%s",a+1);
	q[0]='A'-1;tail=0;
	for (int i=1;i<=n;i++)
		if (a[i]>=q[tail])q[++tail]=a[i];
		else{
			int x=find(a[i]);
			if (x!=-1)q[x]=a[i];
		}
	printf("%d\n",n-tail);
}
2、dp
对应表示改至第位为止,最后一位的最小代价,
对应转移方程:
就是答案,复杂度
#include<bits/stdc++.h>
using namespace std;
int n,ans;
char a[1000005];
int f[1000005][30];
int main(){
	scanf("%d",&n);
	scanf("%s",a+1);
	memset(f,0x3f,sizeof(f));
	for (int i=1;i<=26;i++)f[0][i]=0;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=26;j++)f[i][j]=min(f[i][j-1],f[i-1][j]+(a[i]!=j+'A'-1));
	printf("%d",f[n][26]);
} 
B dd爱探险
状压dp
首先个点次跳完,明白这个跳跃过程其实是一条链,每个点只有被经过和没被经过两个状态,所以典型状压dp
对于状态,转成二进制数形式,第位对应,对应为时表示这个点已经被经过,对应则表示没有
定义dp数组,状态表示如上,表示当前停在这个点上,这四个状态,表示没经过加速,表示经过一次重力加速,表示经过一次反重力加速,表示两次加速都已经结束,注意状态转移
最后枚举最后停留的位置就是答案,复杂度
#include<bits/stdc++.h>
using namespace std;
int n,p[20][20],f[65540][20][5];
int c[20],a[20],b[20];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)scanf("%d",&p[i][j]);
	memset(f,0x3f,sizeof(f));	
	for (int i=0;i<n;i++)f[1<<i][i+1][0]=0;
	for (int t=1;t<(1<<n);t++){
		int y=t;
		for (int i=1;i<=n;i++)c[i]=y%2,y/=2;
		int m1,m2;
		m1=m2=0;
		for (int i=1;i<=n;i++)
			if (c[i])a[++m1]=i;
			else b[++m2]=i;
		for (int i=1;i<=m1;i++)
			for (int j=1;j<=m2;j++){
				f[t+(1<<(b[j]-1))][b[j]][0]=min(f[t+(1<<(b[j]-1))][b[j]][0],f[t][a[i]][0]+p[a[i]][b[j]]);	
				f[t+(1<<(b[j]-1))][b[j]][1]=min(f[t+(1<<(b[j]-1))][b[j]][1],min(f[t][a[i]][0],f[t][a[i]][1]+p[a[i]][b[j]]));
				f[t+(1<<(b[j]-1))][b[j]][2]=min(f[t+(1<<(b[j]-1))][b[j]][2],min(f[t][a[i]][0]+2*p[a[i]][b[j]],f[t][a[i]][2]+p[a[i]][b[j]]));
				f[t+(1<<(b[j]-1))][b[j]][3]=min(f[t+(1<<(b[j]-1))][b[j]][3],min(f[t][a[i]][1]+2*p[a[i]][b[j]],f[t][a[i]][2]));
				f[t+(1<<(b[j]-1))][b[j]][3]=min(f[t+(1<<(b[j]-1))][b[j]][3],f[t][a[i]][3]+p[a[i]][b[j]]);	
			}
	}
	int ans=1000000000;
	for (int i=1;i<=n;i++)ans=min(ans,f[(1<<n)-1][i][3]);
	printf("%d\n",ans);
}
C dd爱科学2.0
dp
与A题dp解法一样,只要转移条件改成即可
#include<bits/stdc++.h>
using namespace std;
int n,ans;
char a[1000005];
int f[1000005][30];
int main(){
	scanf("%d",&n);
	scanf("%s",a+1);
	memset(f,0x3f,sizeof(f));
	for (int i=1;i<=26;++i)f[0][i]=0;
	for (int i=1;i<=n;++i)
		for (int j=1;j<=26;++j)f[i][j]=min(f[i][j-1],f[i-1][j]+abs(a[i]-(j-1+'A')));
	printf("%d",f[n][26]);
} 
D dd爱矩阵
贪心+优先队列
先把问题简化一下,如果两行,每行个数,怎么选
把两行分别降序,如果令第一行为数组,第二行为数组
则可得到最大值为,并且得到
所以可以把全部推入优先队列当中,并且标记对应的,每次取出,再把推入优先队列当中,次操作即可得到前
复杂度
回到这个题目,由于是行,可以每次处理两行,并成一行新的,次操作把行并成一行,复杂度
#include<bits/stdc++.h>
using namespace std;
int n,a[1005],b[1005],c[1005];
struct t{
	int x,z;
	friend bool operator<(t x,t y){
		return x.z<y.z;
	} 
};

bool cmp(int x,int y){
	return x>y;
}
int main(){
	priority_queue<t>q;
	scanf("%d",&n);
	for (int i=1;i<=n;i++)scanf("%d",&b[i]);
	sort(b+1,b+1+n,cmp);
	for (int i=2;i<=n;i++){
		for (int j=1;j<=n;j++)scanf("%d",&a[j]);
		sort(a+1,a+1+n,cmp);
		for (int j=1;j<=n;j++){
			t p;
			p.x=1;p.z=a[1]+b[j];q.push(p);
		}
		for (int j=1;j<=n;j++){
			t pp=q.top();t p;
			q.pop();
			c[j]=pp.z;
			p.x=pp.x+1;
			p.z=pp.z-a[pp.x]+a[p.x];
			q.push(p);
		}
		for (int j=1;j<=n;j++)b[j]=c[j];
		while (!q.empty())q.pop();	
	}
	for (int j=1;j<=n;j++)printf(j==n?"%d\n":"%d ",b[j]);
}
E dd爱旋转
模拟,算复杂度肯定不能每次操作完整个矩阵动一次
发现每次操作都会上下翻转,所以上下可以通过操作次数的奇偶直接控制
操作相当于在上下翻转的情况下左右再翻转一次,所以再左右可以通过操作次数奇偶直接控制
所以直接一遍枚举判断情况解决,复杂度
#include<bits/stdc++.h>
using namespace std;
int n,Q;
int a[2005][2005];
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)scanf("%d",&a[i][j]);
	scanf("%d",&Q);
	int s1,s2;
	s1=s2=1;
	while (Q--){
		int x;
		scanf("%d",&x);
		s1=1-s1;
		if (x==2)s2=1-s2;
	}
	if (s1==1)
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)printf(j==n?"%d\n":"%d ",s2?a[i][j]:a[i][n-j+1]);		
	else
	for (int i=n;i>=1;i--)
		for (int j=n;j>=1;j--)printf(j==1?"%d\n":"%d ",s2?a[i][j]:a[i][n-j+1]);
} 
F dd爱框框
单调队列维护窗口移动,复杂度
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x,a[10000005],w;
int n;
int main(){
	scanf("%d%lld",&n,&x);
	for (int i=1;i<=n;i++)scanf("%lld",&a[i]);
	int l,r;
	l=0;r=n+1;
	int s,t;
	s=1;t=0;
	w=0;
	for (int i=1;i<=n;i++){
		w+=a[i];t++;
		while (w-a[s]>=x)w-=a[s++];
		if (w>=x){
			if (t-s+1<r-l+1)r=t,l=s;
		}
	}
	printf("%d %d\n",l,r);
}
G dd爱捣乱
G题数据出了点问题,影响了部分同学,出题人在这里再次表示抱歉
首先讨论完美串满足条件,如果是奇串,则每一位前后两位不同,即
如果是偶串,则相邻两位不同
综上,只要任意连续三位都满足两两不同,就是一个完美串
那么一个很显然的想法,枚举每一位的情况,保证再枚举前两位情况,保证不同的情况下更新答案
复杂度
复杂度显然有点偏大,常数没控制好极有可能
所以进一步想,每一位最多只会受前两位和后两位的影响,根据鸽巢原理,实际上最多只有五种情况:,必有一种情况满足完美串
所以对于每一位只要枚举改变量就行了,表示把第位的改变量是,第位的改变量是的最小代价

最后枚举最后两位改变量就是答案
复杂度
#include<bits/stdc++.h>
using namespace std;
int n,ans;
char b[1000005];
int a[1000005];
int f[1000005][6][6];
int main(){  scanf("%d",&n);  scanf("%s",b+1);  for (int i=1;i<=n;i++)a[i]=b[i]-'a';  memset(f,-1,sizeof(f));  for (int i=-2;i<=2;i++)  for (int j=-2;j<=2;j++)  if ((a[1]+i+26)%26!=(a[2]+j+26)%26)f[2][i+2][j+2]=abs(i)+abs(j);  for (int i=3;i<=n;i++)  for (int j=-2;j<=2;j++)  for (int k=-2;k<=2;k++)  if (f[i-1][j+2][k+2]!=-1)  for (int t=-2;t<=2;t++)  if ((a[i]+t+26)%26!=(a[i-2]+j+26)%26&&(a[i]+t+26)%26!=(a[i-1]+k+26)%26){  if (f[i][k+2][t+2]==-1)f[i][k+2][t+2]=f[i-1][j+2][k+2]+abs(t);  else f[i][k+2][t+2]=min(f[i][k+2][t+2],f[i-1][j+2][k+2]+abs(t));  }   ans=1e9;  for (int i=0;i<=4;i++)  for (int j=0;j<=4;j++)  if (f[n][i][j]!=-1)ans=min(ans,f[n][i][j]);  printf("%d\n",ans); 
H dd爱捣乱
不管是多少,把位置取余,余数相等的位置的值必然相等,通过简单贪心可知,肯定是把这些位置的数都改成余数相等的位置中值最小的那个数
因为给定了限制条件,所以只要枚举所在的位置,可以直接利用前缀和计算出最小改变量,复杂度
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k;
ll a[1000005],g[1000005],f[1000005],b[1000005];
int main(){
	scanf("%d%d",&n,&k);
	k++;
	for (int i=1;i<=n;i++)scanf("%lld",&a[i]);
	for (int i=0;i<k;i++)g[i]=1000000001;
	memset(f,0,sizeof(f));
	memset(b,0,sizeof(b));
	for (int i=1;i<=n;i++)f[i%k]+=a[i];
	for (int i=1;i<=n;i++)g[i%k]=min(g[i%k],a[i]);
	for (int i=1;i<=n;i++)b[i%k]++;
	ll ss=a[1];
	for (int i=2;i<=n;i++)ss=min(ss,a[i]);
	ll ans=100000000000000000ll;
	ll pp=0;
	for (int i=1;i<=n;i++)pp+=a[i];
	for (int i=0;i<k;i++)
		ans=min(ans,f[i]-g[i]*b[i]+pp-f[i]-(1ll*n-b[i])*ss);
	printf("%lld\n",ans);	
} 










全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐