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;
  }