我去，是 57 龙

Tiat_Siba_Ignareo · 2025-09-26 13:10:00 · 题解

标题来源：sasakure 的《Apollo》。小心 3,5,7。

其实吧，抛开细节和码量（参考数据：我的代码有 19.53\text{KB}，157 个 if）不谈，这个题挺有趣的。

我是一个 Sub 一个 Sub 写过来的。因为太难写了。

每个小部分只放核心代码，不然太长了。完整代码在最后。

讨论每个 Sub 的时候会排除做前面的 Sub 时已经判掉的情况。

Subtask1

这个 Subtask 还是非常简单的。显然把所有加在一起，判断总和是不是质数。由于数据规模稍大，以及后面要写爆搜对时间有一定要求，为了效率，我用了 Miller-Rabin。

::::info[代码]

if (k == 1){
  for (int i = 1; i <= n; i++)
    sum += a[i];
  if (isp(sum)){
    cout << "1\n" << n << " ";
    for (int i = 1; i <= n; i++)
      cout << a[i] << " ";
    cout << "\n";
  }else{
    cout << "0\n" << n << " ";
    for (int i = 1; i <= n; i++)
      cout << a[i] << " ";
    cout << "\n";
  }
}

::::

Subtask2

数据很小，直接状压爆搜。

::::info[代码]

void dfs(int S, int now, int dep){
//  cerr << S << " " << mn[S] << " " << now << "\n";
    if (S == (1 << n) - 1 && dep != k + 1)
        return;
    if (now >= mn[S])
        return;
    mn[S] = now; 
    if (dep >= k + 1)
        return;
    for (int T = 1; T < (1 << n); T++){
        if (S & T)
            continue;
        long long sum = 0;
        for (int i = 1; i <= n; i++)
            if (T & (1 << i - 1))
                sum += a[i];
    //  cerr << T << " " << sum << " " << isp(sum) << "\n";
    //  system("pause");
        dfs(S | T, now + isp(sum), dep + 1);
    }
}
void dfs2(int S, int now, int dep){
//  cerr << S << " " << now << " " << dep << "\n";
//  cerr << mn[S] << "\n";
//  if (now > mn[S])
//      return;
    if (fnd)
        return;
    if (dep > k + 1)
        return;
    if (dep == k + 1 && S == (1 << n) - 1){
    //  cerr << now << " " << mn[S] << "\n"; 
        if (now == mn[S]){
            fnd = 1;
            for (int i = 1; i <= k; i++){
                cout << ans[i].size() << " ";
                for (auto u : ans[i])
                    cout << u << " ";
                cout << "\n";
                ans[i].clear(); 
            }
        }
        return;
    }else if (dep == k + 1)
        return;
    for (int T = 1; T < (1 << n); T++){
        if (S & T)
            continue;
        long long sum = 0;
        for (int i = 1; i <= n; i++)
            if (T & (1 << i - 1)){
                sum += a[i];
                ans[dep].emplace_back(a[i]);
            }
        dfs2(S | T, now + isp(sum), dep + 1);
        ans[dep].clear();
    }
}

::::

Subtask3

上面的爆搜跑的很慢，可以改成记忆化，这样子优化会相当大，可以通过 n \leq 10，T \leq 20。但是当 T 大的时候会挂掉。所以当 T>20 的时候搜 n \leq 5，因为 n \leq 5 的情况可能会很多，这样简化会比较好。n \ge 6 边界不多，跑不动就跑不动了。

::::info[代码]

void dfs(int S, int now, int dep){
//  cerr << S << " " << mn[S] << " " << now << "\n";
    if (S == (1 << n) - 1 && dep != k + 1)
        return;
    if (now >= mn[S])
        return;
    if (S == (1 << n) - 1){
        for (int i = 1; i <= k; i++)
            ans[i] = tmp[i];
    }
    mn[S] = now; 
    if (dep >= k + 1)
        return;
    for (int T = 1; T < (1 << n); T++){
        if (S & T)
            continue;
        long long sum = 0;
        for (int i = 1; i <= n; i++)
            if (T & (1 << i - 1)){
                sum += a[i];
                tmp[dep].emplace_back(a[i]);
            }
    //  cerr << T << " " << sum << " " << isp(sum) << "\n";
    //  system("pause");
        dfs(S | T, now + isp(sum), dep + 1);
        tmp[dep].clear();
    }
}

::::

Subtask4

