联赛Day2

Posted on Edited on In Word count in article: 1.9k Reading time ≈ 7 mins.
联赛Day2

T1

对所有的边建一张新图，可以发现，图中所有的环一定都是长度为偶数的，那么对于每个环的方案数就是 \(2\)，用并查集就可以了

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <cstdio>

using namespace std;

const int maxn = 1e5 + 10;
const int mod = 998244353;

int f[maxn << 1], in[maxn], out[maxn];

int find(int x)
{
	if (x == f[x]) return x;
	return f[x] = find(f[x]);
}

inline void merge(int x, int y)
{
	f[find(x)] = find(y);
}

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

int main()
{
	int n = __read() << 1;
	for (int i = 1; i <= n; ++i) f[i] = i;
	for (int i = 1; i <= n; ++i) {
		int u = __read(), v = __read();

		if (in[v]) merge(in[v], i);
		else in[v] = i;

		if (out[u]) merge(out[u], i);
		else out[u] = i;
	}

	int ans(1);
	for (int i = 1; i <= n; ++i) 
		if (f[i] == i) ans = ans * 2 % mod;
	printf ("%d\n", ans);
}

T2

题目可以转化一下，因为对于一个 \(a[i]!=i\) 的东西来说，这个点可以是左移，也可以是右移那么就可以得到一系列 \(p_i\) 的关系，那么就可以根据建立的 \(p_i\) 的关系来做一个 \(n^2\) 的 \(dp\)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;
const int maxn = 5e3 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

int a[maxn], d[maxn], f[maxn];
int pre[maxn], suf[maxn];

inline int add(int x, int y)
{
    x += y;
    if (x >= mod) return x - mod;
    return x;
}

int main()
{
    int n = __read();
    for (int i = 1; i <= n; ++i) {
        a[i] = __read() + 1;
        if (a[i] == i) return puts("0"), 0;
        if (i > a[i]) {
            if (a[i] > 1) {
                if (d[a[i] - 1] == 2)return puts("0"), 0;
                else d[a[i] - 1] = 1;
            } 
            if (i < n) {
                if (d[i - 1] == 2)return puts("0"), 0;
                else d[i - 1] = 1;
            }
            for (int j = a[i]; j < i - 1; ++j) {
                if (d[j] == 1) return puts("0"), 0;
                else d[j] = 2;
            }
        } else {
            if (a[i] < n) {
                if (d[a[i] - 1] == 1) return puts("0"), 0;
                else d[a[i] - 1] = 2;
            }
            if (i > 1) {
                if (d[i - 1] == 1) return puts("0"), 0;
                else d[i - 1] = 2;
            }
            for (int j = i; j < a[i] - 1; ++j) {
                if (d[j] == 2) return puts("0"), 0;
                else d[j] = 1;
            }
        }
    }
    f[1] = pre[1] = suf[1] = 1;
    for (int i = 1; i < n - 1; ++i) {
        if (d[i] == 1) 
            for (int j = 1; j <= i + 1; ++j)
                f[j] = pre[j - 1];
        else  
            for (int j = i + 1; j; --j)
                f[j] = suf[j];
        for (int j = 1; j <= i + 1; ++j) pre[j] = add(pre[j - 1], f[j]);
        for (int j = i + 1; j >= 1; --j) suf[j] = add(suf[j + 1], f[j]);
    }
    int ans(0);
    for (int i = 1; i < n; ++i) 
        ans = add(ans, f[i]);
    printf ("%d\n", ans);
}

T3

就是一个构造，显然对于 \(n=2\land m=2\) 的情况一定是有解的

那么对于所有的情况，都可以先把最外面的两层清空（一个角的就可以了），如果此时矩阵空了那就是其中一个解，否则无解，为什么呢？

0h4sfO.png

这是个什么意思呢？

就是三个 \(+\) 的和应该与三个 \(-\) 的和相等才有解（行列消一下就可以了），所以对于所有的操作，这个值都是不会发生改变的，既三个 \(+\) 减去三个 \(-\) 的值恒为 \(0\)

然后可以暴力构造出这样的零

0hT8b9.png

既被红色部分框起来的都是 \(0\)，那么右下角的那一个一定是 \(0\)，同理可以退出整张表都是零，证毕

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;
const int maxn = 2e3 + 10;
const int mod = 1e9 + 7;
const int dlta = 1e3;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

void print(ll x)
{
    if (x / 10) print(x / 10);
    putchar(x % 10 + '0');
}

int n, m, top;
int a[maxn][maxn];
ll dx[maxn], dy[maxn], dk[maxn];
//to get the change in O(1)
ll opt[maxn << 2], pos[maxn << 2], del[maxn << 2];
//handicraft stack，to store answers

inline ll g(int x, int y)
{
    return dx[x] + dy[y] + dk[y - x + dlta] + a[x][y];
}

