美团笔试AK 8.12

整体难度不大，6000hc可信度极高，冲团子就完事了

第一题思路：用mp存下标，然后判断是否相邻即可

#include <iostream>
#include <map>
#include <unordered_map>
using namespace std;
unordered_map<int,int>mp;
int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        int w;cin>>w;
        mp[w]=i;
    }
    int x,y;
    cin>>x>>y;
    if(abs(mp[x]-mp[y])==1){
        cout<<"Yes"<<endl;
    }else cout<<"No"<<endl;
}

第二题思路：看是否有从n~1的通路，然后判断逆时针快还是顺时针快就好了

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
#define ll long long
const int N = 1e5+5;
ll k[N];
int main(){
    ll sum=0;
    ll lesum=0;
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>k[i];
        sum+=k[i];
    }
    int x,y;cin>>x>>y;
    if(y>=x){
        for(int i=x;i<y;i++){
            lesum+=k[i];
        }
    }else{
        for(int i=y;i<x;i++){
            lesum+=k[i];
        }
    }
    // cout<<lesum<<' '<<sum-lesum<<endl;
    ll ans=min(lesum,sum-lesum);
    cout<<ans<<endl;
}

第三题思路：求横向纵向的前缀和

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 1e3+5;
ll k[N][N];
ll sumN[N][N];
ll sumM[N][N];
int main(){
    int n,m;
    cin>>n>>m;
    ll allsum=0;
    memset(sumN,0,sizeof(sumN));
    memset(sumM,0,sizeof(sumM));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>k[i][j];
            allsum+=k[i][j];
        }
    }
    ll ans=allsum;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            sumN[i][j]=sumN[i][j-1]+k[i][j];
        }
    }
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=m;j++){
    //         cout<<sumM[i][j]<<' ';
    //     }cout<<endl;
    // }
    for(int i=1;i<m;i++){
        ll lesum=0;
        for(int j=1;j<=n;j++){
            lesum+=sumN[j][i];
        }
        ans=min(ans,abs(allsum-lesum-lesum));
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            sumM[i][j]=sumM[i-1][j]+k[i][j];
        }
    }
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=m;j++){
    //         cout<<sumM[i][j]<<' ';
    //     }cout<<endl;
    // }
    for(int i=1;i<n;i++){
        ll lesum=0;
        for(int j=1;j<=m;j++){
            lesum+=sumM[i][j];
        }
        // cout<<lesum<<endl;
        ans=min(ans,abs(allsum-lesum-lesum));
    }
    cout<<ans<<endl;
}

第四题思路：先处理成连通块，然后就是油田问题了

#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
using namespace std;
const int N = 1e4+5;
vector<string>v[N];
string target;
string mapInfo[N];
int dir[4][2]={0,1,0,-1,1,0,-1,0};
int lastans;
void dfs(int n,int m,int x,int y,vector<vector<int> >&vis){
    vis[x][y]=1;
    for(int i=0;i<4;i++){
        int xx=x+dir[i][0];
        int yy=y+dir[i][1];
        if(xx<0||xx>=n||yy<0||yy>=m){
            continue;
        }
        if(vis[xx][yy]==1){
            continue;
        }
        if(mapInfo[xx][yy]==mapInfo[x][y]){
            dfs(n,m,xx,yy,vis);
        }
    }
}
void calculate(int hang,int lie){
    int n=hang;
    int m=lie;
    vector<vector<int> >vis;
    for(int i=0;i<n;i++){
        vector<int>temp;
        for(int j=0;j<m;j++){
            temp.push_back(0);
        }
        vis.push_back(temp);
    }
    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(vis[i][j]==0){
                dfs(n,m,i,j,vis);
                ans++;
            }
        }
    }
    lastans=min(lastans,ans);
    // cout<<ans<<endl;
}
void desolve(string target,int hang,int lie){
    
    int hanglen=target.length()/hang;
    int beindex=0;
    for(int i=0;i<hang;i++){
        string temp;
        temp=target.substr(beindex,hanglen);
        beindex+=hanglen;
        mapInfo[i]=temp;
    }
    calculate(hang,lie);
}
int main(){
    int n;cin>>n;
    cin>>target;
    lastans=n;
    for(int i=1;i<=n;i++){
        if(n%i==0){
            desolve(target,i,n/i);
        }
    }
    cout<<lastans<<endl;
}

第五题思路：优先判断叶子结点，通过一个队列来维护就好了

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#define ll long long
#define ull unsigned long long
const int N = 1e5+5;
using namespace std;
vector<int>ve[N];
int du[N];
ll val[N];
int vis[N];
queue<int>q;
int n;
int ans;
bool judge(int index1,int index2){
    ull tar=val[index1]*val[index2];
    ull use=sqrt(tar);
    if(tar==use*use){
        return true;
    }else{
        return false;
    }
    
}
void solve(int index){
    int flag=0;
    int tar=0;
    for(int i=0;i<ve[index].size();i++){
        if(vis[ve[index][i]]==1)continue;
        if(judge(index,ve[index][i])==true){
            // cout<<123123<<endl;
            flag=1;
            tar=ve[index][i];
            break;
        }
    }
    if(flag==1){
        vis[index]=1;
        vis[tar]=1;
        for(int i=0;i<ve[index].size();i++){
            du[ve[index][i]]--;
            if(du[ve[index][i]]==1&&vis[ve[index][i]]==0){
                // cout<<"aaa"<<endl;
                q.push(ve[index][i]);
            }
        }
        for(int i=0;i<ve[tar].size();i++){
            du[ve[tar][i]]--;
            if(du[ve[tar][i]]==1&&vis[ve[tar][i]]==0){
                // cout<<"bbb"<<endl;
                q.push(ve[tar][i]);
            }
        }
        ans+=2;
    }else{
        vis[index]=1;
        for(int i=0;i<ve[index].size();i++){
            du[ve[index][i]]--;
            if(du[ve[index][i]]==1&&vis[ve[index][i]]==0){
                q.push(ve[index][i]);
            }
        }
    }
}
int main(){
    memset(vis,0,sizeof(vis));
    ans=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>val[i];
    }
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        ve[u].push_back(v);
        ve[v].push_back(u);
        du[u]++;
        du[v]++;
    }
    for(int i=1;i<=n;i++){
        if(du[i]==1){
            q.push(i);
        }
    }
    while(!q.empty()){
        int w=q.front();q.pop();
        // cout<<w<<endl;
        if(vis[w]==0){
            solve(w);
        }
        // cout<<w.index<<' '<<w.du<<endl;
    }
    cout<<ans<<endl;
}