The 2nd Universal Cup. Stage 22: Hangzhou结束了，所以可以把题解扔出来了。

题面：

V-Diagram

长度为 $n$ 的 $1$ -索引整数序列 $a$ 是V-图，如果 $n \ge 3$ 且存在满足以下条件的索引 $i$ （ $1< i < n$ ）：

  • $a_j > a_{j + 1}$ 用于 $1 \le j < i$
  • $a_j > a_{j - 1}$ 为 $i <j \le n$ 。

给定V-图 $a$ ，找出具有最大可能平均值的V-图 $b$ ，使得 $b$ 是 $a$ 的连续子序列。
序列的连续子序列可以通过从序列的开头和结尾移除一些（可能为零）元素来获得。
签到题，题解说二分答案也行，但我做的时候用的是贪心。因为对于一个V图来讲，首先一定要包含最小的那个点，然后就是向左右两边扩展取最大。要求在现行复杂度内通过，所以不能直接暴力解，那么观察性质，由于保证是V图所以这个序列对应的图像的每一段的斜率都大于1，换句话说就是i每次改变1（增加一个数），纵坐标ai变化量至少大于1（加上ai），即$\frac{S+a_i}{len+1}$,S表示选中的ai的总和，len表示选的个数，所以不管怎么样选的ai越大越好,并且在选取的时候试单增的，即每多选一个数，对于平均值一定是有贡献的（糖水不等式）。所以假设一开始只有V图的极小值，S = $a_{minn}$,len = 1，要考虑怎么选增幅最大，由于序列a是V图，那么也就是形如8,6,5,3,1,2,4,5,6,7,10这样的，最好的情况一定是包含了10或8，并且在取10或8的时候一定是取了之前的数，那么就要考虑三种情况：选只包含10的最大V图，也就是选3,1,2,4,5,6,7,10；选只包含8的最大V图，也就是8,6,5,3,1,2；全选,8,6,5,3,1,2,4,5,6,7,10。三者取最大即可。
记得开long long以及使用cout时设置精度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#define int long long
#define N 300005

int n, a[N];

void solve() {
	cin >> n;
	int pos, minn = 1e9 + 7, sum = 0;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		sum += a[i];
		if (minn > a[i]) pos = i, minn = a[i];
	}
	double ans = (double)sum / n;
	sum = 0;
	for (int i = pos - 1; i <= n; ++i) sum += a[i];
	ans = max((double)sum / (n - pos + 2), ans);
	sum = 0;
	for (int i = 1; i <= pos + 1; ++i) sum += a[i];
	ans = max((double)sum / (pos + 1), ans);
	cout << ans << endl;
}

Mysterious Tree

这是一个交互问题。

Randias有一个具有 $n$ 个顶点的未知隐藏树。树要么是链要么是星。

兰迪亚斯现在需要确定树是链还是星。他可以提出以下形式的问题，但不得超过 $\lceil \frac{n}{2} \rceil + 3$ 次：

-顶点 $u$ 和顶点 $v$ （ $1 \le u, v \le n$ ， $u \neq v$ ）之间是否有边？

兰迪亚斯需要确定这棵树是两种中的哪一种。帮助他提出问题并确定答案。

一棵树称为链，当且仅当存在一个置换 $p_{1}, p_{2}, \ldots, p_{n}$ ，使得对于每个 $i$ （ $1 \le i < n$ ），树中都有一条边 $(p_{i}, p_{i + 1})$ 。

这里，长度为 $n$ 的排列是一个数组，其中从 $1$ 到 $n$ 的每个整数恰好出现一次。一棵树称为星当且仅当存在一个顶点 $u$ ，使得每隔一个顶点 $v$ ，树中就有一条边 $(u, v)$ 。

在这个问题中，交互者是自适应的，这意味着秘密树不是事先固定的。

相反，交互者可以在交互期间任意改变树。尽管如此，在每一个时刻，这棵树都会与你得到的所有答案保持一致。

