華為/小紅書2021批筆試題解

總結：為啥大家筆試都能撞一起…只能加油亂rush幾個…

（由于他倆都是晚7:00-9:00…還有個騰訊是8-10點的…所以就只能挑幾個好寫的沖了）

華為Part：

T3

題目大意：給出$n?m$n?m的矩陣，每個格子有三個值$d,r,s$d,r,s,r為這一步往右走的概率，d為這一步往下走的概率，s為原地不動的概率，求從$(1,1)$(1,1)到$(n,m)$(n,m)的期望步數，
n?m<=1e6

一道正常的筆試題，算是難得的非常正常了…
dp轉移方程如下：

$dp[G(i,j)]=(dp[G(i+1,j)]?d[G(i,j)]+dp[G(i,j+1)]?r[G(i,j)]+1)\mathrm{/}(1.0?s[G(i,j)]);$dp[G(i,j)]=(dp[G(i+1,j)]?d[G(i,j)]+dp[G(i,j+1)]?r[G(i,j)]+1)/(1.0?s[G(i,j)]);

upd：

應評論區要求解釋下$1\mathrm{/}(1.0?s[G(i,j)])$1/(1.0?s[G(i,j)])的含義…
比如每次有0.5的概率走出格子，那么期望需要2次才能走出這個格子，
每次有1/3的概率走出格子，期望需要3次走出該格子，（幫助大家理解舉的例子…）
那么考慮每次有p的概率走出格子，則期望需要1/p次走出這個格子，
故得到上面式子的$1\mathrm{/}(1.0?s[G(i,j)])$1/(1.0?s[G(i,j)])

沒了，

Java代碼：

import java.util.*;

public class zbr01
{
	public static double []d=new double[100005];
	public static double []r=new double[100005];
	public static double []s=new double[100005];
	public static double []dp=new double[100005];
	public static int n,m;
	
	public static int G(int x,int y)
	{
		return m*(x-1)+y;
	}
	
	public static void main(String[] args)
	{
		Scanner S=new Scanner(System.in);
		n=S.nextInt(); m=S.nextInt();
		for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
		{
			d[G(i,j)]=S.nextDouble();
			r[G(i,j)]=S.nextDouble();
			s[G(i,j)]=S.nextDouble();
		}
		for(int i=n;i>=1;i--)
		{
			for(int j=m;j>=1;j--)
			{
				if(i==n&&j==m) continue;
				dp[G(i,j)]=(dp[G(i+1,j)]*d[G(i,j)]+dp[G(i,j+1)]*r[G(i,j)]+1)/(1.0-s[G(i,j)]);
			}
		}
		System.out.println(dp[1]);
	}
}

T1

題目大意：emm…完全沒啥價值的大模擬…略略略…

大大大大大模擬~~~~（我永遠討厭大模擬.jpg）

（不過順便發現了下Java的contains函式…差點就自己去寫hash了…Java廢物落淚.jpg

Java代碼：

import java.util.*;

public class zbr01
{
	public static String s[]=new String[100005];
	public static String t[]=new String[100005];
	
	public static void main(String[] args)
	{
		Scanner S=new Scanner(System.in);
		int cnt=0;
		while(true)
		{
			s[++cnt]=S.nextLine();
			if(s[cnt].length()==1) break;
		}
		char q=s[cnt].charAt(0);
		
		for(int i=1;i<=cnt-1;i++)
		{
			String tmp="";
			int len=s[i].length();
			for(int j=0;j<len;j++)
			{
				char p=s[i].charAt(j);
				if(p<q) tmp+=p;
			}
			t[i]=tmp;
		}
		String p2=S.nextLine(),p3="";
		int l=p2.length();
		for(int i=0;i<l;i++)
		{
			char p=p2.charAt(i);
			if(p<q) p3+=p;
		}
		for(int i=1;i<=cnt-1;i++)
		{
			if(t[i].contains(p3))
				System.out.println(s[i]);
		}
	}
}

T2

這啥，題面怎么這么長，待會再來康…（就咕咕咕了）
好像賽后看依然沒看懂題面？？？
老語文fw落淚.jpg

小紅書Part：

函式式編程…孩子本來就不會Java了…雪上加霜…而且寫的巨慢 當場去世.jpg（

以及做過兩次小紅書了…怎么都是每個題都不給資料范圍啊…這小紅書咋回事啊.jpg？？？（除了這個T3？）

T1

題目大意：給出長度為n的陣列，選擇一個最小的區間進行排序，使得所有陣列升序排列，
資料范圍未知

就是個結構體排序，拿id出來亂搞的事…然而我又不會Java結構體排序了…
順便學習了波Java的Map函式…

代碼也是用map模擬了C++的結構體排序…時間復雜度$O(nlogn)$O(nlogn) TLE，，，

以下是 TLE 78per代碼

更新$O(n)$O(n)做法：
找出開頭部分和結尾部分的最長的遞增序列，放一個L在開頭位置，一個R在結尾開始遞增，且大于中間所有數的數，的開頭位置，L到R表示為需要排序的序列區間，由于隨著L的增加，R也是單調增加的（易得…）那么用一個two-pointer就能做到嚴格$O(n)$O(n)復雜度了，

（由于是口胡演算法沒有代碼…個人感覺十分對！…早說資料范圍肯定就寫這個了啊hhh）

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);
		n=S.nextInt();
		for(int i=0;i<n;i++) arr[i]=S.nextInt();
		for(int i=0;i<n;i++) b[i]=arr[i];
		Arrays.sort(b,0,n);
		Map<Integer,Integer> ml = new HashMap<Integer,Integer>();
		Map<Integer,Integer> mr = new HashMap<Integer,Integer>();
		for(int i=0;i<n;i++)
		{
			boolean c=ml.containsKey(b[i]);
			if(c==false) ml.put(b[i],i);
			mr.put(b[i],i);
		}
		
		int L=0,R=0;
		for(int i=0;i<n;i++)
		{
			int l=ml.get(arr[i]),r=mr.get(arr[i]);
			if(l>i||r<i) {L=i; break;}
		}
		
		for(int i=n-1;i>=0;i--)
		{
			int l=ml.get(arr[i]),r=mr.get(arr[i]);
			if(l>i||r<i) {R=i; break;}
		}
		if(L==0&&R==0) System.out.println("-1 -1");
		else System.out.println(L+" "+R);
	}
}

T2

題目大意：求一個n*m的矩陣的mex(最小未出現的自然數)，
資料范圍未知

不懂這種題是來干啥的…來賣萌的嗎hhh

Java代碼：

import java.util.*;

public class zbr01
{
	public static String s[]=new String[100005];
	public static String t[]=new String[100005];
	
	public static int []p=new int[1000005];
	public static int [][]arr=new int[1005][1005];
	
	public static int findMin()
	{
		int n=arr.length,m=arr[0].length;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				if(arr[i][j]>n*m) continue;
				p[arr[i][j]]=1;
			}
		}
		int ans=1;
		while(p[ans]==1) ans++;
		return ans;
	}
	
	public static void main(String[] args)
	{
		Scanner S=new Scanner(System.in);
		arr[0][0]=3; arr[0][1]=1; arr[0][2]=4;
		arr[1][0]=5; arr[1][1]=8; arr[1][2]=10;
		System.out.println(findMin());
	}
}

T3

由于Java寫的巨慢…騰訊也開始一會兒了…直接跑路去寫騰訊了，，，
（雖然好像這個有資料范圍了（霧）
賽后：這啥啊，我怎么還是看不懂題意（
老語文fw再次落淚.jpg

END