A - Median?

题目大意

给定正整数$a,b,c$，判断$b$是否为三个数中的中位数（即从小到大排序后是第二个，不是平均数）。
$1\le a,b,c\le 100$

输入格式

$a~b~c$

输出格式

如果$b$是三个数中的中位数，输出Yes；否则，输出No。

样例

$a$	$b$	$c$	输出
$5$	$3$	$2$	`Yes`
$2$	$5$	$3$	`No`
$100$	$100$	$100$	`No`

分析

本来就是A题，其实没什么难的，~~比赛的时候就是看成平均数WA了..~~（上面应该讲的够清楚了）

当然可以直接将三个数排序（简单粗暴），也可以判断$a\le b\le c$和$c\le b\le a$中是否有至少一个成立。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


#include <cstdio>
using 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\times W$的网格上，有恰好两个位置上各有一颗棋子，别的都是空位。
你可以从任意一个棋子开始，通过上下左右移动，前往另一个棋子的位置。
求至少要移动多少次？

输入格式

先是一行$H,W$，用空格隔开，然后有$H$行，每行是一个长度为$W$的字符串，-表示这个位置是空位，o表示这里有一颗棋子（详见样例）。

输出格式

输出一行，即至少要移动的次数。

样例

样例输入1

1
2
3


2 3
--o
o--

样例输出1

1

3

样例输入2

1
2
3
4
5
6


5 4
-o--
----
----
----
-o--

样例输出2

1

4

分析

本题不需要$\text{BFS}$，由于没有障碍物，直接找到两颗棋子，并输出$x_\text{diff}+y_\text{diff}$（即$x,y$的坐标差之和）即可。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


#include <cstdio>
#include <vector>
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("%d\n", x1 - x2 + (y1 > y2? y1 - y2: y2 - y1));
	return 0;
}

C - Max - Min Query

题目大意

我们有一个序列$S$，初始为空。
请处理如下$Q$个操作：

1 x：将$x$插入至$S$的末尾。
2 x c：从$S$中删除$c$个$x$，如果不够删就直接删完。
3：求$S$中最大值与最小值的差。

$1\le Q\le 2\times 10^5$
$0\le x\le 10^9$
$1\le c\le Q$

输入格式

$Q$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$

输出格式

对于每个操作$3$，输出$S$中最大值与最小值的差。

分析

~~典型STL练习题~~

本题可以用multiset或map解决，这里介绍使用map的方法（仅限C++使用）。
C++中，我们需要用到std::map<int, int>的如下方法：

mp[x]或int& operator[](int&& key)
返回key对应的value的引用，如果之前没有用到过则创建并返回$0$。
时间复杂度：$\mathcal O(\log n)$，其中$n$为map中元素总数。
iterator begin()
返回最小的元素对应的指针，mp.begin()->first可以获得mp的最小元素
时间复杂度：$\mathcal O(1)$
iterator rbegin()
返回最大的元素对应的指针，mp.rbegin()->first可以获得mp的最大元素
时间复杂度：$\mathcal O(1)$
size_type erase(const int& key)
将key以及对应的value从map中删除，返回删除的元素个数（$0$或$1$），返回值一般可以忽略。
时间复杂度：$\mathcal O(\log n)$，其中$n$为map中元素总数。

这时，每个查询都可转换为上述操作，详见代码。

代码

 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


#include <cstdio>
#include <map>
using namespace std;

int main()
{
	int q;
	scanf("%d", &q);
	map<int, int> cnt;
	while(q--)
	{
		int op;
		scanf("%d", &op);
		if(op == 3) printf("%d\n", cnt.rbegin()->first - cnt.begin()->first);
		else if(op == 1)
		{
			int x;
			scanf("%d", &x);
			cnt[x] ++;
		}
		else if(op == 2)
		{
			int x, m;
			scanf("%d%d", &x, &m);
			if(cnt[x] > m) cnt[x] -= m;
			else cnt.erase(x);
		}
	}
	return 0;
}

