求各位佬看看 卡 3 4 8了!
查看原帖
求各位佬看看 卡 3 4 8了!
813227
Hunter19019楼主2022/12/4 17:22
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[45];
int b[12];
int s;
bool flag = false;
inline bool judge()
{
    for(int i = 1; i <= n - 1; i++)
        for(int j = i + 1; j <= n; j++)
        {
            if(!binary_search(a,a+m,b[i] + b[j])) return false;
        }
    return true;
}
void dfs(int cur,int mi,int sum)
{

    if(flag || sum < mi) return;
    if(cur == 2)
    {
        int h = a[0] - b[1];
        b[cur] = h;
        dfs(cur + 1, h,sum - h);
        return;
    }
    if(cur == n)
    {
        b[n] = sum;
        if(a[m - 1] == b[n] + b[n - 1] && judge())
            flag = true;
        return;
    }
    for(int i = 0; i < m; i++)
    {
        b[cur] = a[i] - b[1];
        if(b[cur] < b[cur - 1]) continue;
        if(binary_search(a,a+m,b[2] + b[cur]))
            dfs(cur + 1,b[cur],sum - b[cur]);
        else continue;
        if(flag) return;
    }
    return;
}
int main()
{
    while (scanf("%d",&n)==1){
        s = 0;
        flag = false;
        m = n * (n - 1) >> 1;
        for(int i = 0; i < m; i++) {
            scanf("%d",&a[i]);
            s += a[i];
        }
        if(s % (n - 1) != 0)
            printf("Impossible");
        else {
            s = s / (n - 1);
            sort(a, a + m);
            int q = a[0] >> 1;
            for(int i = 0; i <= q; i++)
            {
                b[1] = i;
                dfs(2,i,s - i);
                if(flag) break;
            }
            if (flag){
                for (int i = 1; i <= n; i++) printf("%d ", b[i]);
            }
            else printf("Impossible");
        }
        printf("\n");
    }
    return 0;
}
2022/12/4 17:22
加载中...