ABC300 题解

0 - 写在前面

这是我打的第一场 ABC。

那时候我还是小朋友。

唉唉, 时至今日才有能力做出 然而还是不会 Ex

记得当年 _fairytale_ 和马好像都被 D 薄纱了 (?)

A - N-choice question

计算出 然后暴力找即可

int n, A, B;

int main () {
	fastread

	std::cin >> n >> A >> B;
	rep (i, 1, n) { 
		int c; std::cin >> c; 
		if (c == A + B) { std::cout << i; return 0; } 
	}

	return 0;
}

B - Same Map in the RPG World

发现数据范围特别小

直接暴力枚举 暴力算即可

int n, m;

char a[maxn][maxn];
char b[maxn][maxn];

int a_new[maxn][maxn];
inline bool chk (int s, int t) {
	rep (i, 0, n - 1) {
		rep (j, 0, m - 1) {
			a_new[(i + s) % n][(j + t) % m] = a[i][j]; 
		}
	}

	rep (i, 0, n - 1) { rep (j, 0, m - 1) { if (a_new[i][j] != b[i][j]) { return false; } } }
	return true;
}

int main () {
	fastread

	std::cin >> n >> m;
	rep (i, 0, n - 1) { rep (j, 0, m - 1) { std::cin >> a[i][j]; } }
	rep (i, 0, n - 1) { rep (j, 0, m - 1) { std::cin >> b[i][j]; } }

	rep (s, 0, n - 1) {
		rep (t, 0, m - 1) {
			if (chk (s, t)) { std::cout << "Yes\n"; return 0; }
		}
	}

	std::cout << "No\n";

	return 0;
}

C - Cross

枚举中心点后非常容易做

int n, m;
int a[maxn][maxn];

inline int getdis (int nowx, int nowy, int dx, int dy) {
	int dis = 0;
	while (a[nowx + dx][nowy + dy]) { nowx += dx; nowy += dy; dis ++; }
	return dis;
}

int ans[maxn];

int main () {
	fastread

	std::cin >> n >> m;
	rep (i, 1, n) { rep (j, 1, m) { char ch; std::cin >> ch; a[i][j] = bool (ch == '#'); } }

	rep (i, 1, n) {
		rep (j, 1, m) {
			if (not a[i][j]) { continue; }
			
			int dis = 0x3f3f3f3f;

			for (auto dx : { -1, 1 }) {
				for (auto dy : { -1, 1 }) {
					dis = std::min (dis, getdis (i, j, dx, dy));
				}
			}
			ans[dis] ++;
		}
	}

	rep (i, 1, std::min (n, m)) { std::cout << ans[i] << " "; } std::cout << "\n";

	return 0;
}

D - AABCC

注意到

考虑复杂度为 的做法

容易发现, 直接暴力枚举 加上剪枝后复杂度是对的

然后就做完了

注意开 __int128 (否则在剪枝的时候复杂度会爆炸)

std::bitset <10000000> np;
std::vector <i64> primes;

inline void sieve (int R) {
	np[1] = true;
	for (int i = 2; i <= R; i++) {
		if (not np[i]) { primes.push_back (i); }

		for (auto p : primes) {
			if (p * i > R) { break; }
			np[i * p] = true;
			if (i % p == 0) { break; }
		}
	}
}

i64 n;

int main () {
	fastread
	
	unsigned long long _n; std::cin >> _n; n = _n;

	sieve (10000000);
	
	int ans = 0;
	rep (i, 0, primes.size () - 1) {
		i64 a = primes[i];
		if (a * a > n) { break; }
		
		rep (j, i + 1, primes.size () - 1) {
			i64 b = primes[j];
			if (a * a * b > n) { break; }
		
			rep (k, j + 1, primes.size () - 1) {
				i64 c = primes[k];
				if (a * a * b * c * c > n) { break; }
				
				ans ++;
			}
		}
	}
	
	std::cout << ans << "\n";

	return 0;
}

E - Dice Product 3

注意到这个问题存在显然的状态与转移

