目录
2021“MINIEYE杯”中国大学生算法设计超级联赛（2）【解题报告】
The___Flash
编辑于 2021年08月09日 09:51

Replay

Problem A. I love cube

代码实现

代码块
C++
自动换行
复制代码
#include <bits/stdc++.h>
using namespace std;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch))
    {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

typedef long long ll;
typedef unsigned long long ull;

const int M = (int)1e5;
const int N = (int)1e5;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;

ll quick(ll a, ll b, ll p = mod)
{
    ll s = 1;
    while(b)
    {
        if(b & 1) s = s * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return s;
}

ll inv(ll n, ll p = mod)
{
    return quick(n, p - 2, p);
}

void work()
{
    ll n; scanf("%lld", &n);
    if(n == 1)
    {
        printf("0\n");
        return;
    }
    --n;
    n = n % mod;
    ll ans = n * (n + 1) % mod * inv(2) % mod;
    ans = ans * ans % mod;
    ans = ans * 8 % mod;
    printf("%lld\n", ans);
}

int main()
{
//    cout << 5 * log2(inf) * (M + 2 * N) << "\n";
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
    int T; scanf("%d", &T);
    for(int ca = 1; ca <= T; ++ca)
    {
//        printf("Case #%d:\n", ca);
        work();
    }
//    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}
复制成功

Problem B. I love tree

代码实现

代码块
C++
自动换行
复制代码
#include <bits/stdc++.h>
using namespace std;

template <typename T>
void read(T& n)
{
    n = 0; int f = 1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
    while( isdigit(ch)) {n = n * 10 + ch - '0', ch = getchar();}
    n *= f;
}

template <typename T>
void print(T n)
{
    if(n < 0) putchar('-'), n = -n;
    if(n > 9) print(n / 10);
    putchar(n % 10 + '0');
}

template <typename T>
void print(T n, char ch)
{
    print(n), putchar(ch);
}

typedef __int128 ll;

const int M = (int)1e5;

namespace TA
{
    struct TA
    {
        int n; ll tree[M + 5];
        void init(int _n) {n = _n; for(int i = 0; i <= n; ++i) tree[i] = 0;}
        inline int lowbit(int n) {return n&-n;}
        void add(int a, ll b) {for(int i = a; i <= n; i += lowbit(i)) tree[i] += b;}
        ll ask(int r) {ll s = 0; for(int i = r; i; i -= lowbit(i)) s += tree[i]; return s;}
    } t[5];

    void getUpdate(ll d[], ll b[], ll len)
    {
        d[0] = b[0] + b[1] + b[2];
        d[1] = -2 * b[0] - b[1] + b[2];
        d[2] = b[0];
        d[3] = -b[0] - (len + 1) * b[1] - (len + 1) * (len + 1) * b[2];
        d[4] = 2 * b[0] + (2 * len + 1) * b[1] + (2ll * len * len + 2 * len - 1) * b[2];
        d[5] = -b[0] - len * b[1] - len * len * b[2];
    }

    void add(int l, int r, ll b[])
    {
        ll d[6]; getUpdate(d, b, r - l + 1);
        ll p[6] = {l, l + 1, l + 2, r + 1, r + 2, r + 3}, pw[6] = {1, 1, 1, 1, 1, 1};
        for(int j = 1; j < 5; ++j)
        {
            for(int k = 0; k < 6; ++k)
            {
                t[j].add(p[k], pw[k] * d[k]);
                pw[k] *= p[k];
            }
        }
    }

    void getQuery(ll d[], ll r)
    {
        d[1] = r * r * r + 6 * r * r + 11 * r + 6;
        d[2] = -(3 * r * r + 12 * r + 11);
        d[3] = 3 * r + 6;
        d[4] = -1;
    }

    ll ask(int r)
    {
        ll d[5], s = 0; getQuery(d, r);
        for(int i = 1; i < 5; ++i) s += d[i] * t[i].ask(r);
        s /= 6;
        return (s + t[0].ask(r));
    }

    ll ask(int l, int r)
    {
        return ask(r) - ask(l - 1);
    }
}

namespace HLD
{
    int cnt, head[M + 5];

    struct enode
    {
        int v, nx;
    } Edge[M * 2 + 5];

    int fa[M + 5];
    int sz[M + 5];
    int dep[M + 5];
    int son[M + 5];
    int top[M + 5];
    int rnk[M + 5];
    int dfn[M + 5], dfnCnt;

    void init(int n)
    {
        cnt = 0;
        for(int i = 1; i <= n; ++i)
        {
            head[i] = -1;
        }
    }

    void add(int u, int v)
    {
        Edge[cnt].v = v;
        Edge[cnt].nx = head[u];
        head[u] = cnt++;
    }

    void dfs1(int u, int f)
    {
        fa[u] = f, sz[u] = 1, son[u] = -1;
        for(int i = head[u]; ~i; i = Edge[i].nx)
        {
            int v = Edge[i].v;
            if(v == f) continue;
            dep[v] = dep[u] + 1;
            dfs1(v, u);
            sz[u] += sz[v];
            if(son[u] == -1 || sz[son[u]] < sz[v]) son[u] = v;
        }
    }

    void dfs2(int u, int tp)
    {
        top[u] = tp, dfn[u] = ++dfnCnt, rnk[dfnCnt] = u;
        if(son[u] == -1)    return;
        dfs2(son[u], tp);
        for(int i = head[u]; ~i; i = Edge[i].nx)
        {
            int v = Edge[i].v;
            if(v == fa[u] || v == son[u])   continue;
            dfs2(v, v);
        }
    }

    void update(int x, int y)
    {
        int l = 1, r = 0, xx = x, yy = y, fx = top[x], fy = top[y];
        while(fx != fy)
        {
            if(dep[fx] > dep[fy]) r += dep[x] - dep[fx] + 1, x = fa[fx], fx = top[x];
            else                  r += dep[y] - dep[fy] + 1, y = fa[fy], fy = top[y];
        }
        if(dfn[x] < dfn[y]) r += dep[y] - dep[x] + 1;
        else                r += dep[x] - dep[y] + 1;
        x = xx, y = yy, fx = top[x], fy = top[y]; ll b[3]; int len;
        while(fx != fy)
        {
            if(dep[fx] > dep[fy])
            {
                len = dep[x] - dep[fx] + 1;
                b[0] = 1ll * (l + len) * (l + len);
                b[1] = -2 * (l + len);
                b[2] = 1;
                l += len;
                TA::add(dfn[fx], dfn[x], b), x = fa[fx], fx = top[x];
            }
            else
            {
                len = dep[y] - dep[fy] + 1;
                b[0] = 1ll * (r - len) * (r - len);
                b[1] = 2 * (r - len);
                b[2] = 1;
                r -= len;
                TA::add(dfn[fy], dfn[y], b), y = fa[fy], fy = top[y];
            }

        }
        if(dfn[x] < dfn[y])
        {
            len = dep[y] - dep[x] + 1;
            b[0] = 1ll * (r - len) * (r - len);
            b[1] = 2 * (r - len);
            b[2] = 1;
            TA::add(dfn[x], dfn[y], b);
        }
        else
        {
            len = dep[x] - dep[y] + 1;
            b[0] = 1ll * (l + len) * (l + len);
            b[1] = -2 * (l + len);
            b[2] = 1;
            TA::add(dfn[y], dfn[x], b);
        }
    }
}

void work()
{
    int n; read(n); HLD::init(n);
    for(int i = 2, u, v; i <= n; ++i)
    {
        read(u); read(v);
        HLD::add(u, v), HLD::add(v, u);
    }
    HLD::dep[1] = 1;
    HLD::dfs1(1, 0);
    HLD::dfs2(1, 1);
    for(int i = 0; i < 5; ++i) TA::t[i].init(n);
    int q; read(q);
    for(int i = 1, op, a, b, x; i <= q; ++i)
    {
        read(op);
        if(op == 1)
        {
            read(a), read(b);
            HLD::update(a, b);
        }
        else if(op == 2)
        {
            read(x);
            print(TA::ask(HLD::dfn[x], HLD::dfn[x]), '\n');
        }
    }
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}
复制成功

Problem C. I love playing games

Problem D. I love counting

代码实现

代码块
C++
自动换行
复制代码
#include <bits/stdc++.h>
using namespace std;

template <typename T>
inline void read(T& x)
{
    x = 0; int f = 1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
    while(isdigit(ch))  {x = x * 10 + ch - '0', ch = getchar();}
    x *= f;
}

template <typename T>
void print(T x)
{
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

template <typename T>
void print(T x, char ch)
{
    print(x), putchar(ch);
}

typedef long long ll;
typedef unsigned long long ull;

const int M = (int)1e5;
const int N = (int)16;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;

int n, q;
int c[M + 5];
struct qnode
{
    int l, r, a, b, id;
    bool operator<(const qnode& b)const
    {
        return r < b.r;
    }
} s[M + 5];

int tot;
struct trieNode
{
    int cnt, nx[2];
} trie[(N + 1) * M * 17 / 2 + 5];

int tree[M + 5];
int pre[M + 5];
int ans[M + 5];

inline int lowbit(int n)
{
    return n&-n;
}

void add(int rt, int a, int b)
{
    int p = rt, u;
    trie[p].cnt += b;
    for(int i = N; i >= 0; --i)
    {
        u = (a>>i&1);
        if(!trie[p].nx[u]) trie[p].nx[u] = ++tot;
        p = trie[p].nx[u];
        trie[p].cnt += b;
    }
}

int add(int p, int x)
{
    for(int i = p; i <= n; i += lowbit(i)) add(tree[i], c[p], x);
}

int query(int rt, int a, int b)
{
    int p = rt, ua, ub, v0, v1, ans = 0;
    for(int i = N; i >= 0; --i)
    {
        ua = (a>>i&1), ub = (b>>i&1);
        v0 = trie[p].nx[0], v1 = trie[p].nx[1];
        if(!ua && !ub)
        {
            if(!v0 && !v1)     assert(0);
            else if(!v0 && v1) return ans;
            else if(v0 && !v1) p = v0;
            else if(v0 && v1)  p = v0;
        }
        else if(!ua && ub)
        {
            if(!v0 && !v1)     assert(0);
            else if(!v0 && v1) p = v1;
            else if(v0 && !v1) return ans += trie[v0].cnt;
            else if(v0 && v1)  ans += trie[v0].cnt, p = v1;
        }
        else if(ua && !ub)
        {
            if(!v0 && !v1)     assert(0);
            else if(!v0 && v1) p = v1;
            else if(v0 && !v1) return ans;
            else if(v0 && v1)  p = v1;
        }
        else if(ua && ub)
        {
            if(!v0 && !v1)     assert(0);
            else if(!v0 && v1) return ans += trie[v1].cnt;
            else if(v0 && !v1) p = v0;
            else if(v0 && v1)  ans += trie[v1].cnt, p = v0;
        }
    }
    ans += trie[p].cnt;
    return ans;
}

int ask(int r, int a, int b)
{
    int ans = 0;
    for(int i = r; i; i -= lowbit(i)) ans += query(tree[i], a, b);
    return ans;
}

int query(int l, int r, int a, int b)
{
    return ask(r, a, b) - ask(l - 1, a, b);
}

void work()
{
    read(n);
    for(int i = 1; i <= n; ++i) read(c[i]);
    read(q);
    for(int i = 1; i <= q; ++i) read(s[i].l), read(s[i].r), read(s[i].a), read(s[i].b), s[i].id = i;
    sort(s + 1, s + q + 1);
    for(int i = 1; i <= n; ++i) tree[i] = ++tot;
    for(int i = 1, r = 0; i <= q; ++i)
    {
        while(r < s[i].r)
        {
            ++r;
            if(pre[c[r]]) add(pre[c[r]], -1);
            add(r, 1);
            pre[c[r]] = r;
        }
        ans[s[i].id] = query(s[i].l, s[i].r, s[i].a, s[i].b);
    }
    for(int i = 1; i <= q; ++i) print(ans[i], '\n');
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
//    int T; scanf("%d", &T);
//    for(int ca = 1; ca <= T; ++ca)
//    {
////        printf("Case #%d: ", ca);
//        work();
//    }
    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}
复制成功

Problem E. I love string

代码实现

代码块
C++
自动换行
复制代码
#include <bits/stdc++.h>
using namespace std;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch))
    {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

typedef long long ll;
typedef unsigned long long ull;

const int M = (int)1e5;
const int N = (int)1e5;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;

int n;
char s[M + 5];

ll quick(ll a, ll b, ll p = mod)
{
    ll s = 1;
    while(b)
    {
        if(b & 1) s = s * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return s;
}

void work()
{
    scanf("%d", &n);
    scanf("%s", s + 1);
    int c = 0;
    char l = s[1], r = s[1];
    for(int i = 2; i <= n; ++i)
    {
        if(l == r && s[i] == l) ++c;
        if(s[i] <= l) l = s[i];
        else          r = s[i];
    }
    printf("%lld\n", quick(2, c));
}

int main()
{
//    cout << 5 * log2(inf) * (M + 2 * N) << "\n";
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
    int T; scanf("%d", &T);
    for(int ca = 1; ca <= T; ++ca)
    {
//        printf("Case #%d:\n", ca);
        work();
    }
//    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}
复制成功

Problem F. I love sequences

Problem G. I love data structure

Problem H. I love exam

代码实现

代码块
C++
自动换行
复制代码
include <bits/stdc++.h>
using namespace std;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch))
    {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

typedef long long ll;
typedef unsigned long long ull;

const int M = (int)51;
const int N = (int)11;
const int O = 501;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)998244353;

int n, m, t, p;
map<string, int> id;
int c[M][N][N];
int f[M][O];
int q[O + 5];
int g[M][O][4];

void init()
{
    id.clear();
    memset(c, 0, sizeof(c));
}

inline int calc(int i, int u, int V, int W, int k)
{
    return f[i][u + k * V] - k * W;
}

void manyBag()
{
    memset(f, -inf, sizeof(f));
    for(int i = 1; i <= n; ++i)
    {
        f[i][0] = 0;
        for(int V = 1; V <= 10; ++V)
        {
            for(int W = 1; W <= 10; ++W)
            {
                int C = c[i][V][W];
                for(int u = 0; u < V; ++u)
                {
                    int l = 1, r = 0;
                    int maxp = (t - u) / V;
                    for(int k = maxp - 1; k >= max(maxp - C, 0); --k)
                    {
                        while(l <= r && calc(i, u, V, W, q[r]) <= calc(i, u, V, W, k)) --r;
                        q[++r] = k;
                    }
                    for(int p = maxp; p >= 0; --p)
                    {
                        while(l <= r && q[l] > p - 1) ++l;
                        if(l <= r) f[i][u + p * V] = max(f[i][u + p * V],
                                                         calc(i, u, V, W, q[l]) + p * W);
                        if(p - C - 1 >= 0)
                        {
                            while(l <= r &&
                                  calc(i, u, V, W, q[r]) <= calc(i, u, V, W, p - C - 1)) --r;
                            q[++r] = p - C - 1;
                        }
                    }
                }
            }
        }
    }
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 0; j <= t; ++j) f[i][j] = min(f[i][j], 100);
    }
}

void groupBag()
{
    memset(g, -inf, sizeof(g));
    g[0][0][0] = 0;
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 0; j <= t; ++j)
        {
            for(int l = 0; l <= p; ++l)
            {
                for(int k = 0; k <= j; ++k)
                {
                    if(l > 0 && f[i][k] < 60)
                    {
                        g[i][j][l] = max(g[i][j][l], g[i - 1][j - k][l - 1] + f[i][k]);
                    }
                    if(f[i][k] >= 60)
                    {
                        g[i][j][l] = max(g[i][j][l], g[i - 1][j - k][l] + f[i][k]);
                    }
                }
            }
        }
    }
}

