#842 div2

https://codeforces.com/contest/1768

A:

题目：

存在两个整数 x 和 k，给出 k，请你找出一个 x， 使得， x! + (x - 1) ! 能够整除 k

思路：

等价变形 x * (x - 1) ! + (x - 1) !, (x + 1)*(x - 1) !， 让 x + 1 = k， 所以 x = k - 1

代码

void solved()
{
    int k;
    cin >> k;
    cout << k - 1 << endl;

}

B：

题目：

现在给出一个长度为 n 的排列，存在一个整数 k。

存在以下操作

1.选择 k 个整数从小到大排列后放到排列的后面
问你最小操作次数变成 1 2 3 4 5 这样

思路：

我们选择一些扔到后面，然后剩下的自动构成合法的。

所以每次从头到尾统计，首先头肯定为 1， 1前面的都要仍到后面，其次

1 - 2中间所有数扔到后面，1 和 2自动在一起，依此类推。统计好要仍多少个数，然后每次最多移动 k 个。

最后与 k 上取整即可。

代码

void solved()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >>a[i];

    int now = 1;
    int ji = 0;

    for(int i = 1; i <= n; i++)
    {
        if(now != a[i]) ji++;
        else now++;
    }

    cout << (ji + m - 1 )/ m << endl;

}

C：

题目：

现在存在一个长度为 n 的数组 a，我们现在要构造两个排列，使得 对应 max(p1[i], p2[i]) == a[i]。

问你能不能构造出这两个排列

思路：

首先我们尽可能的把 max 值放在一个数组里，如果说一个数字出现 2 次，那么肯定要放在另一个数组里。

如果 > 2 次，那么不合法。

这样我们填完了第一步，max都填好了，要填剩下的对应位置的小值。

贪心的来说，数字越小我们越好放，所以我们优先放大值，让大值与大值匹配。

直到不合法。

代码 1

void solved()
{    
    cin >> n;

    vector<int>a1, a2;

    for(int i = 1; i <= n; i++) cin >> a[i].first, a[i].second = i, pd1[i] = pd2[i] = false;

    sort(a + 1, a + n + 1, bmp);

    vector<PII>f1;
    vector<PII>f2;

    for(int i = 1; i <= n; i++)
    {
        int x = a[i].first, id = a[i].second;

        if(!pd1[x])
        {
            pd1[x] = true;
            ans1[id] = x;
            f1.push_back(a[i]);

        }else if(!pd2[x])
        {
            pd2[x] = true;
            f2.push_back(a[i]);
            ans2[id] = x;
        }else
        {
            cout << "NO" << endl;
            return;
        }
    }


    for(int i = 1; i <= n; i++)
    {
        if(!pd1[i])a1.push_back(i);
        if(!pd2[i])a2.push_back(i);
    }

    int z1 = a1.size() - 1;
    int z2 = a2.size() - 1;

    for(int i = 0; i < f1.size(); i++)
    {
        int w = f1[i].first, id = f1[i].second;

        if(a2[z2] > w)
        {
            cout << "NO" << endl;
            return;
        }

        ans2[id] = a2[z2--];
    }


    for(int i = 0; i < f2.size(); i++)
    {
        int w = f2[i].first, id = f2[i].second;

        if(a1[z1] > w)
        {
            cout << "NO" << endl;
            return;
        }

        ans1[id] = a1[z1--];
    }


    cout << "YES" <<endl;

    for(int i = 1; i <= n; i++) cout <<ans1[i] << " "; cout << endl;
    for(int i = 1; i <= n; i++) cout << ans2[i] << " "; cout << endl;

}

代码 2

void solved()
{
    cin >> n;
    set<int>p1, p2;

    for(int i = 0; i < n; i++) cin >> a[i], p1.insert(i + 1), p2.insert(i + 1), ans1[i] = 0, ans2[i] = 0;


    for(int i = 0; i < n; i++)
    {
        if(p1.count(a[i])) p1.erase(a[i]), ans1[i] = a[i];
        else if(p2.count(a[i]))p2.erase(a[i]), ans2[i] = a[i];
        else
        {
            cout << "NO" << endl;
            return;
        }
    }


    for(int i = 0; i < n; i++)
    {
        if(ans1[i])
        {
            int x = ans1[i];

            auto it = p2.lower_bound(x);

            if(it != p2.end() && *it == x) ans2[i] = x, p2.erase(x);
            else if(it != p2.begin() && it != p1.end())
            {
                it--;
                int push = *it;
                ans2[i] = push, p2.erase(push);
            }else
            {
                cout << "NO" << endl;
                return;
            }
        }else
        {
            int x = ans2[i];

            auto it = p1.lower_bound(x);

            if(it != p1.end() && *it == x) ans1[i] = x, p1.erase(x);
            else if(it != p1.begin())
            {
                it--;
                int push = *it;
                ans1[i] = push, p1.erase(push);
            }else
            {

                cout << "NO" << endl;
                return;
            }

        }
    }


    cout << "YES" << endl;
    for(int i = 0; i < n; i++) cout << ans1[i] << " "; cout <<  endl;
    for(int i = 0; i <n; i++) cout << ans2[i] << " "; cout << endl;

}

D:

题目：

现在存在一个排列，你每次可以操作一次，让 ai 和 aj 交换值。 但是你必须让排列只存在一个逆序对。

问你最少操作次数

思路：

已知假设一个排列是 1 2 3 4 .. n， 那么我们相邻两项交换一下， 就存在一个逆序对了。

(冷知识（冒泡排序的最小交换次数是逆序对的数量）)

那么我们力求先变成 1 2 3 .. n。

考虑置换环，对于第 i 个位置上 i != a[i] ，i > a[i] 连一条边。

对于置换环内变成合法的，我们发现只要存在相邻两项在同一个置换环中，我们就能减少一次交换，最终只剩下一个逆序对。

假设存在 cir 个环，我们需要 n - cur 次交换就可以变成 1 2 3 4， 假如存在上述情况，那么需要 n - cur - 1 次，就可以变成

题目要求的情况。

代码

void dfs(int u)
{
    if(vis[u]) return;
    vis[u] = true;
    pd[u] = true;

    if(pd[u - 1] || pd[u + 1]) flag = true;

    dfs(a[u]);
}

void solved()
{
    cin >> n;
    flag = false;

    for(int i = 1; i <= n; i++) cin >> a[i], vis[i] = 0;

    int cir = 0;

    for(int i = 1; i <= n; i++)
    {
        if(!vis[i])
        {
            cir++;
            pd.clear();
            dfs(i);
        }
    }

    if(flag) cout << n - cir - 1 << endl;
    else cout << n - cir + 1 << endl;
}