这一场是真刺激，B题卡了半天搞了个假算法，C,D猜的结论。结果B题fst了，C,D竟然都猜对了，然而三道题还是掉分了……

A Subsequence Permutation

水题。排序即可。

B Running for Gold

记\(t_i < t_j\)表示\(i\)比\(j\)优。这题关键在于，如果\(t_i < t_j\)，\(i\)可能是夺金，而\(j\)必不可能夺金。

所以我们动态维护一个“可能夺金”的人\(x\)，初始令\(x=1\)，并依次和\(2 \sim n\)比较：如果\(t_x<t_i\)，保持不变，否则令\(x=i\)。因为在\(i\)之前有机会夺金的人只有\(x\)，而现在\(t_i<t_x\)，那么当前可能夺金的人就只有\(i\)了。

这样扫到\(n\)，最后再循环一次判断\(x\)是否能真正夺金即可。时间复杂度\(O(n)\).

关键代码：

struct Node
{
	int r[6];
	In bool operator < (const Node& oth)const
	{
		int cnt = 0;
		for(int i = 1; i <= 5; ++i) cnt += r[i] < oth.r[i];
		return cnt >= 3;
	}
}t[maxn];

In int solve()
{
	int x = 1;
	for(int i = 1; i <= n; ++i)
		if(t[i] < t[x]) x = i;
	for(int i = 1; i <= n; ++i) 
		if(i != x && t[i] < t[x]) return -1;
	return x;
}

C Maximize the Intersections

这题官方题解比我讲的明白多了，而且代码更为简单，我只是阐明一个大题思路。

首先我结论是猜对了：对于剩下的\(n-K\)个“新弦”和空着的\(2(n-K)\)个点，第\(i\)条弦的左端点连接第\(i\)个点，右端点连接第\(i+n-K\)个点，交点最多。

首先这样构造一定能保证剩下的\(n-K\)个点两两相交。

至于为什么和固定的“旧弦”的相交个数加起来也最多，按题解我是这么理解的：交换两条“新弦”不会改变这两条弦和其他弦相交的点的个数（自然就包括“旧弦”），因此新弦之间的连接不会对旧弦产生影响。

至于代码，我写的挺烂，题解的更好。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<queue>
#include<assert.h>
#include<ctime>
using namespace std;
#define enter puts("") 
#define space putchar(‘ ‘)
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
#define forE(i, x, y) for(int i = head[x], y; ~i && (y = e[i].to); i = e[i].nxt)
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 1005;
In ll read()
{
	ll ans = 0;
	char ch = getchar(), las = ‘ ‘;
	while(!isdigit(ch)) las = ch, ch = getchar();
	while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - ‘0‘, ch = getchar();
	if(las == ‘-‘) ans = -ans;
	return ans;
}
In void write(ll x)
{
	if(x < 0) x = -x, putchar(‘-‘);
	if(x >= 10) write(x / 10);
	putchar(x % 10 + ‘0‘);
}
int n, K, m;
struct Node
{
	int L, R;
}t[maxn];

int vis[maxn << 1];
int vis2[maxn];
In void calc(int x)
{
	int L = 1, R = 0, cnt = 0;
	while(vis[L]) ++L;
	for(int i = L + 1; i <= m; ++i)
		if(!vis[i])
		{
			++cnt;
			if(cnt == n - x + 1) {R = i; break;}
		}
	vis[L] = vis[R] = x;
	t[x] = (Node){L, R};
}

In int solve()
{
	for(int i = K + 1; i <= n; ++i) calc(i);
	int ret = 0;
	for(int i = 1; i <= n; ++i)
		for(int j = i + 1; j <= n; ++j)
			if((t[i].L < t[j].L && t[i].R < t[j].R && t[i].R > t[j].L) || (t[j].L < t[i].L && t[j].R < t[i].R && t[j].R > t[i].L))
				 ++ret;
	return ret;
}

int main()
{
	int T = read();
	while(T--)
	{
		n = read(), K = read();
		m = n * 2;
		fill(vis + 1, vis + m + 1, 0);
		fill(vis2 + 1, vis2 + n + 1, 0);
		for(int i = 1; i <= K; ++i)
		{
			int L = read(), R = read();
			if(L > R) swap(L, R);
			t[i] = (Node){L, R};
			vis[L] = vis[R] = i;
		}
		write(solve()), enter;
	}
	return 0;
}

题解的写法是先把\(2(n-K)\)个空点按顺序找出来，那么可以直接\(O(n)\)为弦分配点了，而不用想我每次现找。

D Array Differentiation

哈哈，这题的结论我竟然也猜出来了。

正确的思路是这样的：对于\(a_i=b_j-b_k\)，想成图上的一条边\(j \to k\)，同时也就有\(k \to j\)表示\(-a_i\)。

那么\(n\)个点\(n\)条边，必然至少有一个环。而把这个环的边顺序依次加起来，就得到了\(b_{t_1}-b_{t_2}+b_{t_2}-b_{t_3}+\cdots+b_{t_{m-1}}-b_{t_m}+b_{t_m}-b_{t_1}=0\)，即\(\sum\limits_{i=1}^m s_ia_{t_i}=0,s_i \in \{-1, 1\}\).

而对于环外的点，我们根据前驱就能确定剩下的\(b_k\).

因此，存在合法序列\(b\)满足题意\(\Rightarrow\) 存在集合\(t\)，满足\(\sum\limits_{i=1}^m s_i a_{t_i}=0\).

实际上，这是一个等价命题，下面证明他的必要性：
还是将条件\(\sum\limits_{i=1}^m s_i a_{t_i}=0\)看成环，令\(b_{t_1}=0\)，那么对于环内的\(b_{t_i}\)，可以构造\(b_{t_{i+1}}=b_{t_i}+s_ia_{t_i}\)，而对于环外的点，直接令\(b_k=a_k\)即可。至此就构造出了合法的序列\(b\).

证毕。

那么代码就十分好写了，直接\(O(3^n)\)枚举\(a_i\)不选，还是选\(a_i,-a_i\)即可。

主要代码：

bool dfs(int now, int cnt, int sum)
{
	if(cnt && !sum) return 1;
	if(now > n) return 0;
	if(dfs(now + 1, cnt, sum)) return 1;
	if(dfs(now + 1, cnt + 1, sum + a[now])) return 1;
	if(dfs(now + 1, cnt + 1, sum  - a[now])) return 1;
	return 0;
}

int main()
{
	int T = read();
	while(T--)
	{
		n = read();
		for(int i = 1; i <= n; ++i) a[i] = read();
		puts(dfs(1, 0, 0) ? "YES" : "NO");
	}
	return 0;
}

然后比赛的时候我是怎么猜这个结论的呢，我令\(a_i=b_1-b_{i+1}(i<n)\)，然后再\(O(n^2)\)枚举\(a_n\)是否可行，但其实把\(a_n=b_j-b_k\)的\(b_j,b_k\)用\(a_i\)表示，会发现问题就变成了是否存在\(x,y\)，满足\(a_n=a_x-a_y\).但这样显然是不对的，于是最后我就大胆推断，能否有\(a_n=\sum\limits_{i=1}^m s_ia_{t_i}(s_i \in \{-1, 1\})\).然后对于每一个\(a_i\)都作为\(a_n\)判断一次。

会发现，我这个式子移项后就和题解式子一样啦……

?