专栏文章

我去，是 57 龙

TTiat_Siba_Ignareo
P12551题解参与者 9已保存评论 8

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
8 条
当前快照
1 份
快照标识符
@minsf1qf
此快照首次捕获于
2025/12/02 07:35
3 个月前
此快照最后确认于
2025/12/02 07:35
3 个月前
查看原文
标题来源：sasakure 的《Apollo》。小心 3,5,73,5,7。
其实吧，抛开细节和码量（参考数据：我的代码有 19.53KB19.53\text{KB}，157157 个 if）不谈，这个题挺有趣的。
我是一个 Sub 一个 Sub 写过来的。因为太难写了。
每个小部分只放核心代码，不然太长了。完整代码在最后。
讨论每个 Sub 的时候会排除做前面的 Sub 时已经判掉的情况。

Subtask1

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

数据很小，直接状压爆搜。
代码CPP
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≤10n \leq 10，T≤20T \leq 20。但是当 TT 大的时候会挂掉。所以当 T>20T>20 的时候搜 n≤5n \leq 5，因为 n≤5n \leq 5 的情况可能会很多，这样简化会比较好。n≥6n \ge 6 边界不多，跑不动就跑不动了。
代码CPP
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

nn 是偶数且没有 22，显然奇素数可以两两配对，如果 k≤n2k \leq \dfrac{n}{2}，这样配 k−1k-1 组然后把剩下的直接分成一组就可以了。这种分法保证了每组和为偶数，奇异序列数量为 00；否则一定有 2k−n2k-n 组是单个的，其余的两两分成一组。
代码CPP
if (!(n & 1)){
    if (maimai > 2){
      if (k <= n / 2){
        cout << "0\n";
        for (int i = 1; i <= k - 1; i++)
          cout << "2 " << a[i * 2 - 1] << " " << a[i * 2] << "\n";
        cout << n - 2 * (k - 1) << " ";
        for (int i = (k - 1) * 2 + 1; i <= n; i++)
          cout << a[i] << " ";
        cout << "\n";
      }else{
        cout << 2 * k - n << "\n";
        for (int i = 1; i <= 2 * k - n; i++)
          cout << "1 " << a[i] << "\n";
        for (int i = 2 * k - n + 1; i <= n; i += 2)
          cout << "2 " << a[i] << " " << a[i + 1] << "\n";
      }
    }
}

Subtask5

