CF1765L Project Manager

· · 题解

设 N = \sum p。

考虑到每个没有节假日的周必然存在至少一个项目被完成，所以答案不超过 M = 7(N + m)。对于 h_i > M 的节假日，一律无用。

因为一个人会选择编号较小的项目推进，所以按编号从小到大依次模拟每个项目的进度。设当前处理到项目的第 i 部分，在第 cur 天处理了第 i - 1 部分。求出第 a_i 个人在第 cur + 1 天起，第一个工作且没有处理编号更小的项目的日期。

星期一到星期日相互独立，因此考虑对一星期的七天，如果 a_i 在这天工作，分别求后继，再取最小值。这样，在第 h_i 天的假期相当于从 h_i 跳到了 h_i + 7。类似的，一个被占用处理编号更小的项目的日期 p 相当于从 p 跳到了 p + 7。对于前者，直接预处理出 suc_i 表示从 i 开始的对应类型的第一天工作日。对于后者，用 map 维护并查集即可。注意这里并查集是一条链，所以执行 find 的总次数为总点数的线性，而每新增一个点，都意味着找到一个工作且未被占用的后继，所以总点数为 \mathcal{O}(N) 级别。

时间复杂度 \mathcal{O}(m + N\log N)。不压行且两空格缩进的代码竟然获得了 CF 最短解（2022.12.16）？跑得也非常快，前提是开了 ios::sync_with_stdio(0)。

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

constexpr int N = 2e5 + 5;
constexpr int M = 3e6 + 5;
const string week[8] = {
  "",
  "Monday",
  "Tuesday",
  "Wednesday",
  "Thursday",
  "Friday",
  "Saturday",
  "Sunday"
};

int n, m, k, w[N][8], suc[M];
map<int, int> mp[N];
int f(int id, int z) {
  z = suc[z];
  auto it = mp[id].find(z);
  if(it == mp[id].end() || it->second == z) return z;
  return it->second = f(id, it->second);
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin);
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  cin >> n >> m >> k;
  for(int i = 1; i < M; i++) suc[i] = i;
  for(int i = 1; i <= n; i++) {
    int cnt;
    cin >> cnt;
    string day;
    while(cnt--) {
      cin >> day;
      for(int j = 1; j <= 7; j++) {
        if(day == week[j]) w[i][j] = 1;
      }
    }
  }
  for(int i = 1; i <= m; i++) {
    int h;
    cin >> h;
    if(h < M) suc[h] = h + 7;
  }
  for(int i = M - 8; i; i--) suc[i] = suc[suc[i]];

  for(int _ = 1; _ <= k; _++) {
    int p, a, cur = 0;
    cin >> p;
    while(p--) {
      cin >> a;
      int nxt = M;
      for(int i = 1; i <= 7; i++) {
        if(w[a][(cur + i - 1) % 7 + 1]) nxt = min(nxt, f(a, cur + i));
        if(nxt == cur + i) break;
      }
      mp[a][nxt] = nxt + 7, cur = nxt;
    }
    cout << cur << " ";
  }
  cout << "\n";
  return 0;
}
/*
g++ L.cpp -o L -std=c++14 -O2 -DALEX_WEI
*/