贝壳2021批笔试题解

时间:2020-9-8 作者:admin


总结:十分正常…挺欢乐的emm…就是感觉代码量好大啊emm

T2

题目大意:单次操作可以插入一个字符至末尾 / 或将当前已有字符copy一遍到末尾(仅可使用一次)
问最少需要多少次操作得到目标串s

len<=1e6len<=1e6

从长到短枚举copy的长度…然后hash做到单次

O(1)O(1)

判断,copy当前长度是否可行即可。
(Java没有unsigned long long差评!!!)(雾

import java.util.*;

public class zbr01
{
	public static int n,m,k;
	public static String s;
	public static long []b=new long[100005];
	public static long []h=new long[100005];
	
	public static long mod=1000000007;
	
	public static long gh(int l,int r)
	{
		long tmp=h[r],p2=(h[l-1]*b[r-l+1])%mod;
		tmp=(tmp-p2+mod)%mod;
		return tmp;
	}
	
	public static void main(String[] args)
	{
		Scanner S=new Scanner(System.in);
		s=S.nextLine(); s=S.nextLine(); n=s.length();
		s="#"+s; b[0]=1;
		for(int i=1;i<=n;i++) b[i]=(b[i-1]*233)%mod;
		for(int i=1;i<=n;i++)
		{
			char p=s.charAt(i);
			h[i]=(h[i-1]*233+p)%mod;
		}
		int F=0;
		for(int i=n/2;i>=1;i--)
		{
			long p=gh(1,i),q=gh(i+1,2*i);
			if(p==q&&F==0) {F=1; System.out.println(n-i+1);}
		}
		if(F==0) System.out.println(n);
	}
}

T3

题目大意:有n块板子,m种颜色,给出一些特殊关系为i种颜色后不能跟j颜色,问给所有板子涂色的方案数。

n<=1000,m<=10n<=1000,m<=10

考虑

dp[i][j]dp[i][j]

为第i块板子为j种颜色的方案数。
然后胡乱转移即可。。。时间复杂度

O(nm2)O(nm^2)


(非常非常标准的dp入门题了???)

import java.util.*;

public class zbr01
{
	public static int n,m,k;
	
	public static long mod=1000000007;
	public static long [][]dp=new long [1005][15];
	public static int [][]p=new int [15][15];
	
	public static void main(String[] args)
	{
		Scanner S=new Scanner(System.in);
		int T=S.nextInt();
		for(int z=1;z<=T;z++)
		{
			n=S.nextInt(); m=S.nextInt(); k=S.nextInt();
			
			for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) p[i][j]=0;
			for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) dp[i][j]=0;
			
			for(int i=1;i<=m;i++)
			{
				for(int j=1;j<=k;j++)
				{
					int x=S.nextInt();
					p[i][x]=1;
				}
			}
			
			for(int i=1;i<=m;i++) dp[1][i]=1;
			long ans=0;
			
			for(int i=2;i<=n;i++)
			{
				for(int j=1;j<=m;j++)
				{
					for(int k=1;k<=m;k++)
					{
						if(p[j][k]==1) continue;
						dp[i][k]=(dp[i-1][j]+dp[i][k])%mod;
					}
				}
			}
			for(int i=1;i<=m;i++) ans=(ans+dp[n][i])%mod;
			System.out.println(ans);
		}
	}
}

T4

题目大意:自己有一个

valval

值,给两个数组,在其中顺着从

[1,n][1,n]

取数。每次可以选择一个数组的开头取走一个数
从第一个数组取一个数需要

val=a1[i],val+=b1[i]val-=a1[i],val+=b1[i]

;
从第二个数组取一个数需要

val=a2[i],val+=b2[i]val-=a2[i],val+=b2[i]

;(均按顺序操作)
你需要自己确定一个最小的val值,使得任何时候val值大小都>=1。

考虑

dp[i][j]dp[i][j]

为 能让第一个数组打到i,第二个数组打到j的最低血量。
然后记录四个前缀和,即可判断当前状态的血量,以及能不能继续打。
直接

