题解 UVA10125 【Sumsets】

首先将式子变形成$a+b=d-c$ 接下就可以$O(n^2)$枚举$a+b$，并用$hash$记录下来，再$O(n^2)$枚举判断是否存在合法的$d,c$使得$d-c=a+b$ 如果用$map$时间复杂度会有点爆炸 但强大的$STL$里其实还有一个容器叫$unordered\_map$ 它是用$hash$实现的$map$，可以实现$O(1)$查询 头文件为$unordered\_map$ 不过它是$C++11$的新特性，$NOIP$应该无法使用。 ```cpp #include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <unordered_map> #define LL long long using namespace std; LL read() { int k = 0, f = 1; char c = getchar(); while(c < '0' || c > '9'){ if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') k = k*10+c-48, c=getchar(); return k*f; } struct zzz { int p1, p2; bool x; }; unordered_map <LL,zzz> q; LL a[1010]; void solve() { LL n = read(), ans = -0x7fffffff; q.clear(); if(!n) exit(0); for(int i = 1; i <= n; ++i) a[i] = read(); sort(a+1, a+n+1); for(int i = 1; i <= n; ++i) for(int j = 1; j < i; ++j) q[a[i]+a[j]].x = 1, q[a[i]+a[j]].p1=i, q[a[i]+a[j]].p2=j; for(int i = 1; i <= n; ++i) for(int j = 1; j < i; ++j) if(q[a[i]-a[j]].x && q[a[i]-a[j]].p1 != i && q[a[i]-a[j]].p2 != j && q[a[i]-a[j]].p1 != j && q[a[i]-a[j]].p2 != i) ans = max(ans, a[i]); //a,b,c,d要为不同元素 if(ans!=-0x7fffffff) printf("%d\n",ans); else printf("no solution\n"); } int main() { while(1) solve(); return 0; } ```