526互联

[2022 China Collegiate Programming Contest (CCPC) Guilin Site](https://codeforces.com/gym/104008) CEM

发布时间 2023-09-12 11:38:02作者: nannan4128

2022 China Collegiate Programming Contest (CCPC) Guilin Site CEM

C. Array Concatenation

思路：数学推柿子

考虑有两种操作：

  1. 复制 \(b' = \{b_1,b_2,...,b_{|b|},b_1,b_2,...,b_{|b|} \}\)
  2. 翻转\(b' = \{b_{|b|},b_{|b|-1},...,b_1,b_1,b_2,...,b_{|b|}\}\)

要求我们计算\(\sum_{i = 1}^{n'}\sum_{j = 1}^{i}b_j(\bmod 1,000,000,007)\)的最大值。

分析：我们把原数组看成一个元素，正序用\(0\)表示，逆序用\(1\)表示。
\(0一开始\)

\(00复制\)
\(10翻转\)

\(0000复制\)
\(1100翻转\)
\(1010复制\)
\(1010翻转\)

\(00000000复制\)
\(11110000翻转\)
\(11001100复制\)
\(11001100翻转\)
\(10101010复制\)
\(10101010翻转\)
\(10101010复制\)
\(10101010翻转\)

通过上述的模拟，我们发现，除非一直复制，不然最终得到的都是一半正序一半逆序。那么答案最终只有\(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)+(3*10)+(1+8+10)+(3*10*2)+(1+8+10)+(3*10*3)+(1+8+10)\)

我们把\((1+8+10)+(3*10)+(1+8+10)+(3*10*2)+(1+8+10)+(3*10*3)+(1+8+10)\)分成两部分考虑

对于第一部分：\(0+(3*10)+(3*10*2)+(3*10*3) = n*10*\dfrac{(0+3)*4}{2}\)

扩展到一般性的：\(ans =n*数组和 *\dfrac{(0+总项数-1)*总项数}{2}\),其中总项数为：\(2^m\)

对于第二部分：\((1+8+10)+(1+8+10)+...+(1+8+10)\)

这部分答案就是\(总项数*数组前缀和的和\)

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

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

// 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

对于三个点\(A(x_1,y_1),B(x_2,y_2),C(x_3,y_3)\)，其中\(A,B\)点已知，让你求出\(C\)点使得\(S\Delta ABC\)最小。

\(\vec{AB} = (x_2-x_1,y_2-y_1),\vec{AC} = (x_3-x_1,y_3-y_1)\)

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

令\((x_2-x_1) = a,(y_2-y_1) = b\)

那么就只需要求\(|-bx+ay|\)的最小值时候的\(x,y\)就\(ok\)啦。

\(|-bx+ay|\)的最小值就是\(\gcd(a,b)\)

我们只需要用\(exgcd(-b,a,x,y)\)求解就可以了。

最后答案求的是\((x_3,y_3) = (x+x_1,y+y_1)\)

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

注意：

  1. 逆序对用树状数组求就好了
  2. 考虑记录当前\(head\)的位置，\(reverse\)也不用真的去翻转，只需要考虑当且是逆序还是顺序即可(和翻转的奇偶性有关)。
// 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;
}