[Atcoder]NEC Programming Contest 2022 (AtCoder Beginner Contest 267) 题解
[Atcoder]NEC Programming Contest 2022 (AtCoder Beginner Contest 267) 题解
场上写到 F 题，两道题没写出来。赛后补了一道题。
果然我就只配当个 Beginner.
E
可以说是 Dijkstra 的一种变体，挺有意思的。由于我们只关心最大值，那么删掉小于潜在最大值的点是有益无害的，那么从代价最小的点开始删，动态维护即可。
#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).
#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).
然后空间也可以简单压缩一下，类似于背包的倒刷就行。
#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 之流忘光光了。