Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

联合省选 2021 A卷

发表于 分类于
本文字数： 22k 阅读时长 ≈ 20 分钟
标签：                                    

代码量小，很智慧的一套题。

Day 1

T1 P7514 [省选联考 2021 A/B 卷] 卡牌游戏

首先发现一个性质，注意到 $a _ i$ 是递增的，那么 $a _ {i - 1} < a _ i < a _ {i + 1}$ ，$a _ i$ 是不会成为极差中的一个的，着意味着再翻牌时，一个数左右都没有翻，那么这个数是完全没有必要翻的。于是，进一步，翻的牌只会在序列左侧的前缀和右侧的后缀。预处理出前缀最值和后缀最值，枚举两个分界点，可以在 $O(n ^ 2)$ 内完成。

考虑二分答案，确定了极差，枚举左侧的分界点，那么右侧的分界点的可能的最后的位置是单调递增的，所以考虑双指针。如何将所有的情况都考虑到，将所有的两个指针移动的后的情况都来判断答案，仍有可能遗漏。如当前左指针 $l$ 右指针 $r$ 是一个极大的区间。那么 $[l, k] (k \in [l, r])$ 都可以成为一种决策，我们也考虑到了。但是当 $l$ 向后移动一格后，成为 $l + 1$ ， $[l + 1, k] (k \in [l + 1, r - 1])$ 就没有被考虑了，也就是样例中我们最后构造的答案和样例解释中是不一样的。正确性有待证明。感性地理解一下，因为指针范围内是合法的，最开始没有成功是因为后面需要翻的牌控制了最值。如果控制着最小值，那么左指针移动不可能减小最小值，不会成功；如果控制着最大值，我们就需要尽快让左指针移动使得相应的右指针移动覆盖掉控制着最大值的位置，否则一直没有解。

查看代码 
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
#include <cstdio>
#include <algorithm>
using namespace std;
void chkmax(int &x, int k)
{
    (x < k) && (x = k);
}
void chkmin(int &x, int k)
{
    (x > k) && (x = k);
}
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 1e6 + 10, inf = 1e9;
int n, m, w[N], v[N], mn1[N], mx1[N], mn2[N], mx2[N];
bool check(int x)
{
    for (int i = 1, j = 1; i <= n; i++)
        for (; j <= n && w[j] - w[i] <= x; j++)
        {
            int mn = min(mn1[i - 1], mn2[j + 1]), mx = max(mx1[i - 1], mx2[j + 1]);
            chkmin(mn, w[i]), chkmax(mx, w[j]);
            if (mx - mn <= x && n - (j - i + 1) <= m)
                return true;
        }
    return false;
}
int main()
{
    read(n), read(m);
    int l = inf, r = 1;
    for (int i = 1; i <= n; i++)
    {
        read(w[i]);
        chkmin(l, w[i]), chkmax(r, w[i]);
    }
    for (int i = 1; i <= n; i++)
        read(v[i]);
    for (int i = 1, mn = inf, mx = 1; i <= n; i++)
    {
        chkmin(mn, v[i]), chkmax(mx, v[i]);
        mn1[i] = mn, mx1[i] = mx;
    }
    for (int i = n, mn = inf, mx = 1; i; i--)
    {
        chkmin(mn, v[i]), chkmax(mx, v[i]);
        mn2[i] = mn, mx2[i] = mx;
    }
    mn1[0] = mn2[n + 1] = inf;
    r -= l, l = 0;
    int res = r;
    while (l <= r)
    {
        int mid = l + r >> 1;
        check(mid) ? (res = mid, r = mid - 1) : l = mid + 1;
    }
    printf("%d", res);
    return 0;
}

T2 P7515 [省选联考 2021 A 卷] 矩阵游戏

如果不考虑对原矩阵数的范围的限制，那么可以随便构造。显然如果这个矩阵的第一行第一列全部确定了，那么这个矩阵就可以确定了。让第一行第一列全部是 $0$ ，然后递推即可。现在有了对原矩阵数的范围的限制，即有了很多个不等式，那么可以考虑差分约束。现在我们要对矩阵进行变换，使得矩阵依然合法的情况下调整为范围内的数。可以发现，对于每一行或一列，按照加减加减的顺序依次变化一个值，依然合法，因为任意两个相邻的数的和都是 $0$ 。这样做一定可以使得所有的情况被包含，因为第一行第一列可以随便操作。

