也是打上搜了。
小木棍
曾经在题库上做过，数据水就过了，交洛谷发现只有 87pts。
《剪 枝 盛 宴》
- 钦定长度：最小肯定是最长的那根木棍，最长肯定是所有木棍的总和，并且这个长度一定只能是总和的因数。
- 选择顺序：如果选一个长的合法，那么选若干个和相同的短的一定合法但不优，因此按长度倒序排序。
- 如果合法立即回溯。
- 回溯后立即撤销标记，省略 memset。
- 每次拼接只会取长度不比上一次选择的木棍长的木棍，可以二分找。
- 如果某一根木棍不合法，与其长度相同的所有其他木棍均不合法。
- 如果某根小木棍与当前拼接刚好为钦定长度但不合法，此后一定不会出现合法方案，直接回溯。
点击查看代码
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define lx ll
inline lx qr()
{
char ch = getchar(); lx x = 0, f = 1;
for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
return x * f;
}
#undef lx
#define qr qr()
#define fi first
#define se second
#define pii pair<int, int>
#define P_B(x) push_back(x)
#define M_P(x, y) make_pair(x, y)
const int Ratio = 0;
const int N = 100 + 5;
const int mod = 998244353;
int n, sum, ans;
int a[N];
bool yz[N], ok;
namespace Wisadel
{
void Wdfs(int nlen, int nok, int ned, int id)
{
if(nlen == ned)
{
if(nok == sum / ned){ok = 1; return ;}
fo(i, 1, n) if(!yz[i])
{
yz[i] = 1;
Wdfs(a[i], nok + 1, ned, i);
yz[i] = 0;
if(ok) return ;
break;
}
return ;
}
int l = id + 1, r = n;
while(l < r)
{
int mid = (l + r) >> 1;
if(a[mid] <= ned - nlen) r = mid;
else l = mid + 1;
}
int zc = 0;
fo(i, l, n) if(!yz[i] && a[i] != zc)
{
yz[i] = 1;
Wdfs(nlen + a[i], nok, ned, i);
yz[i] = 0;
if(ok) return ;
if(nlen + a[i] == ned) return ;
zc = a[i];
}
}
short main()
{
// freopen(".in", "r", stdin), freopen(".out", "w", stdout);
n = qr;
fo(i, 1, n) a[i] = qr, sum += a[i];
ans = sum;
sort(a + 1, a + 1 + n, [](int a, int b){return a > b;});
fo(i, a[1], sum) if(sum % i == 0)
{
yz[1] = 1;
Wdfs(a[1], 1, i, 1);
yz[1] = 0;
if(ok){ans = i; break;}
}
printf("%d\n", ans);
return Ratio;
}
}
signed main(){return Wisadel::main();}