本来不想写题解的。。可是今日头条要4.1号才出题解那我就蛮写一下咯（昨天做完题要和GF视频就没写了
ios岗只有3题编程
1.输入一个数组，寻找一个严格按照先递增后递减的数组，输出区间的标号，如果没有就输出-1 -1
思路就是扫一遍递增的开始的前置位，再扫一遍递减的后置位，然后减一下找最大值
#include <bits/stdc++.h>
#define rep(i,a,b) for (int i=a;i<b;i++)
using namespace std;
const int N=1e7+11;
int l[N],r[N],a[N];
int main()
{
int n;
cin>>n;
rep(i,0,n)
scanf("%d",&a[i+1]);
a[0]=INT_MAX;
l[0]=0;
rep(i,1,n+1)
if (a[i]>a[i-1])l[i]=l[i-1];
else l[i]=i;
a[n+1]=INT_MAX;
for (int i=n;i>=1;i--)
if (a[i]>a[i+1]) r[i]=r[i+1];
else r[i]=i;
int ans=-120,al=0,ar=0;
rep(i,2,n)
if (-l[i]+r[i]>ans&&l[i]!=i&&r[i]!=i) al=l[i],ar=r[i],ans=r[i]-l[i];
cout<<al-1<<' '<<ar-1<<endl;
return 0;
}
2.第二题给n个句子，然后给m个查询，查询给的结果是之前句子中单词匹配数最高的结果
首先把每个句子把单词做切分，构成n个set，然后每次查询也把句子通过单词做一次切分，然后遍历n个set每次把查询set中的成员来统计匹配数量
#include <bits/stdc++.h>
#define rep(i,a,b) for (int i=a;i<b;i++)
using namespace std;
const int N=2e4+100;
char s[N];
char dic[666][N];
set<string>se[666],a;
set<string>::iterator it;
int main()
{
int n,m;
cin>>n>>m;
getchar();
rep(i,0,n)
{
gets(s);
strcpy(dic[i], s);
string st;
int len=strlen(s);s[len++]=' ';s[len]=0;
for (int j=0;s[j];j++)
if (s[j]==' ') se[i].insert(st),st.clear();
else st+=s[j];
}
rep(i,0,m)
{
gets(s);
string st;
a.clear();
int len=strlen(s);s[len++]=' ';s[len]=0;
for (int j=0;s[j];j++)
if (s[j]==' ') a.insert(st),st.clear();
else st+=s[j];
int ans=0,p=-1;
rep(j,0,n)
{
int tot=0;
for (it=a.begin();it!=a.end();it++)
if (se[j].count(*it)) tot++;
if (tot>ans) ans=tot,p=j;
}
printf("%s\n",dic[p]);
}
return 0;
}
/*
6 3
An algorithm is an effective method that can be expressed within a finite amount of space and time
Starting from an initial state and initial input the instructions describe a computation
That when executed proceeds through a finite number of successive states
Eventually producing output and terminating at a final ending state
The transition from one state to the next is not necessarily deterministic
Some algorithms known as randomized algorithms incorporate random input
Next to the transition
Wormhole infinite time and space
The transition from one state to the next is not necessarily deterministic
*/
3.有两个等长数组A和B，每次查询时候两个数a,b，求同时存在a<=A[i]&&b<=B[i]的数量
首先把A和B绑定起来按A排个序，然后我们要求(a,b)成立的个数，从最大的A[i]中往小的遍历，找到零界值，然后代表着这个区间内a肯定是满足条件的，接下来就要看b在这个区间内满足<B的个数。因为它给的数据量都是1e5，所以按普通的遍历估计是不行的，所以我用了一个线段树来进行这种查询。把这个区间内的B[i]全部加入线段树内，然后每次查询时候时间复杂度就是O（lg N） （为什么的话自己去看线段树咯~） 然后每次就用b为索引进行查询。但是这里有一个tips，就是要把查询的(a,b)组也进行排个序，这样每次从最大的a开始进行建树，这样可以保证每次查询的区间是有小变大的，树大小是递增的，这样就可以不用去做delete操作了。
#include <bits/stdc++.h>
#define rep(i,a,b) for (int i=a;i<b;i++)
using namespace std;
#define PII pair<int,int>
#define mp make_pair
#define x first
#define y second
const int N=1e5+111;
PII a[N];
struct node
{
PII b;
int id;
}q[N];
bool cmp(const node &a,const node &b)
{
return a.b<b.b;
}
int ans[N];
int f[N<<2],Z,Y=1e5;
int add(int l=1,int r=1e5,int p=1)
{
int mid=l+r>>1;
if (l==r) return f[p]=f[p]+1;
if (Z<=mid) return f[p]=add(l,mid,p*2)+f[2*p+1];
if (Z>mid) return f[p]=add(mid+1,r,p*2+1)+f[2*p];
}
int ask(int l=1,int r=1e5,int p=1)
{
int mid=l+r>>1;
if (Z<=l&&r<=Y) return f[p];
if (Y<=mid) return ask(l,mid,2*p);
if (Z>mid) return ask(mid+1,r,2*p+1);
return ask(l,mid,2*p)+ask(mid+1,r,2*p+1);
}
int main()
{
int n,m;
cin>>n>>m;
rep(i,0,n)
scanf("%d",&a[i].x);
rep(i,0,n)
scanf("%d",&a[i].y);
sort(a,a+n);
rep(i,0,m)
scanf("%d%d",&q[i].b.x,&q[i].b.y),q[i].id=i;
sort(q,q+m,cmp);
int p=n-1; //区间从后往前扩大
for (int i=m-1;i>=0;i--)
{
while (a[p].x>=q[i].b.x&&p>=0)
{
Z=a[p].y; //添加a[p].y进入树中
add();
p--;
}
Z=q[i].b.y; //对q[i].b.y进行查询
ans[q[i].id]=ask();
}
rep(i,0,m)
printf("%d\n",ans[i]);
return 0;
}
/*
3 2
3 2 4
6 5 8
1 1
4 8
*/
可能描述不够好，有错误希望可以指出~THX
