包对的
2025-08-16 17:44:10
发布于:广东
0阅读
0回复
0点赞
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <numeric>
using namespace std;
using ll = long long;
bool canTransform(const vector<ll>& initial, int N, const vector<ll>& target, int M) {
ll sum_initial = accumulate(initial.begin(), initial.end(), 0LL);
ll sum_target = accumulate(target.begin(), target.end(), 0LL);
if (sum_initial != sum_target) {
return false;
}
if (M == N) {
vector<ll> initial_rev = initial;
reverse(initial_rev.begin(), initial_rev.end());
return (initial == target) || (initial_rev == target);
}
if (M == 1) {
return (target.size() == 1 && target[0] == sum_initial);
}
queue<vector<ll>> q;
set<vector<ll>> visited;
vector<ll> initial_rev = initial;
reverse(initial_rev.begin(), initial_rev.end());
q.push(initial);
visited.insert(initial);
if (initial_rev != initial) {
q.push(initial_rev);
visited.insert(initial_rev);
}
while (!q.empty()) {
vector<ll> current = q.front();
q.pop();
int L = current.size();
if (L == M) {
if (current == target) {
return true;
}
continue;
}
if (L < M) {
continue;
}
// 尝试所有可能的翻折(k为左边部分长度,1<=k<L)
for (int k = 1; k < L; ++k) {
int m = L - k; // 右边部分长度
vector<ll> left(current.begin(), current.begin() + k); // 左边:[0..k-1]
vector<ll> right(current.begin() + k, current.end()); // 右边:[k..L-1]
vector<ll> folded;
if (m > k) {
// 右边更长:右边多出的部分(m - k个)放在最左边
for (int i = k; i < m; ++i) {
folded.push_back(right[i]);
}
// 重叠部分:右边[i]与左边[k-1-i]相加(i从0到k-1)
for (int i = 0; i < k; ++i) {
folded.push_back(right[i] + left[k - 1 - i]);
}
} else if (k > m) {
// 左边更长:左边多出的部分(k - m个)放在最左边
for (int i = 0; i < k - m; ++i) {
folded.push_back(left[i]);
}
// 重叠部分:左边[i + (k - m)]与右边[m - 1 - i]相加(i从0到m-1)
for (int i = 0; i < m; ++i) {
folded.push_back(left[i + (k - m)] + right[m - 1 - i]);
}
} else {
// 长度相等:全部重叠,右边[i]与左边[k-1-i]相加
for (int i = 0; i < k; ++i) {
folded.push_back(right[i] + left[k - 1 - i]);
}
}
// 检查翻折后是否匹配目标
if (folded.size() == M && folded == target) {
return true;
}
if (!visited.count(folded)) {
visited.insert(folded);
q.push(folded);
}
// 检查翻折后翻转的状态
vector<ll> folded_rev = folded;
reverse(folded_rev.begin(), folded_rev.end());
if (folded_rev.size() == M && folded_rev == target) {
return true;
}
if (!visited.count(folded_rev)) {
visited.insert(folded_rev);
q.push(folded_rev);
}
}
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 0;
int N;
while (t < 5 && cin >> N) {
t++;
vector<ll> initial(N);
for (int i = 0; i < N; ++i) {
cin >> initial[i];
}
int M;
cin >> M;
vector<ll> target(M);
for (int i = 0; i < M; ++i) {
cin >> target[i];
}
cout << (canTransform(initial, N, target, M) ? "S" : "N") << '\n';
}
return 0;
}
这里空空如也
有帮助,赞一个