2023-9.12 百度 移动软件 笔试

被锁简历了，还是提前批投的，有点无奈。

选择基本都是蒙的。

第一题：

思路：把构造序列，转化成求类似于最长上升子序列的过程，当然并不需要真的求出来。

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
void solve()
{
	int n;cin>>n;
	vector<int>a(n+1,0);
	for(int i=1;i<=n;i++)cin>>a[i];
	int cur=0;
	int idx=0;
	while(idx<(int)a.size())
	{
		while(idx<(int)a.size()&&a[idx]!=cur+1)idx++;
		
		if(a[idx]==cur+1)idx++,cur++;
	}
	cout<<(cur?n-cur:-1)<<endl;
    return ;
}
int main()
{
	freopen("test.in","r",stdin);
	solve();
	return 0;
}

第二题：

最开始没读懂题，后来理解了以后，发现其实原始任务的操作是固定的，因此只需要考虑如何插入即可。

过程抽象出来就是，区间修改，然后查询区间最大值

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
#define int long long
#define l first
#define r second
int st[N][32];
void init(vector<int>&a)
{
	int n=(int)a.size()-2;
	for(int j=0;j<=(int)log2(n);j++)
	 for(int i=1;i+(1<<j)-1<=n;i++)
	  if(!j)st[i][j]=a[i];//i+(1<<j)-1-x+1=1<<(j-1)
	  else st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
void solve()
{
	int n,m,k,t;
	cin>>n>>m>>k>>t;
	vector<int>a(n+2,0);
	vector<pair<int,int>>op(m+1);
	for(int i=1;i<=m;i++)cin>>op[i].l;
	for(int i=1;i<=m;i++)cin>>op[i].r;
	
	for(int i=1;i<=m;i++)
	{
		int l=op[i].l,r=op[i].r;
		a[l]++,a[r+1]--;
	}
	for(int i=1;i<=n;i++)a[i]+=a[i-1];//差分数组
	
	init(a);

	int ans=0;
	for(int i=1;i+k-1<=n;i++)
	{
		int l=i,r=i+k-1;//
		int len=(int)log2(r-l+1);
		int maxv=max(st[l][len],st[r-(1<<len)+1][len]);
	    if(maxv<t)ans++; 
	}
	cout<<ans<<endl;
    return ;
}
//t=2 k=3 
//1 1 1 2 2 1 1 1 1 1
//
signed main()
{
	freopen("test.in","r",stdin);
	solve();
	return 0;
}