第45届ICPC亚洲赛区昆明站

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

L Simone and graph coloring

链接

https://ac.nowcoder.com/acm/contest/12548/L?&headNav=acm

题意

给你一个排列,排列的长度不超过$10^6$。你要对他的每一个元素进行染色,要求染色后不存在任何一个逆序对的两个元素颜色相同。你需要输出染色的数组。

输入

1
2
3
4
5
2
4
1 3 4 2
2
1 2

输出

1
2
3
4
2
1 1 1 2
1
1 1

题解

逆向思维,我们假设自己已经有了一个答案,我们对着这个答案按照颜色对排列进行子序列拆分,则有几个颜色就有一个子序列,这些子序列恰好构成原排列的一个划分。

可以断言,每一个子序列都是严格单调增。

然后回到正向思维,我们要做的就是把这个排列分成n个单调增的划分,如何最小化n?

我们贪心地维护一些桶,并按顺序枚举排列中的元素,把他们放到这些桶里面,保证桶中的数据单调增,如果他无法放入任何桶,则为他新建一个桶,如果他可以放入多个桶,则选择最后一个元素最大的那个桶。

代码

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
#include <iostream>
#include <vector>
#include <map>

using namespace std;

void solve(vector<int> a) {
map<int, int> mp;
vector<int> color(a.size());

int cnt = 0;


mp[a[0]] = 1;
color[0] = ++cnt;

for (int i = 1; i < a.size(); i++) {
// *it >= key
auto it = mp.lower_bound(a[i]);

if (it == mp.begin()) {
mp[a[i]] = ++cnt;
color[i] = cnt;
} else {
--it;
mp[a[i]] = it->second;
color[i] = it->second;
mp.erase(it);
}
}

cout << cnt << "\n";
for (int x:color) {
cout << x << " ";
}
cout << "\n";
}


int main() {
ios::sync_with_stdio(false);
cin.tie(0);

int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
solve(a);
}
}

M Stone Games

链接

https://ac.nowcoder.com/acm/contest/12548/M

题意

给你一个长度1e6的数组,1e5组询问,每次询问这个数组的一个子串(subString), 对于这个子串的所有子序列(subSequence),他们各自的和构成的集合的mex为多少。强制在线。

补充: mex函数表示是:不在该集合中的最小的非负整数的值

输入

1
2
3
4
5
6
7
5 5
1 4 2 1 6
1 3
2 1
2 4
1 4
3 4

输出

1
2
3
4
5
8
15
4
9
4

说明

由于进行了强制在线处理,所有的输入进行了加密,下面是解密后的内容

In the example above, the actual query intervals are [2,4],[1,5],[3,5],[1,4] and [3,4].

题解

暴力

考虑一个数列,他的所有子序列各自的和的mex要怎么计算,比如1 4 2 1 6 20 21

先排序1 1 2 4 6 20 21, 然后依次检验前缀和,

首先整数区间[0,0]都可行,只要一个数不选即可

然后考虑第一个数1,区间变为[0,1]

然后考虑第二个数1,区间变为[0,2]

然后考虑第三个数2,区间变为[0,4]

然后考虑第一个数4,区间变为[0,8]

然后考虑第一个数6,区间变为[0,14]

然后考虑第一个数20,前缀无法扩展了因为你无论如何都无法构造出数字15,于是最后一个数字21也不用考虑了。

区间加速

上面的办法太慢了,如果这个序列长度为n,则要计算n次。能不能加速这个过程?

考虑到如果枚举到第i个数的时候,区间为[0,x], 则对于所有小于等于x+1的数,我们都可以合并到区间,一旦发现没有小于等于x+1的数的时候,算法可以结束了,这个序列无法构造数字x+1

由于每一轮枚举可以把很多数字加入到区间中,区间的右端点以指数的方式增加,所以这个算法只会枚举lg次。

主席树维护区间和

剩下的问题就是区间中小于等于x的数的和是多少了,这个是主席树模版题。

J Parallel Sort

链接

