- [A - Median?](https://atcoder.jp/contests/abc253/tasks/abc253_a)
- 题目大意
- 输入格式
- 输出格式
- 样例
- 分析
- 代码
- [B - Distance Between Tokens](https://atcoder.jp/contests/abc253/tasks/abc253_b)
- 题目大意
- 输入格式
- 输出格式
- 样例
- 样例输入1
- 样例输出1
- 样例输入2
- 样例输出2
- 分析
- 代码
- [C - Max - Min Query](https://atcoder.jp/contests/abc253/tasks/abc253_c)
- 题目大意
- 输入格式
- 输出格式
- 分析
- 代码
- [D - FizzBuzz Sum Hard](https://atcoder.jp/contests/abc253/tasks/abc253_d)
- 题目大意
- 输入格式
- 输出格式
- 分析
- 代码
- [E - Distance Sequence](https://atcoder.jp/contests/abc253/tasks/abc253_e)
- 题目大意
- 输入格式
- 输出格式
- 分析
- 代码
给定正整数
a
,
b
,
c
a,b,c
a,b,c，判断
b
b
b是否为三个数中的中位数（即从小到大排序后是第二个，不是平均数）。
1
≤
a
,
b
,
c
≤
100
1le a,b,cle 100
1≤a,b,c≤100
a b c a~b~c a b c
输出格式如果 b b b是三个数中的中位数，输出Yes；否则，输出No。
样例| a a a | b b b | c c c | 输出 |
|---|---|---|---|
| 5 5 5 | 3 3 3 | 2 2 2 | Yes |
| 2 2 2 | 5 5 5 | 3 3 3 | No |
| 100 100 100 | 100 100 100 | 100 100 100 | No |
本来就是A题，其实没什么难的，比赛的时候就是看成平均数WA了…（上面应该讲的够清楚了）
当然可以直接将三个数排序（简单粗暴），也可以判断 a ≤ b ≤ c ale ble c a≤b≤c和 c ≤ b ≤ a cle ble a c≤b≤a中是否有至少一个成立。
代码#includeusing namespace std; int main() { int a, b, c; scanf("%d%d%d", &a, &b, &c); puts((a <= b && b <= c) || (c <= b && b <= a)? "Yes": "No"); return 0; }
B - Distance Between Tokens 题目大意
在
H
×
W
Htimes W
H×W的网格上，有恰好两个位置上各有一颗棋子，别的都是空位。
你可以从任意一个棋子开始，通过上下左右移动，前往另一个棋子的位置。
求至少要移动多少次？
先是一行 H , W H,W H,W，用空格隔开，然后有 H H H行，每行是一个长度为 W W W的字符串，-表示这个位置是空位，o表示这里有一颗棋子（详见样例）。
输出格式输出一行，即至少要移动的次数。
样例 样例输入12 3 --o o--样例输出1
3样例输入2
5 4 -o-- ---- ---- ---- -o--样例输出2
4分析
本题不需要 BFS text{BFS} BFS，由于没有障碍物，直接找到两颗棋子，并输出 x diff + y diff x_text{diff}+y_text{diff} xdiff+ydiff（即 x , y x,y x,y的坐标差之和）即可。
代码#include#include using namespace std; int main() { int h = 0, w = 0, x1 = -1, y1 = -1, x2 = -1, y2 = -1; char c; while((c = getchar()) != ' ') h = (h << 3) + (h << 1) + (c ^ 48); while((c = getchar()) != 'n') w = (w << 3) + (w << 1) + (c ^ 48); for(; h--; getchar()) for(int i=w; i--; ) if(getchar() == 'o') if(x1 == -1) x1 = h, y1 = i; else { x2 = h, y2 = i; break; } printf("%dn", x1 - x2 + (y1 > y2? y1 - y2: y2 - y1)); return 0; }
C - Max - Min Query 题目大意
我们有一个序列
S
S
S，初始为空。
请处理如下
Q
Q
Q个操作：
- 1 x：将 x x x插入至 S S S的末尾。
- 2 x c：从 S S S中删除 c c c个 x x x，如果不够删就直接删完。
- 3：求 S S S中最大值与最小值的差。
1
≤
Q
≤
2
×
1
0
5
1le Qle 2times 10^5
1≤Q≤2×105
0
≤
x
≤
1
0
9
0le xle 10^9
0≤x≤109
1
≤
c
≤
Q
1le cle Q
1≤c≤Q
Q
Q
Q
query
1
text{query}_1
query1
query
2
text{query}_2
query2
⋮
vdots
⋮
query
Q
text{query}_Q
queryQ
对于每个操作 3 3 3，输出 S S S中最大值与最小值的差。
分析典型STL练习题
本题可以用multiset或map解决，这里介绍使用map的方法（仅限C++使用）。
C++中，我们需要用到std::map
- mp[x]或int& operator[](int&& key)
返回key对应的value的引用，如果之前没有用到过则创建并返回 0 0 0。
时间复杂度： O ( log n ) mathcal O(log n) O(logn)，其中 n n n为map中元素总数。 - iterator begin()
返回最小的元素对应的指针，mp.begin()->first可以获得mp的最小元素
时间复杂度： O ( 1 ) mathcal O(1) O(1) - iterator rbegin()
返回最大的元素对应的指针，mp.rbegin()->first可以获得mp的最大元素
时间复杂度： O ( 1 ) mathcal O(1) O(1) - size_type erase(const int& key)
将key以及对应的value从map中删除，返回删除的元素个数（ 0 0 0或 1 1 1），返回值一般可以忽略。
时间复杂度： O ( log n ) mathcal O(log n) O(logn)，其中 n n n为map中元素总数。
这时，每个查询都可转换为上述操作，详见代码。
代码#include#include
D - FizzBuzz Sum Hard 题目大意
输出 1 1 1到 N N N之间不是 A A A或 B B B的倍数的数之和。
1 ≤ N , A , B ≤ 1 0 9 1le N,A,Ble 10^9 1≤N,A,B≤109
输入格式N A B N~A~B N A B
输出格式输出答案。
分析根据容斥原理，
1
1
1到
N
N
N之间是
A
A
A或
B
B
B的倍数的数之和为：
(
A
(A
(A的倍数之和
)
+
(
B
)+(B
)+(B的倍数之和
)
−
(
)-(
)−(同时为
A
,
B
A,B
A,B的倍数之和
)
)
)。
又因为同时为
A
,
B
A,B
A,B的倍数的数是
[
A
,
B
]
[A,B]
[A,B]（最小公倍数）的倍数，所以可转化为
(
A
(A
(A的倍数之和
)
−
(
B
)-(B
)−(B的倍数之和
)
+
(
[
A
,
B
]
)+([A,B]
)+([A,B]的倍数之和
)
)
)。
再设
f
(
N
)
=
1
+
2
+
⋯
+
N
,
g
(
x
,
N
)
=
x
f
(
⌊
N
X
⌋
)
=
(
N
f(N)=1+2+dots+N,g(x,N)=xf(lfloorfrac N Xrfloor)=(N
f(N)=1+2+⋯+N,g(x,N)=xf(⌊XN⌋)=(N以内所有
x
x
x的倍数之和
)
)
)，
则答案为
Ans
=
f
(
N
)
−
g
(
A
)
−
g
(
B
)
+
g
(
[
A
,
B
]
)
text{Ans}=f(N)-g(A)-g(B)+g([A,B])
Ans=f(N)−g(A)−g(B)+g([A,B])
总时间复杂度为求解
[
A
,
B
]
[A,B]
[A,B]的复杂度，即
O
(
log
max
{
A
,
B
}
)
mathcal O(log max{A,B})
O(logmax{A,B})。
这里使用了另一种 g ( x , N ) g(x,N) g(x,N)的求法，思路类似。
#includeusing namespace std; using LL = long long; inline LL sum(const LL& x, const LL& n) { LL cnt = n / x; return x * cnt * (cnt + 1LL) >> 1LL; } int main() { int n, a, b; scanf("%d%d%d", &n, &a, &b); LL x = b, y = a; while(b ^= a ^= b ^= a %= b); LL t = x / a * y; // t = lcm(a, b) printf("%lldn", sum(1, n) - sum(x, n) - sum(y, n) + sum(t, n)); return 0; }
E - Distance Sequence 题目大意
求符合如下条件的 A = ( A 1 , … , A N ) A=(A_1,dots,A_N) A=(A1,…,AN)的个数，对 998244353 998244353 998244353取模：
- 1 ≤ A i ≤ M 1le A_ile M 1≤Ai≤M（ 1 ≤ i ≤ N 1le ile N 1≤i≤N）
-
∣
A
i
−
A
i
+
1
∣
≥
K
|A_i-A_{i+1}|ge K
∣Ai−Ai+1∣≥K（
1
≤
i
<
N
1le i
2
≤
N
≤
1000
2le Nle 1000
2≤N≤1000
N
M
K
N~M~K
N M K 输出符合条件的序列的个数，对
998244353
998244353
998244353取模。 很明显是
DP
text{DP}
DP（动态规划）的思路，仿照01背包的方式，我们设计如下状态： 但是注意到这里有个求和的操作，显然可以用前缀/后缀和优化，用
O
(
1
)
mathcal O(1)
O(1)的时间复杂度求出两个和，因此时间复杂度降到
O
(
N
M
)
mathcal O(NM)
O(NM)，可以通过。 最后一个坑，需要注意特判
K
=
0
K=0
K=0的情况，答案为
M
N
m
o
d
998244353
M^Nbmod 998244353
MNmod998244353。 特判使用快速幂，
DP
text{DP}
DP建议使用滚动表（又称数组重复利用）技巧，优化后实测：
1
≤
M
≤
5000
1le Mle 5000
1≤M≤5000
0
≤
K
<
M
0le K
dp
(
i
,
j
)
=
(
A
i
=
j
的可能数
)
text{dp}(i,j)=(A_i=jtext{的可能数})
dp(i,j)=(Ai=j的可能数)
状态转移方程也很简单，即：
dp
(
i
,
j
)
=
∑
p
=
1
j
−
k
dp
(
i
−
1
,
p
)
+
∑
p
=
j
+
k
m
dp
(
i
−
1
,
p
)
text{dp}(i,j)=sum_{p=1}^{j-k}text{dp}(i-1,p)+sum_{p=j+k}^mtext{dp}(i-1,p)
dp(i,j)=p=1∑j−kdp(i−1,p)+p=j+k∑mdp(i−1,p)
那么，如果直接暴力循环计算，整个算法的时间复杂度是
O
(
N
M
2
)
mathcal O(NM^2)
O(NM2)，显然不能通过。
本题到此结束。#include