注意只能问$\lceil \frac{n}{2} \rceil + 3$次，研究一下链和菊花图的性质，发现菊花图只有一个点是和所有点全部相连，那么首先需要想办法询问到一条存在的边，不妨询问(1, 2),(3, 4),(5, 6), . . . ,(n − 1, n)，这里还要注意如果n是奇数的话还要再问一次(n,1)是不是存在边才能完全保证问完全。如果全都不存在，则必然不是菊花。
现在假设存在的边是 (u, v)，我们需要在至多三次询问内确定是链还是菊花。
因为我们找到了一条已经确定存在的边，假设这个图是菊花图，那么可以找两个不同的点，设为p1,p2。
先问一遍p1和u。
如果有，说明如果是菊花图只有u才有可能是菊花中心，再问p2和u，如果也有那么一定是菊花图，如果没有，那么说明只能是链图因为u已经度是2了如果是菊花图u结点是不可能度为2的。
如果没有，那只能说明u不可能是菊花图的中心。
然后问p1和v，同问p1和u的处理方式判断是菊花图还是链图。这种情况是问的次数最多的，刚好用完。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
void solve() {
	cin >> n;
	int u, v;
	auto output = [&](int x, int y) -> void{cout << "? " << x << ' ' << y << endl << endl;};
	bool flag = false;
	for (int i = 2, input; i <= n; i += 2) {
		output(i - 1, i);
		cin >> input;
		if (input) {
			u = i - 1, v = i;
			flag = true;
			break;
		}
	}
	if (n & 1) {
		output(1, n);
		int input;
		cin >> input;
		if (input) {
			u  = 1, v = n;
			flag = true;
		}
	}
	if (flag) {
		int p1 = 0, p2 = 0;
		for (int i = 1; i <= n; ++i) {
			if (i == u || i == v) continue;
			if (p1) {
				p2 = i;
				break;
			} else p1 = i;
		}
		output(p1, u);
		int st;
		cin >> st;
		if (st) {
			output(p2, u);
			cin >> st;
			if (st) cout << "! " << 2 << endl << endl;
			else cout << "! " << 1 << endl << endl;
		} else {
			output(p1, v);
			cin >> st;
			if (st) {
				output(p2, v);
				cin >> st;
				if (st) cout << "! " << 2 << endl << endl;
				else cout << "! " << 1 << endl << endl;
			} else cout << "! " << 1 << endl << endl;
		}
	} else cout << "! " << 1 << endl << endl;
}

Operator Precedence

构造满足等式$\sum_{i=1}^{n} a_{2 i-1} a_{2 i}=a_{1} a_{2 n} \prod_{i=2}^{n}\left(a_{2 i-2}+a_{2 i-1}\right) \neq 0 .$的序列。
被样例误导了，没想明白怎么构造，但是打完表之后就找到了规律，打表代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
int a[N];
const int n = 7;

bool check(){
	int res1 = 0,res2 = 1;
	for(int i = 1;i<=2*n;i+=2){
		res1 += a[i]*a[i+1];
	}
	for(int i = 2;i<2*n;i+=2){//1 2 3 4 5 6
		res2 *= (a[i]+a[i+1]);
	}
	return res1 == res2;
}

void solve() {
	a[1] = a[n * 2] = 1;
	for (int i = 1; i <= 30; ++i) {
		a[2] = a[2 * n - 1] = -i;
		for (int j = 1; j <= 30; ++j) {
			a[3] = a[2 * n - 2] = j;
			for (int k = 1; k <= 30; ++k) {
				a[4] = a[2 * n - 3] = -k;
				for (int l = 1; l <= 30; ++l) {
					a[5] = a[2 * n - 4] = l;
					for (int o = 1; o <= 30; ++o) {
						a[6] = a[2 * n - 5] = -o;
						for (int p = 1; p <= 30; ++p) {
							a[7] = a[n * 2 - 6] = p;
							if(check()){
								for(int i1 = 1;i1<=2*n;++i1){
									cout<<a[i1]<<' ';
								}
								cout<<endl;
							}
						}
					}
				}
			}
		}
	}
}

n = 7的大概长这样，然后把前几位的拉出来看了下

1
2
3
4
5
6
7
8
9
10
9: 1 -2 1 -2 1 -2 1 -2 5 5 -2 1 -2 1 -2 1 -2 1
7: 1 -2 1 -2 1 -2 4 4 -2 1 -2 1 -2 1 
5: 1 -2 1 -2 3 3 -2 1 -2 1 
3: 1 -2 2 2 -2 1

10: 1 -1 2 -1 2 -1 2 -1 3 -7 -7 3 -1 2 -1 2 -1 2 -1 1
8: 1 -1 2 -1 2 -1 3 -5 -5 3 -1 2 -1 2 -1 1
6: 1 -1 2 -1 3 -3 -3 3 -1 2 -1 1
4: 1 -1 3 -1 -1 3 -1 1 
2: 1 -1 -1 1

然后规律就比较明显了。其实还是复杂了，按照官方题解的构造方法是 考虑到乘法不能乘得太大，那么可以构造类似 x, 2, −1, 2, −1, · · · , 2, −1, y 的序列, 令 y = 1 解出 x 即可。

