题解：UVA10364 Square

题目

我们要判断给定的

N

根木棍是否能够围成一个正方形。

思路

拼成正方形要四条边长度相等，应为木棍的长度为整数，那么木棍的总长必须被 $4$ 整除。
木棍的长度不能超过边长，不然这个木棍就放不了。
运用回溯算法将每根木棍分配到正方形的四条边中。由于可能存在多种分配方式，我们使用回溯算法来遍历所有可能的分配情况，当发现当前的分配方式不合法，就回溯到上一步，尝试其他的分配方式，直到找到一种可以围成正方形的分配方式或者遍历完所有可能的组合。

回溯

分配可以用回溯解决，可是容易发现，单纯的回溯会超时，需要剪枝。

回溯过程中会重复尝试相同长度的木棍，如果有根木棍无法拼接到某条边上，那和它长度相同的木棍也不能拼接。所以遇到长度相同的木棍，直接跳过。
将木棍按长度从长到短排序，这样可以优先选长的木棍拼。
如果边长为 $0$ ，且加入长度为 $a_i$ 的木棍不符合，直接返回。

代码

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t;
int n;
int sum;
int a[21];

bool flag;// 初始值0。
bool v[21];
void dfs(int x, int y, int z) {
    if (flag == 1) {// 找到了方案，即 flag 为 1，返回。
        return;
    }
    if (x == 5) {
        flag = 1;
        return;
    }
    if (y == sum) {// 已构建完，开始建下一条边。
        dfs(x + 1, 0, 0);
    }
    for (int i = z + 1; i <= n; i++) {
        
        if (v[i] == 0 && y + a[i] <= sum) {// 如果第 i 根木棍还未被使用并加入后不会超过目标长度。
            v[i] = 1;
            dfs(x, y + a[i], i);
            v[i] = 0;
        }
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while (t--) {
        cin >> n;
        sum = 0;
        flag = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            sum += a[i];
        }
        if (sum % 4 != 0) {//总长不能能被 4 整除。
            cout << "no";
        }
        else {
            sum /= 4;
            bool f = 0;
            for (int i = 1; i <= n; i++) {
                if (a[i] > sum) {
                    f = 1;
                    break;
                }
            }
            if (f) {
                cout << "no";
            }
            else {
                for (int i = 1; i <= n; i++) {
                    v[i] = 0;
                }
                dfs(1, 0, 1);
                if (flag) {//找到了。
                    cout << "yes";
                }
                else {
                    cout << "no";
                }
            }
        }
        cout << endl;
    }
    return 0;
}

题解：UVA10364 Square

文章操作

题目

思路

回溯

代码

相关推荐

评论

题解：UVA10364 Square