美团3.13笔试题
感觉题目比较简单
第一题：就是一个n行m列矩阵，让你输出行列翻转。
输入:
3 3
1 2 3
4 5 6
7 8 9
输出：
1 4 7
2 5 8
3 6 9
c语言语法题
/*
* @Author: 7QQQQQQQ
* @IDE: vscode
* @Date: 2021-03-13 16:01:11
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e2+50;
int a[N][N];
int main(){
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(int j=1;j<=m;j++){
for(int i=1;i<=n;i++){
cout<<a[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
第二题：给你一个字符串，你提取数字后，对数字进行从小到大输出，数字要去除前导0
简单模拟题
/*
* @Author: 7QQQQQQQ
* @IDE: vscode
* @Date: 2021-03-13 16:10:08
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e2+50;
int main(){
string s;cin>>s;
vector<string > ans;
for(int i=0;i<s.size();i++){
if(s[i]>='0' && s[i]<='9'){
string q="";
while(i<s.size() && s[i]>='0' && s[i]<='9'){
q+=s[i];
++i;
}
--i;
string a="";
int flag=0;
for(int j=0;j<q.size();j++){
if(q[j]=='0' && !flag) continue;
flag=1;
a+=q[j];
}
if(a.size()==0) a="0";
ans.push_back(a);
}
}
sort(ans.begin(),ans.end(),[](string a,string b){
if(a.size()!=b.size()) return a.size()<b.size();
return a<b;
});
for(auto &x:ans) cout<<x<<endl;
return 0;
}
第三题：给n个数，求每个窗口大小为m的众数是多少
输出n-m+1行
我的做法是考虑维护一个版本号机制，就是延迟删除即可，优先队列维护一个当前的值和当时的版本号，这里的版本号指当时这个数字出现的次数。
第四题：给一棵树，每个点有权值，让选择点，要求选择不相邻的点，求使得权值最大，在使得权值最大的情况下，求选择的点中最小的权值最大是多少
/*
* @Author: 7QQQQQQQ
* @IDE: vscode
* @Date: 2021-03-13 16:12:48
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+50;
int a[N];
struct node{
int val,cnt;
friend bool operator<(node a,node b){
if(a.cnt!=b.cnt) return a.cnt<b.cnt;
return a.val>b.val;
}
};
map<int,int>mp;
int main(){
int n,m;cin>>n>>m;
priority_queue<node> que;
for(int i=1;i<=n;i++){
cin>>a[i];
if(i<=m){
que.push({a[i],++mp[a[i]]});
}
}
cout<<que.top().val<<endl;
for(int i=m+1;i<=n;i++){
mp[a[i-m]]--;
que.push({a[i],++mp[a[i]]});
while(!que.empty()){
node now=que.top();
if(now.cnt!=mp[now.val]){
que.pop();
continue;
}
break;
}
cout<<que.top().val<<endl;
}
return 0;
}
树型dp
其实就是树型dp入门题，那个没有上司的舞会。
只不过他多要求输出最小点权的最大值
那么只需要在dp转移的时候维护一个mi数组一起转移就可以啦
/*
* @Author: 7QQQQQQQ
* @IDE: vscode
* @Date: 2021-03-13 16:23:05
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+50;
ll val[N];
vector<int> e[N];
ll dp[N][2];//表示以i为根的子树选了 1/0 当前根/不选根 的最大值
ll mi[N][2];
void dfs(int x,int fa){
dp[x][1]=val[x];
mi[x][1]=val[x];
dp[x][0]=0;
for(auto &son:e[x]){
if(son==fa) continue;
dfs(son,x);
dp[x][1]+=dp[son][0];
mi[x][1]=min(mi[x][1],mi[son][0]);
dp[x][0]+=max(dp[son][1],dp[son][0]);
if(dp[son][1]>dp[son][0]) mi[x][0]=min(mi[x][0],mi[son][1]);
else if(dp[son][1]<dp[son][0]) mi[x][0]=min(mi[x][0],mi[son][0]);
else mi[x][0]=min(mi[x][0],max(mi[son][0],mi[son][1]));
}
}
int main(){
memset(mi,63,sizeof mi);
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>val[i];
}
for(int i=1;i<n;i++){
int x,y;cin>>x>>y;
e[x].push_back(y);
e[y].push_back(x);
}
dfs(1,0);
ll S1=0,S2=0;
for(int i=1;i<=n;i++){
S1=max(S1,max(dp[i][0],dp[i][1]));
}
cout<<S1<<" ";
for(int i=1;i<=n;i++){
if(S1==dp[i][0]) S2=max(S2,mi[i][0]);
if(S1==dp[i][1]) S2=max(S2,mi[i][1]);
}
cout<<S2;
return 0;
}
问最多能走多少个点。
也很简单，就是对于有边的点，我们比较一下点权大小，然后去建单向边，
然后对每个点去dfs即可，因为要去我下一个点的点权比当前小，所以构造出来的图是一片森林，因为原图可能不连通，可能是多棵树。
dfs即可。
如果我之前算过从1出发，最多能走5个点，那么我下次走到1，就无须继续走了，直接加上从1能走的最远的路即可。
/*
* @Author: 7QQQQQQQ
* @IDE: vscode
* @Date: 2021-03-13 17:06:42
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+50;
vector<int> e[N];
ll val[N];
ll dis[N],vis[N];
void dfs(int x,int f){
vis[x]=1;
ll nxt=0;
for(auto &y:e[x]){
if(y==f) continue;
if(!vis[y]) dfs(y,x);
nxt=max(nxt,dis[y]);
}
dis[x]+=nxt;
}
int main(){
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>val[i];
dis[i]=1;
}
for(int i=1;i<=m;i++){
int x,y;cin>>x>>y;
if(val[x]>val[y]) e[x].push_back(y);
if(val[x]<val[y]) e[y].push_back(x);
}
ll ans=0;
for(int i=1;i<=n;i++){
if(!vis[i]) dfs(i,0);
}
for(int i=1;i<=n;i++){
ans=max(ans,dis[i]);
}
cout<<ans;
return 0;
}