对于一个奇素数 p，当且仅当 p=3 时，p+2 和 p+4 均为素数，否则 p+2 和 p+4 必有一个数为合数。

证明：根据结论 1，(6k+1)+2 和 (6k+5)+4 一定为合数。

由于 2k+1=n，所以当存在奇素数不为 3 的时候，这样配掉至多 3 个数，剩下的肯定够配。当有奇素数 +2 为合数的时候，因为 n\ge 7，一定有至少 4 个 2，一定可以把 3 个 2 凑一组（k=2 要和后面的 2 合并）。这样子分组既不会超限也不会不够。

然后就是奇素数全为 3 的情况。显然 3+3+3=9 是一个合数。剩下的全是 2，可以轻松配掉。

至此，这一部分得到了解决。

三、 1 个奇素数的情况

分类讨论这个奇素数加多少是合数。

如果 +2 是合数，那么依旧奇素数和 2 配掉，3 个 2 凑一组，剩下的划分。k=2 合并两组即可。

如果 +4 是合数，那么奇素数和两个 2 配掉，剩下的直接划分。

如果是一个 3 并且 k 卡满了，会发现一定有一个 2 落单，所以会有 1 个奇异序列。特判掉。没卡满的话依然可以分出来。

讨论完这些，这个 Subtask 就完成了。

::::info[代码]