void work()
{
    init();
    cin >> n;
    string name;
    for(int i = 1; i <= n; ++i)
    {
        cin >> name;
        id[name] = i;
    }
    cin >> m;
    for(int i = 1, x, y; i <= m; ++i)
    {
        cin >> name >> x >> y;
        ++c[id[name]][y][x];
    }
    cin >> t >> p;
    manyBag();
    groupBag();
    int mx = -1;
    for(int j = 0; j <= t; ++j)
    {
        for(int k = 0; k <= p; ++k) mx = max(mx, g[n][j][k]);
    }
    cout << mx << "\n";
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T; cin >> T;
    for(int ca = 1; ca <= T; ++ca)
    {
//        printf("Case #%d:\n", ca);
        work();
    }
//    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}
复制成功

Problem I. I love triples

Problem J. I love permutation

Problem K. I love max and multiply

代码实现

代码块
C++
自动换行
复制代码
#include <bits/stdc++.h>
using namespace std;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch))
    {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

typedef long long ll;
typedef unsigned long long ull;

const int M = (int)3e5;
const int N = (int)18;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)998244353;

int n;
int a[M + 5];
int b[M + 5];
int aMax[M + 5], aMin[M + 5];
int bMax[M + 5], bMin[M + 5];

void init()
{
    memset(aMax, -inf, sizeof(aMax)), memset(aMin, inf, sizeof(aMin));
    memset(bMax, -inf, sizeof(bMax)), memset(bMin, inf, sizeof(bMin));
    for(int i = n - 1; i >= 0; --i)
    {
        aMax[i] = aMin[i] = a[i];
        bMax[i] = bMin[i] = b[i];
        for(int j = 0; j <= N; ++j)
        {
            if(!(i>>j&1) && (i|(1<<j)) < n)
            {
                aMax[i] = max(aMax[i], aMax[i|(1<<j)]);
                aMin[i] = min(aMin[i], aMin[i|(1<<j)]);
                bMax[i] = max(bMax[i], bMax[i|(1<<j)]);
                bMin[i] = min(bMin[i], bMin[i|(1<<j)]);
            }
        }
    }
}

