0812美团笔试题解及代码分享
T1
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int maxl=1e6+10;
int n,m,tot,ans;
int a[maxl];
char s[maxl];
inline void prework()
{
cin>>n;
for(int i=1;i<=n;i++)
{
int x;cin>>x;
a[x]=i;
}
int x,y;cin>>x>>y;
if(abs(a[x]-a[y])==1)
puts("Yes");
else
puts("No");
}
inline void mainwork()
{
}
inline void print()
{
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
prework();
mainwork();
print();
return 0;
}
T2
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int maxl=1e6+10;
int n,m,tot;ll ans;
ll a[maxl],sum[maxl];
char s[maxl];
inline void prework()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i],sum[i]=sum[i-1]+a[i];
a[i+n]=a[i];
}
for(int i=n+1;i<=2*n;i++)
sum[i]=sum[i-1]+a[i];
int x,y;
cin>>x>>y;
if(x>y)
swap(x,y);
ll ans=min(sum[y-1]-sum[x-1],sum[x+n-1]-sum[y-1]);
cout<<ans;
}
inline void mainwork()
{
}
inline void print()
{
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
prework();
mainwork();
print();
return 0;
}
T3
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int maxl=1e3+10;
int n,m,tot;ll ans;
int a[maxl][maxl];
ll row[maxl],col[maxl];
char s[maxl];
inline void prework()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
row[i]+=a[i][j];
col[j]+=a[i][j];
}
}
inline void mainwork()
{
ll you=0,xia=0,zuo=0,shang=0;
for(int j=1;j<=m;j++)
you+=col[j];
ans=you;xia=you;
for(int j=1;j<m;j++)
{
you-=col[j];
zuo+=col[j];
ans=min(ans,abs(you-zuo));
}
for(int i=1;i<n;i++)
{
shang+=row[i];
xia-=row[i];
ans=min(ans,abs(shang-xia));
}
}
inline void print()
{
cout<<ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
prework();
mainwork();
print();
return 0;
}
T4 因为一定要整除，所以枚举所有因数就行了，然后构造完以后bfs或者dfs搞flood fill求连通块个数，O(nsqrt(n))
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int maxl=1e6+10;
int n,m,tot,ans;
int a[maxl];
string s;
int tx[4]={0,1,0,-1};
int ty[4]={1,0,-1,0};
inline void prework()
{
cin>>n;
cin>>s;
}
inline void solv(int c)
{
vector<string> b;int nowid=0;
int r=n/c;
for(int i=1;i<=r;i++)
{
b.emplace_back(s.substr(nowid,c));
nowid+=c;
}
vector<vector<int>> vis(r,vector<int>(c,0));
auto bfs=[&](int ix,int iy) ->void
{
using pii=pair<int,int>;
queue<pii> q;
q.push({ix,iy});vis[ix][iy]=true;
char ch=b[ix][iy];
while(q.size())
{
pii d=q.front();q.pop();
for(int k=0;k<4;k++)
{
int x=d.first+tx[k],y=d.second+ty[k];
if(x<0 || x>=r || y<0 || y>=c ||
vis[x][y] || ch!=b[x][y])
continue;
vis[x][y]=1;
q.push({x,y});
}
}
};
int cnt=0;
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)
if(!vis[i][j])
{
cnt++;
bfs(i,j);
}
ans=min(ans,cnt);
}
inline void mainwork()
{
ans=n;int up=sqrt(n);
for(int i=1;i<=up;i++)
if(n%i==0)
solv(i),solv(n/i);
}
inline void print()
{
cout<<ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
prework();
mainwork();
print();
return 0;
}
T5 设dp[u][1]表示u为染红点，某个子节点也染红，u子树最多的染色点个数，dp[u][0]则表示u不染色的子树最多个数。可以注意到dp[u][1]如果选择把a[u]和a[v]染红，那么转移的时候v只能选择dp[v][0]，因为要求v之前不被染色
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int maxl=1e6+10;
int n,m,tot,ans;
ll a[maxl];
int dp[maxl][2];
char s[maxl];
vector<int> e[maxl];
inline void prework()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<n;i++)
{
int u,v;cin>>u>>v;
e[u].emplace_back(v);
e[v].emplace_back(u);
}
}
inline bool x2(ll x,ll y)
{
ll d=sqrt(x*y);
return d*d==x*y;
}
inline void dfs(int u,int fa)
{
for(int &v:e[u])
{
if(v==fa) continue;
dfs(v,u);
dp[u][0]+=max(dp[v][1],dp[v][0]);
}
for(int &v:e[u])
{
if(v==fa || !x2(a[u],a[v])) continue;
dp[u][1]=max(dp[u][1],dp[u][0]-max(dp[v][0],dp[v][1])+2+dp[v][0]);
}
}
inline void mainwork()
{
dfs(1,0);
ans=max(dp[1][0],dp[1][1]);
}
inline void print()
{
cout<<ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
prework();
mainwork();
print();
return 0;
}
#秋招##笔试##美团##美团笔试##美团秋招#