1
2
3
4
5
6
7
8
void solve() {
	cin >> n;
	if (n == 3)
		return cout << "1 -10 6 6 -10 1" << endl, void();
	cout << 1 << ' ';
	for (int i = 2; i <= 2 * n - 1; i += 2) cout << 2 << ' ' << -1 << ' ';
	cout << (2 - 2 * (n - 2)) / 2 << endl;
}

Snake Move

Putata 正在他的笔记本电脑上玩一个著名的蛇形游戏，一条蛇在大小为 $n \times m$ 的网格上移动。网格的某些单元格中可能有障碍物。蛇可以用一串坐标对来表示，这些坐标对决定了蛇身体的位置： $(x_1, y_1), (x_2, y_2), \ldots, (x_k, y_k)$ .这里， $k$ 表示蛇的长度。蛇头位于 $(x_1, y_1)$ ，蛇尾位于 $(x_k, y_k)$ ，蛇身的相邻部分位于共用一条边的单元格中。
在这个游戏中，蛇被编程为一系列以字符串表示的命令。您可以使用 5 种命令：

  • ‘L’:命令小蛇向左移动一步。蛇头将移动到 $(x_1, y_1 - 1)$ 。
  • ‘R’:命令蛇向右移动一步。蛇头将移动到 $(x_1, y_1 + 1)$ 处。
  • ‘U’:命令蛇向上移动一步。蛇头将移动到 $(x_1 - 1, y_1)$ 处。
  • ‘D’:命令蛇向下移动一步。蛇头将移动到 $(x_1 + 1, y_1)$ 处。
  • ‘S’:将蛇的长度缩短一步。蛇身的尾部将被删除。长度将变为 $k - 1$ 。注意，当 $k = 1$ 时无法执行此操作。

当蛇头移动时，蛇身的每个部分也会相应移动。具体来说，身体的第 $i$ 部分（ $2 \leq i \leq k$ ）会移动到 第$(i - 1)$ 部分在命令之前的位置。蛇不能移动到有障碍物的单元格中，也不能移动到网格外。此外，蛇也不能与自己碰撞。因此你应该保证蛇身的任何两个部分都不会共用同一个位置。
考虑下面的角情况：蛇头位于 $(x_1, y_1)$ ，蛇尾位于 $(x_k, y_k)$ 。如果头部移动到 $(x_1’, y_1’)$ ，那么就允许移动到 $(x_1’, y_1’) = (x_k, y_k)$ ：如果我们考虑现实世界中的情况，头部移动到单元格时，尾部正好移动到单元格外。类似地，在 $k = 2$ 处使用一条命令就可以交换头部和尾部。
您将得到网格的地图和蛇的身体序列。让 $f(i, j)$ 表示普塔塔为使蛇头到达 $(i, j)$ 所需的最少指令数，如果不可能，则为 $0$ 。你必须计算
$\left(\sum_{i = 1}^n\sum_{j = 1}^m f(i, j)^2\right) \bmod 2^{64}\text{.}$

输入

输入的第一行包含三个整数 $n$ 、 $m$ 和 $k$ （ $1 \leq n, m \leq 3000$ 、 $1 \leq k \leq \min\{nm, 10^5\}$ ），分别表示网格的大小和蛇的长度。

在接下来的 $k$ 行中， $i$ /th行包含两个整数 $x_i$ 和 $y_i$ （ $1 \leq x_i \leq n$ , $1 \leq y_i \leq m$ , $|x_i - x_{i+1}| + |y_i - y_{i+1}| = 1$ ），分别表示蛇身 $i$ /th部分的位置。保证所有 $k$ 对 $(x_i, y_i)$ 都是成对不同的。同时保证每个部分都位于一个没有障碍物的单元格中。

在接下来的 $n$ 行中， $i$ /th行包含一个长度为 $m$ 的字符串。如果 $(i, j)$ 单元格为空，那么这些行中 $i$ /th的 $j$ 个字符就是”.”。如果单元格 $(i, j)$ 被障碍物占据，则该字符为 “#”。
输出

打印一行，其中包含一个整数：问题答案。