ll c[M + 5];

void work()
{
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) scanf("%d", &a[i]);
    for(int i = 0; i < n; ++i) scanf("%d", &b[i]);
    init();
    c[n - 1] = 1ll * a[n - 1] * b[n - 1];
    for(int i = n - 2; i >= 0; --i)
    {
        c[i] = c[i + 1];
        c[i] = max(c[i], 1ll * aMin[i] * bMin[i]);
        c[i] = max(c[i], 1ll * aMax[i] * bMax[i]);
        c[i] = max(c[i], 1ll * aMax[i] * bMin[i]);
        c[i] = max(c[i], 1ll * aMin[i] * bMax[i]);
//        printf("c[%d] = %lld\n", i, c[i]);
    }
    ll s = 0;
    for(int i = 0; i < n; ++i) s = (s + c[i] % mod) % mod;
    s = (s % mod + mod) % mod;
    printf("%lld\n", s);
}

int main()
{
//    cout << 5 * log2(inf) * (M + 2 * N) << "\n";
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
    int T; scanf("%d", &T);
    for(int ca = 1; ca <= T; ++ca)
    {
//        printf("Case #%d:\n", ca);
        work();
    }
//    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}
复制成功

Problem L. I love 114514

代码实现

代码块
C++
自动换行
复制代码
#include <bits/stdc++.h>
using namespace std;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch))
    {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

typedef long long ll;
typedef unsigned long long ull;

const int M = (int)1e5;
const int N = (int)1e5;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)998244353;

void work()
{
    string s;
    cin >> s;
    if(s.find("114514") != string::npos) cout << "AAAAAA\n";
    else cout << "Abuchulaile\n";
}

int main()
{
//    cout << 5 * log2(inf) * (M + 2 * N) << "\n";
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
    int T; scanf("%d", &T);
    for(int ca = 1; ca <= T; ++ca)
    {
//        printf("Case #%d:\n", ca);
        work();
    }
//    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}
复制成功

本文为我原创，未经授权禁止转载
cv12562868