目录
写在前面
比赛地址:https://codeforces.com/contest/1923。
为唐氏儿的寒假带来了一个构式的结局,飞舞一个。
天使骚骚不太行啊妈的,推了三条线了感觉剧情太白开水了,咖啡馆也是这个熊样子、、、
A
签到。
显然最优的策略是不断地选择最右侧的 1 进行操作,每次操作等价于将最右侧的连续一段左移一位。
操作次数即为第一个 1 与最后一个 1 之间 0 的个数。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 5e5 + 10;
//=============================================================
int a[kN];
//=============================================================
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
int n; std::cin >> n;
int l = 0, r = 0, cnt = 0;
for (int i = 1; i <= n; ++ i) {
std::cin >> a[i];
if (l == 0 && a[i] == 1) l = i;
if (a[i] == 1) r = i, ++ cnt;
}
std::cout << r - l + 1 - cnt << "\n";
}
return 0;
}
B
贪心,模拟。
显然最优策略是从近往远攻击。
于是记录距离原点各距离的怪物的总血量,模拟求击败各距离的怪物所需最短时间,若该时间大于距离则输。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 3e5 + 10;
//=============================================================
int n, a[kN], x[kN];
LL k, suma[kN];
//=============================================================
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
std::cin >> n >> k;
for (int i = 1; i <= n; ++ i) {
std::cin >> a[i];
suma[i] = 0;
}
for (int i = 1; i <= n; ++ i) {
std::cin >> x[i];
suma[abs(x[i])] += a[i];
}
LL nowt = 0, r = 0, flag = 1;
for (int i = 1; i <= n; ++ i) {
if (suma[i] > r) suma[i] -= r, r = 0;
else r -= suma[i], suma[i] = 0;
LL need = 1ll * ceil(1.0 * suma[i] / k);
if (suma[i] % k) r = k - (suma[i] % k);
nowt += need;
if (nowt > i) flag = 0;
}
std::cout << (flag ? "YES\n" : "NO\n");
}
return 0;
}
/*
1
2 1
1 2
1 2
*/
C
构造。
首先 \(b\) 可以随意构造,则数列 \(a\) 中元素的顺序是不重要的,仅需关注某种元素的数量即可。
手玩样例发现,若某数列 \(a\) 不合法,则该数列一定只能被表示为:1 1 1 1 ....
(很多 1)的形式,使得无论怎么调整 \(b\) 中元素的顺序都会有某位置同为 1,否则总能通过调整元素的值或是顺序使其合法。考虑将数列 \(a\) 升序排序,令构造的数列 \(b\) 降序排序,则若合法,\(b\) 可以构造类似下列形式:
设 \(a\) 中原有 \(l\) 个 1,则 \(a\) 合法等价于存在一种 \(b\) 的构造方案使其中 1 的数量至多为 \(m-l\),即有:
\[\sum_{1\le i\le m} a_i - l \ge 2\times l + 1\times (m - l) \]即:
\[\sum_{1\le i\le m} a_i\ge l + m \]前缀和维护区间和与区间 1 的数量即可 \(O(1)\) 查询某区间是否合法。
注意特判区间长度为 1 时必定不合法。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 5e5 + 10;
//=============================================================
int n, q, a[kN];
LL sum[kN], sum1[kN];
//=============================================================
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
std::cin >> n >> q;
for (int i = 1; i <= n; ++ i) {
std::cin >> a[i];
sum[i] = sum[i - 1] + a[i];
sum1[i] = sum1[i - 1] + (a[i] == 1);
}
while (q --) {
int l, r; std::cin >> l >> r;
LL s = sum[r] - sum[l - 1];
LL s1 = sum1[r] - sum1[l - 1] + (r - l + 1);
std::cout << (l != r && s >= s1 ? "YES\n" : "NO\n");
}
}
return 0;
}
/*
1
8 1
1 1 1 1 2 2 2 2
1 8
1
7 1
1 1 1 1 1 1 5
1 7
*/
D
枚举,二分。
首先是非常重要的结论:对于所有不完全相等的区间,都存在一种操作方案使它们可以合并为一个史莱姆,所需时间为区间长度。正确性显然,不断操作其中的最大者即可。
考虑史莱姆 \(i\) 的答案,分吃掉 \(i\) 的史莱姆来自左侧还是右侧讨论。由上述结论,若来自左侧,则用于合成吃掉 \(i\) 的区间 \([l, i - 1]\) 满足:
- \(1\le l<i\)。
- \(\sum_{l\le j<i} a_j >a_i\)。
- \(a_l\sim a_{i - 1}\) 不完全相等。
对于所有满足上述条件的区间合成并吃掉 \(i\) 所需时间为 \(i - l\),则其中最大的 \(l\) 是最优的。\(a_i\) 为正数,则满足上述条件 2 的位置 \(l\) 可二分求得,为了满足条件 3 仅需再预处理每个数左侧第一个与其不同的数的位置即可。史莱姆来自右侧的情况同理,预处理每个数右侧第一个与其不同的数的位置+二分答案即可求得,上述两种情况取最小值即为答案。
总时间复杂度 \(O(n\log n)\) 级别。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 3e5 + 10;
//=============================================================
int n, a[kN], fl[kN], fr[kN];
LL sum[kN];
//=============================================================
void Init() {
std::cin >> n;
sum[0] = 0;
a[0] = a[n + 1] = -1;
for (int i = 1; i <= n; ++ i) {
std::cin >> a[i];
sum[i] = sum[i - 1] + a[i];
if (a[i] == a[i - 1]) fl[i] = fl[i - 1];
else fl[i] = i - 1;
}
for (int i = n; i; -- i) {
if (a[i] == a[i + 1]) fr[i] = fr[i + 1];
else fr[i] = i + 1;
}
}
bool Check(int l_, int r_, LL val_) {
return sum[r_] - sum[l_ - 1] > val_;
}
void Solve(int pos_) {
int posl = 0, posr = n + 1;
for (int l = 1, r = pos_ - 1; l <= r; ) {
int mid = (l + r) >> 1;
if (Check(mid, pos_ - 1, a[pos_])) {
posl = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
if (posl != 0 && pos_ - posl > 1 && fr[posl] >= pos_) posl = fl[posl];
for (int l = pos_ + 1, r = n; l <= r; ) {
int mid = (l + r) >> 1;
if (Check(pos_ + 1, mid, a[pos_])) {
posr = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
if (posr != n + 1 && posr - pos_ > 1 && fl[posr] <= pos_) posr = fr[posr];
if (posl == 0 && posr == n + 1) std::cout << -1 << " ";
else if (posl == 0) std::cout << posr - pos_ << " ";
else if (posr == n + 1) std::cout << pos_ - posl << " ";
else std::cout << std::min(pos_ - posl, posr - pos_) << " ";
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
Init();
for (int i = 1; i <= n; ++ i) Solve(i);
std::cout << "\n";
}
return 0;
}
E
dsu on tree。
考虑对于所有节点 \(u\) 维护函数 \(f_{u, c}\) 表示满足下列条件的以 \(u\) 为一端点的路径 \((u, v)\) 的数量:
- \(1\le c\le n\)。
- \(a_v = c\)。
- 除 \(u, v\) 外,路径 \((u, v)\) 上无其他颜色为 \(c\) 的节点。
对于所有 \(u\),函数 \(f\) 显然可以 dfs \(O(n)\) 求得。考虑枚举节点 \(u\) 并求得以 \(u\) 为 \(\operatorname{lca}\) 的所有合法路径的数量。考虑按顺序枚举 \(u\) 的儿子 \(i\) 进行 dfs 并在求 \(f\) 的过程中求得贡献,若当前枚举到子树 \(i\) 且 \(f_{c}\) 的增量为 \(d_{c}\),则在更新 \(f\) 前可求得答案的增量为:
\[d_{a_u} + \sum_{c\not= a_u} d_c\times f_c \]发现仅需令子节点 \(v\) 的 \(f_{v, a_v}=1\) 即可将 \(f_{v, c}\) 变为子树 \(v\) 对 \(f_{u, c}\) 的贡献,存在可继承性,一眼感觉很 dsu on tree 的样子,考虑在 dsu 过程中维护 \(f\) 并在 dfs 求子树贡献时求答案即可。
注意删除子树对 \(f\) 的贡献时也应使用 dfs。
总时间复杂度 \(O(n\log n)\) 级别。
更加显然的做法是基于上述函数 \(f\) 考虑枚举路径两端点的颜色,并在以此颜色为关键点建成的虚树上进行 DP 维护 \(f\) 并计算贡献,复杂度同样为 \(O(n\log n)\) 级别。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
const int kM = kN << 1;
//=============================================================
int n, a[kN];
int edgenum, head[kN], v[kM], ne[kM];
int dfnnum, sz[kN], son[kN];
int f[kN], vis[kN];
LL ans;
//=============================================================
void Add(int u_, int v_) {
v[++ edgenum] = v_;
ne[edgenum] = head[u_];
head[u_] = edgenum;
}
void AddDfs(int u_, int fa_, int top_) {
if (!vis[a[u_]]) {
if (a[u_] != a[top_]) ans += 1ll * f[a[u_]];
}
++ vis[a[u_]];
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i];
if (v_ == fa_) continue;
AddDfs(v_, u_, top_);
}
-- vis[a[u_]];
}
void AddDfs1(int u_, int fa_, int top_) {
if (!vis[a[u_]]) ++ f[a[u_]];
++ vis[a[u_]] ;
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i];
if (v_ == fa_) continue;
AddDfs1(v_, u_, top_);
}
-- vis[a[u_]];
}
void DelDfs(int u_, int fa_, int top_) {
if (!vis[a[u_]]) -- f[a[u_]];
++ vis[a[u_]];
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i];
if (v_ == fa_) continue;
DelDfs(v_, u_, top_);
}
-- vis[a[u_]];
}
void Dfs1(int u_, int fa_) {
sz[u_] = 1;
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i];
if (v_ == fa_) continue;
Dfs1(v_, u_);
sz[u_] += sz[v_];
if (sz[v_] > sz[son[u_]]) son[u_] = v_;
}
}
void Dfs2(int u_, int fa_, bool son_) {
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i];
if (v_ == fa_ || v_ == son[u_]) continue;
Dfs2(v_, u_, 0);
}
if (son[u_]) {
Dfs2(son[u_], u_, 1);
}
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i];
if (v_ == fa_ || v_ == son[u_]) continue;
AddDfs(v_, u_, u_);
AddDfs1(v_, u_, u_);
}
ans += f[a[u_]];
if (!son_) {
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i];
if (v_ == fa_) continue;
DelDfs(v_, u_, u_);
}
} else {
f[a[u_]] = 1;
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
std::cin >> n;
edgenum = dfnnum = 0;
ans = 0;
for (int i = 1; i <= n; ++ i) {
son[i] = f[i] = sz[i] = head[i] = 0;
}
for (int i = 1; i <= n; ++ i) std::cin >> a[i];
for (int i = 1; i < n; ++ i) {
int u_, v_; std::cin >> u_ >> v_;
Add(u_, v_), Add(v_, u_);
}
Dfs1(1, 1), Dfs2(1, 0, 0);
std::cout << ans << "\n";
}
return 0;
}
写在最后
学到了什么:
- D:区间最值。
- E:发现树上问题中用于统计答案的某函数可由子节点在适当复杂度内转化为父节点的贡献,可考虑 dsu on tree 加速该过程。