4.26华为笔试，两题都差4%，急死我了

1、spfa求最长路加判环 100%

#include<bits/stdc++.h>
#define x first
#define y second
#define mem(a,b) memset(a,b,sizeof(a))
#define F(i,l,r) for(int i=l;i<=r;i++)
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;

const int N=1005;

struct edge
{
    int v,w;
};
int n,dst[N],vis[N],cnt[N];
vector<edge> g[N];

int spfa(int s)
{
    mem(dst,0);
    mem(vis,0);
    mem(cnt,0);

    queue<int> q;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();

        vis[u]=0;
        for(edge e:g[u])
        {
            int v=e.v,w=e.w;
            if(dst[v]<dst[u]+w)
            {
                dst[v]=dst[u]+w;
                cnt[v]=cnt[u]+1;
                if(cnt[v]>n+10)
                {
                    return -1;
                }
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    int res=0;
    for(int i=1;i<=n;i++)
        res=max(res,dst[i]);
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int k;
        cin>>k;
        while(k--)
        {
            int v;
            cin>>v;
            g[v].push_back({i,1});
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int d=spfa(i);
        if(d==-1)
        {
            cout<<-1<<endl;
            return 0;
        }
        ans=max(ans,spfa(i));
    }
    cout<<ans+1<<endl;

    return 0;
}

2、96%，不知道哪里出bug了

#include<bits/stdc++.h>
#define x first
#define y second
#define mem(a,b) memset(a,b,sizeof(a))
#define F(i,l,r) for(int i=l;i<=r;i++)
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;

const int N=2e5+1000;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    map<int,int> pos;
    deque<pii> q;

    int l,r;
    cin>>l>>r;
    int cnt=r-l+1;
    for(int i=l;i<=r;i++)
    {
        int now=q.size()+1;
        q.push_back({i,now});
        pos[i]=now;
    }
    int m;
    cin>>m;
    while(m--)
    {
        int opt,id;
        cin>>opt>>id;
        if(opt==1)
        {
            int p=0;
            while(true)
            {
                auto t=q.front();
                q.pop_front();
                if(t.y!=pos[t.x]||pos[t.x]==0)
                    continue;
                p++;
                if(p==id)
                    break;
            }
        }
        else if(opt==2)
        {
            pos[id]=0;
        }
        else
        {
            if(id<l||id>r||pos[id])
                continue;
            
            int now=++cnt;
            q.push_back({id,now});
            pos[id]=now;
        }
    }
    while(q.front().y!=pos[q.front().x]||pos[q.front().x]==0)
        q.pop_front();
    cout<<q.front().x<<endl;

    return 0;
}

3、二分+离散化+二维前缀和 96%

#include<bits/stdc++.h>
#define x first
#define y second
#define mem(a,b) memset(a,b,sizeof(a))
#define F(i,l,r) for(int i=l;i<=r;i++)
#define int long long
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;

const int N=120;

int n,m;
pii pos[N];
int sum[N][N];

bool check(int x)
{
    //cout<<"-------"<<x<<endl;
    pii pos1[N],pos2[N];
    vector<int> nx,ny;
    for(int i=1;i<=n;i++)
    {
        pos1[i]={pos[i].x-x,pos[i].y-x};
        pos2[i]={pos[i].x+x,pos[i].y+x};
        nx.push_back(pos1[i].x);
        nx.push_back(pos2[i].x);
        ny.push_back(pos1[i].y);
        ny.push_back(pos2[i].y);
        //cout<<pos1[i].x<<" "<<pos1[i].y<<" "<<pos2[i].x<<" "<<pos2[i].y<<endl;
    }
    sort(nx.begin(),nx.end());
    sort(ny.begin(),ny.end());
    nx.erase(unique(nx.begin(),nx.end()),nx.end());
    ny.erase(unique(ny.begin(),ny.end()),ny.end());
    for(int i=1;i<=n;i++)
    {
        pos1[i].x=lower_bound(nx.begin(),nx.end(),pos1[i].x)-nx.begin()+1;
        pos2[i].x=lower_bound(nx.begin(),nx.end(),pos2[i].x)-nx.begin()+1;
        pos1[i].y=lower_bound(ny.begin(),ny.end(),pos1[i].y)-ny.begin()+1;
        pos2[i].y=lower_bound(ny.begin(),ny.end(),pos2[i].y)-ny.begin()+1;
    }
    mem(sum,0);
    for(int i=1;i<=n;i++)
    {
        sum[pos1[i].x][pos1[i].y]++;
        sum[pos2[i].x+1][pos2[i].y+1]++;
        sum[pos1[i].x][pos2[i].y+1]--;
        sum[pos2[i].x+1][pos1[i].y]--;
    }
    int mx=0;
    for(int i=1;i<=115;i++)
    {
        for(int j=1;j<=115;j++)
        {
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+sum[i][j];
            mx=max(mx,sum[i][j]);
        }
    }
    //cout<<"return:  "<<mx<<endl;
    return mx>=m;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);


    cin>>m>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>pos[i].x>>pos[i].y;
    }

    int l=0,r=1e16;
    while(l<r)
    {
        int mid=(l+r)/2;
        if(check(mid))
            r=mid;
        else
            l=mid+1;
    }
    if(l==1e16)
        cout<<0<<endl;
    else
        cout<<l<<endl;

    return 0;
}