嘴硬一下其实不是很难。
一开始没想明白是怎么回事，以为是走完全部的能到达的格子之后再计算$\left(\sum_{i = 1}^n\sum_{j = 1}^m f(i, j)^2\right) \bmod 2^{64}\text{.}$实际上是问你从起点开始走到(i,j)要多少步，那么就很套路的网格图建图求最短单源路径。
可以用dij，有一个比较难处理的地方是如果当前格子上有蛇的身体占着那么想要移动到这个格子就必须要等蛇身移走。
由于每个操作都可以等价看作初始蛇身必然缩短 1，并且同时控制蛇头移动一步或者不移动。
所以等蛇身移走就等于当前这个位置必须操作 k − i 次后才能访问该点。
这样的话就要先记录初始状态下第 i (2 ≤ i ≤ k) 节蛇身所处的位置，这里用map储存。
如果当前队列的队头移动到是蛇身，那么需要将队头所在位置的最短路长度与k − i 取最大值，然后再+1表示从队头所在位移动到蛇身的位置，松弛蛇身的位置的最短路。
如果当前队列的队头移动到的不是蛇身，那就直接普通的dij松弛即可。
但是注意题目的范围可以发现实际上堆优化的dij过不了，多带了一个log，这里用到了一个小trick：对于边长度固定的图（如等于1），那么BFS找到的从起点结点到任意节点的路径都是最短路。那么其实就可以直接用队列代替优先队列加速。
然后发现如果只用一个队列储存状态会有问题，因为这个边长并不全是1，因为蛇身有一个取max的操作。也就是说从不同情况下（蛇身位置与非蛇身位置）走到蛇身位置无法保证先进队列的一定就是最短路径。
实现的时候可以这样处理：一个队列存不是蛇身的位置，另一个存是蛇身的位置，每次先比较两个队列的队首，谁小就优先出队处理，这样就能保证队列的贪心是正确的。
题目中不太能理解的是取模和平方，取模的问题，其实C++没有哪一个类型能表示2的64次方(当然什么__int128就不算了)，合理怀疑是不需要取模的，取最坏的大概估算一下发现根本到不了2的64次方。对最短路平方还想了好久是不是有什么几何意义。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>

#define int unsigned long long
#define N 3005
using namespace std;

int dist[N][N], m, n, k;
map<array<int, 2>, int> isBody;

vector<array<signed, 2>> d{{1,  0},{-1, 0},{0,  1},{0,  -1}};

void solve() {
//    auto debugSt = [&]() -> void {for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) cout << st[i][j] << " \n"[j == m];};
//    auto debugDist = [&]() -> void {for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) cout << dist[i][j] << " \n"[j == m];};
    cin >> n >> m >> k;
    int headX, headY;
    for (int i = 1; i <= k; ++i) {
        int x, y;
        cin >> x >> y;
        if (i == 1) headX = x, headY = y;
        isBody[array<int, 2>{x, y}] = i;
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            char c;
            cin >> c;
            if (c == '.') dist[i][j] = 1ll << 62;
        }
    }
    queue<array<int, 2>> body, q;

    auto judge = [&](int x, int y) -> bool { return isBody.count(array<int, 2>{x, y}); };

    auto bfs = [&](int x, int y) -> void {
        for (auto [dx, dy]: d) {
            int w = dist[x][y];
            int _x = x + dx, _y = y + dy;
            if (_x < 1 || _x > n || _y < 1 || _y > m) continue;

            if (judge(_x, _y)) {
                w = max(w, k - isBody[array<int, 2>{_x, _y}]);
                if (w + 1 < dist[_x][_y]) {
                    dist[_x][_y] = w + 1;
                    body.push(array<int, 2>{_x, _y});
                }
            } else {
                if (w + 1 < dist[_x][_y]) {
                    dist[_x][_y] = w + 1;
                    q.push(array<int, 2>{_x, _y});
                }
            }
        }
    };

    body.push(array<int, 2>{headX, headY});
    dist[headX][headY] = 0;

    while (!body.empty() || !q.empty()) {
        if (!body.empty() && !q.empty()) {
            auto [qx, qy] = q.front();
            auto [bx, by] = body.front();
            if (dist[qx][qy] < dist[bx][by]) {
                q.pop();
                int x = qx, y = qy;
                bfs(x, y);
            } else {
                body.pop();
                int x = bx, y = by;
                bfs(x, y);
            }
        } else if (!body.empty()) {
            auto [bx, by] = body.front();
            body.pop();
            int x = bx, y = by;
            bfs(x, y);
        } else if (!q.empty()) {
            auto [qx, qy] = q.front();
            q.pop();
            int x = qx, y = qy;
            bfs(x, y);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            ans += dist[i][j] * dist[i][j];
    cout << ans << endl;
}

有个小细节就是dist取1<<62就能保证如果这个点到达不了那么在第87行就不需要判断dist[i][j]<(1<<62)因为相乘之后一定是溢出的，最后会被直接截断成0。
堆优化过不了但可能直接跑朴素dij能过没试过不知道行不行。