【CCCC天梯赛决赛】

饶文津

发布于 2020-06-02 15:39:15

3440

发布于 2020-06-02 15:39:15

文章被收录于专栏：饶文津的专栏饶文津的专栏

cccc的天梯赛决赛，水题一样的水，中档题以上的还是没做出来。补了一下题，觉得其实也不是很难，主要是练的少。

L2-1:红色预警并查集

我做的时候想不到并查集，想到了也不一定做的出来，都是其实不难。每次失去一个城市，重新计算过并查集，比较几个根节点，如果根节点增加了那么就是改变了连通性。

#include<cstdio>
#define N 505
#define M 5005
using namespace std;
int n,m,k,g,cnt,newcnt;
int f[N],u[M],v[M];
int find(int x)
{
    if(f[x]!=x)
        f[x]=find(f[x]);
    return f[x];
}
void un(int a,int b)
{
    int fa=find(a),fb=find(b);
    if(fa!=fb)
        f[fa]=fb;
}
void solve()
{
    f[g]=-1;
    newcnt=0;
    for(int i=0; i<n; i++)if(f[i]!=-1)f[i]=i;
    for(int i=0; i<m; i++)
        if(f[u[i]]!=-1&&f[v[i]]!=-1)
            un(u[i],v[i]);
    for(int i=0; i<n; i++)if(f[i]==i)
            newcnt++;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0; i<n; i++)f[i]=i;
    for(int i=0; i<m; i++)
    {
        scanf("%d%d",&u[i],&v[i]);
        un(u[i],v[i]);
    }
    scanf("%d",&k);
    for(int i=0; i<n; i++)if(f[i]==i)
            cnt++;
    for(int i=1; i<=k; i++)
    {
        scanf("%d",&g);
        solve();
        if(cnt<newcnt)printf("Red Alert: City %d is lost!\n",g);
        else printf("City %d is lost.\n",g);
        cnt=newcnt;
        if(k==i&&k==n)printf("Game Over.");
    }
}

L2-2列车调度最长上升子序列 O（nlogn）解法

这题题意是求1到n的一个排列里可以分成最少多少个下降子序列，如果做过导弹拦截那么容易地可以知道问题等价于求最长上升子序列，而且要用O（nlogn）的解法。s[i]s[i]表示上升子序列的长度为i时最后一个数的最小值。当i<j时，有s[i]<s[j]，因为长度比较长的子序列，它末尾的值也肯定更大。有了这个性质，就可以用二分查找了。每次找出s里值小于a[i]的最大下标j，把s[j]更新为a[i]。

#include<cstdio>
#include<algorithm>
using namespace std;
#define N 100005
int n,a[N],s[N],ans=1;
int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        s[i]=0x3f3f3f3f;
        scanf("%d",&a[i]);
    }
    s[0]=0;
    for(int i=1; i<=n; i++)
    {
        int l=0,r=i-1;
        while(l<r){
            int m=(l+r)>>1;
            if(s[m]<=a[i])l=m+1;
            else r=m;
        }
        if(s[l]<=a[i]){
            s[l+1]=min(s[l+1],a[i]);
            ans=max(ans,l+1);
        }else{
            s[l]=min(s[l],a[i]);
            ans=max(ans,l);
        }
    }
    printf("%d",ans);
}

L3-1 是否完全二叉搜索树

完全二叉树的概念：从上到下，每一层从左到右填充树的节点。题意是给你n个数，从根节点开始每次和节点比较，如果更大，那就插入左子树，更小就插入右子树。遍历的最后一个数字如果刚好是第n个节点，那就是完全二叉树。

#include<cstring>
#include<cstdio>
using namespace std;
int n,t,k,tree[1<<20];
void build(int w,int v)
{
    if(tree[w]==-1)tree[w]=v;
    else if(v>tree[w]) build(w<<1,v);
    else build(w<<1|1,v);
}
int main()
{
    memset(tree,-1,sizeof tree);
    scanf("%d",&n);
    for(int i=0; i<n; i++)
    {
        scanf("%d",&t);
        build(1,t);
    }
    k=1;
    for(int i=1; i<=n; k++)
        if(tree[k]!=-1)
        {
            printf("%d%c",tree[k],i==n?'\n':' ');
            i++;
        }
    if(k==n+1)puts("YES");
    else puts("NO");
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2016-07-21 ，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

二叉树

登录后参与评论

0 条评论

热度