Codeforces #640 div4 F~G (构造二连弹)

题意:求一个只由\(01\)组成的字符串,使得它所有长度为\(2\)的子串满足:每对子串的数字和为\(0,1,2\)的个数为\(a,b,c\).
题解:我们先考虑子串数字和为\(1\)的情况,构造出一个\(10\)的循环串,然后在它的头部尾部适当添加\(1\)和\(0\)，使得a和c也满足即可.需要特判\(b=0\)的情况,并且\(b\)奇偶不同构造情况也不同.

代码:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <stack>

#include <queue>

#include <vector>

#include <map>

#include <set>

#include <unordered_set>

#include <unordered_map>

#define ll long long

#define fi first

#define se second

#define pb push_back

#define me memset

const int N = 1e6 + 10;

const int mod = 1e9 + 7;

using namespace std;

typedef pair<int,int> PII;

typedef pair<long,long> PLL;

int t;

int a,b,c;

string s;

int main() {

    ios::sync_with_stdio(false);

    cin>>t;

     while(t--){

         s="";

         cin>>a>>b>>c;

         if(b==0){

            if(c){

                c++;

                while(c--) s+="1";

            }

            if(a){

                a++;

                while(a--) s+="0";

            }

         }

         else if(b%2==1){

             int tmp=(b+1)/2;

             while(tmp--) s+="10";

             while(c--)   s="1"+s;

             while(a--)   s+="0";

         }

         else{

             int tmp=b/2;

             while(tmp--) s+="10";

             while(c--) s="1"+s;

             while(a--) s+="0";

             s+="1";

         }

      cout<<s<<endl;

     }

    return 0;

}

题意:给你一个数\(n\),构造一个\(1\le p \le n\)的序列,对于\(\forall\;1\le i < n\)有:\(2 \le |p_{i}-p_{i+1}| \le 4\).如果不存在,输出\(-1\).
题解:易知:当且仅当\(n=2\;or\;n=3\)时不满足条件.

首先先将\(1\)~\(n\)中所有的偶数输出,然后:

1.如果\(n\)是偶,那么就先输出第二大和最大的奇数,剩下的奇数递减输出即可.

2.如果n是奇,那么就先输出第三大的奇数,剩下的奇数递减输出即可.

代码:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <stack>

#include <queue>

#include <vector>

#include <map>

#include <set>

#include <unordered_set>

#include <unordered_map>

#define ll long long

#define fi first

#define se second

#define pb push_back

#define me memset

const int N = 2e4;

const int mod = 1e9 + 7;

using namespace std;

typedef pair<int,int> PII;

typedef pair<long,long> PLL;

int t;

int n;

int main() {

    ios::sync_with_stdio(false);

    cin>>t;

     while(t--){

         cin>>n;

         if(n==2 || n==3) puts("-1");

         else{

             for(int i=2;i<=n;i+=2){

                 printf("%d ",i);

             }

             if(n%2==0){

                 printf("%d %d ",n-3,n-1);

                 for(int i=n-5;i>=1;i-=2){

                     printf("%d ",i);

                 }

             }

             else if(n%2==1){

                 printf("%d ",n-4);

                 printf("%d ",n);

                 for(int i=n-2;i>=1;i-=2){

                     if(i!=n-4)

                     printf("%d ",i);

                 }

             }

             puts("");

         }

     }

    return 0;

}

巴特西

Codeforces #640 div4 F~G (构造二连弹)

最新文章

热门文章