P1286の题解

aaron0919 · 2023-08-13 21:07:28 · 题解

P1286の题解

本人第一篇题解！！就崩溃了。。。终于找到能发的了

有一点说一下，题目中分号没用 \dfrac{n(n-1)}{2}，用的 \frac{n(n-1)}{2}，一行里扁扁的看不下去！！！

题目描述

给定 n，和 a_1+a_2,\ a_1+a_3,\dots \ a_1+a_n,\ a_2+a_3,\ a_2+a_4,\dots,\ a_2+a_n,\dots\ a_{n-1}+a_n 求 a_1,\ \dots,\ a_n（多组数据）。

打 Latex 手废了。

贴张图（来自@YudeS）

数学分析

理性分析：尝试打表找规律

设输入为 ans_1 + ans_2,\ \dots\ ,ans_{n-1}+ans_n，即 a_1,\ a_2,\ \dots,\ a_n。

输入 a_1,\ a_2,\ a_3，你是不是很快就能知道：

则

只求 ans_1 的话

输入 a_1,\ a_2,\ a_3,\ a_4,\ a_5,\ a_6，你是不是依然很快就能知道：

则...

停！这里是四个数的和，而题目给的是两个数，并不能直接求出来，是吧？

怎么可能是呢，干嘛要先求四个数，直接求三个数不就行了吗？

再接着，求出第一个数，ans_2,\ ans_3,\ ans_4 就能通过 a_1,\ a_2,\ a_3 直接求出来。

注意，a_1,\ a_2,\ \dots 是不固定的，要枚举所有可能。

好的，打 Latex 手又废了。

分析完毕，分析结果：我找不到规律，暴力即可。（要不然要 n < 10 干嘛，10 都不包括）

程序实现

主题框架

1. 枚举 ans_1。
2. 计算出 ans_2,\ ans_3。
3. 用搜索枚举 ans_k = a_i - ans_1。

细节

1. 输入时判断所有数的和是否为 n - 1 的倍数（可以从我辛辛苦苦打的公式那证明，证明略），如果不是，那就 dream it possible（在梦中成立）。
2. 判断合法的方式，选择 ans_i 的时候判断是否有 ans_i + ans_j = a_k，没有就不合法。

code

AC code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, flag;
int ans[20], a[200];
map<int, int> vis; // 谁告诉 you 每个数不重复

bool check(int num, int k) // 检查是否合法，二分的感觉
{
    for (int i = 1; i < k; i++)
    {
        if (!vis[num + ans[i]])
        {
            return false;
        }
    }
    return true;
}

void dfs(int k, int s) // 已枚举到完 ans_{k-1}，上一个合法的是到 a_s
{
    if (k > n) // 枚举完输出
    {
        for (int i = 1; i <= n; i++)
        {
            printf("%d ", ans[i]);
        }
        printf("\n");
        flag = 1;
        return;
    }
    for (int i = s; i <= n * (n - 1) / 2; i++) // 枚举 ans_k
    {
        if (check(a[i] - ans[1], k))
        {
            ans[k] = a[i] - ans[1]; // 求出 ans_k

            for (int j = 1; j < k; j++) // 不知道叫什么
            {
                vis[ans[k] + ans[j]]--;
            }

            dfs(k + 1, i + 1); // 递归

            if (flag) // 找到就退出
            {
                return;
            }
            for (int j = 1; j < k; j++) // 回溯
            {
                vis[ans[k] + ans[j]]++;
            }
        }
    }
}
int main()
{
    while (scanf("%d", &n) == 1) // 等价于 ~ 和 != EOF
    {
        flag = 0; // 重置
        int sum = 0;
        vis.clear();
        for (int i = 1; i <= n * (n - 1) >> 1; i++) // 数入
        {
            scanf("%d", &a[i]);
            sum += a[i];
            vis[a[i]]++;
        }
        if (sum % (n - 1)) // 判断无解
        {
            printf("Dream it possible\n");
            continue;
        }
        sort(a + 1, a + 1 + n * (n - 1) / 2);
        for (int i = 0; a[1] - i > i; i++) // 枚举第一个数
        {
            ans[1] = i;
            ans[2] = a[1] - i;
            ans[3] = a[2] - i;
            vis[a[1]]--;
            vis[a[2]]--;
            if (vis[ans[2] + ans[3]])
            {
                vis[ans[2] + ans[3]]--;

                dfs(4, 3); // 已经选出前三个了，选第四个

                if (flag) // 已找到
                {
                    break;
                }
                vis[ans[2] + ans[3]]++;
            }
            vis[a[1]]++;
            vis[a[2]]++;
        }
        if (!flag) // 没找到，好强的数据
        {
            printf("Dream it possible\n");
            continue;
        }
    }
    return 0;
}

鸣谢

1. 让我少打了亿点点 \LaTeX 的 @YudeS。
2. 给我没通过的审核，但提出了宝贵的标点符号建议 @swiftc。
3. 给我没通过的审核，但给出了宝贵的标题建议 @CSP_Sept。
4. 给我没通过的审核，但给出了宝贵的标题建议 @_maze。
5. 给我没通过的审核，但给出了宝贵的标点符号建议 @蒟蒻君HJT
6. 给我没通过的审核，但给出了宝贵的行号建议 @_maze

鸣谢这么多应该能过了