UVA10125 Sumsets 题解

sun_qy · 2024-01-16 21:34:51 · 题解

UVA10125 Sumsets 题解

洛谷原题链接

老师刚讲完，写篇题解理一下思路。

题意简述

题意其实很明确，给定一个集合 S，寻找其中的四个元素 a,b,c,d 使得 a+b+c=d 且这四个数两两互异，求出 d 的最大值。

思路

对于等式 a+b+c=d，直接枚举肯定会 TLE 飞，考虑将其变形为 a+b=d-c 的形式以便于映射，通过链表的方式进行处理。

首先，对于链表中的每一个元素，考虑定义一个结构体以存储 d,c 的值。另外对于每个元素可以建立一个权值的概念，用以存储 d-c 即其对应 a+b 的值，一会儿用于枚举。对于链表的储存，可以用哈希的小技巧。

//链表的建立
int head[MOD];
struct node {
    int key, d, c;
    int nxt;
};
inline int hashe(int x) {
    return ((x % MOD) + MOD) % MOD;
}
node lis[MOD];

接着将储存答案的变量初始化为给定的最小值 -536870912，对于多组数据要清空。

//初始化
int n, a[N], cnt, ans;
inline void init() {
    cnt = 0;
    ans = -536870912;
    memset(head, 0, sizeof(head));
}

接下来用上刚写的链表来维护所有的 d-c。有个细节，由于减法不具有交换律，内层循环应采取从 j=1 开始，当 i=j 的时候跳过本次循环的处理方式。

//数据写入
for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= n; j ++) {
        if(i == j) continue;
        lis[++ cnt] = {a[i] - a[j], a[i], a[j], head[hashe(a[i] - a[j])]};
        head[hashe(a[i] - a[j])] = cnt;
    }
}

接下来遍历链表寻找符合条件的 a+b，打擂台找到最大的 d 即可。注意：这里的 a,b,c,d 两两互异，应做出判断。

for(int i = 1; i <= n; i ++) {
    for(int j = i + 1; j <= n; j ++) {
        if(!head[hashe(a[i] + a[j])]) continue;
        for(int x = head[hashe(a[i] + a[j])]; x; x = lis[x].nxt) {
            if(lis[x].key != a[i] + a[j]) continue;
            if(lis[x].d == a[i] || lis[x].c == a[i] || lis[x].d == a[j] || lis[x].c == a[j]) continue;
            ans = max(ans, lis[x].d);
        }
    }
}

最后输出答案即可，时间复杂度 O(Tn^2)，能过。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1002, MOD = 1000007;
int n, a[N], cnt, ans;
int head[MOD];
struct node {
    int key, d, c;
    int nxt;
};
inline int hashe(int x) {
    return ((x % MOD) + MOD) % MOD;
}
node lis[MOD];
inline void init() {
    cnt = 0;
    ans = -536870912;
    memset(head, 0, sizeof(head));
}
signed main() {
    ios :: sync_with_stdio(0), cin.tie(0);
    while(cin >> n && n) {
        init();
        for(int i = 1; i <= n; i ++) cin >> a[i];
        for(int i = 1; i <= n; i ++) {
            for(int j = 1; j <= n; j ++) {
                if(i == j) continue;
                lis[++ cnt] = {a[i] - a[j], a[i], a[j], head[hashe(a[i] - a[j])]};
                head[hashe(a[i] - a[j])] = cnt;
            }
        }
        for(int i = 1; i <= n; i ++) {
            for(int j = i + 1; j <= n; j ++) {
                if(!head[hashe(a[i] + a[j])]) continue;
                for(int x = head[hashe(a[i] + a[j])]; x; x = lis[x].nxt) {
                    if(lis[x].key != a[i] + a[j]) continue;
                    if(lis[x].d == a[i] || lis[x].c == a[i] || lis[x].d == a[j] || lis[x].c == a[j]) continue;
                    ans = max(ans, lis[x].d);
                }
            }
        }
        if(ans == -536870912) printf("no solution\n");
        else printf("%d\n", ans);
    }
    return 0;
}