Atcoder Regular Contest 103 (待补全)

C

搞个桶暴力即可,注意要求两种不同的数字,需要特判一下

D

给定平面上的$N$个点,求$N$个序列,每个序列表示上下左右,起点是远点,然后从原点按照N个序列走,权值是D序列(顺序对应),要求恰好走到这N个点,求这样的序列和D序列

待补

E

You are given a string s of length n. Does a tree with n vertices that satisfies the following conditions exist?

The vertices are numbered 1,2,…,n. The edges are numbered 1,2,…,n−1, and Edge i connects Vertex ui and vi. If the i-th character in s is 1, we can have a connected component of size i by removing one edge from the tree. If the i-th character in s is 0, we cannot have a connected component of size i by removing any one edge from the tree. If such a tree exists, construct one such tree.

题目要构造一颗树,满足上面两个条件(即存在大小是i的子树,且不存在大小为j的子树,其中a[i]=1,a[j]=0,a数组是给定的) 在1~n-1范围内串要是对称的(因为x和n-x的联通大小是并存的),且a[1]=1 a[n]=0 其余的向下面这样连接: 在这里插入图片描述

#include<bits/stdc++.h>
#define debug cout<<"debug "<<++debug_num<<" :"
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
int debug_num=0;

string s;
int n;

const int maxn=1e5+10;

int a[maxn];

bool check(int x)
{
    for(int i=1;i<=x;++i){
        if(a[i]!=a[n-i]) return false;
    }
    if(a[1]!=1 || a[n]!=0) return false;
    return true;
}

int main()
{
    //freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>s;
    n=s.size();
    //cout<<s<<endl;
    for(int i=0;i<n;++i){
        a[i+1]=s[i]-'0';
        //cout<<a[i+1]<<endl;
    }
    if(!check(n/2)){
        cout<<-1<<endl;
    }
    else{
        int tp1=1;
        int tp2;
        for(int i=2;i<=n;++i){
            if(a[i]==1){
                tp2=i;
                cout<<tp2<<" "<<tp1<<endl;
                for(int i=tp1+1;i<tp2;++i){
                    cout<<tp2<<" "<<i<<endl;
                }
                tp1=tp2;
            }
        }
        cout<<n<<" "<<n-1<<endl;
    }
    return 0;
}

F

待补





评论

登录之后就可以评论 / 回复啦(#^.^#)    点此登录    点此注册

评论列表

暂无评论!快写一条吧(๑′ᴗ‵๑)