现在一共有 $n + m$ 次变换，设第 $i$ 行变化的数为 $r _ i$ ，第 $j$ 列变化的数为 $c _ j$ 。对于第一行，变化应为 $+r _ 1, - r _ 1, +r _ 1, - r _ 1\ldots $ 。对于差分约束，需要两个数的差才能做。那么对于第一个数，列上的变化一定要减，即对于第一列，变化为 $-c _ 1, + c _ 1, -c _ 1, + c _ 1 \ldots $ 。可以发现，对于行列和为奇数的点，可以 $+r _ i - c _ j$ ，为偶数的点，可以为 $-r _ i + c _ j$ 。那么不等式可以写作：
$$
0 \le a _ {i, j} \pm r _ i \mp c _ j \le 1000000
$$
$a _ {i, j}$ 是确定的，于是可以写作关于 $r _ i$ 和 $c _ j$ 的不等式，差分约束解即可。

查看代码 
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 310, M = 2e5 + 10, inf = 1e6;
int n, m, A[N][N];
bool vis[N << 1];
LL d[N << 1], wt[M];
int cnt[N << 1];
struct Edge
{
    int v, w;
};
vector<Edge> e[N << 1];
void add(int a, int b, int c)
{
    e[a].push_back((Edge){b, c});
}
bool spfa()
{
    queue<int> q;
    for (int i = 0; i < n + m; i++)
    {
        d[i] = 0;
        q.push(i);
        vis[i] = true;
        cnt[i] = 0;
    }
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        vis[t] = false;
        for (Edge i : e[t])
            if (d[t] + i.w > d[i.v])
            {
                d[i.v] = d[t] + i.w;
                cnt[i.v]++;
                if (cnt[i.v] > n + m)
                    return false;
                if (!vis[i.v])
                {
                    q.push(i.v);
                    vis[i.v] = true;
                }
            }
    }
    return true;
}
int main()
{
    int T;
    read(T);
    while (T--)
    {
        read(n), read(m);
        for (int i = 0; i < n; i++)
            A[i][0] = 0;
        for (int j = 0; j < m; j++)
            A[0][j] = 0;
        for (int i = 1; i < n; i++)
            for (int j = 1, a; j < m; j++)
            {
                read(a);
                A[i][j] = a - A[i - 1][j] - A[i][j - 1] - A[i - 1][j - 1];
            }
        for (int i = 0; i < n + m; i++)
            e[i].clear();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (i + j & 1)
                {
                    add(j + n, i, -A[i][j]);
                    add(i, j + n, A[i][j] - inf);
                }
                else
                {
                    add(i, j + n, -A[i][j]);
                    add(j + n, i, A[i][j] - inf);
                }
        if (!spfa())
        {
            puts("NO");
            continue;
        }
        puts("YES");
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                A[i][j] += i + j & 1 ? d[i] - d[j + n] : d[j + n] - d[i];
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
                write(A[i][j]), putchar(' ');
            puts("");
        }
    }
    return 0;
}

T3 P7516 [省选联考 2021 A/B 卷] 图函数

Algorithm I Floyd $O(n ^ 3 + m)$ 44-80 pts

  • $v > u$ ，点 $v$ 不会对 $f(u, G)$ 有贡献，因为在 $u$ 对 $f(u, G)$ 的贡献后，点 $u$ 被删除了。
  • 一个点 $v$ 对 $f (u, G)$ 有贡献当且仅当 $u$ $v$ 互达且经过的点的编号都大于 $v$ 。如果经过了一个点，其编号 $w < v$ ，即此时存在路径 $u - w - v - u$ ，那么在 $w$ 点会有贡献，并将 $w$ 点删除。所以可以考虑在判断互达时只将满足条件的点作为转移点。
  • 显然需要从后向前加边，但是每次都重新计算复杂度不太好。$f _ {i, j}$ 表示 $i - j$ 路径上，经过的编号最小的边的编号的最大值，这条路径成立当且仅当编号最小的边被加进来后，也就是说，对后面都产生贡献，可以用差分做。

考虑 floyd ，从后向前枚举转移点 $k$ ，统计 $k$ 对 $f([k + 1, n], G)$ 的贡献。对于起点 $i < k$ ，所有的转移点都大于 $i$ ；对于起点 $i > k$ ，只有终点 $j < k$ 才合法。

最后还原差分数组，得到答案。

