Codeforces Round #455 (Div. 2)F. AND-permutations[bitmasks]-白红宇

Codeforces Round #455 (Div. 2)F. AND-permutations[bitmasks]

阅读量：6293 次

发布时间：2019-06-22

本文共 2381 字，大约阅读时间需要 7 分钟。

题目：

题意：给出数字n，找出两种序列，要求下标和数字不同并且与值为0（不为0）

分析：一个只在最高位有1的数字n（例如10000B），n+i-1和n-i每一位正好相反（i=1,2,3……），与值为0.则如果n为偶数，可以构造出第一种序列，从n开始，以最高位为1且小于n的数字为对称轴组合。例如n=10，找到的对称轴为8，第一次处理完10-5、9-6、8-7，不断更新上界，第二次再从6开始类似的处理。只要是偶数一定可以找到答案。

与值不为1，若最大值n为100000B这样的数字，只有最高位有1而且它为最大值，怎么都不可能有数字和他与值为1且和他不同，则输出NO。剩余情况可以利用lowbit函数找到n的最末位1,从n到这个数字之间的数字一定有这一位公共的1（例如100100B，找到的为100100B+100B=101000B），只需要保证他们不和下标相等即可，不断更新下界，小数字会出现问题，特判小于8的情况。

代码：

1 #define _CRT_SECURE_NO_DEPRECATE 2 #pragma comment(linker, "/STACK:102400000,102400000") 3 #include
     
         4 #include
      
          5 #include
       
           6 #include
        
          7 #include
         
             8 #include
          
            9 #include
           
             10 #include
            
             11 #include
             
              12 #include
              
                13 #include
               
                 14 #include
                
                  15 #include
                  16 #include
                  
                    17 #include
                   
                    18 #include
                    
                     19 #define pii pair
                     
                      20 #define mod 100000000721 #define mp make_pair22 #define pi acos(-1)23 #define eps 0.0000000124 #define mst(a,i) memset(a,i,sizeof(a))25 #define all(n) n.begin(),n.end()26 #define lson(x) ((x<<1)) 27 #define rson(x) ((x<<1)|1) 28 #define inf 0x3f3f3f3f29 typedef long long ll;30 typedef unsigned long long ull;31 using namespace std;32 const int maxn = 1e5 + 5;33 int a[maxn];34 int b[maxn];35 36 void getans(int t)37 {38 if (t == 0)return;39 int temp = 1;40 while (temp <= t)temp <<= 1;41 temp >>= 1;42 int cnt = t - temp + 1;43 for (int i = 1; i <= cnt; ++i)44 {45 a[temp + i - 1] = temp - i;46 a[temp - i] = temp + i - 1;47 }48 getans(temp - cnt - 1);49 }50 inline int lowbit(int t)51 {52 return t&(-t);53 }54 int main()55 {56 ios::sync_with_stdio(false);57 cin.tie(0); cout.tie(0);58 int i, j, k, m, n;59 cin >> n;60 if (n & 1)cout << "NO" << endl;61 else62 {63 cout << "YES" << endl;64 getans(n);65 for (int i = 1; i <= n; ++i)cout << a[i] << " ";66 cout << endl;67 }68 double ta = log2(n);69 int tb = ta;70 if (n < 6 || (n >= 8 && tb == ta))cout << "NO" << endl;71 else72 {73 cout << "YES" << endl;74 if (n == 6)cout << "3 6 2 5 1 4" << endl;75 else76 {77 b[1] = 5, b[5] = 1, b[4] = 6, b[6] = 4, b[2] = 3, b[3] = 7, b[7] = 2;78 int ed = 8;79 for (int i = 8; i <= n; i = ed)80 {81 ed += lowbit(i);82 ed = min(ed, n + 1);83 for (int j = i; j < ed - 1; ++j)b[j] = j + 1;84 b[ed - 1] = i;85 }86 for (int i = 1; i <= n; ++i)cout << b[i] << " ";87 cout << endl;88 }89 }90 return 0;91 }

转载于:https://www.cnblogs.com/Meternal/p/8137050.html

你可能感兴趣的文章

第三章：Shiro的配置——深入浅出学Shiro细粒度权限开发框架