inline void Push(int Opt, int Pos, ll delta)
{
    opt[++top] = Opt, pos[top] = Pos, del[top] = delta;
    if (Opt == 1) dx[Pos] += delta;
    else if (Opt == 2) dy[Pos] += delta;
    else dk[Pos + dlta] += delta;
}

inline bool check()
{
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (g(i, j)) return 1;
    return 0;
}

int main()
{
    n = __read(), m = __read();
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            a[i][j] = __read();

    for (int i = n; i >= 1; --i) {
        if (g(i, 1)) Push (1, i, -g(i, 1));
        if (g(i, 2)) Push (3, 2 - i, -g(i, 2));
    }

    for (int i = 3; i <= m; ++i) {
        if (g(2, i)) Push (2, i, -g(2, i));
        if (g(1, i)) Push (3, i - 1, -g(1, i));
    }

    if (check()) puts("-1");
    else {
        printf ("%d\n", top);
        for (int i = 1; i <= top; ++i) {
            printf ("%lld %lld %lld\n", opt[i], pos[i], del[i]);
        }
    }
}

T4

求： \[ ans = \max{s_1s_2+s_2s_3+\cdots+s_ks_{k+1}} \] 这个很容易能发现是一个斜率 \(dp\), 但是对于有负数的点，会出一点小问题

于是考场写了一个 \(O(n^3)\) 的 \(dp\)，结果因为点可以是负的，但是我全部初始化为 \(0\)，显然这是错误的

应该全初始化为 \(-inf\) 才对，害，愉快挂掉

Code(30)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;
const int maxn = 5000 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f; 

inline ll __read()
{
    ll x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

ll s[maxn], ans(-0x6fffffffffffffff);
ll f[maxn][maxn];

int main()
{
    int n = __read();
    for (int i = 1;  i <= n; ++i) 
        s[i] = s[i - 1] + __read();
    memset (f, 128, sizeof f);
    for (int i = 1; i <= n; ++i) {
        f[i][0] = 0;
        for (int j = 0; j < i; ++j)
            for (int k = 0; k < j; ++k)
                f[i][j] = max(f[i][j], f[j][k] + (s[i] - s[j]) * (s[j] - s[k]));
    }
        
    for (int i = 0; i <= n; ++i)
        ans = max(ans, f[n][i]);
    printf("%lld\n", ans);
}

然后来看看正解：

考虑 \(f(i,j)\) 表示当前 \(dp\) 到了 \(i\)，上一个区间右端点为 \(j\) 时的最优答案。则显然有： \[ f(i,j)=\max_{0\le k<j}f(j,k)+(s_i-s_j)(s_j-s_k) \] 显然这是一个斜率优化的式子，扔掉只和 \(i,j\) 有关的常数项，则可以写作： \[ f(i,j)=p+\max_{0\le k<j}f(j,k)-t\times s_k \] 若对于 \(s_a<s_b\) 有 \(f(j,a)-t\times s_a<f(j,b)-t\times s_b\)，那么显然： \[ \frac{f(j,a)-f(j,b)}{s_a-s_b}>t \] 于是我们枚举 \(j\)，按照 \(s\) 排序后暴力维护出一个斜率递减的上凸壳。注意到 \(t = s_i − s_j\) ，我们再按照 \(s_i\) 从大到小枚举 \(i\)，就可以贪心地从凸包前面删点了。

Code(100)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;
const int maxn = 5000 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f; 

inline ll __read()
{
    ll x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

int id[maxn];
ll f[maxn][maxn];
ll s[maxn];

struct Node
{
    ll x, y;
}t[maxn];

inline bool cmp(int x, int y)
{
    return s[x] < s[y];
}

inline bool check(Node a, Node b, Node c)
{
    return (b.y - a.y) * (c.x - a.x) > (c.y - a.y) * (b.x - a.x);
}

int main()
{
    int n = __read();
    for (int i = 1;  i <= n; ++i) 
        s[i] = s[i - 1] + __read(), id[i] = i;
    sort (id, id + n + 1, cmp);
    for (int i = 1; i <= n; ++i) {
        int head(1), tail(0);
        for (int j = 0; j <= n; ++j) {
            if (id[j] < i) {
                Node now = (Node){s[id[j]], f[i][id[j]]};
                while (head < tail && !check(t[tail - 1], t[tail], now)) tail--;
                t[++tail] = now;
            }
        }
        for (int j = n; j >= 0; --j) {
            if (id[j] > i) {
                ll st = (s[id[j]] - s[i]);
                while (head < tail && (t[head].y - t[head + 1].y) <= st * (t[head].x - t[head + 1].x)) ++head;
                f[id[j]][i] = t[head].y + (s[id[j]] - s[i]) * (s[i] - t[head].x);
            }
        }
    }
    ll ans(0);
    for (int i = 0; i < n; ++i) 
        ans = max(ans, f[n][i]);
    printf ("%lld\n", ans);
}