87pts求调,玄关!
  • 板块P1120 小木棍
  • 楼主Lwx112412
  • 当前回复1
  • 已保存回复1
  • 发布时间2025/6/30 00:42
  • 上次更新2025/6/30 20:53:13
查看原帖
87pts求调,玄关!
1304032
Lwx112412楼主2025/6/30 00:42

TLE on #30(本人已疯)

# include <bits/stdc++.h>
# define int long long
# define endl '\n'
# define str string
# define fst ios::sync_with_stdio (0); cin.tie (0); cout.tie (0);

using namespace std;

const int N = 1e6 + 5, M = 2e6 + 5;
const int P = 1e9 + 7;
const int INF = 0x3f3f3f3f3f3f3f3f;

int n;
int a[100];
int sum;
int vis[100];
int len;
int Count;
bool cmp (int x, int y) {
	return x > y;
}
bool dfs (int cnt, int nowlen, int pos) { // genshu, xianzaichangdu, weizhi(jieshangyige)
	if (cnt == Count) {
		return 1;
	} 
	if (nowlen == len) {
		return dfs (cnt + 1, 0, 0);
	}
	int cant = 0;
	for (int i = pos; i <= n; i ++ ) {
		if ((! vis[i]) && ((nowlen + a[i]) <= len) && (a[i] != cant)) {
			vis[i] = 1;
			if (dfs (cnt, nowlen + a[i], i + 1)) {
				return 1;
			}
			vis[i] = 0;
			cant = a[i];
			if (((nowlen + a[i]) == len) || (! nowlen)) {
				return 0;
			}
		} 
	}
	return 0;
}

signed main () {
	fst;
	cin >> n;
	for (int i = 1; i <= n; i ++ ) {
		cin >> a[i];
		sum += a[i];
	}
	sort (a + 1, a + 1 + n, cmp);
	for ( len = a[1]; len <= sum; len ++ ) {
		if (sum % len) {
			continue;
		}
		Count = (sum / len);
		memset (vis, 0, sizeof (vis));
		if (dfs (0, 0, 1)) {
			cout << len;
			return 0;
		}
	}
	return 0;
}
2025/6/30 00:42
加载中...