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;
}

Codeforces 671D Roads in Yusland

题目链接

题意:给出一棵以1为根的有n个点的树与m条权值为ci的链,满足在链的两个端点的lca是他们中的一个(即这些链都是竖直的),所有节点至少被一条链覆盖,问最少选出权值和为多少的链满足方案,无解则输出-1。

 

题解:网上的做法大多是按照dfn把链离线之后用线段树维护,比较难写(大概)。然而我在某课件中看到了一种新颖的做法:应用对偶原理,将原问题转化为一个简单(?)的贪心问题,然后就要调很久了简单了很多。

 

先说对偶原理:对于一个线性规划问题,把它写成标准形式之后,大概是一个系数矩阵与未知数向量的积满足一个约束,最大化(或最小化)一个与未知数向量有关的线性表达式。然后对偶原理大概就是把系数矩阵转置,对于每一个约束建立一个变量。可能有点说不清,大概是比较抽象的缘故吧QAQ。(自行Google对偶原理其实也挺好的)

再看这道题,很快地便可以想到一个线性规划的形式,然后对偶一下:

(哇好丑啊)

然后就变成了问给每一条边赋权值,每条链上边权值之和不得大于ci,问总权值的最大值。

然后就用set的启发式合并就好了

代码: https://pastebin.ubuntu.com/p/cmjQ5x4Dv4/

写得很丑,表介意qwq

51Nod 1380 夹克老爷的逢三抽一

题目:51Nod 1380


题意概述:

3k 个数排成一个圆,每次取出一个数,答案加上它的值,并删去左右两边的数,问答案的最大值

思路:

这个题嘛。。。是在贪心专题里边的啦,那自然是贪心无疑了。然而一开始太naive,想了一个看两眼就会觉得是错误的贪心,就不放出来了qwq。实际上正解大概也算是一个带反悔的贪心(应该算是比较常见的操作了吧)。

先考虑另外一个问题:有一个环上有3k个数,要选出k个不相邻的数,使得他们的和最大。
考虑带反悔的贪心:我们贪心地选取最大的值,当我们选出一个点后,删除其左右的点,并在它的位置上加入一个权值为 a_{left} + a_{right} – a_{now} 的船新节点,选取这个节点的意义为:不选取 now 这个节点,而选择 left right 。重复这个过程 k 遍之后遍得到了答案。这个贪心显然是正确的。

然后我们来证明这个问题和原问题是等价的:
由于我们从 3k 个点中选处了 k 个点,并且两两不相邻。所以肯定可以保证存在一个节点使得它的一侧至少有一个与之相邻的空位(不选取的点),另侧至少有两个与之相邻空位。我们删除这个点及其两边的节点,就转化为从 3 (k – 1) 个点中选出 k – 1 个点,并且两两不相邻的问题。在边界条件 k = 1 时取法是存在的,所以根据数学归纳法,总是可以找到一种方案,使得在原问题中可以取出转化后问题的那些选取的点。证明完毕。

代码:

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<LL, int> P;
const int N = 1e5 + 10;
set<P> S;

int l[N], r[N];
LL a[N];

void del(int pos)
{
    l[r[pos]] = l[pos];
    r[l[pos]] = r[pos];
}

int main()
{
    LL ans = 0;
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", a + i);
        l[i] = i == 1 ? n : i - 1;
        r[i] = i == n ? 1 : i + 1;
        S.insert(P(a[i], i));
    }
    for (int i = 1; i <= n / 3; i++)
    {
        int now = S.rbegin()->se;
        ans += a[now];
        S.erase(P(a[now], now));
        a[now] = a[l[now]] + a[r[now]] - a[now];
        S.insert(P(a[now], now));
        S.erase(P(a[l[now]], l[now]));
        S.erase(P(a[r[now]], r[now]));
        del(l[now]), del(r[now]);
    }
    printf("%lld\n", ans);
    return 0;
}

UOJ #213 圣杯战争

既然是圣杯战争,那主题图片就放一张fate的图咯

pid:70587790_p0

题目:UOJ #213


题意概述:

给你一个序列,定义一个连续子序列的贡献为这个序列中的最大值,分别求对于每种长度的所有连续子序列的贡献,输出异或和。

思路:

看到这道题,大概就能想到对于每一个节点计算贡献。考虑维护每一个端点所统治的区间,进行一番分类讨论:

p r_i – i + 1 i – l_i + 1 中较小的一个, q 为较大的一个。
对于 [1, p) 中的所有长度,加上 a_i \times i
对于 [p, q) 中的所有长度,加上 a_i \times p
对于 [q, p + q) 中的所有长度, 加上 (p + q – i) \times a_i
(只要画张图冷静分析一下就好了)

然后看到区间加的操作,大概想到可以差分,但是这里会加入的是 x \times i ,所以可以考虑维护另一个差分数组,将其前缀和乘上 i 加入答案即可。

hint:

有一个小提示我不得不说……就是 l r 中有一个是 \geq 另一个是<,不然会重复计算贡献,不要搞错了(瞪眼瞪了一万年

代码:

这个LL滥用是因为一开始爆int了,懒得一个一个改了233
还有这个 lr ,我的求法可能和大家不是很一样,其他人基本上写得是单调队列,我写的是类似kmp里面fail数组的求法

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 998244353, N = 1e6 + 100;

LL ori[N], a[N], l[N], r[N], d1[N], d2[N];

int main()
{
    LL n, ans = 0;
    scanf("%lld", &n);
    for (LL i = 1; i <= n; i++) scanf("%lld", a + i);
    for (LL i = 1; i <= n; i++)
        for (l[i] = i; l[i] - 1 >= 1 && a[l[i] - 1] <= a[i]; l[i] = l[l[i] - 1]);
    for (LL i = n; i >= 1; i--)
        for (r[i] = i; r[i] + 1 <= n && a[r[i] + 1] < a[i]; r[i] = r[r[i] + 1]);
    for (LL i = 1; i <= n; i++)
    {
        LL p = i - l[i] + 1, q = r[i] - i + 1; if (p > q) swap(p, q);
        d1[1] += a[i], (d1[p] += MOD - a[i]) %= MOD;
        d2[p] += p * a[i], (d2[q] += MOD - p * a[i] % MOD) %= MOD;
        (d1[q] += MOD - a[i]) %= MOD, d1[p + q] += a[i],
        d2[q] += (p + q) * a[i], (d2[p + q] += MOD - (LL)(p + q) * a[i] % MOD) %= MOD;
    }
    for (LL i = 1; i <= n; i++)
    {
        (d1[i] += d1[i - 1]) %= MOD, (d2[i] += d2[i - 1]) %= MOD;
        ans ^= (d1[i] * i + d2[i] + MOD) % MOD;
    }
    printf("%lld\n", ans);
    return 0;
}