526互联

AtCoder Beginner Contest 297 题解

发布时间 2023-04-11 20:34:22作者: SF71-H

A - Double Click

直接模拟就好。

时间复杂度：\(O(N)\)。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
//#define int long long
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
int n, d, a[105];
signed main () {
	scanf ("%d %d", &n, &d);
	for (int i = 1;i <= n; ++ i) scanf ("%d", &a[i]);
	for (int i = 1;i < n; ++ i) {
		if (a[i + 1] - a[i] <= d) {
			printf ("%d\n", a[i + 1]);
			return 0;
		}
	}
	printf ("-1\n");
	return 0;
}

B - chess960

也是按题意直接模拟就好。

时间复杂度：\(O(1)\)。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
//#define int long long
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
char s[10];
signed main () {
	scanf ("%s", s + 1);
	int x = 0, y = 0;
	for (int i = 1;i <= 8; ++ i) {
		if (s[i] == 'B') {
			if (!x) x = i;
			else y = i;
		}
	}
	if (x % 2 == y % 2) {
		printf ("No\n");
		return 0;
	}
	int z = 0;
	x = y = 0;
	for (int i = 1;i <= 8; ++ i) {
		if (s[i] == 'R') {
			if (!x) x = i;
			else y = i;
		}
		if (s[i] == 'K') z = i;
	}
	if (x < z && z < y) {
		printf ("Yes\n");
	}
	else printf ("No\n");
	return 0;
}

C - PC on the Table

可以发现，连在一起 \(n\) 个 T 最多可以产生 \(\displaystyle \left\lfloor\frac{n}{2}\right\rfloor\) 个 PC，所以从前往后，\(2\) 个为一组替换即可。

时间复杂度：\(O(HW)\)。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
//#define int long long
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
int n, m;
char s[105][105];
signed main () {
	scanf ("%d %d", &n, &m);
	for (int i = 1;i <= n; ++ i) scanf ("%s", s[i] + 1);
	for (int i = 1;i <= n; ++ i) {
		for (int j = 1;j < m; ++ j) {
			if (s[i][j] == 'T' && s[i][j + 1] == 'T') {
				s[i][j] = 'P';
				s[i][j + 1] = 'C';
			}
		}
	}
	for (int i = 1;i <= n; ++ i) {
		for (int j = 1;j <= m; ++ j) {
			printf ("%c", s[i][j]);
		} 
		printf ("\n");
	}
	return 0;
}

D - Count Subtractions

我们考虑倍增。

将多次重复的操作合并（比如说将 \(A\) 减去 \(10^9\) 次 \(B\) 合并为 \(1\) 次），开一个变量算答案即可。

时间复杂度：\(O(\log \max(A,B))\)。

每一次都相当于取余，而每一次都是除以 \(2\) 量级的降低，所以是 \(\log\) 级别的。（类似于 gcd）

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
#define int long long
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
int a, b, ans;
inline void upd () {
	if (a < b) swap (a, b); 
}
signed main () {
	scanf ("%lld %lld", &a, &b);
	upd ();
	while (true) {
		int qwq = a - b;
		qwq /= b;
		ans += qwq;
		a -= qwq * b;
		if (a == b) break;
		if (a > b) a -= b, ans ++;
		upd ();
	}
	printf ("%lld\n", ans);
	return 0;
}

E - Kth Takoyaki Set

这道题不大简单。

一开始看到题不会做，最后观察到 \(N\) 最大才 \(10\) 就会了。

考虑算出第 \(1\) 小值，第 \(2\) 小值，...，第 \(K\) 小值。

发现他们之间可以递推，就是说第 \(i\) 小值（记作 \(f_i\)）可以写成如下形式：

\[f_i=f_j+A_k(0 \leq j < i, 1 \leq k \leq N) \]

其中令 \(f_0=0\)。

可以用一个堆维护，记得一定要满足 \(f_{i}<f_{i+1}\)。