https://ac.nowcoder.com/acm/contest/12548/J

题意

你有一个排列,你需要对他进行排序,你有一个很厉害的并行计算机,能够选择任意个数对,然后在一轮处理之后,将他们两两互换。现在问你至少需要多少轮,你才能将整个排列排好序

数据范围

排列长度小于$10^5$

题解

对于一个排列,我们不要关注其中的数字的大小,排序即将正确的值放入正确的位置即可,即将值i,放入位置i。假设排列为P,排列中的数字分别是$P_1,P_2,P_3…P_n$,把他们写成置换的形式:

$$
\begin{pmatrix}
1 & 2 & 3 & … & n\\
P_1 & P_2 & P_3 & … & P_n
\end{pmatrix}
$$
然后我们考虑$P_i$和$P_j$

$$
\begin{pmatrix}
1 & 2 & … & i & … & j & … & n\\
P_1 & P_2 & … & P_i& … &P_j& … & P_n
\end{pmatrix}
$$
当交换$P_i$和$P_j$后, 变成了:

$$
\begin{pmatrix}
1 & 2 & … & i & … & j & … & n\\
P_1 & P_2 & … & P_j& … &P_i& … & P_n
\end{pmatrix}
$$

注意到

$$
\begin{pmatrix}
1 & 2 & … & i & … & j & … & n\\
P_1 & P_2 & … & P_i& … &P_j& … & P_n
\end{pmatrix} \circ
\begin{pmatrix}
P_i & P_j\\
P_j & P_i
\end{pmatrix}
=\begin{pmatrix}
1 & 2 & … & i & … & j & … & n\\
P_1 & P_2 & … & P_j& … &P_i& … & P_n
\end{pmatrix}
$$

于是我们发现题目本质上就是给我们一个置换,你可以让他和对换进行乘法运算,问你如何操作能让他变成置换:$(1)\circ(2)\circ(3)\circ(4)…(n)$

根据置换分解定理,一个置换一定可以多个循环置换的积,不妨假设原始置换被分解为了$Q_1\circ Q_2\circ Q_3…Q_t$ 其中每一个$Q_i$都是一个循环置换。

我们假设进行了k次交换,则答案为$(a_1,b_1)\circ(a_2,b_2)\circ(a_3,b_3)…(a_k,b_k)$,

则有$(Q_1\circ Q_2\circ Q_3…Q_t)\circ ((a_1,b_1)\circ(a_2,b_2)\circ(a_3,b_3)…(a_k,b_k)) = (1)\circ(2)\circ(3)…(n)$

这里很明显对于每一个$Q_i$分别乘上右侧的答案,得到的都是长度为1的循环置换。于是我们只需要对每一个$Q_i$分别讨论,然后右侧需要乘上的最多的置换就是答案。

不妨考虑$Q_1=(1,2,3,4…x)$ (思考为什么可以不讨论这种: (1,3,5,2,4))

然后考虑对他进行一次对换$(1,y)$ (思考为什么第一个数可以规约到1)

之后变成了: $(\dot 1,2,3,4…y-1)\circ (\dot y,y+1,y+2 … x)$

然后我们发现$Q_1$变成了两个循环置换的乘积,对于下一次交换,我们无法再次使用数字y和数字1,笔者在此也对他们进行了标记,可以看到他们的头顶都有一个点符号。

下一轮的子问题变成了有一个数无法使用。这回到了原点,且限制条件更多,我们不妨直接假设$Q_1$的有一个数不能使用,不妨假设他为x,则$Q_1=(1,2,3,4…\dot x)$

对他进行对换$(1,y)$ 变成了$(\dot 1,2,3,4…y-1)\circ (\dot y,y+1,y+2 … \dot x)$

稍微细心一点就能发现左边的等式为原问题,右边如果$y=x-1$则下一轮可直接完成。

综上,最多两轮可换完所有的数。按照这个思路模拟,我们发现每次交换的数满足这样的性质,进行交换的两个数的和恰好为n。

于是整个问题直接解决。