CF1939C More Gifts 题解

· · 题解

XVIII Open Olympiad in Informatics - Final Stage, Day 1 T3 非官方题解。

赛时没反应过来基环树找环，惨痛 81 分。

以下所有内容均默认数组下标从 0 开始。称一个礼物的“编号”为它是其中一堆中的第几个，也就是说其编号与它在 n 堆中的哪一堆无关。

令 c 为不同的礼物种类数，特判掉 c\le t 的情况，此时答案为 1；接下来只考虑 c>t 的情况，容易发现在这种情况下若一位参赛者如果拿的第一个礼物在第 i(0\le i<k-2) 堆，下一位参赛者的第一个礼物不可能在第 i+2 堆中。

先考虑怎样的分配礼物策略是最优的：显然是对于每个人能拿就拿。于是对于每个 i(0\le i<n)，处理出一位参赛者拿的第一个礼物的编号是 i 时，下一个参赛者第一个拿的礼物的编号，记为 nx_i（如果她的最后一个礼物在和下一个参赛者的第一个礼物不在同一个堆，为了方便，不妨令 nx_i\ge n；即如果下一个参赛者的第一个礼物是下一堆中的第 j 个，那么 nx_i=n+j）。所有的 nx_i 可以使用数组或 std::set 简单地预处理。

但这样还不够。于是对于每个 i 考虑再处理出对于一个第一次拿编号为 i 的礼物的参赛者，从她开始发放礼物，第一个拿到下一个堆的礼物的参赛者拿到的第一个礼物的编号 f_i，以及这个过程中间的参赛者个数 d_i。这部分可以通过 BFS 得出答案。

于是令 p\leftarrow 0，不断执行 p=nx_{f_p}-n 并累加 d_p，即可通过 k\le 10^6 的部分，并像我一样在赛时获得 81 分的高分。这部分的代码实现因人而异，例如你可能需要将最后的答案加上 k 才能的到正确答案，等等。

考虑优化上述的过程。我们发现 p 在经过若干次的循环（这个次数不超过 n）后又会回到原来有过的一个值，并不断循环：因为每个 p 仅对应一个 nx_{f_p}-n，这是一个内向基环树的结构。于是考虑找规律，具体地，找到循环的周期，处理循环之前的部分以及最后剩余的不完整的一个循环里 d_p 的累加值，并快速计算出中间完整循环部分 d_p 的累加值即可得出答案。这部分的实现细节可以参考代码。

可以借助 std::set 与 std::map 较为简单地实现 O(n\log n) 做法（但是有 TLE 的风险）。也可以通过离散化、哈希表使时间复杂度降低至 O(n)。

放代码：

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
struct Hash{
  static uint64_t splitmix64(uint64_t x){
    x+=0x9e3779b97f4a7c15;
    x=(x^x>>30)*0xbf58476d1ce4e5b9;
    x=(x^x>>27)*0x94d049bb133111eb;
    return x^x>>31;
  }
  size_t operator()(uint64_t x)const{
    static const uint64_t FIXED_RANDOM=chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x+FIXED_RANDOM);
  }
};
// 哈希函数，可以参照：https://codeforces.com/blog/entry/62393
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,k,t; long long c=0; cin>>n>>k>>t;
  vector<int> a(n);
  __gnu_pbds::gp_hash_table<int,int,Hash> m;
  for(auto &i:a)
    if(cin>>i;m.find(i)==m.end())m[i]=c++;
  for(auto &i:a)i=m[i]; // 离散化
  if(c<=t)cout<<"1\n",exit(0);
  vector<int> nx(n),d(n),f(n),s(n);
  vector<vector<int> > g(n);
  for(int i=0,l=0,e=0;i<n;i++){
    while(1){
      if(++s[a[l%n]]==1)e++;
      if(e>t){
        nx[i]=l,s[a[l%n]]=0,e--;
        if(l<n)g[l].emplace_back(i);
        break;
      } // 拿的礼物种类 > t
      l++;
    }
    if(!--s[a[i]])e--;
  } // 预处理 nx[i]
  queue<int> q;
  for(int i=n-1;i>=0;i--)
    if(nx[i]>=n)q.emplace(f[i]=i);
  while(!q.empty()){
    int u=q.front(); q.pop();
    for(int i:g[u])
      f[i]=f[u],d[i]=d[u]+1,q.emplace(i);
  } // 预处理 f[i] 与 d[i]
  vector<int> w(n<<1),b(n,-1);
  for(int i=c=0,p=0;i<k;i++){
    if(~b[p]){
      int x=(k-b[p])/(i-b[p]),r=(k-b[p])%(i-b[p]);
      c+=(c-w[b[p]]+d[p])*(x-1);
      for(int j=0;j<r;j++)
        c+=d[p],p=nx[f[p]]-n;
      break;
    } // 找到环
    w[b[p]=i]=(c+=d[p]),p=nx[f[p]]-n;
  } // 基环树找环
  cout<<c+k<<endl;
  return 0;
}