[Atcoder]NEC Programming Contest 2022 (AtCoder Beginner Contest 267) 题解

场上写到 F 题,两道题没写出来。赛后补了一道题。

果然我就只配当个 Beginner.

E

可以说是 Dijkstra 的一种变体,挺有意思的。由于我们只关心最大值,那么删掉小于潜在最大值的点是有益无害的,那么从代价最小的点开始删,动态维护即可。

 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
#include <algorithm>
#include <cstdio>
#include <ctype.h>
#include <queue>
const int bufSize = 1e6;
inline char nc()
{
#ifdef DEBUG
    return getchar();
#endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(char* s)
{
    static char c;
    for (; !isalpha(c); c = nc())
        ;
    for (; isalpha(c); c = nc()) *s++ = c;
    *s = '\0';
}
template <typename T>
inline T read(T& r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc())
        if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 4e5 + 100;
struct node
{
    int to, next;
} E[maxn];
int head[maxn], cnt;
inline void add(int u, int v)
{
    E[++cnt].next = head[u], head[u] = cnt, E[cnt].to = v;
}
long long ans, b[maxn];
int n, m, a[maxn], vis[maxn];
int main()
{
    read(n), read(m);
    for (int i = 1; i <= n; ++i) read(a[i]);
    for (int i = 1, u, v; i <= m; ++i) read(u), read(v), add(u, v), add(v, u), b[u] += a[v], b[v] += a[u];
    std::priority_queue<std::pair<long long, int>, std::vector<std::pair<long long, int>>, std::greater<std::pair<long long, int>>> q;
    for (int i = 1; i <= n; ++i) q.push(std::make_pair(b[i], i));
    while (!q.empty())
    {
        int u = q.top().second;
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        long long res = 0;
        for (int p = head[u]; p; p = E[p].next)
        {
            int v = E[p].to;
            if (!vis[v]) b[v] -= a[u], q.push(std::make_pair(b[v], v)), res += a[v];
        }
        ans = std::max(ans, res);
    }
    printf("%lld\n", ans);
    return 0;
}

F

给一棵树,共 $q$ 个询问,每个询问是关于某点距离为 $a$ 的任意点的编号。

乍一看仿佛点分治板子题……

但其实考虑:只有两种走法,一种是经过某个祖先走到另一棵子树中,另一种是直接走到祖先。

打一个类似于 dsu on tree 的东西,维护每一棵子树中每个深度对应的点编号 id,虽然可以有多个但只记录一个,维护每个子树中的询问。

用启发式合并保证复杂度。

在每一个节点处,尝试处理经过其本身横跨两个子树的询问即可。

实现的话有一点小细节,用 $dep[a] + dep[b] - 2 \times dep[u]$ 来计算路径长度,然后要求 $dep[b] - 2 \times dep[u] = k - dep[a]$,对某个确定的 $a$,寻找是否存在 $b$,那么可以利用一些单调性来保证复杂度。具体看代码吧。

作为一个老年人,场上打出这题属于有点超水平发挥了。。。好吧其实也不至于。

时间复杂度 $O(n \log^2 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
#include <cstdio>
#include <queue>
#include <map>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
#define DEBUG
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(char *s)
{
    static char c;
    for (; !isalpha(c); c = nc());
    for (; isalpha(c); c = nc()) *s++ = c;
    *s = '\0';
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 2e5 + 100;
struct node
{
    int to, next;
} E[2 * maxn];
int head[maxn];
inline void add(const int &x,const int &y)
{
    static int tot = 0;
    E[++tot].next = head[x],E[tot].to = y,head[x] = tot;
}
struct query
{
    int u, k;
} Q[maxn];
int n, m, fa[maxn], dep[maxn], maxdep[maxn], ans[maxn];
std::vector<int> qb[maxn];
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> V[maxn];
std::map<int,int> dep2id[maxn];
void dfs(int u)
{
    for (int p = head[u]; p; p = E[p].next)
    {
        int v = E[p].to;
        if (v == fa[u]) continue;
        dep[v] = dep[u] + 1, fa[v] = u, dfs(v);
    }
}
void dfs2(int u)
{
    dep2id[u][dep[u]] = u;
    maxdep[u] = dep[u];
    for(int p = head[u];p;p=E[p].next)
    {
        int v = E[p].to;
        if(v == fa[u]) continue;
        dfs2(v);
        while(!V[v].empty() && V[v].top().first <= maxdep[u] - 2 * dep[u])
        {
            ans[V[v].top().second] = dep2id[u][V[v].top().first + 2 * dep[u]];
            V[v].pop();
        }
        while(!V[u].empty() && V[u].top().first <= maxdep[v] - 2 * dep[u])
        {
            ans[V[u].top().second] = dep2id[v][V[u].top().first + 2 * dep[u]];
            V[u].pop();
        }
        if (V[u].size() < V[v].size()) std::swap(V[u], V[v]);
        while (!V[v].empty()) V[u].push(V[v].top()), V[v].pop();
        maxdep[u] = std::max(maxdep[u], maxdep[v]);
        if (dep2id[u].size() < dep2id[v].size()) std::swap(dep2id[u], dep2id[v]);
        dep2id[u].merge(dep2id[v]);
    }
    for (std::vector<int>::iterator it = qb[u].begin(); it != qb[u].end(); ++it)
        if (maxdep[u] - dep[u] >= Q[*it].k)
            ans[*it] = dep2id[u][dep[u] + Q[*it].k];
        else
            V[u].push(std::make_pair(Q[*it].k - dep[u], *it));
}
int main()
{
    read(n);
    for (int i = 1, a, b; i < n; ++i) read(a), read(b), add(a, b), add(b, a);
    read(m);
    for (int i = 1; i <= m; ++i) read(Q[i].u), read(Q[i].k), qb[Q[i].u].push_back(i);
    dep[1] = 1, dfs(1);
    dfs2(1);
    for (int i = 1; i <= m; ++i) printf("%d\n",ans[i] > 0 ? ans[i] : -1);
    return 0;
}

G

给一个序列,找其排列方案数量,满足恰好有 $k$ 个 $i$ 满足 $A_i < A_{i+1}$

数据量 $5000$

考虑从无开始构建可能的序列方案,依次插入元素。

那不妨假定从小到大插入元素,将新的元素插入到之前的某个上升子序列中间,则会阻断上升子序列,满足的 $k$ 不变。插入在末尾则会延长上升子序列,$k := k + 1$.

我们可以记录插入到上升子序列中间的坑位和末尾的坑位,事实上这二者是有关系的,两个加起来就是总坑位数量,因此记录一个总坑位,一个末尾坑位就足够了。

总坑位其实就是与当前的序列长度有关的某个数。

当然,还有两种特殊情况:插入到开头。

对于一个目前长度为 $m$ 的序列,可能的插入位置有 $m+1$ 个,假设其中有 $t$ 个上升子序列,则结尾坑位就有 $t$ 个,对应的其他坑位就有 $m+1-t$ 个。

再加一维表示当前满足 $A_i < A_{i+1}$ 的个数,记 $f(m,t,k)$ 为对应的方案数。

假如插入到末尾,则 $f(m+1,t,k+1) += t \times f(m,t,k)$.
插入到中间,则 $f(m+1,t+1,k) += (m+1-t) \times f(m,t,k)$

这个复杂度还是不能接受的,让我们再思考:总坑位、上升子序列长度其实就能直接计算出对应的 $k$ 了。一共 $m$ 个元素,每个上升子序列的结尾都不满足的话,有 $m-1$ 对,$t$ 对不满足,但 $t$ 对不满足的其中有一个一定是结尾的上升子序列,那么 $k = m - t$

那么记录 $t$ 就足够了。

$f(m,t) = t \times f(m-1,t) + (m-t+1) \times f(m-1,t-1)$

这就完成了一个二维的递推,$O(n^2)$ 的复杂度。

当然还有一种非常蛋疼的情况,那就是当前插入的元素与之前的元素相等。可以发现,这种情况下上一个插入的元素一定是在某个上升子序列的结尾,记录一下相等的元素个数 $s$,在转移的时候,如果选择了插入结尾,那其实还是会增加上升子序列的个数的。因此:

$f(m,t) = (t-s) \times f(m-1,t) + (m-t+1+s) \times f(m-1,t-1)$

最后输出 $f(n,n-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
57
58
59
#include <algorithm>
#include <cstdio>
#include <ctype.h>
const int bufSize = 1e6;
inline char nc()
{
#ifdef DEBUG
    return getchar();
#endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(char* s)
{
    static char c;
    for (; !isalpha(c); c = nc())
        ;
    for (; isalpha(c); c = nc()) *s++ = c;
    *s = '\0';
}
template <typename T>
inline T read(T& r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc())
        if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 5100;
const int mod = 998244353;
int n, k, f[maxn], a[maxn];
inline int mul(const int& a, const int& b)
{
    return (1ll * a * b) % mod;
}
inline int add(const int& a, const int& b)
{
    int ret = a + b;
    return ret >= mod ? ret - mod : ret;
}
int main()
{
    read(n), read(k);
    for (int i = 1; i <= n; ++i) read(a[i]);
    std::sort(a + 1, a + 1 + n);
    f[1] = 1;
    int s = 0;
    for (int i = 2; i <= n; ++i)
    {
        s = (a[i] == a[i - 1]) ? s + 1 : 0;
        for (int t = i; t; --t)
            f[t] = add(mul(t - s, f[t]), mul(i + 1 - t + s, f[t - 1]));
    }
    printf("%d\n", f[n - k]);
    return 0;
}

Ex

Extra 题。

也是找方案数,不过这次是选择偶数个元素,满足和为某定值。

如果选择 2 个,就是我们经典的 2-sum 双指针 $O(n)$ 爆杀的问题。

然而 odd sum 乍一看是做不了的,但数据范围有文章可做。

$n \le 10^5,m\le 10^6,a_i \le 10$

数字非常小!记 $s_i = \sum [a_i = i]$.

那么我们现在其实要找的是 $m = 1 \times x_1 + 2 \times x_2 + \ldots + 10 \times x_{10}$ 的分拆,对于 $(x_1,x_2,\ldots,x_{10})$ 的一种可能分拆,其对应的方案数是 $\dbinom{s_1}{x_1} \times \dbinom{s_2}{x_2} \times \ldots \times \dbinom{s_n}{x_n}$.

当然这个是非常难直接枚举的,那我们考虑能不能对某个特定的 $x_i = k$ 时,计算出 $\dbinom{s_i}{k} \times \sum (\prod )$ 的后面系数。

此时的情况类似于什么?不选用数字 $i$ 时,将 $m - k \times x_i$ 分拆的可能方案数。这个似乎是可以递归的。

那我们定义一下,$f(i,n)$ 为不选择数字 $i$ 时,将 $n$ 分拆的可能方案数。但这个时候子问题分解出现了问题,我们可以有一个自然的想法:再枚举一维……

复杂度寄了。

看看选择偶数个有什么好性质吧。


看了一眼题解,要卷积之类的,暂且放弃,现在已经把 FFT 之流忘光光了。

Licensed under CC BY-NC-SA 4.0