考虑概率dp

令 为最终乘到 的概率

于是有

特别地,

但是这时候我们发现似乎没有办法直接计算

因为 要从 转移

于是到了本题最精妙的地方:

我们把 当作未知数, 解出 的递推式

得到

注意到 很大, 而实际有用的状态数比较少, 考虑记忆化搜索

事实上, 存在更高效的状态设计方式:

设 表示 用了 个, 用了 个, 用了 个

这样对于所有 , 状态都是合法的

(此处只给出记忆化搜索版本)

因为记忆化搜索好写

const i64 mod = 998244353;

inline i64 ksm (i64 a, i64 b) {
	i64 res = 1; a %= mod;
	while (b) {
		if (b & 1) { res *= (a % mod); res %= mod; }
		a *= (a % mod); a %= mod; b >>= 1;
	}
	return res;
}

inline i64 inv (i64 x) { return ksm (x, mod - 2); }

i64 inv5;

std::unordered_map <i64, i64> mem;

i64 f (i64 x) {
	if (x == 1) { return 1; }
	if (mem.count (x)) { return mem[x]; }

	i64 res = 0;
	rep (i, 2, 6) { if (x % i == 0) { res += inv5 * f (x / i); res %= mod; }; }

	mem[x] = res; return res;
}

int main () {
	fastread

	inv5 = ksm (5, mod - 2);

	i64 n; std::cin >> n;

	std::cout << f (n);

	return 0;
}

F - More Holidays

首先注意一下性质: 如果可以把多个 中的 x 全部清空, 这些被全部清空的 必定是连续的

笼统的说, 最长的 o 串一定是 的一段后缀 + 一堆全部清空的 + 的一段前缀

(当然, 不一定能够清空很多串, 也未必有 )

我们记 中 o 的数量为

则可以完全清空的 的数量为

我们记这个数量为

则我们可以把 减小

并将 在 意义下考虑

若令 为两个 顺次拼接起来后得到的串

那么我们只需要考虑在 上怎样得到最长的 o 子串即可

考虑枚举左端点, 然后可以二分出右端点

同时我们知道, 随着左端点的右移, 右端点单调不降, 可以使用双指针法

i64 n, m, k;
std::string s;

i64 sum[maxn];

int main () {
	fastread

	std::cin >> n >> m >> k;
	std::cin >> s;
	s = " " + s + s;
	
	rep (i, 1, (n << 1)) { sum[i] = sum[i - 1] + (s[i] == 'x'); }	

	i64 tot = 0; rep (i, 1, n) { tot += s[i] == 'x'; }
	
	i64 cnt = k / tot;
	m -= cnt;
	k %= tot;
	
	i64 ans = 0;
	for (i64 l = 1, r = 1; l <= n and r <= (n << 1); l ++) {
		while (r + 1 <= (n << 1) and sum[r + 1] - sum[l - 1] <= k) { r++; }
		
		if (m == 1) { ans = std::max (ans, std::min (r, n) - l + 1); }
		if (m > 1) { ans = std::max (ans, r - l + 1); }
	}

	ans += cnt * n;

	std::cout << ans << "\n";

	return 0;
}

G - P-smooth number

一眼容斥

但这题和 E 特别像

令 表示考虑前 个质数, 大小小于等于 的合法的数有多少个

转移是显然的

设定阈值记忆化即可

int primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 };
const int lim = (1 << 20);

i64 mem[25][lim + 5];

i64 f (i64 n, int curr) {
	if (not curr) { return log2 (n) + 1; }
	if (n <= lim and mem[curr][n]) { return mem[curr][n]; }

	i64 res = f (n, curr - 1);
	if (n >= primes[curr]) { res += f (n / primes[curr], curr); }
	
	if (n <= lim) { mem[curr][n] = res; }
	return res;
}

int main () {
	fastread

	i64 n, k; std::cin >> n >> k;
	
	int pos = std::lower_bound (primes, primes + 25, k) - primes;
	std::cout << f (n, pos) << "\n";

	return 0;
}