ZROI P2592 题解

题面

点击此处展开题面

找众数战士

给定一个长度为 $n$ 的序列，你需要对于每个前缀，找到出现次数最多的那个数字。如果有多个出现次数最多的数字，输出最小的那个。

由于输出的数字太多了，为了加快输出，你只需要输出所有数字的异或和。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个正整数 $a_i$，表示序列。

由于输入量较大，建议使用快速输入。

输出格式

一个非负整数，表示输出数字的异或和。

样例

输入：

7
1 3 2 2 1 2 1

输出：

1

数据范围

对于 100% 的数据，$1 \leq a_i \leq n$。

• 测试点 1~3：$n \leq 10^3$
• 测试点 4~7：$n \leq 10^5$
• 测试点 8~10：$n \leq 10^7$

提示

（原题在这里给了个快读板子）

解题

记 $f_i$ 为前 $i$ 个数中出现最多的数字。

根据加上第 $i$ 个数后的情况分类讨论：

1. 加上第 $i$ 个数后，$a_i$ 不是前 $i$ 个数中出现最多的数字
2. 加上第 $i$ 个数后，$a_i$ 是前 $i$ 个数中出现最多的数字

对于情况 1，有 $f_i = f_{i - 1}$。

对于情况 2，有 $f_i = a_i$。

如何判断 $a_i$ 是不是出现最多的那个呢？

建一个桶 $b$，$b_i$ 代表到 $i$ 出现过（包括当前计算到的）的次数。本题 $n \leq 10^7$，空间 1 GB，开得下。

对于第 $i$ 个数，记当前数字出现的次数 $b_{a_i}$ 为 $x$，记上一个数字出现的次数 $b_{a_{i - 1}}$ 为 $y$：如果 $x > y$，那么对应情况 1。如果 $x < y$，那么对应情况 2。

发现漏掉了 $x = y$ 的情况。题中说有多个时取值最小的那个，也就是：如果 $a_i < a_{i - 1}$，那么对应情况 1，否则对应情况 2。

发现 $f_i$ 与 $f$ 中除了 $f_{i - 1}$ 以外的元素都无关，所以只需要 $f_1$ 和 $f_2$ 滚动即可。

代码

#include <iostream>
using namespace std;

/**
 * 快读。
 * @see http://zhengruioi.com/problem/2605
 */
namespace IO {
const int N = 1e7 + 5;
char _READ_[N], _PRINT_[N];
int _READ_POS_, _PRINT_POS_, _READ_LEN_;
inline char readc() {
#ifndef ONLINE_JUDGE
  return getchar();
#endif
  if (!_READ_POS_) {
    if (feof(stdin)) return -1;
    _READ_LEN_ = fread(_READ_, 1, N, stdin);
  }
  char c = _READ_[_READ_POS_++];
  if (_READ_POS_ == _READ_LEN_) _READ_POS_ = 0;
  return c;
}
template <typename T>
inline int read(T &x) {  // NOLINT
  x = 0;
  int flag = 1, c;
  while (((c = readc()) < '0' || c > '9') && c != '-')
    if (c < 0) return -1;
  if (c == '-')
    flag = -1;
  else
    x = c - '0';  // NOLINT
  while ((c = readc()) >= '0' && c <= '9') x = x * 10 - '0' + c;
  x *= flag;
  return 0;
}
}  // namespace IO

const int N = 1e7 + 5;
int count[N], n;

int main() {
  IO::read(n);
  int ans = 0;   // 异或和
  int last = 0;  // 上一个答案
  for (int i = 1; i <= n; ++i) {
    int a;
    IO::read(a);
    ++count[a];
    if (count[a] > count[last])
      last = a;  // 当前数字的出现次数更多
    else if (count[a] == count[last] && a < last)
      last = a;  // 一样多，但更小
    ans ^= last;
  }
  printf("%d", ans);
  return 0;
}