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。

于是整个问题直接解决。