9.4美团笔试
AC1235，4题目看错了，以为是01矩阵求四边形，样例没看写了半天ac9%，尬住了
01思路
状态转移方程
a[i][0][0]=(a[i-1][0][1]+a[i-1][0][0])%mod;//表示当前aa状态只能由前面aa或者ab继承 a[i][0][1]=(a[i-1][1][1])%mod;//表示当前ab状态只能由前面bb继承 a[i][1][1]=(a[i-1][1][1]+a[i-1][1][0])%mod;//表示当前bb状态只能由前面ba或者bb继承 a[i][1][0]=(a[i-1][0][0])%mod;//表示当前ba状态只能由前面aa继承
02思路
建图，跑弗洛伊德，一开始91%，然后想到没跑到的可能输出0，然后还是91%，还好看了公告没跑到的-1
建图：先把每个线路能通过的点，放一块，表示这些点到点的距离是1
代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
#define mod 998244353
#define inf 0x3f3f3f3f
using namespace std;
const int N=500+10;
int ans[N][N];
int n,m;
vector<int>a[N];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
int num;scanf("%d",&num);
for(int j=0;j<num;j++){
int u;scanf("%d",&u);
a[u].push_back(i);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j) ans[i][j]=0;
else ans[i][j]=inf;//初始化
}
}
for(int i=1;i<=m;i++){
int x=a[i].size();
for(int j=0;j<x;j++){
for(int k=j+1;k<x;k++){
ans[a[i][j]][a[i][k]]=1;
ans[a[i][k]][a[i][j]]=1;//建图
}
}
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(ans[i][j]>ans[i][k]+ans[k][j]){
ans[i][j]=ans[i][k]+ans[k][j];//弗洛伊德
}
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(ans[i][j]==inf){
ans[i][j]=-1;//没走到的标记为-1
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
printf(j==n?"%d\n":"%d ",ans[i][j]);
}
}
return 0;
}
3思路
全场最简单题，核心代码
for(int i=n-1;i>=0;i--){
if(s[i]=='c')num++;//num表示c的个数
else sum+=num;//sum表示移动次数
}04思路
最后十分钟没想好怎么去重，跑了一个dfs，求一个04思路（评论区两大牛，两个猛男思路）
05思路
前缀和+线段树求区间最小最大值
ac代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
#define mod 998244353
#define inf 0x3f3f3f3f
using namespace std;
const int N=1e5+10;
ll trmin[N*4],trmax[N*4];
ll sum[N];
int n,m,id=0;
ll a[N];
void pushup(int x){
trmin[x]=min(trmin[x<<1],trmin[x<<1|1]);
trmax[x]=max(trmax[x<<1],trmax[x<<1|1]);
}
void build(int x,int l,int r){
if(l==r){
trmin[x]=a[l];
trmax[x]=a[l];//cout<<a[l]<<endl;
return;
}
int mid=(l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
pushup(x);
}
ll querymx(int x,int l,int r,int l1,int r1){
if(l1<=l && r<=r1){
return trmax[x];
}
int mid=(l+r)>>1;
ll zhi=0;
if(l1<=mid){
zhi=max(zhi,querymx(x<<1,l,mid,l1,r1));
}
if(r1>mid){
zhi=max(zhi,querymx(x<<1|1,mid+1,r,l1,r1));
}
return zhi;
}
ll querymi(int x,int l,int r,int l1,int r1){
if(l1<=l && r<=r1){
return trmin[x];
}
int mid=(l+r)>>1;
ll zhi=10000000100;
if(l1<=mid){
zhi=min(zhi,querymi(x<<1,l,mid,l1,r1));
}
if(r1>mid){
zhi=min(zhi,querymi(x<<1|1,mid+1,r,l1,r1));
}
return zhi;
}
int main(){
sum[0]=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);sum[i]=sum[i-1]+a[i];
}
build(1,1,n);
ll sumx=0;
for(int i=1;i<=n-m+1;i++){
ll mi=querymi(1,1,n,i,i+m-1),mx=querymx(1,1,n,i,i+m-1);
ll xx=sum[i+m-1]-sum[i-1]-mi-mx;
if(xx>sumx) id=i,sumx=xx;
}
printf("%d\n",id);
return 0;
}
/*
10 3
14 24 14 22 44 29 33 45 36 48
*/#美团##C/C++#
查看11道真题和解析
美团AI面326人在聊