本文最后更新于:2020年10月8日 早上

题意简述

  • 给定一个长度为 $n$ 的排列 $p$,定义 $F(p)= \operatorname{sort} {i=1}^{i-1} p_i+p{i+1}$;

  • 求出不同的排列 $p’$ 满足 $F(p’)=F(p)$。

  • 定义如果 $\exists i\in \left[1,n\right]:p_i≠p_{i+1}$,则 $p$ 与 $p’$ 是不同的。

题目分析

由于题目可能有多解,我们只需要输出一个可能的解就可以了。

要做到题目给定的条件,我们要使得本来相邻的数现在也相邻 就可以确保在任一条件下成立。

也就是 $p’=\operatorname{reverse}p$。

可以验证反转后 $p’$ 和 $p$ 不同。

分析时间复杂度:$\mathcal O(t\cdot n)$。

代码

#include <bits/stdc++.h>

using namespace std;

#ifndef ONLINE_JUDGE
#    define debug
#endif
namespace luosw {
namespace IO {
    template < typename T >
    inline T read() {
        T    ret = 0, f = 1;
        char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-')
                f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9')
            ret = ret * 10 + ch - '0', ch = getchar();
        return ret * f;
    }
    template < typename T >
    void write(T x) {
        if (x < 0) {
            putchar('-');
            x = -x;
        }
        T y = 10, len = 1;
        while (y <= x) {
            y *= 10;
            len++;
        }
        while (len--) {
            y /= 10;
            putchar(x / y + 48);
            x %= y;
        }
    }
    template < typename T >
    void write(T x, bool flag) {
        if (x < 0) {
            putchar('-');
            x = -x;
        }
        T y = 10, len = 1;
        while (y <= x) {
            y *= 10;
            len++;
        }
        while (len--) {
            y /= 10;
            putchar(x / y + 48);
            x %= y;
        }
        if (flag)
            putchar('\n');
    }
}  // namespace IO
namespace tools {
    template < typename T >
    T cmax(T a, T b) {
        return max(a, b);
    }
    template < typename T >
    T cmin(T a, T b) {
        return min(a, b);
    }
    template < typename T >
    T cgcd(T a, T b) {
        return __gcd(a, b);
    }
    template < typename T >
    T clcm(T a, T b) {
        return a * b / cgcd(a, b);
    }
}  // namespace tools
}  // namespace luosw
#define read(t) t = luosw::IO::read< int >()
int    t, n, a[10000];
signed main() {
    read(t);
    while (t--) {
        read(n);
        memset(a, 0, sizeof(a));
        for (int i = 0; i < n; i++) {
            read(a[i]);
        }
        for (int i = n - 1; i >= 0; i--) {
            luosw::IO::write(a[i]);
            putchar(' ');
        }
        putchar('\n');
    }
#ifdef debug
    system("pause");
#endif
    return 0;
}

本文在 CC BY-NC-ND 4.0( https://creativecommons.org/licenses/by-nc-nd/4.0/deed.zh )协议 的前提下,禁止超过文章30%字数的摘录(对于不超过文章30%字数的摘录,要求在醒目位置注明原文作者与原文链接),同时,在未经作者本人手写签名许可的情况下,禁止任何形式的全文转载,禁止发布任何基于本文的再创作。

CF1400A 题解 上一篇
10.4 数论 下一篇
本博客采用 xCss 的 Valine 评论系统,搭配了 Valine-Admin,垃圾评论将会被过滤。所以在评论的时候,请注意您的语言。如果您的评论被过滤但并非垃圾评论,请发邮件到 luosiweimail@gmail.com 进行申诉。