【BZOJ 4269】再见Xor

Qizy 数论, 线性基, 解题报告, 高斯消元

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4269
离线版题目：http://paste.ubuntu.com/18971803/

这个题目，拿到以后，一脸懵逼啊QAQ，想拿BFS乱搞一搞，估计会T，结果还是可耻地看了题解
高斯消元求线性基QAQ，又没有学过QAQ，I well vegtable are (T_T)
其实也不难，每一个数的二进制看成方程组，然后上高斯消元。
求出线性基之后，全部^起来就是最大值，找一个最小的^一下就是次小值

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 100000+9;

int n,arr[MAXN],cnt;

inline void Gauss(){
	for (int k=31;k;k--){
		int w = 1<<(k-1), pos;
		for (pos=cnt+1;pos<=n;pos++) 
			if (arr[pos]&w) break;
		if (pos==n+1) continue;
		else {
			swap(arr[++cnt], arr[pos]);
			for (int i=1;i<=n;i++)
				if (i!=cnt && (arr[i]&w))
					arr[i] ^= arr[cnt];
		}
	}	
}

int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&arr[i]);
	Gauss(); int vout = 0;
	for (int i=1;i<=cnt;i++) vout ^= arr[i];
	printf("%d ",vout);
	printf("%d\n",vout ^= arr[cnt]);
	return 0;
}

好像还有一种方法，写法跟在线求解亦或方程组很像。
但感觉不如直接高斯消元优雅，且时间复杂度相同，所以就不贴代码啦！

200 thoughts to “【BZOJ 4269】再见Xor”

  48. Having read this I thought it was really informative.
    I appreciate you spending some time and energy to put this
    short article together. I once again find myself spending a lot
    of time both reading and leaving comments. But so what, it was still worth it!

    Reply

  66. Hi, i read your blog occasionally and i own a similar
    one and i was just curious if you get a lot of spam feedback?
    If so how do you reduce it, any plugin or anything you can advise?
    I get so much lately it’s driving me crazy so any support is
    very much appreciated.

    Reply

  70. Today, I went to the beachfront with my kids. I found a sea shell and gave it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.”
    She put the shell to her ear and screamed.
    There was a hermit crab inside and it pinched her ear.

    She never wants to go back! LoL I know this is totally
    off topic but I had to tell someone!

    Reply

  71. My partner and I absolutely love your blog and find the majority of your post’s to be precisely what I’m looking for.
    Would you offer guest writers to write content for you personally?
    I wouldn’t mind producing a post or elaborating on a number of the subjects you write in relation to here.

    Again, awesome web site!

    Reply

  77. Greetings from Idaho! I’m bored to death at work so I decided to browse your
    site on my iphone during lunch break. I enjoy the knowledge you present
    here and can’t wait to take a look when I get home.
    I’m surprised at how fast your blog loaded on my cell phone ..
    I’m not even using WIFI, just 3G .. Anyways,
    excellent site!

    Reply

  112. It’s a shame you don’t have a donate button! I’d definitely donate to this
    superb blog! I suppose for now i’ll settle for bookmarking and adding your RSS feed to my Google account.
    I look forward to fresh updates and will talk
    about this website with my Facebook group. Chat soon!

    Reply

  113. This design is steller! You most certainly know how to keep a reader amused.
    Between your wit and your videos, I was almost moved to start my own blog (well, almost…HaHa!)
    Great job. I really enjoyed what you had to say, and more than that, how you presented it.
    Too cool!

    Reply

  120. Admiring the hard work you put into your website and detailed information you provide.
    It’s nice to come across a blog every once in a while that isn’t the same outdated rehashed material.
    Fantastic read! I’ve saved your site and I’m including your RSS feeds to my
    Google account.

    Reply

  153. I’m not sure why but this website is loading incredibly slow for me.
    Is anyone else having this problem or is it a problem on my end?
    I’ll check back later and see if the problem still exists.

    Reply

  154. Wow, superb blog layout! How long have you ever been blogging for?
    you make blogging glance easy. The total look of your web site is great, let alone the content
    material!

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *