总结：为啥大家笔试都能撞一起…只能加油乱rush几个…
（由于他俩都是晚7:00-9:00…还有个腾讯是8-10点的…所以就只能挑几个好写的冲了）
华为Part：
T3
题目大意：给出 n ∗ m n*m n∗m的矩阵，每个格子有三个值 d , r , s d,r,s d,r,s,r为这一步往右走的概率，d为这一步往下走的概率，s为原地不动的概率，求从 ( 1 , 1 ) (1,1) (1,1)到 ( n , m ) (n,m) (n,m)的期望步数。
n ∗ m < = 1 e 6 n*m<=1e6 n∗m<=1e6
一道正常的笔试题，算是难得的非常正常了…
dp转移方程如下：
d p [ G ( i , j ) ] = ( d p [ G ( i + 1 , j ) ] ∗ d [ G ( i , j ) ] + d p [ G ( i , j + 1 ) ] ∗ r [ G ( i , j ) ] + 1 ) / ( 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)]); 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 / ( 1.0 − s [ G ( i , j ) ] ) 1/(1.0-s[G(i,j)]) 1/(1.0−s[G(i,j)])的含义…
比如每次有0.5的概率走出格子，那么期望需要2次才能走出这个格子。
每次有1/3的概率走出格子，期望需要3次走出该格子。（帮助大家理解举的例子…）
那么考虑每次有p的概率走出格子，则期望需要1/p次走出这个格子。
故得到上面式子的 1 / ( 1.0 − s [ G ( i , j ) ] ) 1/(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 ( n l o g n ) O(nlogn) O(nlogn) TLE。。。
以下是 TLE 78per代码
更新 O ( n ) O(n) O(n)做法：
找出开头部分和结尾部分的最长的递增序列，放一个L在开头位置，一个R在结尾开始递增，且大于中间所有数的数，的开头位置，L到R表示为需要排序的序列区间，由于随着L的增加，R也是单调增加的（易得…）那么用一个two-pointer就能做到严格 O ( n ) 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
