codeforces-#687-D

codeforces-#687-D

十一月 27, 2020

D. XOR-gun

  • 题意

    给出一个长度为1e5d 非递减数列, 每个数ai<1e9

    现在给出一种操作：

    选择两个连续的数 异或后替换进去

    如[2,5,6,8] 选择(5,6) 得到[2,3,8]

    问最小需要几次操作才能使得打破原来数列的非递减性质

    或者输出-1表示不可能

  • 题解

    同样 位运算相关问题一定要想到 按位运算的性质

    我们发现 在题目所给的非递减数列中

    当且仅当 存在三个连续的 数 他们的most significant bit 在同一位上时

    才能通过异或后两个数 打破原来的非递减性质

    那么由于数列非递减 所以超过60个数并且要保证ai的值一定小于1e9

    只能至少存在三个连续的数 他们的most significant bit 在同一位上

    例如

    00..001x

    00..001x

    00..01xx

    00..01xx

    …

    1xxxxxx

    1xxxxxx

    60个数是两个连续最高位在同一位上且ai不超过1e9的情况

    于是当n>60时 只用异或1次就能 达到目的

    题目的量级一下缩小到n=60 以下 可以直接暴力枚举

    n在60以下时 只有两个 相邻区间

    它俩内的数求异或和 记为A和B

    这两个数A>B是才能打破非递减性质

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
//#define P pair<ll,ll>
const int Max=1e5+5;
const int Mod=998244353;
const int inf=0x3f3f3f3f;
 
//#define __DEBUG__
#ifdef __DEBUG__
#define DeBug(format, ...)                                                                            \
{                                                                                                   \
    fprintf(stdout, "[%s:%d]" format "",                                            \
    __FUNCTION__ , __LINE__, ##__VA_ARGS__);                                                        \
}
#else
#define DeBug(format,...)
#endif
/**
 
**/
ll arr[Max],narr[Max];
int main(void){
    //Turnoff;
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>arr[i];
    for(int i=1;i<=n;i++)narr[i]=narr[i-1]^arr[i];
    if(n>60){
        cout<<1<<endl;
        return 0;
    }
    int ans=inf;
    for(int L=1;L<=n;L++){
        for(int lenL=0;lenL+L<=n;lenL++){
            int R=L+lenL+1;
            //DeBug("%d,%d ->%d\n",L,L+lenL,R);
 
            if(R>n)break;
            for(int lenR=0;lenR+R<=n;lenR++){
                DeBug("in\n");
                if((narr[L-1]^narr[L+lenL])>(narr[R-1]^narr[R+lenR])){
                    //DeBug("%d,%d\n",R,R+lenR);
                    DeBug("(%d,%d):%d ",L,L+lenL,(narr[L-1]^narr[L+lenL]));
                    DeBug("(%d,%d):%d \n",R,R+lenR,(narr[R-1]^narr[R+lenR]));
                    ans=min(ans,lenL+lenR);
                }
            }
        }
    }
    if(ans!=inf)cout<<ans<<endl;
    else cout<<-1<<endl;
    return 0;
}