3.18上午美团暑期实习第二次笔试 AK

1、二维前缀和

#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;

int g[N][N];

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

    int n,a,b;
    cin>>n>>a>>b;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        g[x][y]++;
    }
    for(int i=1;i<=1000;i++)
    {
        for(int j=1;j<=1000;j++)
        {
            g[i][j]+=g[i-1][j]+g[i][j-1]-g[i-1][j-1];
        }
    }
    int ans=0;
    for(int i=1;i<=1000;i++)
    {
        for(int j=1;j<=1000;j++)
        {
            ans=max(ans,g[i][j]-g[max(0,i-a-1)][j]-g[i][max(0,j-b-1)]+g[max(0,i-a-1)][max(0,j-b-1)]);
        }
    }
    cout<<ans<<endl;
    return 0;
}

2、set

#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 n,k,a[N];

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

    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];

    int ans=0;
    for(int i=1;i<=n;i++)
    {
        set<int> s;
        int j=i;
        while(j<=n)
        {
            s.insert(a[j]);
            if(s.size()>k)
                break;
            j++;
        }
        ans=max(ans,j-i);
    }
    cout<<ans<<endl;
    return 0;
}

3、corner case挺多的

#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);


    string s;
    cin>>s;
    int n=s.size();
    s='#'+s;
    int l=1,r=n;
    vector<pii> pos;
    while(l<r)
    {
        if(s[l]!=s[r])
            pos.push_back({l,r});
        l++,r--;
    }
    sort(pos.begin(),pos.end());
    if(pos.size()==0)
    {
        for(int i=1;i<=n;i++)
        {
            if(s[i]!='a')
            {
                s[i]=s[n-i+1]='a';
                break;
            }
        }
    }
    else if(pos.size()==1)
    {
        if(s[pos[0].x]=='a'||s[pos[0].y]=='a')
        {
            if(n&1)
            {
                s[(n+1)/2]='a';
            }
        }
        s[pos[0].x]=s[pos[0].y]='a';
    }
    else
    {
        char c=min(s[pos[0].x],s[pos[0].y]);
        s[pos[0].x]=s[pos[0].y]=c;
        c=min(s[pos[1].x],s[pos[1].y]);
        s[pos[1].x]=s[pos[1].y]=c;
    }

    for(int i=1;i<=n;i++)
        cout<<s[i];
    return 0;
}

4、背包dp

#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 a[N],b[N];
int dp[105][5005][55],cost[105][5005][55];

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

    int n,x,y;
    cin>>n>>x>>y;
    for(int i=1;i<=n;i++)
        cin>>a[i]>>b[i];

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=x;j++)
        {
            for(int k=0;k<=y;k++)
            {
                dp[i][j][k]=dp[i-1][j][k];
                cost[i][j][k]=cost[i-1][j][k];
                if(j-a[i]>=0)
                {
                    if(1+dp[i-1][j-a[i]][k]>dp[i][j][k])
                    {
                        dp[i][j][k]=1+dp[i-1][j-a[i]][k];
                        cost[i][j][k]=cost[i-1][j-a[i]][k]+a[i];
                    }
                    else if(1+dp[i-1][j-a[i]][k]==dp[i][j][k])
                        cost[i][j][k]=min(cost[i][j][k],cost[i-1][j-a[i]][k]+a[i]);
                }
                if(j-b[i]>=0&&k>=1)
                {
                    if(1+dp[i-1][j-b[i]][k-1]>dp[i][j][k])
                    {
                        dp[i][j][k]=1+dp[i-1][j-b[i]][k-1];
                        cost[i][j][k]=cost[i-1][j-b[i]][k-1]+b[i];
                    }
                    else if(1+dp[i-1][j-b[i]][k-1]==dp[i][j][k])
                        cost[i][j][k]=min(cost[i][j][k],cost[i-1][j-b[i]][k-1]+b[i]);
                }
            }
        }
    }
    int mn=1e9;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=x;j++)
        {
            for(int k=0;k<=y;k++)
            {
                //cout<<i<<" "<<j<<" "<<k<<" "<<dp[i][j][k]<<" "<<cost[i][j][k]<<endl;
                if(dp[i][j][k]==dp[n][x][y])
                    mn=min(mn,cost[i][j][k]);
            }
        }
    }
    cout<<dp[n][x][y]<<" "<<mn<<endl;
    return 0;
}

5、dfs

#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 n,d[N],sum[N];
vector<int> g[N];

void dfs(int u,int fa,int dst)
{
    if(dst<0)
        return;
    sum[u]++;
    for(int v:g[u])
    {
        if(v!=fa)
            dfs(v,u,dst-1);
    }

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

    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>d[i];
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    for(int i=1;i<=n;i++)
        dfs(i,0,d[i]);
    for(int i=1;i<=n;i++)
        cout<<sum[i]<<" ";
    return 0;
}