美团后台笔试8.29 ac接近五个题目，
1 （ac） 字符串的那个 MT MT
#include <bits/stdc++.h>
using namespace std;
string str;
string head(string s){
int flag =0;
for(int i = 0; i < s.length(); i++){
if(s[i] == 'M'){
flag = 1;
}
if(s[i] == 'T' && flag == 1){
return s.substr(i+1, s.length());
}
}
return s;
}
string rear(string s){
int flag =0;
for(int i = s.length() - 1;i>=0 ;i--){
if(s[i] == 'T'){
flag = 1;
}
if(s[i] == 'M' && flag == 1){
return s.substr(0, i);
}
}
return s;
}
int main(){
int n;
cin>>n;
cin>>str;
cout<<rear(head(str))<<endl;
return 0;
} 2 （ac） 优先级分配地区的题目 #include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
int a;
vector<int>v1(n+1,0),v2;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>a;
if(!v1[a]){
v2.push_back(a);
v1[a] = 1;
j++;
while(j<n){
cin>>a;
j++;
}
}
}
}
for(int i=0;i<n;i++){
cout<<v2[i]<<" ";
}
return 0;
}
3 （小美追小团的题目） 0.91 #include <bits/stdc++.h>
using namespace std;
struct node{
int id;
node* son;
}tree[50005];
int up[50005];
int down[50005];
int path[50005];
int x,y,len;
bool find(int father,int id,int deep){
bool bo = false,isson = false;
node*next = tree[id].son;
up[id] = deep;
while (next !=NULL){
if(next -> id == father){
next = next ->son;
continue;
}
if(find(id,next->id,deep+1)){
len++;
path[len] = id;
isson = true;
}
if(down[next->id] + 1 > down[id]){
down[id] = down[next->id] +1;
}
bo = true;
next = next->son;
}
if(bo == false)
down[id] = 1;
if(id == y || isson)
return true;
else
return false;
}
int main(){
int i,j,k,n,m;
node *next,*before;
cin>>n>>x>>y;
for(int i =0;i <= n; i++){
tree[i].id = i + 1;
tree[i].son = NULL;
up[i] = -1;
down[i] = -1;
}
for(i =0;i<n-1;i++){
cin>>j>>k;
next = tree[j].son;
before = next;
while(next !=NULL){
before = next;
next = next->son;
}
next = new node;
next ->id = k;
next ->son = NULL;
if(before == NULL)
tree[j].son = next;
else
before ->son = next;
next = tree[k].son;
before = next;
while (next !=NULL){
before = next;
next = next->son;
}
next = new node;
next->id = j;
next ->son = NULL;
if(before == NULL){
tree[k].son = next;
} else{
before->son = next;
}
}
len =0;
path[0] = y;
find(-1,x,1);
k = up[path[0]] + down[path[0]];
for( i=0;i<=len/2;i++){
if(up[path[i]] + down[path[i]] > k){
k = up[path[i]] + down[path[i]];
}
}
cout<<k-2;
}
4 选择数据的 非降序子序列题目 暴力解决 0.64（没时间了，不知道暴力能不能全过） #include <bits/stdc++.h>
using namespace std;
int a[100005];
int main(){
int m,n;
cin>>m>>n;
for(int i = 0; i < n; i++){
cin>>a[i];
}
int pre = -1 ,flag = 1;
int count =0;
for(int i = 1;i <= m;i++){
for(int j = i; j <= m; j++){
pre = -1;
flag = 1;
for(int k = 0;k < n;k++){
if(a[k] >= i && a[k] <= j)
continue;
else{
if(a[k] >= pre){
pre = a[k];
}
else{
flag = 0;
break;
}
}
}
if(flag == 1)
count ++;
}
}
cout<<count<<endl;
return 0;
}
5 复制粘贴的题目 ac #include <bits/stdc++.h>
using namespace std;
int a[2005];
int b[2006];
int main(){
int i,j,k,m,n;
int x,y;
char ch[25];
cin>>n;
for(i = 1; i <= n;i++){
cin>>a[i];
b[i] = -1;
}
cin>>m;
gets(ch);
for( i = 0;i< m ;i++){
memset(ch,0,sizeof(ch));
gets(ch);
k =0;
if(ch[0] == '1'){
sscanf(ch,"%d %d %d %d",&j,&k,&x,&y);
while(k > 0){
b[y] = a[x];
k--;
x++;
y++;
}
} else{
sscanf(ch,"%d %d",&j,&k);
cout<<b[k]<<endl;
}
}
return 0;
} 