int cnt = 0;
for (int i = 1; i <= n; i++){
  if (a[i] == 2)
    ++cnt;
  else
    break; 
}
if (cnt & 1){
  cout << "0\n";
  if (k == 2){
    cout << "3 " << a[1] << " " << a[2] << " " << a[3] << "\n";
    cout << n - 3 << " ";
    for (int i = 4; i <= n; i++)
      cout << a[i] << " ";
    cout << "\n";
  }else{
    cout << "3 " << a[1] << " " << a[2] << " " << a[3] << "\n";
    int pos = 4, js = 1;
    while (1){
      if (js == k - 1)
        break;
      cout << "2 " << a[pos] << " " << a[pos + 1] << "\n";
      pos += 2;
      ++js;
    }
    cout << (n - pos + 1) << " ";
    for (int i = pos; i <= n; i++)
      cout << a[i] << " ";
    cout << "\n";
  }
  }else{
  if (n - cnt > 3){
    cout << "0\n";
    memset(buk, 0, sizeof buk);
    for (int i = 1; i <= n; i++)
      if (a[i] != 2)
        buk[a[i] % 3]++;
    for (int i = 1; i <= n; i++)
      flg[i] = 0;
    if (buk[0] >= 3){
      cout << "3 ";
      int cnt = 0, p = 1, js = 1, tot = 0;
      for (int i = 1; i <= n; i++){
        if (a[i] % 3 == 0){
          cout << a[i] << " ";
          flg[i] = 1;
          ++cnt;
          ++tot;
          if (cnt == 3)
            break;
        }
      }
      cout << "\n";
      if (js != k - 1){
        for (int i = 1; i <= n; i++){
          if (!flg[i]){
            ++tot;
            if (p == 1)
              cout << "2 " << a[i] << " ";
            else
              cout << a[i] << "\n";
            p ^= 1;
            flg[i] = 1;
            if (!p)
              js++;
            else if (js == k - 1)
              break;
          }
        }
      }
      cout << n - tot << " ";
      for (int i = 1; i <= n; i++){
        if (!flg[i])
          cout << a[i] << " ";
      }
      cout << "\n";
    }else if (buk[1] >= 3){
      cout << "3 ";
      int cnt = 0, p = 1, js = 1, tot = 0;
      for (int i = 1; i <= n; i++){
        if (a[i] % 3 == 1){
          cout << a[i] << " ";
          flg[i] = 1;
          ++cnt;
          ++tot;
          if (cnt == 3)
            break;
        }
      }
      cout << "\n";
      if (js != k - 1){
        for (int i = 1; i <= n; i++){
          if (!flg[i]){
            ++tot;
            if (p == 1)
              cout << "2 " << a[i] << " ";
            else
              cout << a[i] << "\n";
            p ^= 1;
            flg[i] = 1;
            if (!p)
              js++;
            else if (js == k - 1)
              break;
          }
        }
      }
      cout << n - tot << " ";
      for (int i = 1; i <= n; i++){
        if (!flg[i])
          cout << a[i] << " ";
      }
    }else if (buk[2] >= 3){
      cout << "3 ";
      int cnt = 0, p = 1, js = 1, tot = 0;
      for (int i = 1; i <= n; i++){
        if (a[i] % 3 == 2 && a[i] != 2){
          cout << a[i] << " ";
          flg[i] = 1;
          ++cnt;
          ++tot;
          if (cnt == 3)
            break;
        }
      }
      cout << "\n";
      if (js != k - 1){
        for (int i = 1; i <= n; i++){
          if (!flg[i]){
            ++tot;
            if (p == 1)
              cout << "2 " << a[i] << " ";
            else
              cout << a[i] << "\n";
            p ^= 1;
            flg[i] = 1;
            if (!p)
              js++;
            else if (js == k - 1)
              break;
          }
        }
      }
      cout << n - tot << " ";
      for (int i = 1; i <= n; i++){
        if (!flg[i])
          cout << a[i] << " ";
      }
    }else{
      reverse(a + 1, a + 1 + n);
      cout << "3 ";
      int cnt = 0, p = 1, js = 1, tot = 3;
      int p1, p2, p3;
      for (int i = 1; i <= n; i++){
        if (a[i] % 3 == 0){
          p1 = i;
          flg[i] = 1;
          cout << a[i] << " ";
          break;
        }
      }
      for (int i = 1; i <= n; i++){
        if (a[i] % 3 == 1){
          p2 = i;
          flg[i] = 1;
          cout << a[i] << " ";
          break;
        }
      }for (int i = 1; i <= n; i++){
        if (a[i] % 3 == 2){
          p3 = i;
          flg[i] = 1;
          cout << a[i] << " ";
          break;
        }
      }
      cout << "\n"; 
      if (js != k - 1){
        for (int i = 1; i <= n; i++){
          if (!flg[i]){
            ++tot;
            if (p == 1)
              cout << "2 " << a[i] << " ";
            else
              cout << a[i] << "\n";
            p ^= 1;
            flg[i] = 1;
            if (!p)
              js++;
            else if (js == k - 1)
              break;
          }
        }
      }
      cout << n - tot << " ";
      for (int i = 1; i <= n; i++){
        if (!flg[i])
          cout << a[i] << " ";
      }
    }
  }else if (n - cnt == 1){
    reverse(a + 1, a + 1 + n);
    int pos, cnt = 1;
    if (!isp(a[1] + 2)){
      cout << "0\n2 " << a[1] << " " << a[2] << "\n";
      pos = 3;
    }else if (!isp(a[1] + 4)){
      cout << "0\n3 " << a[1] << " " << a[2] << " " << a[3] << "\n";
      pos = 4;
    }else if (!isp(a[1] + 6)){
      cout << (k == n / 2) << "\n4 " << a[1] << " " << a[2] << " " << a[3] << " " << a[4] << "\n";
      pos = 5;
    }
    while (cnt < k - 1){
      cout << "2 " << a[pos] << " " << a[pos + 1] << "\n";
      pos += 2;
      ++cnt;
    }
    cout << n - pos + 1 << " ";
    for (int i = pos; i <= n; i++)
      cout << a[i] << " ";
    cout << "\n";
  }else if (n - cnt == 3){
    reverse(a + 1, a + 1 + n);
  //    reverse(a + 1, a + 4);
    int pos, cnt = 1;
    if (!isp(a[1] + 2)){
      cout << "0\n2 " << a[1] << " " << a[4] << "\n";
      pos = 5;
    }else if (!isp(a[1] + 4)){
      cout << "0\n3 " << a[1] << " " << a[4] << " " << a[5] << "\n";
      pos = 6;
    }else if (!isp(a[1] + 6)){
      cout << "0\n3 3 3 3\n";
      pos = 4;
      while (cnt < k - 1){
        cout << "2 " << a[pos] << " " << a[pos + 1] << "\n";
        pos += 2;
        ++cnt;
      }
      cout << n - pos + 1 << " ";
      for (int i = pos; i <= n; i++)
        cout << a[i] << " ";
      cout << "\n";
      continue;
    }
    while (cnt < k - 1){
      cout << "2 " << a[pos] << " " << a[pos + 1] << "\n";
      pos += 2;
      ++cnt;
    }
    cout << n - pos + 3 << " ";
    cout << a[2] << " " << a[3] << " ";
    for (int i = pos; i <= n; i++)
      cout << a[i] << " ";
    cout << "\n";
  }
}

::::

Subtask7

其实和 n 为奇数会差不多，略难一些。