先總結一下，

A竟然想了 5 5 5分鐘，同機房的人都切掉了之后才開始做，

B因為RE錯了 2 2 2次，罰了許多分；主要是看到 W A WA WA，以為思路錯了，事實上是陣列開笑了，

C想了半天，無果，開 D D D，切掉，

然后回到 C C C，一個同機房的巨佬做出來之后，全機房的人問他怎么做；結果啥也沒聽懂，比賽結束后才恍然大悟，

用了自己的一個 636 636 636分的，才打一場的灰名小號打，應該能上分吧……

Solution

A

對于每一對 ( i , j ) (i,j) (i,j)，配上 ( j , ? i ) (j,-i) (j,?i)即可，

B

開桶記錄，亂搞即可，

C

首先，我加強一下資料: 可能有 m m m個琴弦， m ≤ 100000 m≤100000 m≤100000，

我們考慮貪心，首先，為了將可選的方案數量大幅減少，我們將這兩個陣列分別減去它們各自的最小值，可以發現，對于 b b b中的一個數 k k k，要么選擇 a a a中 k k k的前驅，要么選擇后驅，這可以用決策包容性來證明，

于是，我們在對 a a a排序后，對于 b b b中的每一個數通過二分找到 a a a中它的前驅與后驅，記 c i c_i ci?表示 b i ? a j b_i-a_j bi??aj?， d i d_i di?表示 b i ? a k b_i-a_k bi??ak?，其中 a j a_j aj?為 a a a中 b i b_i bi?的前驅， a k a_k ak?為 a a a中 b j b_j bj?的后驅，

我們將 c c c從小到大排序，同時使 c c c中的值與 d d d中的值相對應，可以發現，對于每一個位置的配對，決策在 c c c或 d d d中；并且在最優解中，一定是前面一段先選擇了 c c c，后選擇了 d d d，

我們列舉這個位置，使得在這個位置及其之前選擇了 c c c，后面選擇了 d d d，即這個位置為差的最大值，至于差的最小值，為后面選擇的 d d d中的最小值，可以通過預處理后綴最小值來 O ( 1 ) O(1) O(1)查詢，我們求出每一對的差的最大值減去最小值，然后取 m i n min min即可，

總時間復雜度 O ( n ( l o g n + l o g m ) + m l o g m ) O(n(logn+logm)+mlogm) O(n(logn+logm)+mlogm)，

花絮: 一位機房巨佬Guess00賽時把這題切了，我們一起膜拜他吧！ orz

D

一道水的構造題，

我們從后往前掃一遍，維護一個堆，記錄下當前掃到的物品的從小到大排序的結果；每次取出堆頂作為當前這一次放進去的物品價值，并繼續向前掃，

最后，我們再用相同的方式，使用一個堆，從前往后掃一遍，用來判斷我們這種構造方案是否可行，如果可行直接輸出方案，否則輸出 ? 1 -1 ?1，

時間復雜度 O ( n l o g n ) O(nlogn) O(nlogn)，注意陣列開大，

Code

A

#include <bits/stdc++.h>
#define int long long
using namespace std;

int t,n;
int a[200005];

signed main()
{
	cin>>t;
	while (t--)
	{
		cin>>n;
		for (int i=1;i<=n;i++)  cin>>a[i];
		for (int i=1;i<=n;i++)
		{
			if (i%2==1)  cout<<a[i+1]<<' ';
			else cout<<-a[i-1]<<' ';
		}
		cout<<endl;
	}
	return 0;
}

B

#include <bits/stdc++.h>
#define int long long
using namespace std;

int t,n,m,x;
int a[1005][1005],v[1000005],num[1000005],ans[1005][1005];

signed main()
{
	cin>>t;
	while (t--)
	{
		cin>>n>>m;
		for (int i=1;i<=n*m;i++)  v[i]=num[i]=0;
		for (int i=1;i<=n;i++)
		{
			for (int j=1;j<=m;j++)  ans[i][j]=0;
		}
		for (int i=1;i<=n;i++)
		{
			cin>>a[i][1];
			v[a[i][1]]=i;
			for (int j=2;j<=m;j++)  cin>>a[i][j];
		}
		for (int i=1;i<=m;i++)
		{
			for (int j=1;j<=n;j++)
			{
				cin>>x;
				num[v[x]]=j;
			}
		}
		for (int i=1;i<=n;i++)
		{
			for (int j=1;j<=m;j++)  ans[num[i]][j]=a[i][j];
		}
		for (int i=1;i<=n;i++)
		{
			for (int j=1;j<=m;j++)  cout<<ans[i][j]<<' ';
			cout<<endl;
		}
	}
	return 0;
}

C

//by gh
#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#define DEBUG cerr << "Passing Line " << __LINE__<< " in Function [" << __FUNCTION__ << "].\n";
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int INF = 0x3f3f3f3f;
const ll llINF = 1e18;
const int MAXN = 1e5 + 5;
const int MAXM = 10;
const int m = 6;

int n;
int a[MAXN],b[MAXN],suf[MAXN];
pii c[MAXN];

int main(){
    // freopen("data.in","r",stdin);
    // freopen("data.out","w",stdout);
    for(int i = 1;i <= m;i++)
        scanf("%d",&a[i]);
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
        scanf("%d",&b[i]);
    sort(a + 1,a + 1 + m);
    sort(b + 1,b + 1 + n);
    for(int i = 2;i <= m;i++)
        a[i] -= a[1];
    a[1] = 0;
    for(int i = 2;i <= n;i++)
        b[i] -= b[1];
    b[1] = 0;
    for(int i = 1;i <= n;i++){
        int x = upper_bound(a + 1,a + 1 + m,b[i]) - a - 1;
        c[i].first = b[i] - a[x];
        x = lower_bound(a + 1,a + 1 + m,b[i]) - a;
        if(x == m + 1)
            c[i].second = -INF;
        else
            c[i].second = b[i] - a[x];
    }
    sort(c + 1,c + 1 + n);
    int ans = INF;
    suf[n] = c[n].second;
    for(int i = n - 1;i >= 1;i--)
        suf[i] = min(suf[i + 1],c[i].second);
    for(int i = 1;i <= n;i++)
        ans = min(ans,c[i].first - suf[i + 1]);
    printf("%d\n",ans);
    return 0;
}

D

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n,pos=0,a[200005];

struct node
{
	char x;
	int num;
}tmp[200005];

signed main()
{
	cin>>n;
	for (int i=1;i<=2*n;i++)
	{
		cin>>tmp[i].x;
		if (tmp[i].x=='-')  cin>>tmp[i].num;
	}
	priority_queue<int,vector<int>,greater<int> > q;
	for (int i=2*n;i>=1;i--)
	{
		if (tmp[i].x=='-')
		{
			int now=tmp[i].num;
			q.push(now);
		}
		else
		{
			int x=q.top();
			a[i]=x;
			q.pop();
		}
	}
	for (int i=1;i<=2*n;i++)
	{
		if (tmp[i].x=='+')
		{
			int now=tmp[i].num;
			q.push(now);
		}
		else
		{
			int x=q.top();
			if (tmp[i].num!=x)  return cout<<"NO"<<endl,0;
			q.pop();
		}
	}
	cout<<"YES"<<endl;
	for (int i=1;i<=2*n;i++)
	{
		if (a[i])  cout<<a[i]<<' ';
	}
	cout<<endl;
	
	return 0;
}