A ~ D 懒得写。
不是因为题不好，其实我觉得做起来非常舒适。但就是懒得写了（
E - House Planning
\(d_1,d_2\) 全打乱感觉很难。先看看不打乱怎么做。
对于每个 \(i\)，我们知道 \(d_{1,i}=|p_1-h_i|\) 和 \(d_{2,i}=|p_2-h_i|\) 。
容易发现 \(x=|p_1-p_2|\) 是个关键的量，它一定与 \(d_{1,i}+d_{2,i}\) 或 \(|d_{1,i}-d_{2,i}|\) 相等。
用 \(i=1\) 找到 \(x\) 的两个可能值，然后用 \(i=2\sim n\) 验证。非常 easy 啊。
回到原题，\(d_1,d_2\) 都是打乱的。
那么 \(d_{1,1}\) 在 \(d_2\) 中对应的元素有 \(n\) 种可能，因此 \(x\) 有 \(2n\) 个可能值。
现在的问题是，对于一个 \(x\) 的可能值，如何进行验证。
赛时想法：二分图匹配大力艹。
然而我甚至已经忘记二分图匹配怎么写了。大寄特寄。
感觉自己很傻逼。
赛后看题解，发现正解做法要简洁得多：
考虑 \(d_1,d_2\) 中最大的元素 \(t\) 。
由于 \(d_1,d_2\) 中没有 \(t+x\) 这个元素，因此 \(t\) 只能匹配到 \(|t-x|\) 。
如果也没有 \(|t-x|\) ，就寄了。否则重复上述步骤，直到所有元素都匹配完。
时间复杂度 \(O(n^2\log n)\) 。
感觉自己非常傻逼。
View Code
#include<stdio.h>
#include<queue>
#include<map>
#define rep(i,l,r) for (int i=l; i<=r; ++i)
const int N=1005;
int T,n,m,x,f,mn,d1[N],d2[N],p[N];
std::map<int,int>v1,v2;
struct Node { int i,x; };
bool operator < (Node p,Node q) { return p.x<q.x; }
std::priority_queue<Node>Q;
inline int abs(int x) { return x>0?x:-x; }
inline int min(int x,int y) { return x<y?x:y; }
bool check() {
m=0,v1.clear(),v2.clear();
while (!Q.empty()) Q.pop();
rep(i,1,n) {
++v1[d1[i]],Q.push({1,d1[i]});
++v2[d2[i]],Q.push({2,d2[i]});
}
while (!Q.empty()) {
Node q=Q.top(); Q.pop();
if (q.i==1) {
if (!v1[q.x]) continue; --v1[q.x];
int &t=v2[abs(q.x-x)];
if (!t) return 0; --t,p[++m]=q.x;
}
else {
if (!v2[q.x]) continue; --v2[q.x];
int &t=v1[abs(q.x-x)];
if (!t) return 0; --t,p[++m]=x-q.x;
}
}
return 1;
}
int main() {
scanf("%d",&T);
while (T--) {
scanf("%d",&n),f=0;
rep(i,1,n) scanf("%d",d1+i);
rep(i,1,n) scanf("%d",d2+i);
rep(i,1,n) {
x=d1[1]+d2[i];
if (check()) { f=1; break; }
x=abs(d1[1]-d2[i]);
if (check()) { f=1; break; }
}
if (!f) { puts("NO"); continue; }
puts("YES"),mn=0;
for (int i=1; i<=n; ++i)
mn=min(mn,p[i]);
for (int i=1; i<=n; ++i)
printf("%d ",p[i]-mn);
printf("\n%d %d\n",-mn,x-mn);
}
return 0;
}