A. ABC

思路：

1.先给结论,当$|string|\geq3$时,无论如何排列均存在回文串.

Proof:

先不妨以1为例子给出含1的所有长度为3的字符串分别是 111,110,100;

对于111显然无论如何排均存在长度$\geq2$的回文,对于110,可能的排列有110,011,101,显然无论1是否和1在一起都存在长度$\geq$2的回文串.100和110的情况类似.又由于字符串只含01,因此任意长度$\geq 3$的回文必然包含长度为3的字串,而长度为3的字串无论如何排列都必然包含长度$\geq 2$的回文串,因此当字符串长度$\geq 3$时,必然输出NO。

其次当长度为2的时候只需特判 $11$,$00$.两种输出为$YES$的情况即可。

AC Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
void solve()
{
   int n;cin>>n;
   string s;cin>>s;
   if(n<=2)
   {
           if(n==1)cout<<"YES"<<endl;
           else 
           {
                   if(s[0]==s[1])cout<<"NO"<<endl;
                   else cout<<"YES"<<endl;
           }
   }
   else cout<<"NO"<<endl;
   return;       
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
      //  freopen("test.in","r",stdin);
        int t;cin>>t;
        while(t--)solve();
        return 0;
}

Roof Construction

思路：

1. 假设$2^{k}$为$\geq {n-1}$的最大的2的次方。

2. 其次证明任意一种方案。答案都一定是$\geq {2^k}$,这很容易证明,因为是排列因此数的连续的,那么无论如何排列,都一定会有最高一位上是0和最高一位上是1的两个数相邻进行异或。此时异或的值就一定是$\geq {2^k}$的。

3. 然后 把比$2^k$大的放在右,比其小的放在左侧,特别的0要放在2^k的左侧,这样左侧最高位没有1得到的结果肯定比$2^k$小右侧最高位全是1异或后 最高位1被消去。还是比$2^k$小。最后结果是$2^k \bigoplus 0$此时得到的最大的结果就是2^k。

AC Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
void solve()
{
        int n;cin>>n;
        int cur;
        for(int i=0;i<30;i++)
         if((1<<i)<=n-1)cur=(1<<i);


        vector<int>a;
        vector<int>b;

        for(int i=1;i<=n-1;i++)
         if(i<cur)a.push_back(i);
        for(int i=1;i<=n-1;i++)
         if(i>cur)b.push_back(i);

        for(auto c:a)cout<<c<<' ';
        cout<<0<<' '<<cur<<' ';
        for(auto c:b)cout<<c<<' ';
        cout<<endl;

        return;
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    //    freopen("test.in","r",stdin);
        int t;cin>>t;
        while(t--)solve();
        return 0;
}