Codeforces Round #813 (Div. 2) (补题中)

标签：main int st read flag 补题 -- Div 813

战绩：

 

 A. Wonderful Permutation

签到题。

计算前k个就把最小的那k个转移到前k项，看数组前k项缺多少最小前k项就行，可以在O(k)的复杂度内解决。

int main()
{
    read(T);
    while(T--)
    {
        read(n);read(k);
        for(int i=1;i<=n;i++) 
        {
            read(a[i]);
            b[i]=a[i];
        }
        
        sort(a+1,a+1+n);
        int ans=0;
        for(int i=1;i<=k;i++)
        {
            for(int j=1;j<=k;j++)
            {
                if(a[i]==b[j]) break;
                else if(j==k) ans++;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

赛时代码复杂度O（k²）

O(n复杂度代码)：应付n和k的限制可以更大

int main()
{
    cin>>T;
    while(T--)
    {
        int n,k;
        cin>>n>>k;
        int ans=0;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=k;i++)if(a[i]>k)ans++;
        cout<<ans<<endl;
    }
}

赛后代码

 B. Woeful Permutation

最大的利用每个数字的lcm就是让两个数字没有除了1以外的公因数也就是两两互质，每个数字n和n-1或者n+1是一定互质的。

题目要求最大，我们就从最后一位开始往前，两两交换数字，这样得到的答案一定是最大的。

int main()
{
    read(T);
    while(T--)
    {
        read(n);
        a[0]=1;
        for(int i=1;i<=n;i++) a[i]=i;
        for(int i=n;i>=1;i--)
        {
            if(i%2==n%2) swap(a[i],a[i-1]);
        }
        for(int i=1;i<=n;i++) cout<<a[i]<<" ";
        cout<<endl;
    }
    return 0;
}

View Code

C. Sort Zero

给定的数字一定是一组正数，我们每次把一种数字变为0，也就意味着这个数字会变成最小的那个。

当某一位变成0之后，我们很容易发现，为了不递减，前面的所有位置都会变为0，所以对原数组一定是保留最后那一节不递减序列。

可以用set维护，实现很快。

int main()
{
    read(T);
    while(T--)
    {
        st.clear();
        read(n);
        for(int i=1;i<=n;i++)
        {
            read(a[i]);
            b[i]=0;
        }
        for(int i=2;i<=n;i++) if(a[i]<a[i-1]) b[i]=1;
        bool flag=1;
        for(int i=n;i>=1;i--)
        {
            if(!flag) st.insert(a[i]);
            else if(b[i]==1) flag=0;
        }
        flag=1;
        for(int i=n;i>=1;i--)
        {
            if(!flag) st.insert(a[i]);
            else if(st.find(a[i])!=st.end()) flag=0;
        }
        cout<<st.size()<<endl;
    }
    return 0;
}

View Code

 

标签：main,int,st,read,flag,补题,--,Div,813
From： https://www.cnblogs.com/ztlsw/p/16585104.html