2020牛客寒假算法基础集训营6（B tarjan + 拓扑）C（二分）E（唯一分解）I(最小生成树)

题目链接

题解链接

这场发挥中等，7题，E题数学唯一分解优化没搞出来，I题MST（最小生成树）也没搞出来。

B-图

由于出度只有一个，那么就可以考虑tarjan缩点后跑一遍拓扑维护最大值就可以了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
struct edge
{
    int from;
    int to;
    int next;
}e[N*100];
int n,head[N];
int cnt,inde,sccnum;
int dfn[N],low[N],in[N],out[N],scc[N],val[N];
stack<int>que;
void tarjan(int root)//已成功的求出连通分量了
{
    dfn[root]=low[root]=++inde;//更新时间戳
    que.push(root);//点入栈
    for(int i=head[root];i;i=e[i].next)//遍历边
    {
        int v=e[i].to;//这条边的下一个顶点
        if(!dfn[v])
        {
            tarjan(v);
            low[root]=min(low[v],low[root]);//low只与儿子的low比较
        }
        else if(!scc[v])low[root]=min(low[root],dfn[v]);//v有可能在上方
    }
    if(low[root]==dfn[root])
    {
        sccnum++;
        int x;
        int v=0;
        do
        {
            x=que.top();
            que.pop();
            v++;
            scc[x]=sccnum;
        }while(x!=root);
        val[sccnum]=v;
    }
}
void add_edge(int u,int v)
{
    e[++cnt].from=u;
    e[cnt].to=v;//下一个点
    e[cnt].next=head[u];//下一条边
    head[u]=cnt;
}
int tar;
ll ans;
vector<int>G[N];
struct node
{
    int u;
    ll w;
};
ll mx[N];
void bfs()
{
    ll ans=0;
    queue<node>que;
    for(int i=1;i<=sccnum;++i){
        if(in[i]==0) {
            //printf("i:%d\n",i);
            que.push({i,val[i]});
            mx[i]=val[i];
        }
        mx[i]=val[i];
        ans=max(ans,mx[i]);
    }
    while(que.size())
    {
        node now=que.front();que.pop();
        for(int v:G[now.u]){
            //printf("u:%d v:%d\n",now.u,v);
            mx[v]=max(mx[v],now.w+val[v]);
            in[v]--;
            if(in[v]==0){
                que.push({v,mx[v]});
                ans=max(ans,mx[v]);
            }
        }
    }
    printf("%lld\n",ans);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        add_edge(i,x);
    }
 
    //puts("****");
 
    for(int i=1;i<=n;i++)
    if(!dfn[i]) tarjan(i);
 
    //printf("sccnum:%d\n",sccnum);
 
    for(int i=1;i<=n;i++)
    {
        for(int j=head[i];j;j=e[j].next)
        {
            if(j==0) break;
            int v=e[j].to;
            if(scc[i]!=scc[v])
            {
                G[scc[i]].push_back(scc[v]);
                in[scc[v]]++;
                //printf("scc:%d v:%d\n",scc[i],scc[v]);
            }
        }
    }
    bfs();
    //printf("%lld\n",ans);
}

 

C-汉诺塔

最近好多这类题啊，牛客两次，cf一次了，从后面枚举  二分一下找第一个大于的值  就可以了

我是用了multiset维护

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define pi pair<int, int>
#define mk make_pair
#define se second
#define fi first
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
const int N=1e5+10;
struct node
{
    int id,x,y;
}a[N];
bool cmp(node a,node b)
{
    if(a.x==b.x) return a.y<b.y;
    return a.x<b.x;
}
int n;
int ans[N];
int vis[N];
 
