Submission #43460450

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)
int read(){int r;scanf("%d",&r);return r;}

const int K = 10000;
const int N = 2000;
bitset<K+10> can[N+10]; // can[i...n][长度] = bool(后面i..n的字符能否品出 长度)
bitset<K+10> dp[N+10]; // dp[1..i][长度] = bool(可能对答案贡献(后缀长度可能+前缀最小),且前缀1..i 可拼成
string ans[2]; // ans[i] = 处理完前i个 最长的 可能的 字符串, 滚动i&1
string&cs(int i){return ans[i&1];}
vector<string> arr;
char tmp[K+10];

vector<int> make_z(const string&s) {
  int l = 0; // 保持r最大
  int n = size(s);
  vector<int> z(n,0);
  rep(i,1,n) {
    int r = l + z[l] - 1;
    z[i] = max(0,min(r-i+1,z[i-l]));
    while(i + z[i] < n and s[i + z[i]] == s[z[i]]) z[i]++;
    if(i + z[i] - 1 > r) l = i;
  }
  z[0] = n;
  return z;
}

// prefix[p] vs prefix[q] + arr[j]
int cmp(const vector<int>&z,int i, int p, int q) {
  // [............]
  // [........p]..]
  // [.....q][si....]
  const int szs = size(arr[i]);
  if (p <= q) return 0;
  int lcp = z[szs + q];
  if (lcp >= szs || q + lcp >= p) return 0;
  return (cs(i-1)[q + lcp] < arr[i][lcp]) ? -1 : 1;
}

// sign( (ans[i-1][0..p] + s[i])
//   -   (ans[i-1][0..q] + s[i]))
// < -1, = 0, > 1
int cmp2(const vector<int>&z,int i,int p, int q) { // p,q 0-index
  // z = s[i] + '$' + ans[i-1]
  // [.....p][si......]
  // [..........q][si......]
  //         [   ]      lcp(si,ans[i-1][p+1..q])
  //              [   ] lcp(si,si[q-p..])
  //z:       0      szs-1
  // szs+1
  int szs = size(arr[i]);
  if (p > q) return -cmp2(z,i, q, p);
  int lcp = z[szs + p]; // lcp(si,ans[i-1][p+1..q])
  if (lcp < q - p) {
    if (lcp >= szs) return 0;
    return (cs(i-1)[p + lcp] < arr[i][lcp]) ? -1 : 1;
  }
  lcp = z[q - p]; // lcp(si,si[q-p..])
  if (q + lcp >= p + szs) return 0;
  return (arr[i][lcp] < arr[i][q - p + lcp]) ? -1: 1;
}

int main() {
  int n=read();
  int k=read();
  arr.resize(n+1); // 1-index
  rep(i,1,n+1) {
    scanf("%s",tmp);
    int sz=strlen(tmp);
    rep(j,0,sz) arr[i].push_back(tmp[j]);
  }
  can[n + 1][0] = 1;

  // Zeroes are shifted in, and bits that would go to an index out of range are dropped (ignored).
  per(i,1,n+1) can[i] = can[i + 1] | (can[i + 1] << (int)size(arr[i]));

  dp[0][0] = 1;
  rep(i,1,n+1){
    // 不使用j的情况
    cs(i) = cs(i - 1);
    per(j,0,k+1) if(dp[i-1][j] and can[i+1][k-j]) { // 对于上一个成立,对于当前不使用, 可能不成立
      cs(i) = cs(i).substr(0,j); // 先只用关心最长的即可
      break;
    }
    const int sz = size(arr[i]);
    auto z = make_z(arr[i] + cs(i - 1)); // [0..sz-1][sz..sz+len(cs(i-1))-1]
    z.push_back(0); // cmp2 中 z[q-p] 可能超长
    // decide cs[i]
    int nxt = -1; // 只记录合成的(prefix[ans[i-1]] + s[i])最优的
    rep(j,0,k-sz+1) if (dp[i-1][j] and can[i+1][k-(j+sz)]) { // j => j+sz
      if (nxt == -1) { // 暂无方案
        int res = cmp(z,i,size(cs(i)), j); // 和 转移过来的 方案比
        if (res == 1 || (res == 0 and j + sz > (int)size(cs(i)))) nxt = j; // 更小,或前缀相等但是更长
      } else if (cmp2(z,i, nxt, j) <= 0){
        nxt = j;
      }
    }
    if (nxt == -1) {// s[i] is not a suffix of cs[i]
      // 对于上一个成立, 对于当前不使用, 可能不成立,
      // 这种状态不清理其实也不影响,因为后面拼接时也有校验,不会产生贡献
      rep(j,0,k+1) if(dp[i-1][j] and can[i+1][k-j]) dp[i][j] = 1;
    } else {
      // ans [.............]
      //     [.....nxt][si.....]
      //                 | 匹配以后的0/1会变
      cs(i) = cs(i - 1).substr(0, nxt) + arr[i];
      // 和原来相等的部分
      rep(j,0,size(cs(i - 1))+1) dp[i][j] = (dp[i - 1][j] and can[i+1][k-j] and cmp(z,i, j, nxt) == 0);
      dp[i][size(cs(i))] = 1;
      // 又 前面 的 + arr[i] 拼成
      rep(j,0, size(cs(i)) - sz) if(dp[i - 1][j] and can[i+1][k-sz-j] and cmp2(z,i,j,nxt) == 0)dp[i][j+sz]=1;
    }
  }
  printf("%s\n",cs(n).c_str());
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int read()’:
./Main.cpp:5:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    5 | int read(){int r;scanf("%d",&r);return r;}
      |                  ~~~~~^~~~~~~~~
./Main.cpp: In function ‘int main()’:
./Main.cpp:70:10: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   70 |     scanf("%s",tmp);
      |     ~~~~~^~~~~~~~~~

Judge Result