dp[i][j]=min(dp[i1][j]+resx,dp[i][j1]+resy)dp[i][j]=min(dp[i-1][j]+resx,dp[i][j-1]+resy)

转移即可,时间复杂度

O(n2)O(n^2)

;

(也是十分标准的dp板子题了…

import java.util.*;

public class zbr01
{
	public static int []a1=new int[1005];
	public static int []a2=new int[1005];
	public static int []b1=new int[1005];
	public static int []b2=new int[1005];
	public static int []pa1=new int[1005];
	public static int []pa2=new int[1005];
	public static int []pb1=new int[1005];
	public static int []pb2=new int[1005];
	
	public static int [][]dp=new int[1005][1005];
	
	public static int inf=2000000001;
	
	public static void main(String[] args)
	{
		Scanner S=new Scanner(System.in);
		int n=S.nextInt();
		for(int i=n;i>=1;i--) a1[i]=S.nextInt();
		for(int i=1;i<=n;i++) {a2[i]=S.nextInt(); pa2[i]=pa2[i-1]+a2[i];}
		for(int i=n;i>=1;i--) b1[i]=S.nextInt();
		for(int i=1;i<=n;i++) {b2[i]=S.nextInt(); pb2[i]=pb2[i-1]+b2[i];}
		
		for(int i=1;i<=n;i++) {pa1[i]=pa1[i-1]+a1[i]; pb1[i]=pb1[i-1]+b1[i];}
		
		for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) dp[i][j]=inf; dp[0][0]=0;
		
		for(int i=0;i<=n;i++) for(int j=0;j<=n;j++)
		{
			if(i>=1)
			{
				int res=dp[i-1][j];
				res-=pa1[i-1]; res+=pb1[i-1]; res-=pa2[j]; res+=pb2[j];
				if(res>=a1[i]) dp[i][j]=Math.min(dp[i][j],dp[i-1][j]);
				else dp[i][j]=Math.min(dp[i][j],dp[i-1][j]+(a1[i]-res));
			}
			
			if(j>=1)
			{
				int res=dp[i][j-1];
				res-=pa1[i]; res+=pb1[i]; res-=pa2[j-1]; res+=pb2[j-1];
				if(res>=a2[j]) dp[i][j]=Math.min(dp[i][j],dp[i][j-1]);
				else dp[i][j]=Math.min(dp[i][j],dp[i][j-1]+(a2[j]-res));
			}
		}
		System.out.println(dp[n][n]+1);
	}
}

T1

(由于完全没有价值被扔到最后)

题目大意:完全没有价值的大模拟…大家都会就略略略了…

大大大大大大大模拟…(我永远讨厌大模拟.jpg)

import java.util.*;

public class zbr01
{
	public static int n,m;
	public static int []arr=new int[100005];
	public static int []b=new int[100005];
	
	public static void main(String[] args)
	{
		Scanner S=new Scanner(System.in);
		int T=S.nextInt();
		for(int z=1;z<=T;z++)
		{
			String s=S.next(); char a=s.charAt(0);
			s=S.next(); char b=s.charAt(0);
			s=S.next(); char c=s.charAt(0);
			s=S.next(); char d=s.charAt(0);
			
			int x1=0,x2=0;
			if(a=='J'&&d=='B'||a=='J'&&c=='B') x1++;
			if(a=='S'&&d=='J'||a=='S'&&c=='J') x1++;
			if(a=='B'&&d=='S'||a=='B'&&c=='S') x1++;
			
			if(b=='J'&&d=='B'||b=='J'&&c=='B') x2++;
			if(b=='S'&&d=='J'||b=='S'&&c=='J') x2++;
			if(b=='B'&&d=='S'||b=='B'&&c=='S') x2++;
			
			if(x1==x2) System.out.println("same");
			else if(x1>x2) System.out.println("left");
			else System.out.println("right");
		}
	}
}

END:怎么感觉又在水时间…天天摸鱼…再写这种题算法水平要完蛋了((

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。