2020牛客寒假算法基础集训营6

题解

A.配对：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const double eps=1e-6;
priority_queue<int,vector<int>,greater<int> >que;
int a[N],b[N];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    sort(a+1,a+1+n);
    sort(b+1,b+1+n);
    int cnt=0,ans=0;
    for(int i=n;i>=n-k+1;i--)
    {
        int t=a[i]+b[2*n-k+1-i];
        que.push(t);
    }
    ans=que.top();
    printf("%d\n",ans);
    return 0;
}

B.图：

思路：

  先用拓扑排序，把所有不在环中的点选择出来标记。然后处理环，遍历每一个环，求出环内的点数，然后把环内的所有的点的 num 数组都赋相同的值。然后，从非环内的点进行记忆化搜索，求出每个点对应 $\text{num}$num 数组数值,取最大即可。
  一开始用了 $\text{stl}$stl 的 $\text{map}$map 和 $\text{set}$set ，$\text{t}$t 了好几发，时间差别竟然这么大。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+6;
const double eps=1e-6;
const ll mod=1e9+7;
//map<int,map<int,int> >mp;
int pic[N],num[N],degree[N];
bool vis[N],book[N];
void read(int &x)
{
    x=0;
    int f=1;
    char c;
    c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')
            f=-1;
        c=getchar();
    }
    while(isdigit(c))
    {
        x=x*10+c-'0';
        c=getchar();
    }
    x*=f;
}
int ans;
void bfs(int n)
{
    queue<int>que;
    for(int i=1;i<=n;i++)
    {
        if(degree[i]==0)
            que.push(i);
    }
    while(!que.empty())
    {
        int now=que.front();
        que.pop();
        vis[now]=1;
        int t=pic[now];
        degree[t]--;
        if(degree[t]==0)
            que.push(t);
    }
}
void solve(int x)
{
    int tx=x;
    int t=pic[x];
    int cnt=1;
    book[x]=1;
    int f=0;
    while(!book[t]||t==tx&&f==0)
    {
        book[t]=1;
        if(t!=tx)
            cnt++;
        else
            f=1;
        //mp[x][t]=1;
        x=t;
        t=pic[x];
    }
    num[tx]=cnt;
    t=pic[tx];
    while(t!=tx)
    {
        num[t]=cnt;
        t=pic[t];
    }
}
int dfs(int v)
{
    if(num[v])
        return num[v];
    int t=pic[v];
    return num[v]=dfs(t)+1;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        read(pic[i]);
        degree[pic[i]]++;
    }
    bfs(n);
    ans=0;
    for(int i=1;i<=n;i++)//环
    {
        if(!vis[i]&&num[i]==0)
            solve(i);
    }
    for(int i=1;i<=n;i++)
    {
        if(vis[i]&&num[i]==0)
            num[i]=dfs(i);
    }
    for(int i=1;i<=n;i++)
    {
        if(ans<num[i])
            ans=num[i];
    }
    printf("%d\n",ans);
    return 0;
}
/*
6
3
1
2
2
3
5
*/

附上题解代码：

作者：珩月
链接：https://ac.nowcoder.com/discuss/367149?type=101&order=0&pos=1&page=1
来源：牛客网

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
 
using namespace std;
const int N = 1000050;
 
int to[N], siz[N], n, vis[N], ins[N], sta[N];
int dfs(int x){
    if(siz[x]) return siz[x];
    return siz[x] = 1 + dfs(to[x]);
}
int main()
{
    int i, j, k, h;
    scanf("%d", &n);
    for(i = 1; i <= n; i ++)
        scanf("%d", &to[i]);
    for(i = 1; i <= n; i ++){
        if(vis[i] == 0){
            j = i;
            while(vis[j] == 0){
                sta[++ sta[0]] = j;
                vis[j] = ins[j] = 1;
                j = to[j];
            }
            if(ins[j]){
                k = j, h = 0;
                do{
                    k = to[k];
                    h ++;
                }while(k != j);
                do{
                    k = to[k];
                    siz[k] = h;
                }while(k != j);
            }
            while(sta[0]){
                ins[sta[sta[0]]] = 0;
                sta[0] --;
            }
        }
    }
    for(i = 1, h = 0; i <= n; i ++)
        h = max(h, dfs(i));
    printf("%d", h);
     
    return 0;
}

基环树：

  基环树有且仅有一个环，所以也被成为环套树。从一个点出发，沿着出边一路走下去，一定会走到一个环。

C.汉诺塔：

D.重排列：

E.立方数：

H.云：

I.导航系统：