暴力求 HACK

赛时写了个神秘暴力做法过了，至今不知时间复杂度，感觉不太对，但是不知道怎么 hack。

思路：

下文称题中标号为颜色。

注意到每一种颜色的奶牛之间是相互独立的，考虑将不同颜色的奶牛分开，将颜色为

i

的下标存到 a[i] 里面。

考虑到对于不同的组距离，由整除分块得其分组数量为

O(\sqrt n)

个；反过来，分组数量不同，如果每一个组数量选取一个组距离为代表，其数量大概也是

O(\sqrt n)

个的。

于是对于每一种颜色的奶牛，先在

x=1

时求出每一个组的开头位置，存在一个 it 数组中。然后求 it 中相邻两个下标之差的最小值，将其作为新的

x

进行计算。

更新

x

之后需要更新 it 数组。具体实现上，我直接暴力比较相邻两个指针的下标之差，若其小于

x

，则将后一个指针一直向右移动。这感觉很有问题，复杂度可能是错的。

分组之后用差分前缀和统计答案。

在洛谷上只跑了三秒多，我不会 hack，求大佬 hack。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
vector<int> a[N];

int ans[N];

int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    int v;
    cin >> v;
    a[v].emplace_back(i);
  }
  vector<vector<int>::iterator> it;
  for (int i = 1; i <= n; ++i) {
    if (a[i].empty()) continue;
    it.clear();
    int diff = n + 1;
    it.push_back(a[i].begin());
    for (auto j = a[i].begin(); j != a[i].end(); ++j) {
      if (*j - *it.back() > 1) {
        diff = min(diff, *j - *it.back());
        it.push_back(j);
      }
    }
    ans[1] += it.size();
    ans[diff] -= it.size();
    if (diff > n) continue;
    int x = diff;
    for (; x <= n;) {
      diff = n + 1;
      for (auto j = it.begin() + 1; j != it.end(); ++j) {
        while (*j != a[i].end() && *(*j) - *(*(j - 1)) <= x) ++(*j);
        if (*j == a[i].end()) {
          it.erase(j, it.end());
          break;
        }
        diff = min(diff, *(*j) - *(*(j - 1)));
      }
      ans[x] += it.size();
      ans[diff] -= it.size();
      if (diff > n) break;
      // cerr << i << ' ' << x << ' ' << diff << ' ' << '\n';
      x = diff;
    }
  }
  for (int i = 1; i <= n; ++i) ans[i] += ans[i - 1];
  for (int i = 1; i <= n; ++i) cout << ans[i] << '\n';
  return 0;
}

讨论操作

回复

相关推荐

暴力求 HACK