本來不想寫題解的只祠。畅卓。可是今日頭條要4.1號(hào)才出題解那我就蠻寫一下咯（昨天做完題要和GF視頻就沒寫了
ios崗只有3題編程
1.輸入一個(gè)數(shù)組徒仓，尋找一個(gè)嚴(yán)格按照先遞增后遞減的數(shù)組，輸出區(qū)間的標(biāo)號(hào)洁墙，如果沒有就輸出-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個(gè)句子热监，然后給m個(gè)查詢捺弦，查詢給的結(jié)果是之前句子中單詞匹配數(shù)最高的結(jié)果
首先把每個(gè)句子把單詞做切分，構(gòu)成n個(gè)set孝扛，然后每次查詢也把句子通過單詞做一次切分列吼，然后遍歷n個(gè)set每次把查詢set中的成員來統(tǒng)計(jì)匹配數(shù)量
#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.有兩個(gè)等長(zhǎng)數(shù)組A和B，每次查詢時(shí)候兩個(gè)數(shù)a,b苦始，求同時(shí)存在a<=A[i]&&b<=B[i]的數(shù)量
首先把A和B綁定起來按A排個(gè)序寞钥，然后我們要求(a,b)成立的個(gè)數(shù)，從最大的A[i]中往小的遍歷盈简，找到零界值，然后代表著這個(gè)區(qū)間內(nèi)a肯定是滿足條件的太示，接下來就要看b在這個(gè)區(qū)間內(nèi)滿足<B的個(gè)數(shù)柠贤。因?yàn)樗o的數(shù)據(jù)量都是1e5，所以按普通的遍歷估計(jì)是不行的类缤，所以我用了一個(gè)線段樹來進(jìn)行這種查詢臼勉。把這個(gè)區(qū)間內(nèi)的B[i]全部加入線段樹內(nèi)，然后每次查詢時(shí)候時(shí)間復(fù)雜度就是O（lg N） （為什么的話自己去看線段樹咯~） 然后每次就用b為索引進(jìn)行查詢餐弱。但是這里有一個(gè)tips宴霸，就是要把查詢的(a,b)組也進(jìn)行排個(gè)序，這樣每次從最大的a開始進(jìn)行建樹膏蚓，這樣可以保證每次查詢的區(qū)間是有小變大的瓢谢，樹大小是遞增的，這樣就可以不用去做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; //區(qū)間從后往前擴(kuò)大
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進(jìn)入樹中
add();
p--;
}
Z=q[i].b.y; //對(duì)q[i].b.y進(jìn)行查詢
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
*/
可能描述不夠好氓扛，有錯(cuò)誤希望可以指出~THX
