A – The bottom of the ninth (abc351 A)
题目大意
给定(9)个 (a_i)和 (8)个 (b_i),问最后一个 (b_9)是多少,使得 (sum a_i 。
解题思路
答案就是(sum a_i – sum b_i + 1)。
神奇的代码
a = sum(map(int, input().split()))
b = sum(map(int, input().split()))
print(a - b + 1)
B – Spot the Difference (abc351 B)
题目大意
给定两个二维矩阵,仅一个位置元素不一样,找出那个位置。
解题思路
二维遍历一下就找到了。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector a(n), b(n);
for (auto& x : a)
cin >> x;
for (auto& x : b)
cin >> x;
auto solve = [&]() {
for (int i = 0; i
C – Merge the balls (abc351 C)
题目大意
给定一个队列,执行以下(q)次操作。
每次操作,队尾塞一个 大小为 (2^{a_i})的球。然后重复以下操作:
- 若队尾两个球的大小不同,结束该操作
- 否则,移除队尾两个的两个球,放一个大小 (2^{a_i+1})的球 。回到上述操作。
解题思路
直接模拟即可,因为每个球最多只会被移除一次,最多只有(q)个球,因此从对球的操作次数考虑时间复杂度的话,其时间复杂度是 (O(q))。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector team;
while (n--) {
int x;
cin >> x;
team.push_back(x);
while (team.size() > 1) {
int a = team.back();
int b = team[team.size() - 2];
if (a == b) {
team.pop_back();
team.pop_back();
team.push_back(a + 1);
} else {
break;
}
}
}
cout
D – Grid and Magnet (abc351 D)
题目大意
给定一个二维网格,一些格子上有磁铁,当走到磁铁格子上下左右的格子后,就动不了了。
问从哪个格子出发,其可以到达的格子数最多。
注意不是一次出发能到达的格子的最大值,是好格子的数量,存在一条路径到达好格子。
解题思路
考虑朴素的做法,就是(O((hw)^2)),即枚举起点,然后 (BFS)得到到达的格子的数量。由于 (h,w leq 10^3),这显然会超时。
在 (O((hw)^2))中,枚举起点花了 (O(hw)),每次 (BFS)花了 (O(hw))。
考虑枚举起点能否优化。会发现有些枚举起点是无用的。
假设磁铁周围的格子是终止格子
,如果枚举的一个起点是非终止格子
,且其左边也是个非终止格子
,那这两个格子的答案应该是一样的。因为它们可以相互到达,没任何影响,所能到达的点的范围是一样的。
由此,对于这个非终止格子
,和周围同样是非终止格子
合并在一起,在这个区域内任选一个格子进行一次 (BFS),就能得到该格子的答案, 且这也是这个区域内所有非终止格子
的答案。
因此预处理出所有的终止格子
和非终止格子
,然后从所有的未被访问过的非终止格子
进行(BFS),求得访问过的格子数量。注意终止格子
在不同的(BFS)可以重复访问,但同个 (BFS)只能访问一次,所以 终止格子
的访问状态在每次(BFS)之前要重置,为避免重置访问状态带来的额外开销,访问状态(visit[i])就改为记录访问时间 (time[i]),这样根据访问时间,也能判断本次 (BFS)是否访问该格子,也免去了重置 (visit[i]=0)的开销。
由于所有非终止格子
只会访问一次,每个终止格子
最多只会访问三次(一个方向是磁铁,然后可能有三个方向到达此格子),因此最后的时间复杂度是(O(hw))。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int h, w;
cin >> h >> w;
vector a(h);
for (auto& x : a)
cin >> x;
bool empty = false;
vector> stop(h, vector(w, 0));
array dx = {1, 0, -1, 0};
array dy = {0, 1, 0, -1};
for (int i = 0; i = 0 && ni = 0 && nj > visited(h, vector(w, 0));
int ans = empty;
int tt = 0;
for (int i = 0; i > q;
q.push({i, j});
visited[i][j] = tt;
int cnt = 0;
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
cnt++;
if (stop[x][y]) {
continue;
}
for (int k = 0; k = 0 && nx = 0 && ny
E – Jump Distance Sum (abc351 E)
题目大意
二维网格,(n)个点,一次可以往四个角的方向走。定义 (dist(p_i, p_j)) 为从(p_i to p_j)需要的最小步数。若不能到达,则假定步数为(0)。
求(sum_{i=1}^{n} sum_{j=i + 1}^{n} dist(p_i, p_j))。
解题思路
考虑怎样的情况是不能到达的。容易发现,一个格子不能到达其上下左右相邻的格子。
更进一步的,对每个点((x,y)),当移动时,观察 (x+y)的变化 ,会发现只有三种情况:(-2, 0, +2),无论哪种,其 (x+y)的奇偶性不变。因此可以得到 (x+y)奇偶性不同的点无法相互到达。相同的点或许可以到达(实际上是可以的)。
先对所有点根据 (x+y)的奇偶性分类,考虑同类别的(p_i, p_j),其 (dist)如何计算。
简单起见,考虑 ((x_i, y_i) to (x_j, y_j)) ,且(x_j > x_i, y_j > y_i)。每次移动,对于每个座标上的值,都得 (+1, -1),假设 (x_j – x_i > y_j – y_i),为了最小步数,那我肯定每次选择的动作,都会让 (x_i + 1)。至于 (y_i),如果每次也 (y_i + 1),那最终就超过了 (y_j),因此中间需要一些 (y_i – 1),来避免超过 (y_j)。即一开始先 ((+1, +1)),当 (y_i == y_j)后,就 ((+1, +1))和 ((+1, -1))交替,以保持 (y_i == y_j)不变,同时 (x_i to x_j)。
但这样最后能到达 ((x_j, y_j))吗?就看是否满足 ((+1, +1))和 ((+1, -1))数量相等。当(y_i == y_j)时,还需要执行 (left = x_j – x_i)个步骤,如果 (left)是偶数,则((+1, +1))和 ((+1, -1))数量相等,可行。事实上,因为(x_i + y_i)和 (x_j + y_j)奇偶性相同,并且 (y_i == y_j),因此 (x_i,x_j)的奇偶性也相同,则 (x_j – x_i)必定是偶数,因此也一定能到达 (x_j, y_j))。
由上述分析可以得知, (dist(p_i, p_j) = max (|x_i – x_j|, |y_i – y_j|)) 。
朴素求和就是(O(n^2)),棘手在(max)上,注意到上述距离实际上是切比雪夫距离,可以
绝对值去掉的方式比较套路,可以对 (x_i)排序,然后按顺序遍历 (x_i),这样 (x_i – x_j)就始终是一个符号,但是外层还套了一个 (max)比较棘手。
注意到上述距离实际上是切比雪夫距离,可以将其转换成曼哈顿距离。得到新点((frac{x_i + y_i}{2}, frac{x_j + y_j}{2})),然后计算两点的曼哈顿距离,即两维度的差的绝对值的和。其中 (x)维度和 (y)维度是可以分开算的,因此就按照上述绝对值去掉的方式,维护前缀和,计算求和即可。
时间复杂度是(O(n))。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
array>, 2> p{};
for (int i = 0; i > x >> y;
p[(x + y) & 1].push_back({x + y, x - y});
}
auto solve_one = [&](vector& x) -> LL {
sort(x.begin(), x.end());
LL ans = 0, sum = 0;
for (int i = 0; i >& p) -> LL {
vector x, y;
for (auto& [a, b] : p) {
x.push_back(a);
y.push_back(b);
}
return solve_one(x) + solve_one(y);
};
LL ans = solve(p[0]) + solve(p[1]);
ans /= 2;
cout
F – Double Sum (abc351 F)
题目大意
给定(n)个数 (a_i),计算 (sum_{i=1}^{n}sum_{j=i+1}^{n}max(a_j-a_i, 0))
解题思路
将求和式变一下,即为(sum_{j=1}^{n}sum_{i
即两个二维偏序问题,一个关于(i 的计数问题,一个关于(i 的 (a_i)求和问题。
二维偏序的解法,假想在一个二维坐标系内,就是问一个矩形的和。
可通过循环满足一个不等式关系(即满足一维),再用一个数据结构维护另一个不等式关系(维护另一维)求和。
以第一个偏序问题为例,即枚举下标(j),把小于 (j)的加入到数据结构中(满足了 (i ),然后在满足小于(a_j)范围求和,此为一个区间查询操作。故可以建一棵树状数组或线段树维护此查询操作。其下标的含义是(a_j)而不是 (j)。由于这里的 (a_j)高达 (10^8),但数量不超过 (10^5),因此需要事先离散化。
神奇的代码
#include
using namespace std;
using LL = long long;
// starting from 1
template class fenwick {
public:
vector fenw;
int n;
fenwick(int _n) : n(_n) { fenw.resize(n); }
inline int lowbit(int x) { return x & -x; }
void modify(int x, T v) {
for (int i = x; i 0; i -= lowbit(i)) {
v += fenw[i];
}
return v;
}
};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector a(n);
set candidate;
for (auto& x : a) {
cin >> x;
candidate.insert(x);
}
map rank;
for (auto x : candidate) {
rank[x] = rank.size() + 1;
}
fenwick presum(rank.size() + 1), cnt(rank.size() + 1);
LL ans = 0;
for (int i = 0; i
G – Hash on Tree (abc351 G)
题目大意
给定一棵有根树,根是(1)。点有权值(a_i),定义树的权值为(f(1))。
(f)的计算方式为:
- 若 (i)是叶子,则 (f(i) = a_i)。
- 否则, (f(i) = a(i) + prod_{j in son(i)} f(j))
执行(q)次操作,每次操作修改一个点的权值,回答修改后的树的权值,即(f(1))。
解题思路
神奇的代码
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net