题目描述

小度最近在研究超导材料，他合成了 $N$ 个新材料排成一排，而每个材料根据基于流程会设置一个编号$P$，表示种类。 小度发现相同种类的材料在距离小于等于$K$ 的情况下会发生反应。
小度想知道哪些种类的材料会发生反应，输出这些种类 $P$ 的异或值。

输入格式：

第一行，两个整数 $N , K (1 \le N , K \le 50000)$
接下来 $N$ 行，每行一个整数，即该位置材料的的种类编号 $P (1 \le P \le 1000000)$

输出格式：

一行，一个整数，会发生反应的种类$P$ 的异或值。

样例

输入：

5 3
1
2
4
1
4

输出：

5

题目分析

模拟题，没什么好说的，也不用哈希表,$O(n)$过得去

C++ 代码

#include<bits/stdc++.h> 
#define int long long
using namespace std;
const int N = 1000010;
int d[N];
bool st[N];
int n , k , p;
signed main( )
{
    cin >> n >> k;
    for(int i = 1 ; i <= n ; i ++)
    {
        int x;
        cin >> x;
        if(d[x] && i - d[x]<= k)
            if(!st[x])
            {
                p ^= x;
                st[x] = true;
            }
        d[x] = i;   
    }
    cout << p << '\n';
    return 0;
}

Go 代码

package main

import "fmt"

func main() {
    var a , st [1000010]int64
    var n , k , p , i int64
    fmt.Scanf("%d %d\n" , &n , &k)
    for i = 1 ; i <= n ; i ++{
        var x int64
        fmt.Scanf("%d\n" , &x)
        if a[x] == 0 {
            a[x] = i
        } else {
            if i - a[x] <= k && st[x] == 0 {
                p ^= x
                st[x] = 1
            } else {
                a[x] = i
            }
        }
    }
    fmt.Printf("%d" , p)
}