查看代码 
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
#include <cstdio>
#include <algorithm>
using namespace std;
void chkmax(int &x, int k)
{
    (x < k) && (x = k);
}
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 1e3 + 10, M = 2e5 + 10;
int n, m, ans[M], f[N][N];
int main()
{
    read(n), read(m);
    for (int i = 1, u, v; i <= m; i++)
    {
        read(u), read(v);
        f[u][v] = i;
    }
    for (int k = n; k; k--)
    {
        for (int i = k + 1; i <= n; i++)
            ans[min(f[i][k], f[k][i])]++;
        for (int i = 1; i < k; i++)
            if (f[i][k])
                for (int j = 1; j <= n; j++)
                    chkmax(f[i][j], min(f[i][k], f[k][j]));
        for (int i = k + 1; i <= n; i++)
            if (f[i][k])
                for (int j = 1; j < k; j++)
                    chkmax(f[i][j], min(f[i][k], f[k][j]));
    }
    ans[m + 1] = n;
    for (int i = m; i; i--)
        ans[i] += ans[i + 1];
    for (int i = 1; i <= m + 1; i++)
        write(ans[i]), putchar(' ');
    return 0;
}

Algorithm II Tarjan $O(mn(n + m))$ 44 pts

判断一点和那些点互达可以建反图，分别做 DFS；这里用了 tarjan 。思路很暴力，依次加入每条边，枚举每个 $v$ ，（这两者顺序随便），只经过 $[v, n]$ 的点，判断有多少个点和 $v$ 互达。

查看代码 
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
86
87
88
89
90
91
92
93
94
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
void chkmin(int &x, int k)
{
    (x > k) && (x = k);
}
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 1e3 + 10, M = 2e5 + 10;
struct Edge
{
    int u, v;
};
vector<Edge> e;
vector<int> g[N];
int n, m, ans[M];
bool vis[N];
int top, stk[N];
int stmp, dfn[N], low[N];
int tarjan(int x, int &st)
{
    dfn[x] = low[x] = ++stmp;
    stk[++top] = x;
    vis[x] = true;
    for (int i : g[x])
    {
        if (i < st)
            continue;
        if (!dfn[i])
        {
            tarjan(i, st);
            chkmin(low[x], low[i]);
        }
        else if (vis[i])
            chkmin(low[x], dfn[i]);
    }
    int res = 0;
    if (dfn[x] == low[x])
    {
        int y;
        do
        {
            res++;
            y = stk[top--];
            vis[y] = false;
        } while (y != x);
    }
    return res;
}
int main()
{
    read(n), read(m);
    for (int i = 1, u, v; i <= m; i++)
    {
        read(u), read(v);
        e.push_back((Edge){u, v});
    }
    for (int i = m; ~i; i--)
    {
        if (i < m)
            g[e[i].u].push_back(e[i].v);
        int res = 0;
        for (int j = 1; j <= n; j++)
        {
            res += tarjan(j, j);
            top = stmp = 0;
            for (int k = 1; k <= n; k++)
                vis[k] = dfn[k] = 0;
        }
        ans[i] = res;
    }
    for (int i = 0; i <= m; i++)
        write(ans[i]), putchar(' ');
    return 0;
}

Algorithm III BFS $O(n(n + m))$ 100 pts

思想大概是上面两个加起来。对于每个 $v$ ，我们还是需要知道和每个点互达经过的边的最小编号的最大值。建反图，考虑一侧的情况。我们暴力从后向前加边，对于每条边，我们考察是否能更新。如果这条边 $(u, v)$ 中的 $u$ $v$ 都已经有答案了，那么没有必要再找了；如果 $u$ 有答案，但是 $v$ 没有答案，那么一定可以更新若干的点的答案，进行一次遍历；如果都没有答案，将边加入图中备用。可以发现每个点的答案只刚好被一条边所更新，所以这部分的复杂度为 $O(n + m)$ 。

同样的，最后还原差分数组。

