2019 Multi-University Training Contests

My input method doesn’t work again. I’ll write this article in English.

Contest 1 Prob A. Blank

Consider record the last appeared position of each number. The order doesn’t matter. Use a simple dp to calculate the answer.

Complexity: O(n^4)

Code:

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
const int N = 111;

void Ad(int &x, int y) { if ((x += y) >= MOD) x -= MOD; }

int l[N], r[N], x[N], pos[N], id[N];

bool cmp(int x, int y)
{
    return r[x] == r[y] ? l[x] < l[y] : r[x] < r[y];
}

int dp[2][N][N][N];

int main()
{
    int T;
    int n = 100, m;
    for (scanf("%d", &T); T--; )
    {
        memset(dp, 0, sizeof dp);
        dp[0][0][0][0] = 1;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; i++) scanf("%d%d%d", l + i, r + i, x + i), id[i] = i;

        sort(id + 1, id + m + 1, cmp);
        for (int i = 1, p = 1, q = 1; i <= n; i++, p ^= 1)
        {
            for (int j = 0; j <= i; j++)
                for (int k = 0; k <= j; k++)
                    for (int t = 0; t <= k; t++)
                        dp[p][j][k][t] = 0;


            for (int j = 0; j < i; j++)
                for (int k = 0; k <= j; k++)
                    for (int t = 0; t <= k; t++)
                    {
                        Ad(dp[p][j][k][t], dp[p ^ 1][j][k][t]);
                        Ad(dp[p][i - 1][j][k], dp[p ^ 1][j][k][t]);
                        Ad(dp[p][i - 1][j][t], dp[p ^ 1][j][k][t]);
                        Ad(dp[p][i - 1][k][t], dp[p ^ 1][j][k][t]);
                    }


            for (; q <= m && r[id[q]] == i; q++)
            {
                for (int j = 0; j < i; j++)
                    for (int k = 0; k <= j; k++)
                        for (int t = 0; t <= k; t++)
                            if ((j >= l[id[q]]) + (k >= l[id[q]]) + (t >= l[id[q]]) + 1 != x[id[q]])
                                dp[p][j][k][t] = 0;
            }
        }

        int ans = 0;
        for (int j = 0; j < n; j++)
            for (int k = 0; k <= j; k++)
                for (int t = 0; t <= k; t++)
                    Ad(ans, dp[n & 1][j][k][t]);
        printf("%d\n", ans);
    }

    return 0;
}

Contest 1 Prob B Operation

This problem shows my ignorance to Linear Base XD.

Build Linear Bases for each prefix of the array. When a new element is append to LB, put its contribution to the highest “1” in binary.
Hmmm, I can’t explain it well. To Be Updated.

Code:

#include <bits/stdc++.h>
using namespace std;
const int N = 500100;

int vec[N][32], pos[N][32];

void append(int p, int x)
{
    memcpy(pos[p], pos[p - 1], 32 * sizeof(int));
    memcpy(vec[p], vec[p - 1], 32 * sizeof(int));
    int curp = p;
    for (int i = 30; i >= 0; i--) if (x >> i)
    {
        if (!vec[p][i])
        {
            vec[p][i] = x, pos[p][i] = curp;
            break;
        }
        if (curp > pos[p][i])
        {
            swap(vec[p][i], x);
            swap(pos[p][i], curp);
        }
        x ^= vec[p][i];
    }
}

int main()
{
    int T;
    for (scanf("%d", &T); T--; )
    {
        int ans = 0;
        int n, m;
        scanf("%d%d", &n, &m);
        int x, opt, l, r;
        for (int i = 1; i <= n; i++) scanf("%d", &x), append(i, x);
        for (int i = 1; i <= m; i++)
        {
            scanf("%d", &opt);
            if (opt == 1)
            {
                scanf("%d", &x);
                append(++n, x ^ ans);
            }
            else
            {
                scanf("%d%d", &l, &r);
                l = (l ^ ans) % n + 1, r = (r ^ ans) % n + 1;
                if (l > r) swap(l, r);
                ans = 0;
                for (int i = 30; i >= 0; i--)
                {
                    if (pos[r][i] >= l && (ans ^ vec[r][i]) > ans)
                        ans ^= vec[r][i];
                }
                printf("%d\n", ans);
            }
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注