题目内容
(题目内容改编自群友分享内容)
塔子哥最近学会了一种新的排序算法:X排序。
X排序算法的描述如下:首先,算法需要按某种规则选择该数列上至多X个位置,将其对应的数抽出来,其他的数都往左对齐,之后这X个数排好序之后依次放在原数列未尾,以上过程算作一次操作。
例如,对于数列 [ 1 , 3 , 5 , 4 , 2 ] [1,3,5,4,2] [1,3,5,4,2] ,当X=2时可以选样数字5和4,之后数列变成 [ 1 , 3 , 2 , 4 , 5 ] [1,3,2,4,5] [1,3,2,4,5] 。
塔子哥现在得到了一个数组 a,但是他现在很忙,需要你帮忙计算出最少需要多少次上述操作,使得整个数列从小到大排好序?
# 输入描述
第一行一个正整数T,表示有T组数据。
对于每一组数据,第一行输入两个正整数 n n n , x x x ;
第二行输入 n n n 个数 a 1 , a 2 , … , a n a_1,a_2,\dots ,a_n a1,a2,…,an, 该序列是一个 1~n 的排列。
对于所有数据: 1 ⩽ x ⩽ n ⩽ 1 0 5 , 1 ⩽ a t ⩽ n , a i ≠ a j , 1 ⩽ T ⩽ 5 1\leqslant x \leqslant n \leqslant 10^5,1\leqslant a_t \leqslant n, a_i \neq a_j, 1 \leqslant T \leqslant 5 1⩽x⩽n⩽105,1⩽at⩽n,ai=aj,1⩽T⩽5
输出描述
对于每一组数据,输出一行一个整数,表示答案。
样例
输入
25 11 2 3 4 55 21 3 5 4 2
输出
02
样例解释
第一组数据,原数列已经排好序,则无需进行任何操作;
第二组数据,操作如下:
[ 1 , 3 , 5 , 4 , 2 ] [1,3,5,4,2] [1,3,5,4,2] -> [ 1 , 5 , 4 , 2 , 3 ] [1,5,4,2,3] [1,5,4,2,3]
[ 1 , 5 , 4 , 2 , 3 ] [1,5,4,2,3] [1,5,4,2,3] -> [ 1 , 2 , 3 , 4 , 5 ] [1,2,3,4,5] [1,2,3,4,5]
思路:二进制拆位 + 离线处理 + 妙用set
0.这道题的一眼做法是开20个线段树,然后区间覆盖的板子。但是这里我给出一个稍微有意思的做法。这个问题的本质是可离线的序列上的区间覆盖问题
1.观察到我们是所有操作都做完,最后做一次询问,而不是边操作边询问,所以可以使用离线技巧。
离线:说简单点,就是不按他读入的顺序来处理这些操作。我们可以自由的对操作进行排序来处理
2.又观察到它所给的操作是位运算+覆盖,所以考虑按二进制的每一位去做:把序列的某一个二进制位摘出来排成数组,那么这些操作等价于在01数组上反复做区间覆盖。然后又可以离线,所以我们不难想到按时间倒着扫描这些操作。
从倒着扫描这个角度来看,我们其实可以发现每个点最终的结果只会被最晚的cover这个点的那次操作给影响。所以可以想到搞一个set把数字1~n塞到set里。然后对于区间 [ l , r ] [l,r] [l,r] , 我们不停的在set里二分找 i ∈ [ l , r ] i \in [l,r] i∈[l,r] 的点,覆盖,然后删除即可. 最后,我们将这些二进制位结果合并一下作为十进制整数输出即可。
由于我们涉及到了比较多的二进制操作,可以使用bitset来缩短编码。
怎么样,大概理清思路了吗?先别急着看下面的标程,试着自己动手敲一下,然后来我们的OJ上提交一发试试看吧
代码 + 注释
#include<bits/stdc++.h>using namespace std;const int maxn = 100005;int l[maxn] , r[maxn];// bitset学习资料:/magisk/p/8809922.htmlbitset<40> a[maxn] , x[maxn] , res[maxn];int main (){int n;// 输入cin >> n;for (int i = 1 ; i <= n ; i++) {int g; cin >> g;a[i] = g;}int q;cin >> q;for (int i = 1 ; i <= q ; i++) {int g; cin >> g;l[i] = g;}for (int i = 1 ; i <= q ; i++) {int g; cin >> g;r[i] = g;}string op_str;cin >> op_str;op_str = '#' + op_str;for (int i = 1 ; i <= q ; i++) {int g; cin >> g;x[i] = g;}// 按位计算for (int d = 0 ; d <= 21 ; d++){// 离线处理,并把问题变成序列上的区间覆盖// {l , r , 0/1} 代表将区间[l,r]覆盖成0/1vector<tuple<int , int , int >> op_arr;for (int i = 1 ; i <= q ; i++){char op = op_str[i];int nowx = x[i][d];if (op == '='){op_arr.push_back(make_tuple(l[i] , r[i] , nowx));}else if (op == '&'){if (nowx == 0)op_arr.push_back(make_tuple(l[i] , r[i] , 0));}else {if (nowx == 1)op_arr.push_back(make_tuple(l[i] , r[i] , 1));}}// 建立set,一开始所有点都待处理set<int> rest;for (int i = 1 ; i <= n ; i++) rest.insert(i);// 倒着扫,因为每个点只会被最晚的覆盖它的操作影响reverse(op_arr.begin() , op_arr.end());for (auto &op : op_arr){int l = get<0>(op);int r = get<1>(op);int v = get<2>(op);int cnt = 0;// 不停的找元素属于[l,r] , 直到没有....while (rest.size()){auto it = rest.lower_bound(l);if (it == rest.end() || *it > r) break;a[*it][d] = v;rest.erase(it);}}}// 输出for (int i = 1 ; i <= n ; i++){cout << a[i].to_ulong();if (i == n) cout << endl;else cout << " "; }return 0;}
更多大厂笔试真题与题解,尽在塔子哥学算法的OJ!