int main()
{
    cin>>n;
    rep(i,1,n) {scanf("%d%d",&a[i].x,&a[i].y);a[i].id=i;}
    sort(a+1,a+1+n,cmp);
 
    multiset<pi>st;
    //st.insert(make_pair(a[n].y,a[n].id));
 
    int col=0;
    for(int i=n;i;--i){
        pi tmp=make_pair(a[i].y,a[i].id);
        auto it=st.lower_bound(tmp);
 
        if(it!=st.end()){
 
            ans[tmp.se]=ans[(*it).se];
            st.erase(it);
 
        }
        else ans[tmp.se]=++col;
        st.insert(tmp);
    }
 
    printf("%d\n",col);
    for(int i=1;i<=n;++i) printf("%d ",ans[i]);
}

E-立方数

 

听群友说 这是个原题

贴题解

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define pi pair<int, int>
#define mk make_pair
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
const int N=40000;
int n,len;
ll pri[N],pri_3[N];
bool ispri[N];
void init()
{
    for(int i=2;i<N;++i){
        if(!ispri[i]){
            pri[++len]=i;
            pri_3[i]=1ll*i*i*i;
        }
        for(int j=1;j<=len&&i*pri[j]<N;++j){
            ispri[i*pri[j]]=1;
            if(i%pri[j]==0) break;
        }
    }
}
int main()
{
    init();
	int _;cin>>_;while(_--)
	{
	    ll x;
	    scanf("%lld",&x);
        ll ans=1;
	    for(int i=1;i<=len&&pri[i]<=x;++i){
            if(x%pri[i]==0){
                while(x%pri_3[pri[i]]==0){
                    ans=ans*pri[i];
                    x=x/pri_3[pri[i]];
                }
                while(x%pri[i]==0){
                    x=x/pri[i];
                }
            }
	    }
	    ll res=0,l=1,r=1000000;
	    while(l<=r){
            ll mid=l+r>>1;
            if(mid*mid*mid>=x) res=mid,r=mid-1;
            else l=mid+1;
	    }
	    if(res*res*res==x) ans=ans*res;
	    printf("%lld\n",ans);
	}
}

I-导航系统

保存所有的边权，跑一遍最小生成树，然后再跑一遍floyd  判断新的二维数组是否等于原始的数组。

我代码注释部分不知道为什么加了就会wa，我觉得也没毛病，希望有大佬可以指点指点~

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define pi pair<int, int>
#define mk make_pair
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
const int N=600,inf=0x3f3f3f3f;
int dp[N][N];
int n;
int vis[N][N],fa[N],len,l1,ans[N];
struct node
{
    int u,v,w;
}c[N*N];
bool cmp(node a,node b)
{
    return a.w<b.w;
}
int fin(int x)
{
    if(fa[x]!=x) fa[x]=fin(fa[x]);
    return fa[x];
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j)
    scanf("%d",&dp[i][j]);
    
	mem(vis,inf);
	rep(i,1,n) fa[i]=i,vis[i][i]=0;

//	rep(i,1,n)
//	rep(j,1,n)
//    rep(k,1,n){
//        if(i==j||k==i||k==j) continue;
//        if(dp[i][j]==dp[i][k]+dp[k][j]) continue;
//        if(dp[i][k]==dp[i][j]+dp[j][k]) continue;
//        if(dp[j][k]==dp[j][i]+dp[i][k]) continue;
//        puts("No");
//        return 0;
//	}

	for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            if(i==j) continue;
            c[++l1]={i,j,dp[i][j]};
        }
	}
    sort(c+1,c+1+l1,cmp);
    for(int i=1;i<=l1;++i){
        int f1=fin(c[i].u);
        int f2=fin(c[i].v);
        if(f1==f2) continue;
        fa[f1]=f2;
        vis[c[i].u][c[i].v]=vis[c[i].v][c[i].u]=c[i].w;
        ans[++len]=c[i].w;
    }

    rep(k,1,n)
    rep(i,1,n)
    rep(j,1,n){
        vis[i][j]=min(vis[i][j],vis[i][k]+vis[k][j]);
    }
    rep(i,1,n)
    rep(j,1,n)
    if(vis[i][j]!=dp[i][j]){
        puts("No");
        return 0;
    }
    puts("Yes");
    sort(ans+1,ans+1+len);
    for(int i=1;i<=len;++i)
    printf("%d\n",ans[i]);
}