查看代码 
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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 1e3 + 10, M = 2e5 + 10;
int n, m, ans[M], f[2][N];
struct Edge
{
    int u, v;
} e[M];
vector<int> g[2][N];
void dfs(int op, int x, int &edg)
{
    f[op][x] = edg;
    for (int i : g[op][x])
        !f[op][i] && (dfs(op, i, edg), 0);
}
int main()
{
    read(n), read(m);
    for (int i = 1; i <= m; i++)
        read(e[i].u), read(e[i].v);
    for (int i = 1; i <= n; i++)
    {
        for (int k = 0; k < 2; k++)
            for (int j = 1; j <= n; j++)
            {
                g[k][j].clear();
                f[k][j] = 0;
            }
        f[0][i] = f[1][i] = m + 1;
        for (int j = m; j; j--)
            if (e[j].u >= i && e[j].v >= i)
                for (int k = 0; k < 2; k++, swap(e[j].u, e[j].v))
                    if (f[k][e[j].u] && !f[k][e[j].v])
                        dfs(k, e[j].v, j);
                    else if (!f[k][e[j].u] && !f[k][e[j].v])
                        g[k][e[j].u].push_back(e[j].v);
        for (int j = i; j <= n; j++)
            if (f[0][j] && f[1][j])
                ans[min(f[0][j], f[1][j])]++;
    }
    for (int i = m; i; i--)
        ans[i] += ans[i + 1];
    for (int i = 1; i <= m + 1; i++)
        write(ans[i]), putchar(' ');
    return 0;
}

Day 2

T1 P7518 [省选联考 2021 A/B 卷] 宝石

为了方便，记 $w _ i$ 表示 $i$ 位置上的时容器中第 $w _ i$ 的宝石。

将过程 $s - t$ 分解为两部分 $s - lca - t$ 。考虑树上倍增。对于 $s - lca$ 的部分，首先将 $s$ 跳到第一个 $w _ i = 1$ 的位置，然后倍增上去。具体实现时，维护一个 $pre _ i$ 表示从当前节点到根节点， $i$ 号宝石出现的最近的最近的位置。 $up _ {i, k}$ 表示从 $i$ 节点开始，向上找到最近的一个位置使得 $w _ {up _ {i, k}} - w _ i = 2 ^ k$ 。这样可以在 $O(\log n)$ 的时间内找到 $s - lca$ 的答案。

考虑第二部分，之所以不容易做，是因为从上至下有多个儿子，但从下至上又不满足顺序。可以发现，只要最后的值确定了，那么可以从下向上验证 。所以考虑二分。同样地，需要找到第一个位置，为了保证时间复杂度正确，需要将所有的询问的验证离线下来，一起找，才能保证最后只搜索了 $\log n$​ 次。

