2022 CCPC桂林 CEM

2022 China Collegiate Programming Contest (CCPC) Guilin Site CEM

C. Array Concatenation

思路：数学推柿子

考虑有两种操作：

1. 复制
2. 翻转

要求我们计算的最大值。

分析：我们把原数组看成一个元素，正序用表示，逆序用表示。

通过上述的模拟，我们发现，除非一直复制，不然最终得到的都是一半正序一半逆序。那么答案最终只有种情况，全复制或者存在翻转(一半正，一半逆)。但由于发生一次翻转后，原数组变成了回文的，无论执行哪个操作都是一样的。

那么，我们考虑最后一次翻转就可以了。

进一步考虑，如果只有复制是什么样子的呢？
$$
172原数组\
172 \ 172第一次复制 \
172 \ 172 \ 172 \ 172第二次复制\
\
对于第二次复制:172 \ 172 \ 172 \ 172\
(1+8+10)+(11+18+20)+(12+28+30)+(31+38+40)\
(1+8+10)+(310)+(1+8+10)+(3102)+(1+8+10)+(3103)+(1+8+10)\
$$
我们把$(1+8+10)+(310)+(1+8+10)+(3102)+(1+8+10)+(3103)+(1+8+10)$分成两部分考虑

对于第一部分：$0+(310)+(3102)+(3103) = n10*\dfrac{(0+3)*4}{2}$

扩展到一般性的：,其中总项数为：

对于第二部分：

这部分答案就是

上述分析了只复制的情况，那么对于有翻转的呢？

对于只复制和有翻转的情况，第一部分的答案是一样的，对于第二部分的唯一区别就是前缀和的和不一样。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll n,m;
ll pre_a[N],pre_b[N];
ll qmi(ll a, ll b, ll mod)
{
    ll ans = 1 % mod;
    while(b)
    {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    cin>>n>>m;
    ll sum0 = 0,sum1 = 0;
    for(int i = 1;i <= n; i++)
        cin>>pre_a[i],pre_b[i] = pre_a[i];
    for(int i = 1; i <= n; i++)
    {
        pre_a[i] = (pre_a[i-1]+pre_a[i])%mod;
        sum0 += pre_a[i];
        sum0 %= mod;
    }

    for(int i = n; i >= 1; i--)
    {
        pre_b[i] = (pre_b[i+1]+pre_b[i])%mod;
        sum1 += pre_b[i];
        sum1 %= mod;
    }
    ll inv2 = qmi(2,mod-2,mod);
    ll cnt = qmi(2,m,mod);
    ll ret = cnt*inv2%mod;
    ll ans = n*pre_a[n]%mod*cnt%mod*((cnt-1)%mod+mod)%mod*inv2%mod;

    cout<<max((ans+cnt*sum0%mod)%mod,(ans+ret*sum0%mod+ret*sum1%mod)%mod)<<"\n";
    return 0;
}

E. Draw a triangle

思路：计算几何+数论exgcd

对于三个点，其中点已知，让你求出点使得最小。

我们考虑用叉乘求面积$|\dfrac{(x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1)}{2}|$

令

那么就只需要求的最小值时候的就啦。

的最小值就是

我们只需要用求解就可以了。

最后答案求的是

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if(b == 0)
    {
        x = 1; y = 0;
        return a;
    }
    ll xx,yy;
    ll d = exgcd(b, a % b, xx, yy);
    x = yy;
    y = xx - (a / b) * yy;
    return d;
}

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        ll x1,y1,x2,y2,x,y;
        cin>>x1>>y1>>x2>>y2;
        ll a = x2-x1, b = y2-y1;
        if(a==0)
            cout<<x1-1<<" "<<y1<<"\n";
        else if(b==0)
            cout<<x1<<" "<<y1-1<<"\n";
        else
        {
            //((x2-x2)(y3-y1)-(y2-y1)(x3-x1))/2
            //(-bx+ay)/2
            ll d = exgcd(-b,a,x,y);
            cout<<x+x1<<" "<<y+y1<<"\n";
        }
    }

    return 0;
}

M. Youth Finale

思路：模拟+数据结构

我们考虑两种操作对当且逆序对数的影响：

1. 新的逆序对数 = 最大逆序对数(n*(n+1)/2)-当且逆序对数
2. ：考虑第一个数到最后去了会有什么影响？新的逆序对数=当且逆序对数-小于的元素个数(与比它小的数形成的逆序对消失了）+大于的元素个数。

注意：

1. 逆序对用树状数组求就好了
2. 考虑记录当前的位置，也不用真的去翻转，只需要考虑当且是逆序还是顺序即可(和翻转的奇偶性有关)。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 10;
const int N = 6e5 + 10;
ll a[N];

template<class T>
struct BIT {
    T c[N];
    int size;
    void resize(int s) { size = s;}
    T query(int x) { // 1 ... x
        assert(x <= size);
        T s = 0;
        for (; x; x -= x & (-x)) {
        s += c[x];
    }
    return s;
    }

    void modify(int x, T s) { // a[x] += s
        assert(x != 0);
        for (; x <= size; x += x & (-x)) {
            c[x] += s;
        }
    } 
};

BIT<ll> c;
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    //翻转p' = n(n-1)/2-p
    //转移p' = p-比x小的(x-1)个数+(n-x)比x大的数
    ll n,m,ans = 0;
    cin>>n>>m;
    c.resize(n+10);
    for(int i = 0; i < n; i++)
        cin>>a[i];
    for(int i = 0;i < n; i++)
    {
        ans += c.query(n)-c.query(a[i]);
        c.modify(a[i],1);
    }
    cout<<ans<<"\n";
    ans %= 10;
    int head = 0,nxt = 1;
    ll all = n*(n-1)/2;
    all %= mod;
    string s;
    cin>>s;
    int sz = s.size();
    for(int i = 0;i < sz; i++)
    {
        if(s[i]=='S')
        {
            ans = ((ans-(a[head]-1)+(n-a[head])%mod+mod)%mod+mod)%mod;
            head = ((head+nxt)%n+n)%n;
        }
        else if(s[i]=='R')
        {
            ans = ((all-ans)%mod+mod)%mod;
            head = ((head+(n-1)*nxt)%n+n)%n;
            nxt *= -1;
        }
        cout<<ans;
    }
    cout<<"\n";

    return 0;
}