列表

详情

NC23867. Chino with Train to the Rabbit Town

描述

Chino的数学很差，因此Cocoa非常担心。这一天，Cocoa准备教Chino学习异或。
众所周知，，即“a异或b”表示了a和b的二进制按位异或的结果（在C/C++中，表示了异或运算。），它的规则是如果这一位相同为0，否则为1.例如，，因为，，根据定义，它们之间的异或值是，下面是异或运算的真值表：

A B
0 0 0
0 1 1
1 0 1
1 1 0

异或还有一些非常有趣的性质，比如，，之类的。定义很简单，Chino也一下就学会了，那么现在就是作业时间啦！
开往兔子镇的火车一开始还是手摇式的木板车，所有人都在木板上做成一排，当然，就像你想的那样，旅途非常尬。如今，铁路修好了，因此人们可以坐火车来到兔子镇。有一个问题就是怎么划分车厢——大家都希望能够单独一个车厢，但在大部分情况下这是做不到的。
火车上有个乘客，坐在第i位的乘客对车厢的划分有一个意愿值，我们定义一节车厢的总意愿值为这节车厢所有人意愿值的异或和，即，如果这节车厢包含了第名乘客，那么这节车厢的意愿值是.特别地，如果这节车厢只有一名乘客i，那么这节车厢的意愿值就是a_i.这个意愿值当然越高越好，但是这会让当局非常难办，因此他们确定了一个标准k，k的范围介于所有可能出现的意愿值之间。现在的任务就是让尽可能多的车厢的意愿值为k.
题目对Chino来说太难啦，你能帮一帮Chino吗？

输入描述

第一行是两个数n, k；接下来一行是n个数ai

输出描述

题目中要求的答案

示例1

输入: 

3 1
1 2 3

输出: 

2

说明:

我们划分成[1]和[2,3]两段，显然每段的异或和都是1.注意，同一位乘客只能被划分在一节车厢中，即，你不能做出类似[1,2],[2,3]的划分

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 357ms, 内存消耗: 620K, 提交时间: 2020-05-01 00:39:56 

#include<bits/stdc++.h>
using namespace std;
map<int, int> mp;
int main()
{
	int n, k,sum=0,ans=0,x;
	cin >> n >> k;
	mp[0] = 1;
	for (int i = 1; i <= n; i++)
	{
		cin >> x;
		sum = sum^x;
		if (mp[sum^k] > 0)
		{
			ans++;
			mp.clear();
			sum = 0;
			mp[0] = 1;
		}
		else
		{
			mp[sum] = 1;
		}
	}
	cout << ans << endl;
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 78ms, 内存消耗: 892K, 提交时间: 2019-04-07 21:37:57 

#include<bits/stdc++.h>
using namespace std;
int a[500005];
int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	int x,s=0,ans=0,mx=0;;
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		k^=x;
		a[s]=i;
		if(a[k]>mx){
			mx=i;
			a[k]=0;
			ans++;
		}
		s^=x;
	}
	printf("%d\n",ans);
}

上一题

© 2024 nowcoder.com