Lenstar的博客

博客

Tags
None

ARC043C 题解

2021-01-13 19:06:14 By Lenstar

ARC043C 転倒距離

定义两个排列 $A, B$ 的距离为满足 $(i, j)$ 在 $A, B$ 中顺序相反的无序对数。现在给定排列 $A$ 和 $B$,构造一个排列 $C$ 使得 $dis(A, C) = dis(B, C)$。

若 $(i, j)$ 在 $A,B$ 中的相对位置相同,则对 $dis(A, C)$ 和 $dis(B, C)$ 有相同的贡献。若不同,则对其中一个有 $1$ 的贡献。容易发现有解当且仅当 $dis(A, B)$ 为偶数。将 $A$ 映射为 $1, 2\dots n$。则 $dis(A, B)$ 等于 $B$ 的逆序对数,设为 $s$。

现在我们要构造一个 $C$ 使得 $B$ 中一半的逆序对变成正序对。设 $p$ 为最早满足 $[1, p]$ 中逆序对数大于 $\frac s2$ 的位置。将 $1$ 到 $p – 1$ 排序,再将 $p$ 插入到中间即可。

看代码应该好懂一些吧。

#include <bits/stdc++.h>

const int N = 1e5 + 10;


template<typename T = int> inline T read()
{
    T x = 0, f = 0; char ch = getchar();
    while (!isdigit(ch)) f |= ch == '-', ch = getchar();
    while ( isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    return f ? -x : x;
}

struct BIT
{
    int f[N];
    #define lowbit(x) (x & -x)

    inline void Add(int x, int dat = 1)
    {
        for (; x < N; x += lowbit(x)) f[x] += dat;
    }

    inline int Ask(int x)
    {
        int res = 0;
        for (; x; x -= lowbit(x)) res += f[x];
        return res;
    }
}T;

int a[N], A[N], b[N], s[N];

int main()
{
    int n = read(), p = 0; int64_t sum = 0;
    for (int i = 1; i <= n; ++i) a[A[i] = read()] = i;
    for (int i = 1; i <= n; ++i) b[i] = a[read()];
    for (int i = 1; i <= n; ++i) s[i] = T.Ask(N - 1) - T.Ask(b[i]), T.Add(b[i]);
    for (int i = 1; i <= n; ++i) sum += s[i];
    if (sum & 1) return puts("-1"), 0; sum >>= 1;
    for (int i = 1; i <= n; ++i)
    {
        if (sum < s[i]) {p = i; break;}
        sum -= s[i];
    }
    std::sort(b + 1, b + p);
    for (int i = 1; i <= sum; ++i) std::swap(b[p], b[p - 1]), --p;
    for (int i = 1; i <= n; ++i) printf("%d ", A[b[i]]); puts("");
    return 0;
}

退役感言

2020-12-07 22:15:08 By Lenstar

$2020.12.17$ 准备退役了。终究还是会退役啊。

我也不知道为啥当初要选择来海亮学信奥,可能只是为了逃避文化课,来打游戏,颓废。但是,我迟早要面对它。现在文化课给我的压力是很大的,我发现老师上课讲的我基本上就完全不会,小机房也没啥学文化课的氛围。而且信奥方面,我现在模拟赛天天爆 $0$ 垫底。我越发感觉自己不适合学信奥。我感觉我现在再这么搞下去很不行,于是我准备退役。

回顾这一整年的学习经历,有一说一,我还是学到了一些东西的。但是从大体来说,我颓废的时间太多。平常的题目一般就抄个题解,有时候连抄都不抄,就直接复制粘贴上去。模拟赛也基本上不认真打,要么就是网上找原题,或者拿同学的代码。实在搞不动就直接写个最低档暴力颓废。现在一认真打,问题马上就暴露出来。这样一整年搞下来,我现在进省队的希望非常小,我自己认为,我已经无法达到更高的水平了。

我总结出了我退役的四点原因:

  • 自身实力不足。$ZJOI2020$ 垫底,$APIO2020$ 近乎爆 $0$,$NOI$ 同步赛完全爆 $0$,这都显示出我的实力不足。确实应该退役。
  • 文化课不足以支持我停课学信奥,小机房没有学习氛围。因为我在机房就会划水打游戏,影响了小机房学习氛围。而且我到寝室学习就会影响同学(其实是同学说我内卷),导致我也不能在寝室学习。这样我就没有学习文化课的时间了。这也说明我确实应该退役
  • 自身信心不足。通过这几次考试,我每次垫底,而且得分都是最高分的一半不到。尤其是某一次考试,我的得分是最高分的 $\frac 1{10}$。这也极大的打击了我的信心。
  • 来自其他各方面的压力。其实我感觉我的家长,老师其实也不是很支持我继续学下去,我也难以承受他们给我带来的压力。而且通过他们对我的批评教育,我也认识到我自己还有很多不足,也说明了我确实是一个失败者。

最近,我看了时队的一篇文章,这篇文章说了关于沉没成本的问题,我也意识到我确实不能继续再这样走下去,不能总是以自己以前花了多少时间来找借口,要赶紧退役。

谢谢朋友们。

upd1 on 2020.12.18

以后就突然想到什么就更新一下吧。

我认为,退役要乘早,但是要经过慎重考虑。如果你在学习过程中一直想着退役,那么你的学习就不会成功(想法决定做法)。退役要抓紧时间,不要犹豫,这样你的学习效率就会下降(就和我一样一事无成)。

upd2 on 2020.12.24

昨天举办表彰大会,从大会上,我见识到了许多强者,也越发感觉自己的弱小。我也感觉到其实现在的形势也不适合我继续学下去(看起来维尼都不支持我学)。

为啥Lenstar在LsOJ上啥权限都没有啊

2020-07-27 13:19:04 By Lenstar
共 3 篇博客