D - FizzBuzz Sum Hard

题目大意

输出$1$到$N$之间不是$A$或$B$的倍数的数之和。

$1\le N,A,B\le 10^9$

输入格式

$N~A~B$

输出格式

输出答案。

分析

根据容斥原理，$1$到$N$之间是$A$或$B$的倍数的数之和为：
$(A$的倍数之和$)+(B$的倍数之和$)-($同时为$A,B$的倍数之和$)$。
又因为同时为$A,B$的倍数的数是$[A,B]$（最小公倍数）的倍数，所以可转化为$(A$的倍数之和$)-(B$的倍数之和$)+([A,B]$的倍数之和$)$。

$$\text{Ans}=f(N)-g(A)-g(B)+g([A,B])$$

总时间复杂度为求解$[A,B]$的复杂度，即$\mathcal O(\log \max\{A,B\})$。

代码

这里使用了另一种$g(x,N)$的求法，思路类似。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


#include <cstdio>
using 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("%lld\n", sum(1, n) - sum(x, n) - sum(y, n) + sum(t, n));
	return 0;
}

E - Distance Sequence

题目大意

求符合如下条件的$A=(A_1,\dots,A_N)$的个数，对$998244353$取模：

$1\le A_i\le M$（$1\le i\le N$）
$|A_i-A_{i+1}|\ge K$（$1\le i < N$）

$2\le N\le 1000$
$1\le M\le 5000$
$0\le K < M$

输入格式

$N~M~K$

输出格式

输出符合条件的序列的个数，对$998244353$取模。

分析

$$\text{dp}(i,j)=(A_i=j\text{的可能数})$$$$\text{dp}(i,j)=\sum_{p=1}^{j-k}\text{dp}(i-1,p)+\sum_{p=j+k}^m\text{dp}(i-1,p)$$

那么，如果直接暴力循环计算，整个算法的时间复杂度是$\mathcal O(NM^2)$，显然不能通过。

但是注意到这里有个求和的操作，显然可以用前缀/后缀和优化，用$\mathcal O(1)$的时间复杂度求出两个和，因此时间复杂度降到$\mathcal O(NM)$，可以通过。

最后一个坑，需要注意特判$K=0$的情况，答案为$M^N\bmod 998244353$。
本题到此结束。

代码

特判使用快速幂，$\text{DP}$建议使用滚动表（又称数组重复利用）技巧，优化后实测：

时间：$49\mathrm{ms}\to39\mathrm{ms}$
空间：$21220\mathrm{kb}\to1664\mathrm{kb}$

 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


#include <cstdio>
#define maxn 1002
#define maxm 5005
#define MOD 998244353
using namespace std;

using LL = long long;
int qpow(LL a, LL b)
{
	LL ans = 1LL;
	while(b > 0)
	{
		if(b & 1LL) ans = ans * a % MOD;
		a = a * a % MOD, b >>= 1LL;
	}
	return ans;
}

inline void mod(int& x) { if(x >= MOD) x -= MOD; }
int dp[2][maxm];

int main()
{
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	if(k == 0)
	{
		printf("%d\n", qpow(m, n));
		return 0;
	}
	for(int i=1; i<=m; i++)
		dp[0][i] = 1;
	for(int i=1; i<n; i++)
	{
		int c = i & 1, p = c ^ 1, s = 0;
		for(int j=k+1; j<=m; j++)
			mod(s += dp[p][j]);
		for(int j=1; j<=m; j++)
		{
			if(j > k) mod(s += dp[p][j - k]);
			mod(dp[c][j] = s);
			if(j + k <= m)
			{
				mod(s -= dp[p][j + k]);
				if(s < 0) s += MOD;
			}
		}
	}
	int ans = 0, t = n & 1 ^ 1;
	for(int i=1; i<=m; i++)
		mod(ans += dp[t][i]);
	printf("%d\n", ans);
	return 0;
}