题解：P10460 防线

MisserinaAFO · 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);
    }
}