总共40道选择题+2道代码题(ak) , 希望有面试

40道选择题 :

DS(时间复杂度，图论,排序...)+计网+数据库+java基础(如:多态，接口，抽象类)+Linux常见命令+进程互斥，死锁 ；

有印象的 :

1. ()进程是所有进程的起点 : init
2. 那个算法可以避免死锁 : 银行家算法
3. Linux用于移动文件或目录的命令 : mv

1.调酒

// 由于材料短缺 ， 只够每种酒做一份的量 
// n 代表多少顾客 ， 每个顾客都有两份要点的酒 
// m 代表托尼能调的酒的编号范围 
// 求最多的能够满意的顾客 

看到数据范围小，直接二进制枚举就行了 :

#include<bits/stdc++.h>
using namespace std ;
#define PII pair<int,int>  
#define x first
#define y second 

const int N = 40 ;
int t[N] ;
int ans  = 0 ;

int main(){
	int n  , m ; cin >> n >> m ;
	vector<PII> a ;
	for(int i=0;i<n;i++){
        int ax , bx ; cin >> ax >> bx ;
        if(ax>m||bx>m) continue ;
        a.push_back({ax,bx}) ;
    }
    n = a.size() ;
	for(int i=0;i<(1<<n);i++){// 枚举所有的二进制可能 
		// if(i!=5) continue ;
		for(int k=0;k<N;k++) t[k] = 0 ;// 初始化 
		bool tag = true ;
		int cnt = 0  ;
		for(int j=0;j<n;j++){
			if((i>>j)&1){// 判断第j个选不选 
				cnt ++ ;
				t[a[j].x-1]++ ;
				t[a[j].y-1]++ ;
				if(t[a[j].x-1]>1) {
					tag = false ;
					break ;
				}
				if(t[a[j].y-1]>1){
					tag = false ;
					break ;
				}
				// cout << i << " " << j << endl ;
			}
		}
		// cout << i << " " << tag <<  " " << cnt << endl ;
		if(tag) ans = max(ans,cnt) ;
	}
	cout << ans << endl ;
}

2.盘古开山

// n座山，高度分别为hi
// 选择严格单调递增子区间开山
// 1e5
// 一次操作 ， 将一座山的高度修改为任意非负整数
// 求最长区间

dp : 用 r[i] 统计记录以该点为起点，后面是多长的子序列， 用l[i] 记录以该点为终点，前面是多长的子序列 , 然后枚举每一个点 :

• i==1 : ans = max(ans,r[2]+1) ;
• i==n : ans = max(ans,l[n-1]+1);
• else :如果a[i+1]-a[i-1]>=2 ,那么修改a[i]也就可以将左右连接起来 ，否则只能连接一段 ;

#include<bits/stdc++.h>
using namespace std ;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define PII pair<int,int>  
#define x first
#define y second 
#define int long long
#define endl '\n' 

const int N = 1e5 + 10 ;
int a[N] ;

inline void YSS(){
	int n ; cin >> n ;
	for(int i=1;i<=n;i++) cin >> a[i] ;
	if(n==1){
		cout << 1 << endl ;
		return ;
	}
	// 找到最右边
	vector<int> l(n+1,0) , r(n+1,0) ;
	r[n] = 1 ;// 记录以该点为起点，后面是多长的子序列 
	l[1] = 1 ;// 记录以该点为终点，前面是多长的子序列
	int ans = 0 ; 
	for(int i=n-1;i>=1;i--){
		if(a[i]<a[i+1]) r[i] = r[i+1]+1;
		else r[i] = 1 ;
		ans = max(r[i],ans) ;
	}
	for(int i=2;i<=n;i++){
		if(a[i]>a[i-1]) l[i] = l[i-1]+1 ;
		else l[i] = 1 ;
		ans = max(ans,l[i]) ;
	}
	for(int i=1;i<=n;i++){
		if(i==1) ans = max(ans,r[i+1]+1);
		else if(i==n)ans = max(ans,l[i-1]+1) ;
		else{// 修改a[i] 
			if(a[i+1]-a[i-1]>=2){
				ans = max(ans,l[i-1]+r[i+1]+1) ;
			}else{
				ans = max(ans,l[i-1]+1) ;
				ans = max(ans,r[i+1]+1) ;
			}
		}
	}	
	cout << ans << endl ;
}

signed main(){
	IOS
	int T ; cin >> T ;
	while(T--){
		YSS() ;
	}
	return 0 ;
}