#839 div3

https://codeforces.com/contest/1772

C：

题目：

现在给出一个单调递增的整数序列，我们定义这个序列的特征为，把这个序列变为每两个相邻的数字相减，不同数字的个数。

现在可以任意排列这个序列，问你最多特征的排列是什么

思路：

首先是不同数字的个数，贪心的来说，希望从小到大来构造。

然后其他的构不成不同数字了，再不影响前面构造的情况下添加尽可能大的数字即可

代码

void solved()
{
    memset(f, 0, sizeof f);

    int k, n;
    cin >> k >> n;

    a[1] = 1;
    int sum = 1;

    vector<int> ans;

    int sheng = -1;
    ans.push_back(1);
    f[1] = true;

    for(int i= 2; i <= k; i++)
    {
        if(ans[i - 2] + sum <= n)
        ans.push_back(ans[i - 2] + sum), f[ans[i - 2] + sum] = true, sum++;
        else
        {
            sheng = k - i + 1;
            break;
        }
    }


    if(sheng == -1)
    {
        for(int i = 0; i < ans.size(); i++) cout << ans[i] << " ";
        cout << endl;
    }else
    {
        int cnt = 0;

        for(int i = n; i >= 1; i--)
        {
            if(f[i] == false)
            {
                cnt++;
                ans.push_back(i);
            }


            if(cnt == sheng)
            {
                sort(ans.begin(), ans.end());

                for(int i = 0; i < ans.size(); i++) cout << ans[i] << " ";
                cout << endl;
                return;
            }
        }
    }


}

D：

题目：

给出一个序列，现在你找到一个 x，对所有的序列 取 |ai - x|，问你序列还是不是递增。

思路：

对于两个相邻不合法的，我们最低的 x 是 (a[i] - a[i + 1] ) / 2, 把两个相邻的变成合法的，x 越大可能原本合法的两个变成不合法。

所以我们对于所有的不合法取一个 max，所以至少要到 max 才能把全部不合法的变成合法的。

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


    int mxx = 0;


    for(int i = 0; i < n - 1; i++)
    {

        if(a[i] > a[i + 1])
        {
            int x = (a[i + 1] + a[i]) / 2;
            if((a[i + 1] + a[i]) % 2 != 0) x++;

            mxx = max(mxx, x);
        }
    }


    for(int i = 0; i < n; i++)
    {
        a[i] = abs(a[i] - mxx);
    }

    bool p1 = true;

    for(int i = 0; i < n - 1; i++)
    {
        if(a[i] > a[i + 1])
        {
            p1 = false;
            break;
        }
    }

    if(p1)
    {
        cout << mxx << endl;
        return;
    }

    cout << -1 << endl;

}

E:

题目：

现在存在两个玩家为 ，fir 和 sec，分别为先手和后手。

现在存在一个序列，为 1 - n 每个数字只出现一次，起初每个元素都是 red。

现在每轮存在三种操作，每个人任选其中一个操作进行。

1.选择一个元素变成 blue

2.可以选择所有的 blue元素，任意排列

3.不进行操作

如果说 fir 赢，那么为他排序之后全部元素变成单增，如果 sec 赢，那么他排完序之后所有元素变为单减。

思路：

首先对于每个人的优先策略是，把不合法的位置变成 blue，这样排序排序之后就 win。

那么我们先统计一下每个人不需要动的元素和需要动的元素，和都需要动的元素。

因为 fir 先手。fir 要赢就要赶在 sec 前把需要的位置都变为 blue，然后该 sec了，但是 sec 这时无法直接排序变成他想要的。

那么下一轮 fir 直接排序，fir 赢了。

所以如果先手在完成了所有需要的染色，后手没染完，那么先手 win。

先手必须在后手完成所有染色之前染色，否则后手可以阻止。

sec + other <= fir， 此处有等于，因为先手可以先染色一下。

后手同理，

fir + other < sec 这没有等于，因为当后手染色完之后，该先手直接 win了，

代码

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

    int cnt = n;
    int fir, sec;
    fir = sec = 0;
    int oth = 0;

    for(int i = 1; i <= n; i++)
    {
        if(i == a[i] && a[i] == cnt) fir++, sec ++;
        else if(i == a[i]) fir++;
        else if(cnt == a[i]) sec++;
        else oth ++;
        cnt--;
    }

    if(fir + oth <= ) cout << "First" << endl;
    else if(fir + oth < sec) cout << "Second" << endl;
    else cout << "Tie" << endl;

}