co

说明：本文为co_fun算法集训活动参考答案，有兴趣参与co_fun算法集训的同学可以关注b站 “co_fun算法内推社区” 获得群号。

co_fun算法集训活动，针对算法基础一般的同学，从常见考点开始训练，每日三道题，会有讲解。

三个月攻坚大厂笔试面试算法题。

2022.4.3-1

#include
#define int long long
#define MAXN 1000005
using namespace std;
int dp[1005][1005];
int a[1005][1005];
signed main()
{
    int n;cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
             dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j];
    cout<<dp[n][n]<<endl;
}

2022.4.3-2

#include
#define int long long
#define MAXN 1000005
using namespace std;
int pre[MAXN];
int get(int x)
{
    int flag=0;
    int m=x;
    while(m)
    {
        if(m%10==7)flag=1;
        m/=10;
    }
    if(flag||x%7==0)return 0;
    return x*x;
}
signed main()
{
    for(int i=1;i<=1000000;i++)
        pre[i]=get(i)+pre[i-1];
    int t;cin>>t;
    while(t--)
    {
        int x;cin>>x;
        cout<<pre[x]<<endl;
    }
}

2022.4.3-3

#include
#define int long long
#define MAXN 1000005
using namespace std;
int dp[20005];
signed main()
{
    dp[0]=1;
    int v,n;cin>>v>>n;
    for(int i=1;i<=n;i++)
    {
        int t;cin>>t;
        for(int j=v;j>=t;j--)
            dp[j]|=dp[j-t];
    }
    for(int i=v;i>=0;i--)
    {
        if(dp[i])
        {
            cout<<v-i<<endl;
            return 0;
        }
    }
}

2022.4.4-1

#include
#define int long long
#define MAXN 2005
using namespace std;
int n,h,r;
int x[MAXN],y[MAXN],z[MAXN];
int vis[MAXN];
bool check(int a,int b)
{
    return (x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b])+(z[a]-z[b])*(z[a]-z[b])
     <= 4*r*r;
}
void dfs(int now)
{
    if(vis[now])return;
    vis[now]=1;
    for(int i=1;i<=n;i++)
        if(check(now,i))
            dfs(i);
}
void solve()
{
    memset(vis,0,sizeof(vis));
    cin>>n>>h>>r;
    for(int i=1;i<=n;i++)
        cin>>x[i]>>y[i]>>z[i];
    for(int i=1;i<=n;i++)
        if(z[i]-r<=0)
            dfs(i);
    for(int i=1;i<=n;i++)
        if(vis[i]&&z[i]+r>=h)
    {
        cout<<"Yes"<<endl;
        return;
    }
    cout<<"No"<<endl;
}
signed main()
{
    int T;cin>>T;
    while(T--)
        solve();
}

2022.4.4-2

#include
#define MAXN 300005
using namespace std;
int a[MAXN],in[MAXN];
int val[MAXN][26];
vector<int> edge[MAXN];
int vis[MAXN];
void dfs(int now)
{
    if(vis[now])return;
    for(int i=0;i<edge[now].size();i++)
    {
        int to=edge[now][i];
        dfs(to);
        for(int i=0;i<26;i++)
            val[now][i]=max(val[now][i],val[to][i]);
    }
    val[now][a[now]]++;
    vis[now]++;
}
signed main()
{
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        char c;cin>>c;
        a[i]=c-'a';
    }
    for(int i=1;i<=m;i++)
    {
        int u,v;cin>>u>>v;
        edge[u].push_back(v);
        in[v]++;
    }
    for(int i=1;i<=n;i++)
        if(in[i]==0)
            dfs(i);
    int ans=0;
    for(int i=1;i<=n;i++)
        for(int j=0;j<26;j++)
            ans=max(ans,val[i][j]);
    cout<<ans<<endl;
}

2022.4.3-3

#include
#define int long long
#define MAXN 200005
using namespace std;
struct P{
    int x,y,v;
    bool operator<(const P& a)const&{
        if(v==a.v)return x>a.x;
        return v>a.v;
    }
};
int g[MAXN],val[MAXN];
int l[MAXN],r[MAXN];
int del[MAXN];
priority_queue<P> pq;
vector<P> ans;
signed main()
{
    int n;cin>>n;
    for(int i=1;i<=n;i++)
    {
        char c;cin>>c;
        if(c=='B')g[i]=1;
        cin>>val[i];
        if(i!=1)l[i]=i-1;
        if(i!=n)r[i]=i+1;
    }
    for(int i=1;i<=n-1;i++)
        if(g[i]+g[i+1]==1)
            pq.push(P{i,i+1,abs(val[i]-val[i+1])});
    while(pq.size())
    {
        P now=pq.top();
        pq.pop();
        if(del[now.x]||del[now.y])
            continue;
        del[now.x]=del[now.y]=1;
        ans.push_back(now);
        int ll=l[now.x],rr=r[now.y];
        if(ll&&rr)
        {
            r[ll]=rr;
            l[rr]=ll;
            if(g[ll]+g[rr]==1)
                pq.push(P{ll,rr,abs(val[ll]-val[rr])});
        }
    }
    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++)
        cout<<ans[i].x<<' '<<ans[i].y<<endl;
}