Codeforces Round #758 (Div.1 + Div. 2)

1608A - Find Array

直接从2-n+1即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,T;
int main()
{
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=2;i<=n+1;i++) printf("%d ",i);
        printf("\n");
    }
    return 0;
}

1608B - Build the Permutation

首先考虑怎样才能有解,设有a个峰b个谷,那么a+b+1<n,并且a和b最多差一个,画一画就能发现,因为两个峰之间必有一个谷

然后考虑构造,直接取最大的a+b+2个,大的作峰,小的作谷,然后剩余的按从小到大放在最前面即可,具体的看代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int p[maxn];
int main()
{
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    int T,n,a,b;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&a,&b);
        if(abs(a-b)>1 || a+b+2>n){printf("-1\n"); continue;}
        int flag=0;
        if(a<b) swap(a,b),flag=1;
        int pos=n;
        if(a==b)
        {
            for(int i=0;i<=a;i++) p[n-i*2]=pos--;
            for(int i=0;i<=b;i++) p[n-i*2-1]=pos--;
            for(int i=1;i<=pos;i++) p[i]=i;
        }
        else
        {
            for(int i=0;i<a;i++) p[n-i*2-1]=pos--;
            for(int i=0;i<=a;i++) p[n-i*2]=pos--;
            for(int i=1;i<=pos;i++) p[i]=i;            
        }
        for(int i=1;i<=n;i++)
        {
            if(!flag) printf("%d ",p[i]);
            else printf("%d ",n-p[i]+1);
        }
        printf("\n"); 
    }
    return 0;
}

1608C - Game Masterh

个人觉得这道题非常的棒

首先我们要倒着考虑这个问题,如果x最后胜者,那么x一定在最后一轮赢了一个人y,倒数第二轮应该是x或y赢了z,这样依次拓展下去,如果能拓展到所有的人,就意味着x可以最终获胜

显然这个过程可以和图联系起来,考虑每一个人向他能打败的人连一个边,那么要是可以从x出发走到所有的点,就意味着x最终可以取胜,至此我们得到了一个Codeforces Round #758 (Div.1 + Div. 2)的算法

继续考虑优化,由于这张图已经有Codeforces Round #758 (Div.1 + Div. 2)级别的边了,所以一定要从这里入手优化,我们分别按照两张地图上的能力作为关键字排序,而后每次仅连接 i 和 i+1 即可,这样就仅仅连 2n-2 条边,又发现能到所有点相当于走到a最大或者b最大的点(因为他们可以战胜任何人),所以我们从amax和bmax两个位置出发遍历整张图即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int T,n;
struct capability
{
    int val,id;
}a[maxn],b[maxn];
vector <int> G[maxn];
bool cmp(capability x,capability y)
{
    return x.val<y.val;
}
int main()
{
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i].val),a[i].id=i;
        for(int i=1;i<=n;i++) scanf("%d",&b[i].val),b[i].id=i;
        sort(a+1,a+n+1,cmp),sort(b+1,b+n+1,cmp);
        vector <int> ans(n+5,0);
        for(int i=1;i<=n;i++)
            G[i].clear();
        for(int i=1;i<n;i++) G[a[i].id].push_back(a[i+1].id);
        for(int i=1;i<n;i++) G[b[i].id].push_back(b[i+1].id);
        ans[a[n].id]=ans[b[n].id]=1;
        queue <int> q;
        q.push(a[n].id),q.push(b[n].id);
        while(!q.empty())
        {
            int u=q.front(); q.pop();
            for(auto to:G[u])
            {
                if(ans[to]) continue;
                ans[to]=1;
                q.push(to);
            }
        }
        for(int i=1;i<=n;i++) printf("%1d",ans[i]);
        printf("\n");
    }
    return 0;
}

上一篇:Kruskal重构树 学习笔记


下一篇:Re:从零开始的二项式反演