CF AIM Tech Round 4 (Div. 1) A. Sorting by Subsequences

传送门：https://codeforces.com/problemset/problem/843/A

题意：给一串无重复元素的序列，可对子序列（无需连续）进行递增排序，使得对所有子序列排序后整个序列有序，输出可分的最大子序列数目及每个子序列大小和各个元素

看到是A 以为很水直接上手搞

数组a记元素 b复制一下a，对b排序，因为元素无重复用map标记一下a中每个元素应排在第几位

（刚开始忘了子序列无需连续了就产生了下面的奇怪想法

用了样例试一下

1 2 3 4 5 6

83 -75 -49 11 37 62

6 1 2 3 4 5

1 2 3 4 5 6

3 2 1 6 5 4

发现1的位置是3 前面元素的下标最大值必须3 不然这段序列排完后面就<=3的数就没法排了只能整个序列排一下了

所以令x=1，遍历找到x的位置看是否满足条件，比如说找到是3 那前面3个数就可以排了接下来x=4，继续找就对了不满足就只能输出按整个排了

嗯自信满满

哇写着写着发现不对劲

扫了下题目发现第一个样例的输出有点奇怪咧哦子序列无需连续

哈哈哈那就不用这么麻烦了

再对样例涂涂改改，发现直接从第一个元素开始替换到某元素下标为该元素下标就行了

e.g. 83应该排到6这个位置，6这个位置上的元素是62，应该要排到5的位置继续下去要排到原本83的1的位置就要把所有元素都访问一遍刚好就是输出

3应该排到3这个位置，3这个位置上是1就是3这个元素的下标只要把1 3位置换一下就可以了推下去就和输出一样了

哈哈哈开始上手搞

...

搞定

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<list>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> p;
typedef long double ld;
#define mem(x) memset(x, 0, sizeof(x))
#define me(x) memset(x, -1, sizeof(x))
#define fo(i,n) for(i=0; i<n; i++)
#define sc(x) scanf("%lld", &x)
#define pr(x) printf("%lld
", x)
#define pri(x) printf("%lld ", x)
#define lowbit(x) x&-x
const ll MOD = 1e18 +7;
const ll N = 6e6 +5;
ll a[N], b[N];
map<ll,ll>mp, vis;
set<ll> v[N];
int main()
{
    ll i, j ,k, l=0;
    ll n, m, t;
    cin>>n;
    for(i=1; i<=n; i++)
        cin>>a[i], b[i]=a[i];
    sort(b+1,b+n+1);
    for(i=1; i<=n; i++)
        mp[b[i]]=i;
    ll co=0, mx=0, x=1;

    //for(i=1; i<=n; i++) cout<<mp[a[i]]<<' ';cout<<endl;

    for(i=1; i<=n; i++)
    {

        if(vis[i]) continue;
        k=mp[a[i]];
        v[l].insert(i);
        //cout<<i<<" ";
        while(1)
        {
            vis[k]=1;
            v[l].insert(k);
            //cout<<k<<" ";
            if(mp[a[k]]==i) break;
            k=mp[a[k]];
        }
        l++;
        //cout<<endl;
    }
    cout<<l<<endl;
    set<ll>::iterator it;
    for(i=0; i<l; i++)
    {
        cout<<v[i].size();
        for(it=v[i].begin(); it!=v[i].end(); it++)
            k=*it,cout<<" "<<k;
        cout<<endl;
    }
    return 0;
}

View Code