即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

【hihoCoder挑战赛28 A】异或排序

编程语言 harlow_cheng 22℃ 0评论

【题目链接】:http://hihocoder.com/problemset/problem/1509

【题意】


【题解】





每次找到相邻两个数的二进制形式中;


不同的最高位;


显然S在这一位必然是确定的;


必须在这一位确定数字让a[i]< a[i+1];


至于更高位的,它们的数字是相同的,以及更低位的;


它们都任意;


因为要对于所有的i∈[1..n-1]都满足要求


所以看看哪些位置最后是确定的;


(或者发生了抵触->直接输出0)


然后剩下的位置的个数为x;


则答案就为2^x;





【Number Of WA





0





【完整代码】

#include 
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)

typedef pair<int,int> pii;
typedef pair pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 50+10;
const int MAX = 7e4;

int n,g[N];
LL a[N];

int main()
{
    //freopen("F:\\rush.txt","r",stdin);
    ios::sync_with_stdio(false),cin.tie(0);//scanf,puts,printf not use
    cin >> n;
    rep1(i,1,n)
        cin >> a[i];
    ms(g,255);
    rep1(i,2,n)
    {
        LL x = a[i-1],y = a[i];
        for (LL t = 1LL<<59,c = 59;t;t>>=1,c--)
        {
            if ((t&x)==(t&y)) continue;
            if (t&x)
            {
                if (g[c]==-1)
                    g[c] = 1;
                else
                    if (g[c]!=1)
                        return cout <<0 << endl,0;
            }
            else
                if (g[c]==-1)
                    g[c] = 0;
                else
                    if (g[c]!=0)
                        return cout <<0<0;
            break;
        }
    }
    LL ans = 1;
    rep1(i,0,59)
        if (g[i]==-1)
            ans <<=1;
    cout << ans << endl;
    return 0;
}

转载请注明:CodingBlog » 【hihoCoder挑战赛28 A】异或排序

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情