P2463 WA on #5 求调
  • 板块题目总版
  • 楼主Ryanhao
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/1/19 16:22
  • 上次更新2025/1/19 18:59:52
查看原帖
P2463 WA on #5 求调
741633
Ryanhao楼主2025/1/19 16:22
#include <cstdio>
using namespace std;

const int maxn = 1e3+5, maxm = 1e2+5;

int A[maxn][maxm],a[maxn][maxm],n[maxn];
int nxt[maxm]; // for A[1]

int main() {
  int N;
  scanf("%d",&N);
  for (int i = 1; i <= N; i++) {
    scanf("%d",n+i);
    for (int j = 0; j < n[i]; j++) {
      scanf("%d",A[i]+j);
      if (j > 0) a[i][j-1] = A[i][j]-A[i][j-1]; 
      // reset dis-array
      //printf("%d ",a[i][j]);
    }
    //puts("");
    n[i]--;
  }
  nxt[1] = 0;
  for (int i = 1; i < n[1]; i++) {
    int j = nxt[i];
    while(j && a[1][i]!=a[1][j]) j = nxt[j];
    if (a[1][i] == a[1][j]) nxt[i+1] = j+1;
    else nxt[i+1] = 0;
  }
  //for (int i = 1; i <= n[1]; i++) printf("%d ",nxt[i]); puts("");
  for (int len = n[1]; len >= 1; len--) { // O(m)
    bool F = 1;
    for (int i = 2; i <= N; i++) {
      if (n[i] < len) F = 0; // too long!
    }
    if (!F) continue; // shorter
    F = 0;
    for (int stt = 1; stt+len-1 <= n[1]; stt++) { 
      // start point and len decided the list of the compare string. O(m)
      bool G = 1;
      for (int I = 2; I <= N; I++) { // O(n)
        int cnt = 0;
        for (int i = 0, j = 0; i <= n[I]; i++) { // O(2m)
          while(j&&a[I][i]!=a[1][j+stt-1]) j = nxt[j];
          if (a[I][i]==a[1][j+stt-1]) j++;
          if (j == len) cnt++;
          //printf("%d,%d\n",i,j);
        }
        //printf("sub(&%d+%d), cnt:%d\n",stt,len,cnt);
        if (!cnt) {
          G = 0; break; // if don't, go away bye~!
        }
      }
      if (G) {
        F = 1; break; // find a string can compare all.
      }
    }
    if (F) {
      printf("%d",len+1);
      return 0;
    }
  } 
}
2025/1/19 16:22
加载中...