难度从这里开始。
首先分析 k>⌊n2⌋k > \lfloor \dfrac{n}{2} \rfloor。这种情况和偶数差不多，把单个的拎出来，把其他的两两配掉。
然后分析 k≤⌊n2⌋k \leq \lfloor \dfrac{n}{2} \rfloor 的情况。考虑证明 n>5n > 5 时答案必定为 00。
证明：考虑把每个质数按照  mod 3\bmod 3 的余数分类。根据鸽巢原理，至少有一个余数出现了 33 次。所以一定能够分出一组 33 的倍数。找出哪个出现了至少 33 次即可。剩下的两两一组也一定是合数。
分这三种情况讨论就做完了。
代码CPP
    if (maimai > 2){
      if (k <= n / 2){
        cout << "0\n";
        memset(buk, 0, sizeof buk);
        for (int i = 1; i <= n; i++)
          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{
          cout << "3 ";
          int cnt = 0, p = 1, js = 1, tot = 0;
          for (int i = 1; i <= n; i++){
            if (a[i] % 3 == 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{
        cout << 2 * k - n << "\n";
        for (int i = 1; i <= 2 * k - n; i++)
          cout << "1 " << a[i] << "\n";
        for (int i = 2 * k - n + 1; i <= n; i += 2)
          cout << "2 " << a[i] << " " << a[i + 1] << "\n";
      }
    }

Subtask6

现在可能有 22 了，但是 k>⌊n2⌋k > \lfloor \dfrac{n}{2} \rfloor。
直接放可能会出问题，因为 22 和奇素数不能分在一起。处理方式其实很简单，有多的一个 22 就优先把 22 先拎出来，然后尽可能多配掉 22 和 22 还有 22 和奇数。因为 k>⌊n2⌋k > \lfloor \dfrac{n}{2} \rfloor，稍微算一下就可以发现非奇异序列一定可以在不考虑 22 加奇素数的情况下取到上界，这样就可以做了。
代码CPP
int cnt = 0;
for (int i = 1; i <= n; i++){
  if (a[i] == 2)
    ++cnt;
  else
    break; 
}
for (int i = 1; i <= n; i++)
  flg[i] = 0;
cout << 2 * k - n << "\n";
if (cnt & 1)
  cout << "1 2\n";
int qwq = (n - k);
for (int i = 1 + (cnt & 1); i <= 2 * qwq + (cnt & 1); i += 2)
  cout << "2 " << a[i] << " " << a[i + 1] << "\n";
for (int i = 2 * qwq + (cnt & 1) + 1; i <= n; i++)
  cout << "1 " << a[i] << "\n";

Subtask8

我先做的是这个 Subtask。
我们上面处理掉了很多情况，剩下有 22 并且 k≤⌊n2⌋k \leq \lfloor \dfrac{n}{2} \rfloor 的情况。
首先，如果 22 是奇数个，可以把 33 个 22 分在一起，其他的就都可以两两分组，这样答案就是 00。然后思考 22 是偶数个怎么做。
显然，当奇素数数量 >5>5 的时候是好做的。根据前面 Subtask5 的方法处理掉奇素数就可以了。
那 ≤5\leq 5 呢？其实依旧可以套用上面的爆搜做，但是如果要分讨怎么办？直接分三种情况。

一、55 个奇素数的情况

会发现答案依然可以为 00。除去 >5>5 个奇素数的三种情况，剩下的情况一定取满了每一个  mod 3\bmod 3 的余数，把这三个放一起就可以了。reverse 一下原数列会好判一点。

二、33 个奇素数的情况

这里开始就要考虑给奇数加上 22 了。给出两个结论：

结论 11

>6>6 的所有素数 pp 一定满足 p≡1(mod6)p \equiv 1 \pmod 6 或者 p≡5(mod6)p \equiv 5 \pmod 6。
证明： 6k+2=2(3k+1)6k+2=2(3k+1)，6k+3=3(2k+1)6k+3=3(2k+1)，6k+4=2(3k+2)6k+4=2(3k+2)，6k=3×2×k6k=3\times2\times k，均不可能为素数。

结论 22

对于一个奇素数 pp，当且仅当 p=3p=3 时，p+2p+2 和 p+4p+4 均为素数，否则 p+2p+2 和 p+4p+4 必有一个数为合数。
证明：根据结论 11，(6k+1)+2(6k+1)+2 和 (6k+5)+4(6k+5)+4 一定为合数。
由于 2k+1=n2k+1=n，所以当存在奇素数不为 33 的时候，这样配掉至多 33 个数，剩下的肯定够配。当有奇素数 +2+2 为合数的时候，因为 n≥7n\ge 7，一定有至少 44 个 22，一定可以把 33 个 22 凑一组（k=2k=2 要和后面的 22 合并）。这样子分组既不会超限也不会不够。
然后就是奇素数全为 33 的情况。显然 3+3+3=93+3+3=9 是一个合数。剩下的全是 22，可以轻松配掉。
至此，这一部分得到了解决。

三、 11 个奇素数的情况

分类讨论这个奇素数加多少是合数。
如果 +2+2 是合数，那么依旧奇素数和 22 配掉，33 个 22 凑一组，剩下的划分。k=2k=2 合并两组即可。
如果 +4+4 是合数，那么奇素数和两个 22 配掉，剩下的直接划分。
如果是一个 33 并且 kk 卡满了，会发现一定有一个 22 落单，所以会有 11 个奇异序列。特判掉。没卡满的话依然可以分出来。
讨论完这些，这个 Subtask 就完成了。
代码CPP
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

其实和 nn 为奇数会差不多，略难一些。
22 有偶数个是好做的。22 和 22 分，奇素数和奇素数分。
22 有奇数个的时候要特判 k=n2k = \dfrac{n}{2}，这种情况直接找有没有一个奇素数加上 22 是合数，有就和 22 配掉，奇异序列个数为 00；没有就随便拉一个配，个数为 11。
剩下的情况还是和上面一样讨论。唯一的区别在于只有一个奇素数 33 的时候由于 k<n2k<\dfrac{n}{2}，我们多了两个 22，可以把 33 配掉了。这种情况没有奇异序列了。
这里只给出偶数个 22 和 k=n2k=\dfrac{n}{2} 的代码：
代码CPP
if (!(cnt & 1)){
        cout << "0\n";
        for (int i = 1; i <= 2 * k - 2; i += 2)
          cout << "2 " << a[i] << " " << a[i + 1] << "\n";
        vector<int> tmp;
        tmp.clear();
        for (int i = 2 * k - 1; i <= n; i++)
          tmp.emplace_back(i);
        cout << tmp.size() << " ";
        for (int i = 2 * k - 1; i <= n; i++)
          cout << a[i] << " ";
        cout <<"\n";
      }else if (k == n / 2){
        bool chk = 1;
        for (int i = 1; i <= n; i++)
          if ((a[i] & 1) && !isp(a[i] + 2)){
            chk = 0;
            swap(a[i], a[1]);
            break;
          }
        cout << chk << "\n";
        sort(a + 2, a + 1 + n);
        for (int i = 1; i <= n; i += 2)
          cout << "2 " << a[i] << " " << a[i + 1] << "\n";
}
完整代码CPP
#include<bits/stdc++.h>
using namespace std;
int t, n, k, a[100005], flg[100005], maimai, tt;
vector<int> ans[100005], tmp[105];
long long p[] = {0, 2, 3, 5, 7, 11, 13, 17, 19};
int mn[2005], fnd, buk[5];
typedef long long ll;
ll slowtm(ll x, ll k, ll m){
	return (__int128)x * k % m;
}
ll qpow(ll x, ll k, ll m){
	ll ans = 1;
	while(k){
		if (k & 1)
			ans = slowtm(ans, x, m);
		x = slowtm(x, x, m);
		k >>= 1;
	}
	return ans;
}
bool Miller_Rabin(ll n, ll a){
	ll vp = n - 1, r = 0, pan;
	while (!(vp & 1))
		r++, vp >>= 1;
	pan = qpow(a, vp, n);
	if (pan == 1)
		return 1;
	for (int i = 0; i < r; i++){
		if (pan == n - 1)
			return 1;
		pan = slowtm(pan, pan, n);
	}
	return 0;
}
bool isp(ll n){
	if (n < 2)
		return 0;
	for (int i = 1; i <= 8; i++){
		if (n == p[i])
			return 1;
		if (n % p[i] == 0)
			return 0;
		if (!Miller_Rabin(n, p[i]))
			return 0;
	}
	return 1;
}
void dfs(int S, int now, int dep){
	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]);
			}
		dfs(S | T, now + isp(sum), dep + 1);
		tmp[dep].clear();
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> t;
	tt = t;
	while (t--){
		cin >> n >> k;
		ll sum = 0;
		maimai = INT_MAX;
		for (int i = 1; i <= n; i++){
			cin >> a[i];
			maimai = min(maimai, a[i]);
		}
		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";
			}
		}else if (n <= 10 && tt <= 20 || n <= 5){
			memset(mn, 0x3f, sizeof mn);
			fnd = 0;
			dfs(0, 0, 1);
			cout << mn[(1 << n) - 1] << "\n";
			for (int i = 1; i <= k; i++){
				cout << ans[i].size() << " ";
				for (auto u : ans[i])
					cout << u << " ";
				cout << "\n";
				ans[i].clear();
			}
		}else if (!(n & 1)){
			if (maimai > 2){
				if (k <= n / 2){
					cout << "0\n";
					for (int i = 1; i <= k - 1; i++)
						cout << "2 " << a[i * 2 - 1] << " " << a[i * 2] << "\n";
					cout << n - 2 * (k - 1) << " ";
					for (int i = (k - 1) * 2 + 1; i <= n; i++)
						cout << a[i] << " ";
					cout << "\n";
				}else{
					cout << 2 * k - n << "\n";
					for (int i = 1; i <= 2 * k - n; i++)
						cout << "1 " << a[i] << "\n";
					for (int i = 2 * k - n + 1; i <= n; i += 2)
						cout << "2 " << a[i] << " " << a[i + 1] << "\n";
				}
			}else{
				if (k <= n / 2){
					int cnt = 0;
					for (int i = 1; i <= n; i++){
						if (a[i] == 2)
							++cnt;
						else
							break; 
					}
					if (!(cnt & 1)){
						cout << "0\n";
						for (int i = 1; i <= 2 * k - 2; i += 2)
							cout << "2 " << a[i] << " " << a[i + 1] << "\n";
						vector<int> tmp;
						tmp.clear();
						for (int i = 2 * k - 1; i <= n; i++)
							tmp.emplace_back(i);
						cout << tmp.size() << " ";
						for (int i = 2 * k - 1; i <= n; i++)
							cout << a[i] << " ";
						cout <<"\n";
					}else if (k == n / 2){
						bool chk = 1;
						for (int i = 1; i <= n; i++)
							if ((a[i] & 1) && !isp(a[i] + 2)){
								chk = 0;
								swap(a[i], a[1]);
								break;
							}
						cout << chk << "\n";
						sort(a + 2, a + 1 + n);
						for (int i = 1; i <= n; i += 2)
							cout << "2 " << a[i] << " " << a[i + 1] << "\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]){
										if (p == 1 && a[i] == 2 && a[i + 1] != 2){
											continue;
										}
										++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]){
										if (p == 1 && a[i] == 2 && a[i + 1] != 2){
											continue;
										}
										++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]){
										if (p == 1 && a[i] == 2 && a[i + 1] != 2){
											continue;
										}
										++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]){
											if (p == 1 && a[i] == 2 && a[i + 1] != 2){
												continue;
											}
											++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 << "0\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";
					}
				}else{
					int cnt = 0;
					for (int i = 1; i <= n; i++){
						if (a[i] == 2)
							++cnt;
						else
							break; 
					}
					for (int i = 1; i <= n; i++)
						flg[i] = 0;
					cout << 2 * k - n << "\n";
					if (cnt & 1)
						cout << "1 2\n";
					int qwq = (n - k);
					for (int i = 1 + (cnt & 1); i <= 2 * qwq + (cnt & 1); i += 2)
						cout << "2 " << a[i] << " " << a[i + 1] << "\n";
					for (int i = 2 * qwq + (cnt & 1) + 1; i <= n; i++)
						cout << "1 " << a[i] << "\n";
				}
			}
		}else{
			if (maimai > 2){
				if (k <= n / 2){
					cout << "0\n";
					memset(buk, 0, sizeof buk);
					for (int i = 1; i <= n; i++)
						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{
						cout << "3 ";
						int cnt = 0, p = 1, js = 1, tot = 0;
						for (int i = 1; i <= n; i++){
							if (a[i] % 3 == 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{
					cout << 2 * k - n << "\n";
					for (int i = 1; i <= 2 * k - n; i++)
						cout << "1 " << a[i] << "\n";
					for (int i = 2 * k - n + 1; i <= n; i += 2)
						cout << "2 " << a[i] << " " << a[i + 1] << "\n";
				}
			}else{
				if (k <= n / 2){
					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";
						}
					}
				}else{
					int cnt = 0;
					for (int i = 1; i <= n; i++){
						if (a[i] == 2)
							++cnt;
						else
							break; 
					}
					for (int i = 1; i <= n; i++)
						flg[i] = 0;
					cout << 2 * k - n << "\n";
					if (cnt & 1)
						cout << "1 2\n";
					int qwq = (n - k);
					for (int i = 1 + (cnt & 1); i <= 2 * qwq + (cnt & 1); i += 2)
						cout << "2 " << a[i] << " " << a[i + 1] << "\n";
					for (int i = 2 * qwq + (cnt & 1) + 1; i <= n; i++)
						cout << "1 " << a[i] << "\n";
				}
			}
		}
	}
	return 0;
}

结语 做完这道题的感想

萌新时期，总会觉得过掉一道黑题是十分遥远的，写掉一个码量巨大的题是永远做不到的。
但是，真正花时间下去，用最朴素的热爱钻研出一个题，经过一番鏖战做完之后，才发现，不过如此。
难吗？难。但是不累。因为心中的热爱在驱动。或许写的时候会无数次破防，无数次质疑自己，但是，在 Accepted 跳出来的那一瞬间，就会意识到，一切都是值得的。静下心来，就能够一次次取得突破。
“蚓无爪牙之利，筋骨之强，上食埃土，下饮黄泉，用心一也；蟹六跪而二螯，非蛇鳝之穴无所寄托者，用心躁也。”
2025 赛季已经开始，愿我们都能在这段时间内静下心来，在每一场比赛中取得令自己满意的成绩，不给 OI 之旅留下遗憾。

评论

共 8 条评论，欢迎与作者交流。

正在加载评论...