自动搬运

查看原文

来自洛谷，原作者为

	Misserina AFOed 24.7.8-24.11.30

搬运于2025-08-24 22:58:10，当前版本为作者最后更新于2024-07-22 15:19:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P10460 防线

我的算法比较与众不同：位运算。

首先需要明确一点：如果一组数据中只有一个数据出现了奇数次，那么把全部数据异或一遍，最后剩下的就是出现奇数次的那个数，因为两个相同数字异或后总是零。

然后再遍历全部防线，找出那个出现奇数次的防具出现次数即可。

代码如下：

#include <bits/stdc++.h>
using namespace std;
int t,n,s,e,d;
struct defender {
	int st;
	int en;
	int dis;
};
defender arr[200005];
int main() {
	scanf("%d",&t);
	for (int i=1;i<=t;i++) {
		scanf("%d",&n);
		int m=0;
		for (int i=1;i<=n;i++) {
			scanf("%d%d%d",&s,&e,&d);
			defender tmp;
			tmp.st=s;
			tmp.en=e;
			tmp.dis=d;
			arr[i]=tmp;
			for (int k=s;k<=e;k+=d) m^=(k+1); //排除k=0的特殊情况
		}
		if (m==0) {
		    printf("There's no weakness.\n");
		    return 0;
		}
		m--;
		int num=0;
		for (int i=1;i<=n;i++) {
			if (m<=arr[i].en && m>=arr[i].st && (m-arr[i].st)%arr[i].dis==0) num++;
		}
		printf("%d %d\n",m,num);
	}
}