时间复杂度：\(O(NK \log NK)\)。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
#define int long long
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
int n, k, rnk[200005], a[15];
priority_queue < int, vector < int >, greater < int > > heap;
inline void add (int x) {
	for (int i = 1;i <= n; ++ i) heap.push (x + a[i]);
}
signed main () {
	scanf ("%lld %lld", &n, &k);
	for (int i = 1;i <= n; ++ i) scanf ("%lld", &a[i]);
	rnk[0] = 0;
	add (0);
	for (int i = 1;i <= k; ++ i) {
		while (true) {
			int u = heap.top ();
			heap.pop ();
			if (u > rnk[i - 1]) {
				rnk[i] = u;
				break;
			}
		}
		add (rnk[i]);
	}
	printf ("%lld\n", rnk[k]);
	return 0;
}

F - Minimum Bounding Box 2

一开始看到题就想到转化思路了。

设横坐标极差为 \(i\)，纵坐标极差为 \(j\) 的方案数记作 \(m_{i,j}\)，那么答案就是：

\[E(val)=\dfrac{\displaystyle \sum_{i=1}^{N}\sum_{j=1}^{M}ij(N-i+1)(M-j+1)m_{i,j}}{\dbinom{K}{NM}} \]

问题就是求 \(m\) 数组的值。

考虑正难则反，用总方案数减去不合法的方案数。

容易想到用一波容斥（比如说某一条边界没有选点）。

具体的式子见代码：

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
#define int long long
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
const int mod = 998244353;
inline int pow_mod (int a, int b, int p) {
	int res = 1;
	while (b) {
		if (b & 1) res = res * a % p;
		b >>= 1;
		a = a * a % p;
	}
	return res;
}
int fac[1000005], ifac[1000005], num[1005][1005], n, m, k;
inline int com (int N, int M) {
	if (N < M || N < 0 || M < 0) return 0;
	return fac[N] * ifac[M] % mod * ifac[N - M] % mod;
}
inline int pick (int x, int y) {
	if (x <= 0 || y <= 0) return 0;
	else return com (x * y, k);
}
inline int calc () {
	int ans = 0;
	for (int i = 1;i <= n; ++ i) {
		for (int j = 1;j <= m; ++ j) {
			int val = i * j * num[i][j] % mod * (n - i + 1) % mod * (m - j + 1) % mod;
			ans = (ans + val) % mod;
		}
	}
	int tot = com (n * m, k);
	ans = ans * pow_mod (tot, mod - 2, mod) % mod;
	return ans;
}
signed main () {
	scanf ("%lld %lld %lld", &n, &m, &k);
	fac[0] = ifac[0] = 1;
	for (int i = 1;i <= 1e6; ++ i) {
		fac[i] = fac[i - 1] * i % mod;
		ifac[i] = pow_mod (fac[i], mod - 2, mod);
	}
	for (int i = 1;i <= n; ++ i) {
		for (int j = 1;j <= m; ++ j) {
			num[i][j] = com (i * j, k);
			if (num[i][j] == 0) continue;
			num[i][j] -= 2 * pick (i - 1, j);
			num[i][j] -= 2 * pick (i, j - 1);
			num[i][j] += pick (i - 2, j);
			num[i][j] += pick (i - 1, j - 1) * 4;
			num[i][j] += pick (i, j - 2);
			num[i][j] -= pick (i - 2, j - 1) * 2;
			num[i][j] -= pick (i - 1, j - 2) * 2;
			num[i][j] += pick (i - 2, j - 2);
			num[i][j] = (num[i][j] % mod + mod) % mod;
		}
	}
	printf ("%lld\n", calc ());
	return 0;
}

G - Constrained Nim 2

根据一般的巴什博弈，修改一下结论有 \(\text{SG}(k)=\dfrac{k \bmod (L+R)}{L}\)。

然后就是平凡的 Nim 游戏了。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
#define int long long
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
int n, l, r, a[200005];
signed main () {
	scanf ("%lld %lld %lld", &n, &l, &r);
	int ans = 0;
	for (int i = 1;i <= n; ++ i) {
		scanf ("%lld", &a[i]);
		ans ^= ((a[i] % (l + r)) / l);
	}
	if (!ans) printf ("Second\n");
	else printf ("First\n");
	return 0; 
}