小木棍

6
zengfj LV 7 MOD @ 2025-2-21 12:52:22
没有加nxt数组优化之前总是差个10多毫秒，跟某些人AC的代码来比实在找不到哪里可以再优化了，只能坚守住最后的倔强没有二分查找。

注释都在代码里了，就懒得写了。
```
#include <bits/stdc++.h>
using namespace std;

int a[80], n, tot;
bool used[80]; // DFS时记录每根木棍的使用情况
//vector<int> lens; // 可能的原始长度，也就是a之和的约数。
int curLen; // 当前正在尝试的原始木棍长度
int curCnt; // 当前正在尝试的长度对应的原始木棍根数
int nxt[80]; // nxt[i]记录第i根拼接失败后，下面该拼哪一根（后面第一根长度不同的）。

// 尝试拼出原始长度为curLen的木棍
// len：当前已经拼出来的（半成品）木棍长度
// cnt：正在拼的木棍编号（已经拼好了cnt-1根木棍）
// lastIdx：上一次拼接到第cnt根木棍的小棍编号
bool dfs(int len, int cnt, int lastIdx) {
	// 所有木棍都已拼好
	// ！！！！！这里是极限省时的第1个点：要提前算好curCnt
	// 如果每次都在这里除，时间就会增加几个ms！！！！！
	if (cnt > curCnt)  return true;
	// 当前的木棍拼好了，去拼下一根
	if (len == curLen) return dfs(0, cnt + 1, 1);

	// 剪枝1：从最长的a_i开始尝试拼
	for (int i = lastIdx; i <= n; i++) {
		// failLen != a[i]：相同的失败长度a[i]就不要重复试了
		if (!used[i] && len + a[i] <= curLen) {
			used[i] = 1;
			if (dfs(len + a[i], cnt, i + 1)) return true;
			// 如果没有在上一句返回true，说明a[i]这个长度拼接失败
			used[i] = 0; // 还原现场
			// 剪枝3：如果当前尝试拼入第一根就失败，
			// 那这个分支就不用继续了
//			if (len == 0) return false;
			// 剪枝4：若当前恰好拼出一整根curLen的木棍，
			// 但接下来拼剩余原始木棍的递归分支失败，
			// 那么当前分支也不用继续做了
			if (len == 0 || len + a[i] == curLen) return false;
			// 拼接下一个不同的长度
            i = nxt[i];
		}
	}
	return false; // 所有分支均尝试过，搜索失败
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		tot += a[i];
	}

	// DFS时，从最长的a_i开始尝试拼，可以更早判断失败（减小搜索空间）
	sort(a + 1, a + 1 + n, greater<int>());

	// ！！！！！这里是极限省时的第2个非常重要的点！！！！！
	nxt[n] = n;
	for (int i = n - 1; i >= 1; i--) {
		nxt[i] = i;
		if (a[i] == a[i + 1]) nxt[i] = nxt[i + 1];
	}

	// 找出tot的所有比a[1]大的约数，这些是原始长度的备选项
	// 优化点：枚举到tot/2！！！！！
	for (curLen = a[1]; curLen <= tot >> 1; curLen++) {
		if (tot % curLen) continue;
		curCnt = tot / curLen;
		if (dfs(0, 1, 1)) {
			printf("%d", curLen);
			return 0;
		}
	}
	// 如果tot/2之内都无解，那么一定是所有小木棍拼成一整根。
	printf("%d", tot);
	return 0;
}
```
- C23huangminzhe @ 2025-2-21 19:25:08
  
  \o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/\o/
- C23huangyuran @ 2025-2-24 13:29:17
  
  @ o/[doge]