18 ABC405 A ~ E 题解

A、B

略

A code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cstdio>

using namespace std;

const int N = 1e5 + 10;
int main () {
	int n, x;
	scanf ("%d%d", &n, &x);
	if (n >= 1600 && n <= 2999 && x == 1) {
		printf ("Yes\n");
		return 0;
	} 
	if (n >= 1200 && n <= 2399 && x == 2) {
		printf ("Yes\n");
		return 0;
	}
	printf ("No\n");
	return 0;
}

B code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;
const int N = 1e5 + 10;
int n, x;
int a[N];
int cnt[N];

int main () {
	scanf ("%d%d", &n, &x);
	for (int i = 1; i <= n; i++)
		scanf ("%d", &a[i]), cnt[a[i]]++;
	for (int i = 1; i <= x; i++) {
		if (cnt[i] == 0) {
			printf ("0\n");
			return 0;
		}
	}
	for (int i = n; i >= 1; i--) {
		cnt[a[i]]--;
		if (cnt[a[i]] == 0) {
			printf ("%d\n", n - i + 1);
			return 0;
		}
	}
	return 0;
}

C

给你一个长度为 N 的整数序列 A = (A_1, A_2, \dots, A_N) 。

计算 \sum_{1\leq i<j\leq N} A_{i}A_{j} 的值。

设 s um[i] 表示 i 的前缀和，由样例可得

code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N = 3e5 + 10;

int n;
ll a[N], sum[N];
int cnt[N];

int main () {
	scanf ("%d", &n);
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		scanf ("%lld", &a[i]);
		ans += sum[i - 1] * a[i];
		sum[i] = sum[i - 1] + a[i];
	}
	printf ("%lld\n", ans);
	
	return 0;
}

D

问题陈述

一天，高桥来到一家电影院，决定在每块地板砖上画上箭头，每个箭头都指向最近的紧急出口。

给你一个有 N 行和 M 列的网格。 (i, j) 表示从上往下第 i 行，从左往右第 j 列的单元格。
每个单元格由以下字符 S_{i,j} 表示：

• .：走廊单元格
• #：墙壁
• E：紧急出口

对于每个走廊单元格，找到距离它最近的出口，并向通向出口的路径标上箭头

input

7 20
....................
..#..#..####..#E##..
..#..#..#..#..#.....
..E###..#..#..####..
.....#..#..E.....#..
.....#..####..####..
....................

output

>v<<<<<>>>>>>>>v<<<<
>v#^<#^^####v^#E##vv
>v#^<#v^#>v#vv#^<<<<
>>E###vv#>v#vv####^<
>>^<<#vv#>>E<<<<<#^<
>>^<<#vv####^<####^<
>>^<<<<<>>>>^<<<<<^<

多源BFS板子，可惜考的时候我不会，所以T飞了

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>

using namespace std;

typedef long long ll;

const int N = 1e3 + 10;

int n, m;
//0->单元格  1->墙  2->出口
int a[N][N], d[N][N], ans[N][N];
int dx[5] = {0, -1, 0, 1, 0};
int dy[5] = {0, 0, 1, 0, -1};
char c[N];

struct node {
	int x, y;
};
//dir 1234 -> 上右下左 -> 顺时针
            //下左上右
			//3 4 1 2
void bfs () {
	queue <node> q;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			if (a[i][j] == 2) {
				d[i][j] = 0;
				q.push({i, j});
			}
		}
	while (q.size()) {
		int x = q.front().x;
		int y = q.front().y;
		q.pop();
		
		for (int i = 1; i <= 4; i++) {
			int tx = x + dx[i];
			int ty = y + dy[i];
			if (tx < 1 || tx > n || ty < 1 || ty > m || a[tx][ty] != 0) 
				continue;
			if (d[tx][ty] == -1) {
				d[tx][ty] = d[x][y] + 1;
				ans[tx][ty] = i;
				q.push({tx, ty});
			}
			
		}
	}
	
}

int main () {
	scanf ("%d%d", &n, &m);
	memset (d, -1, sizeof d);
	
	for (int i = 1; i <= n; i++) {
		scanf ("%s", c + 1);
		for (int j = 1; j <= m; j++) {
			if (c[j] == '.') continue;
			if (c[j] == '#') a[i][j] = 1;
			if (c[j] == 'E') a[i][j] = 2;
		}
	}
	
	bfs ();
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i][j] == 2) {
				printf ("E");
				continue;
			}
			if (a[i][j] == 1) {
				printf ("#");
				continue;
			}
//dir 1234 -> 上右下左 -> 顺时针
	//反方向   下左上右
			//3 4 1 2
			if (ans[i][j] == 3) printf ("^");
			if (ans[i][j] == 4) printf (">");
			if (ans[i][j] == 1) printf ("v");
			if (ans[i][j] == 2) printf ("<");
			
		}
		printf ("\n");
	}
	return 0;
}

E

你有 A 个苹果、 B 个桔子、 C 根香蕉和 D 粒葡萄。
要把这些 A+B+C+D 水果从左到右排成一行，使下面的条件全部成立，一共有多少种情况？求模数 998244353 。

• 每个苹果都放在每根香蕉的左边。
• 每个苹果都放在每个葡萄的左边。
• 每个桔子都放在每个葡萄的左边。

相同种类的水果不区分

容易发现制约关系

那么相互没有制约关系的水果

因为 C,\,D \to A ，所以 A 一定在 C,\,D 左边
设 i 为最右边苹果的位置，那么 A\leq i\leq A+B
i 之前的位置只能放 AB ，情况数为 C_{i-1}^{A-1}
i 之后的位置可以放 BCD ，但是 BD 有制约关系，所以我们先将 C 放好，剩下的位置从左往右依次放 BD 即可

最终答案

需要预处理阶乘及其逆元

code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;
typedef long long ll;

const int N = 4e6 + 10;
const int mod = 998244353;

ll jc[N], inv[N];
int sum, a, b, c, d;

ll pw (ll x, ll y) {
	ll res = 1, t = x;
	while (y) {
		if (y & 1) {
			res *= t;
			res %= mod;
		}
		t *= t;
		t %= mod;
		y >>= 1;
	}
	return res;
}
void init () {
	jc[0] = 1;
	inv[0] = 1;
	int mn = 4e6;
	for (int i = 1; i <= mn; i++) {
		jc[i] = jc[i - 1] * i;
		jc[i] %= mod;
	}
	//jc[mn]的逆元
	inv[mn] = pw (jc[mn], mod - 2);
	for (int i = mn - 1; i >= 1; i--) {
		inv[i] = inv[i + 1] * (i + 1) % mod;
	}
}
ll calc (int a, int b) {
	return (ll)jc[a] * inv[b] % mod	* inv[a - b] % mod;
}

int main () {
	init ();
	scanf ("%d%d%d%d", &a, &b, &c, &d);
	sum = a + b + c + d;
	//枚举苹果最后一个出现的位置
	ll ans = 0;
	for (int i = a; i <= a + b; i++) {
		ans += calc (i - 1, a - 1) * calc (sum - i, c) % mod;
		ans %= mod;
	}
	printf ("%lld\n", ans);
	return 0;
}