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
*/