查看代码 
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 2e5 + 10, C = 5e4 + 10, K = 20;
int n, m, c, p[N], d[N], w[N];
int st[N], pre[N], up[N][K], down[N][K];
vector<int> g[N];
struct Query
{
    int s, t, l, r, v;
} q[N];
struct Check
{
    int v, id;
};
vector<Check> h[N];
namespace LCA
{
    int stmp, id[N], st[N << 1][K], lg[N << 1];
    void dfs(int x)
    {
        st[++stmp][0] = x;
        id[x] = stmp;
        for (int i : g[x])
            if (!d[i])
            {
                d[i] = d[x] + 1;
                dfs(i);
                st[++stmp][0] = x;
            }
    }
    int dmin(int &x, int &y)
    {
        return d[x] < d[y] ? x : y;
    }
    void init()
    {
        d[1] = 1;
        dfs(1);
        for (int i = 2; i <= stmp; i++)
            lg[i] = lg[i >> 1] + 1;
        for (int k = 1; (1 << k) <= stmp; k++)
            for (int i = 1; i + (1 << k) - 1 <= stmp; i++)
                st[i][k] = dmin(st[i][k - 1], st[i + (1 << k - 1)][k - 1]);
    }
    int lca(int x, int y)
    {
        x = id[x], y = id[y];
        if (x > y)
            swap(x, y);
        int k = lg[y - x + 1];
        return dmin(st[x][k], st[y - (1 << k) + 1][k]);
    }
}
void init(int x = 1, int fa = 1)
{
    up[x][0] = pre[w[x] + 1];
    down[x][0] = pre[w[x] - 1];
    for (int i = 1; i < K; i++)
        up[x][i] = up[up[x][i - 1]][i - 1];
    for (int i = 1; i < K; i++)
        down[x][i] = down[down[x][i - 1]][i - 1];
    int tmp = pre[w[x]];
    pre[w[x]] = x;
    st[x] = pre[1];
    for (int i : g[x])
        (i != fa) && (init(i, x), 0);
    pre[w[x]] = tmp;
}
void dfs(int x = 1, int fa = 0)
{
    int tmp = pre[w[x]];
    pre[w[x]] = x;
    for (Check i : h[x])
        st[i.id] = pre[i.v];
    for (int i : g[x])
        (i != fa) && (dfs(i, x), 0);
    pre[w[x]] = tmp;
}
int main()
{
    read(n), read(m), read(c);
    for (int i = 1, a; i <= c; i++)
        read(a), p[a] = i;
    for (int i = 1, a; i <= n; i++)
        read(a), w[i] = p[a];
    for (int i = 1, a, b; i < n; i++)
    {
        read(a), read(b);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    LCA::init();
    init();
    read(m);
    for (int i = 1, s, t, v; i <= m; i++)
    {
        read(s), read(t);
        int lca = LCA::lca(s, t);
        s = st[s], v = d[s] >= d[lca];
        for (int k = K - 1; ~k; k--)
            d[up[s][k]] >= d[lca] && (s = up[s][k], v += 1 << k);
        q[i].s = lca, q[i].t = t, q[i].l = q[i].v = v, q[i].r = c;
    }
    for (int times = 20; times; times--)
    {
        for (int i = 1; i <= n; i++)
            h[i].clear();
        for (int i = 1; i <= m; i++)
        {
            int mid = q[i].l + q[i].r + 1 >> 1;
            h[q[i].t].push_back((Check){mid, i});
        }
        for (int i = 0; i <= c + 1; i++)
            pre[i] = 0;
        dfs();
        for (int i = 1; i <= m; i++)
        {
            int s = st[i], t = q[i].s, mid = q[i].l + q[i].r + 1 >> 1;
            int ans = mid - (d[s] > d[t]);
            for (int k = K - 1; ~k; k--)
                d[down[s][k]] > d[t] && (s = down[s][k], ans -= 1 << k);
            ans <= q[i].v ? q[i].l = mid : q[i].r = mid - 1;
        }
    }
    for (int i = 1; i <= m; i++)
        write(q[i].l), puts("");
    return 0;
}

T2 P7519 [省选联考 2021 A/B 卷] 滚榜

暴力可以获得一个不错的分数。

考虑 DP ，$f _ {i, j, k, l}$ 表示集合 $i$ 的点完成了滚榜，上一次滚榜的队伍为 $j$ （即当前第一名），有 $k$ 道题，已经一共完成了 $l$ 道题，显然可以写出一个 $O(2 ^ n n ^ 2 m ^ 2)$ 的暴力 DP 。

考虑如何压掉一维，如何将 $k$ 算在 $l$ 里面。注意到 $b _ i$ 不降。一个点选择了 $b _ i$ 后面必须至少选择 $b _ i$ ，这样重新计算贡献，就一定能保证下一次的 $b _ i$ 一定增加，就没有必要有 $k$ 这一维了。

对于每一个集合，提前预处理出 $1$ 的个数，这样可以直接知道后面还有多少个人。

查看代码 
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
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
void chkmax(int &x, int k)
{
    x < k && (x = k);
}
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 13, M = 510, K = 1 << N;
LL f[K][N][M];
int n, m, w[N], cnt[K], cst[N][N];
int main()
{
    read(n), read(m);
    for (int i = 0; i < n; i++)
        read(w[i]);
    for (int i = 0; i < (1 << n); i++)
        cnt[i] = cnt[i >> 1] + (i & 1);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            chkmax(cst[i][j] = w[i] - w[j] + (i < j), 0);
    for (int i = 0; i < n; i++)
    {
        int c = 0;
        for (int j = 0; j < n; j++)
            chkmax(c, cst[j][i]);
        (c * n <= m) && (f[1 << i][i][c * n] = 1);
    }
    for (int s = 0; s < (1 << n); s++)
        for (int i = 0; i < n; i++)
        {
            if (!(s >> i & 1))
                continue;
            for (int j = 0; j < n; j++)
            {
                if (s >> j & 1)
                    continue;
                for (int k = 0; k + cst[i][j] * (n - cnt[s]) <= m; k++)
                    f[s | (1 << j)][j][k + cst[i][j] * (n - cnt[s])] += f[s][i][k];
            }
        }
    LL res = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= m; j++)
            res += f[(1 << n) - 1][i][j];
    write(res);
    return 0;
}

T3 P7520 [省选联考 2021 A 卷] 支配

相关文章