NOI Online

内嵌 Annoucement

Posted by Ghastlcon on March 7, 2020
CC 采用 $\text{CC BY-NC-SA 4.0}$ 许可,转载请注明:“转自 NOI Online

这个比赛非常的意义不明啊,吃力不讨好的工作?不知道从哪里搞来的题,并且实话实说感觉这比赛多多少少和强基计划脱不了关系(

早上起床死活打不开网页,比赛开始后还是打不开,最后从 $\text{UOJ}$ 老哥处拿到了题面,然后瞬间就能登录进去了(

$\text{P1}$

感觉把 $t=2$ 缩掉之后还是很麻烦啊,有点类似二分图判断。

然后如果是个二分图操作只在左右,那就只要两边相等就行了,否则有个奇环,那就相当于任意两点都有奇路径了?然后好像变得比较弱智,$\mathrm O(n)$ 。

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <vector>

#include <utility>

#define N 100020

using namespace std;

int a[N];
vector<int> e[N];
int l[N], c[N];
long long s[N];
bool f[N];
vector<int> g;

void DFSA(int x, int v)
{
    int i;

    if(l[x] != -1)
        return;
    l[x] = v;
    s[v] += a[x];

    for(i = 0; i < (signed)e[x].size(); i ++)
        DFSA(e[x][i], v);

    return;
}

void DFSB(int x, bool v)
{
    int i;

    if(c[x] != 2 && c[x] != v)
        throw 0;
    if(c[x] != 2)
        return;
    c[x] = v;
    g.push_back(x);

    for(i = 0; i < (signed)e[x].size(); i ++)
        DFSB(e[x][i], v ^ 1);

    return;
}

long long DFSC(int x)
{
    int i;
    long long o;

    if(f[x])
        return 0;
    f[x] = true;

    for(i = 0, o = s[x]; i < (signed)e[x].size(); i ++)
        o += DFSC(e[x][i]);

    return o;
}

int Scan(void)
{
    int c, s;

    for(s = 0; (c = getchar()) < '0' || c > '9'; )
        ;
    do
        s = s * 10 + (c & 15);
    while((c = getchar()) >= '0' && c <= '9');

    return s;
}

int main(void) // sequence.cpp
{
    int t, n, m, u, v;
    int i, j;
    vector<pair<int, int> > k;
    long long w;

    freopen("sequence.in" , "r", stdin );
    freopen("sequence.out", "w", stdout);

    t = Scan();
    while(t --)
    {
        n = Scan();
        m = Scan();
        for(i = 0; i < n; i ++)
        {
            scanf("%d", &a[i]);
            l[i] = -1;
            s[i] = 0;
            c[i] = 2;
            f[i] = false;
            e[i].clear();
        }
        for(i = 0; i < n; i ++)
            a[i] = Scan() - a[i];

        k.clear();
        for(i = 0; i < m; i ++)
        {
            w = Scan();
            u = Scan() - 1;
            v = Scan() - 1;
            if(w == 1)
                k.push_back(make_pair(u, v));
            else
            {
                e[u].push_back(v);
                e[v].push_back(u);
            }
        }
        for(i = 0; i < n; i ++)
            if(l[i] == -1)
                DFSA(i, i);

        for(i = 0; i < n; i ++)
            e[i].clear();
        for(i = 0; i < (signed)k.size(); i ++)
        {
            e[l[k[i].first ]].push_back(l[k[i].second]);
            e[l[k[i].second]].push_back(l[k[i].first ]);
        }

        for(i = 0; i < n; i ++)
            if(l[i] == i && !f[i] && c[i] == 2)
                try
                {
                    g.clear();
                    DFSB(i, false);
                    for(j = w = 0; j < (signed)g.size(); j ++)
                        w += (c[g[j]] ? 1 : -1) * s[g[j]];
                    if(w)
                        break;
                }
                catch(...)
                {
                    if(DFSC(i) & 1)
                        break;
                }
        printf("%s\n", i == n ? "YES" : "NO");
    }

    return 0;
}

$\text{P2}$

每轮冒泡会把所有逆序对都减少 $1$,单点修改区间求和,$\mathrm O(n\log n)$,感觉可能有点经典的。

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstring>

#define N 200020

using namespace std;

class Fenwick
{
private:
    long long f[N];

    inline int Lowbit(int x)
    {
        return x & -x;
    }

public:
    Fenwick(void)
    {
        return;
    }

    void ClearFenwick(int n)
    {
        memset(f, 0, sizeof(long long) * (n + 1));

        return;
    }

    void AddFenwick(int x, int v, int n)
    {
        if(x)
            for(; x <= n; x += Lowbit(x))
                f[x] += v;

        return;
    }

    long long SumFenwick(int x)
    {
        long long o;

        for(o = 0; x; x -= Lowbit(x))
            o += f[x];

        return o;
    }
};

int a[N], b[N];
Fenwick f, g;

int Scan(void)
{
    int c, s;

    for(s = 0; (c = getchar()) < '0' || c > '9'; )
        ;
    do
        s = s * 10 + (c & 15);
    while((c = getchar()) >= '0' && c <= '9');

    return s;
}

void Print(long long x)
{
    static int b[63];
    int c;

    if(!x)
        putchar('0');
    else
    {
        for(c = 0; x; x /= 10)
            b[c ++] = x % 10;
        while(c --)
            putchar(b[c] + 48);
    }
    putchar('\n');

    return;
}

int main(void) // bubble.cpp
{
    int n, q, p;
    int i;

    freopen("bubble.in" , "r", stdin );
    freopen("bubble.out", "w", stdout);

    n = Scan();
    q = Scan();
    for(i = 1; i <= n; i ++)
    {
        a[i] = Scan();
        b[i] = f.SumFenwick(n) - f.SumFenwick(a[i]);
        f.AddFenwick(a[i], 1, n);
    }
    f.ClearFenwick(n);

    for(i = 1; i <= n; i ++)
    {
        f.AddFenwick(b[i], b[i], n);
        g.AddFenwick(b[i], 1, n);
    }

    while(q --)
    {
        if(Scan() == 1)
        {
            p = Scan();
            f.AddFenwick(b[p], -b[p], n);
            f.AddFenwick(b[p + 1], -b[p + 1], n);
            g.AddFenwick(b[p], -1, n);
            g.AddFenwick(b[p + 1], -1, n);

            swap(b[p], b[p + 1]);
            if(a[p] < a[p + 1])
                b[p + 1] ++;
            else
                b[p] --;
            swap(a[p], a[p + 1]);

            f.AddFenwick(b[p], b[p], n);
            f.AddFenwick(b[p + 1], b[p + 1], n);
            g.AddFenwick(b[p], 1, n);
            g.AddFenwick(b[p + 1], 1, n);
        }
        else
        {
            p = min(n, Scan());
            Print(f.SumFenwick(n) - f.SumFenwick(p) - (long long)p * (g.SumFenwick(n) - g.SumFenwick(p)));
        }
    }

    return 0;
}

$\text{P3}$

也没啥好说的,直接分成 $\gcd(n,\,k)$ 个环然后环内贪心即可,$\mathrm O(n\sqrt n)$ 。如果喜欢可以做到 $\mathrm O(n\log n)$ 。

注意当 $k=\frac{n}{2}$ 的时候每对数需要计算 $2$ 次(

在外面的公告

在结束 $30$ 分钟前发公告,不弹 $\texttt{alert}$,还必须切到外面才能看到,相当的弱智。

更搞笑的是距离比赛结束 $15$ 分钟有个内嵌 $\texttt{alert}$(

请尽快提交答案!

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <functional>

#define N 200020

using namespace std;

int a[N];
long long o[N];

int GCD(int a, int b)
{
    return !b ? a : GCD(b, a % b);
}

long long Solve(int *a, int n)
{
    int i;
    long long o;

    if(n == 1)
        return (long long)a[0] * a[0];
    if(n == 2)
        return (long long)a[0] * a[1] * 2;

    for(i = 1, o = 0; i < n; i += 2)
        o += (long long)a[i] * a[max(0, i - 2)] + (long long)a[min(n - 1, i + 1)] * a[i - 1];

    return o + (n & 1 ? (long long)a[n - 1] * a[n - 2] : 0);
}

int Scan(void)
{
    int c, s;

    for(s = 0; (c = getchar()) < '0' || c > '9'; )
        ;
    do
        s = s * 10 + (c & 15);
    while((c = getchar()) >= '0' && c <= '9');

    return s;
}

void Print(long long x)
{
    static int b[63];
    int c;

    if(!x)
        putchar('0');
    else
    {
        for(c = 0; x; x /= 10)
            b[c ++] = x % 10;
        while(c --)
            putchar(b[c] + 48);
    }
    putchar('\n');

    return;
}

int main(void) // ring.cpp
{
    int n, q, k;
    int i, t;

    freopen("ring.in" , "r", stdin );
    freopen("ring.out", "w", stdout);

    n = Scan();
    q = Scan();
    for(i = 0; i < n; i ++)
        a[i] = Scan();
    sort(a, a + n, greater<int>());

    memset(o, -1, sizeof(o));
    while(q --)
    {
        k = Scan();
        t = GCD(n, k);

        if(o[t] == -1)
            for(i = o[t] = 0; i < t; i ++)
                o[t] += Solve(a + i * (n / t), n / t);
        Print(o[t]);
    }

    return 0;
}

实际上我 $\text{P2}$ 做了 $10^9$ 次冒泡排序,$\text{P3}$ 没记忆化写了个 $n^2$,居然还能有 $280$,可见 $\text{CCF}$ 的用心程度(

$\text{bubble : 100}$