令当前时间为 \(t\),则序列 \(i\) 取的到 \(j\) 需满足的条件为:\(t\equiv j \pmod {len_i}\)。
多个同余方程要一起考虑,不难想到 excrt(扩展中国剩余定理)。
考虑枚举具体的数字(\(1\sim m\)),遍历 \(1\sim n\),肯定不可能把 excrt 跑完。(这样优化空间很小)
那就只能对于一段序列,元素两两之间都要判断是否能同时存在,具体地,\(\gcd(len_j,len_i)\ |\ place[i]-place[j]\)。(excrt判断有无解)但这样仍会 T。
然后我看了题解,一语点醒梦中人,序列长度小于等于 \(40\)!每次新加入一个元素时,处理一下,只需做 \(40\) 次判断即可(这种换角度的思想很常见)。回头来看,其实这里给出这个条件就在疯狂暗示你该这样做,所以有时面向数据范围编程是一种很好的方法。
所以用个two-pointers即可,时间复杂度:\(\mathcal {O}(\sum len_i\times 40 \times log(40)\le 4.8*10^7)\)。
#include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #include <vector> #define uint unsigned int #define LL long long using namespace std; const int MAXN = 1e5 + 5, MAXM = 45; int n, m, c[MAXN][MAXM], ans, g[MAXM], ct[MAXM]; int len[MAXN]; vector <int> v[MAXN], place[MAXN]; int Gcd(int x, int y) { return y ? Gcd(y, x % y) : x; } // qwq // 一遍过样例可还行 bool Check(int x, int y, int a, int b) { return ((b - a) % Gcd(x, y)) == 0; } int main() { int x, y; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i ++) { scanf("%d", &len[i]); for(int j = 1; j <= len[i]; j ++) scanf("%d", &y), v[y].push_back(i), place[y].push_back(j); } for(int i = 1; i <= m; i ++) { memset(ct, 0, sizeof(ct)); int l = 0, r = 0; ans = 0; for(; r < v[i].size(); r ++) { if(r && v[i][r] > v[i][r - 1] + 1) l = r, memset(ct, 0, sizeof(ct)); for(int j = 1; j <= 40; j ++) { if(ct[j] && !Check(j, len[v[i][r]], place[i][g[j]], place[i][r])) { while(ct[j]) ct[len[v[i][l ++]]] --; } } ans = max(ans, r - l + 1); ct[len[v[i][r]]] ++; g[len[v[i][r]]] = r; } printf("%d\n", ans); } return 0; }