AtCoder Beginner Contest 238

$A - F$ 题解

A - Exponential or Quadratic

题意

判断 $2^n > n^2$是否成立？

Solution

当 $n$ 为 2,3,4 的时候不成立,否则成立

Code

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int main() {

	int n; cin >> n;

	bool flag = true;

	if(n >= 2 && n <= 4) flag = false;

	puts(flag ? "Yes" : "No");

    return 0;

}

B - Pizza

题意

切披萨，先在 12:00 的位置(钟表的位置) 切一刀，然后按照给定的序列 $A$ ，每次先顺时针旋转 $A_i$ 度，然后在在 12:00 的位置切一刀，问最后的所有披萨块中圆心角最大的是多少度？

Solution

按照题意模拟，在原披萨中每个被切到的地方标记一下，求最大的区间长度即可

Code

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int main() {

	int n; cin >> n;

	vector<bool> vis(361);

	vis[0] = vis[360] = true; //初始化

	int res = 0;

	for(int i = 0; i < n; i ++ ) {

		int x; cin >> x;

		res += x;

		vis[res % 360] = true;

	}

	int l = 0; //上一次被切到的位置

	int ans = 0;

	for(int i = 1; i <= 360; i ++ ) { //注意要枚举到 360°

		if(!vis[i]) continue;

		ans = max(ans, i - l);

		l = i;

	}

	cout << ans << "\n";

    return 0;

}

C - digitnum

题意

定义$f(x)$ 是和 $x$ 的位数相同且小于等于 $x$ 的正整数的个数

$f(1) = 1, f(2) = 2, f(10) = 1 \ ...$

给定一个 $x$ , 求 $f(1) \ + \ f(2) \ + \ f(3) \ + \ ... \ f(x)$ 的值模 $998244353$ 的值

Solution

注意到对于长度确定的数字的 $f(n)$ 的值是 $1 - x$ 的一个公差为$1$ 的序列

因此我们可以枚举数字的长度, 分别计算即可

Code

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

constexpr int MOD = 998244353;

LL chk(int x) {

	LL res = 1;

	while(x -- ) res *= 10;

	return res;

}

int main() {

	#ifndef ONLINE_JUDGE

 		freopen("1.txt", "r", stdin);

 	#endif

	LL x; cin >> x;

	LL ans = 0;

	int len = to_string(x).size();

	for(int i = 1; i <= len; i ++ ) {

		LL r = min(chk(i) - 1, x); //右边界

		LL l = chk(i - 1); //左边界

		LL len = r - l + 1;//计算等差数列的长度

		LL X = len + 1; //等差数列计算公式 len + (len + 1) / 2

		if(len % 2 == 0) len /= 2; //这里为了避免溢出先除以 2

		else X /= 2;

		len %= MOD; //这里为了避免溢出先取模

		X %= MOD; 

		LL res = len * X % MOD; //上面已经除以 2 了

		ans = (ans + res) % MOD;

	}

	cout << ans << "\n";

    return 0;

}

D - AND and SUM

题意

$x \ \& \ y \ = \ a$ $x \ + \ y \ = s$

给定 $a$ 和 $s$ , 判断是否存在合法的 $x$ 和 $y$

Solution

$x + y = x \bigoplus y + (x \& y) * 2$ 异或是不进位加法, $\&$ 是进位，因此要乘以 2

因此我们先判断 $a * 2 \le s$ 是否成立

然后判断 $s - 2 * a$ 二进制下的每一位,如果第 $i$ 位是 1 的话，那么 a 的第 $i$ 位就不可以是 1

Code

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int main() {

	int T; cin >> T;

	while(T -- ) {

		LL a, s; cin >> a >> s;

		LL res1 = a * 2;

		if(a * 2 > s) {

			puts("No");

			continue;

		}

		LL p = s - a * 2; // x ^ y

		bool flag = true;

		for(int i = 0; i < 64; i ++ ) {

			if(p >> i & 1) {

				if(a >> i & 1) {

					flag = false;

					break;

				}

			}

		}

		puts(flag ? "Yes" : "No");

	}

    return 0;

}

E - Range Sums

题意

给定一些区间的和，判断是否可以在其中选择一些区间可以通过这些区间的和算出 $1-n$ 的区间和

Solution

One $DFS$

问题可以抽象成一个图论问题,给定的 $[l, r]$ 区间可以理解为 $l-1 $ 到 $r$ 的一条无向边,判断从 $0$ 是否可以到达 $n$ 即可

Two $DSU$

对于给定的区间 $[l, r]$ 我们可以看成点 $l-1$ 和点 $r$ 是连通的，即可以互相到达的两个点，用并查集合并这两个点

判断最终 $0$ 和 $n$ 是否连通即可

Code

One

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 2e5 + 10;

vector<int> e[N];

bool st[N];

void dfs(int u) {

	if(st[u]) return;

	st[u] = true;

	for(int &v: e[u]) {

		dfs(v);

	}

}

int main() {

	int n, q;

	cin >> n >> q;

	while(q -- ) {

		int x, y; cin >> x >> y;

		e[x - 1].push_back(y);

		e[y].push_back(x - 1);

	}

	dfs(0);

	puts(st[n] ? "Yes" : "No");

	return 0;

}

Two

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 2e5 + 10;

int main() {

	int n, q;

	cin >> n >> q;

	vector<int> p(N);

	iota(p.begin(), p.end(), 0);

	function<int(int)> find = [&](int x) {

		if(p[x] != x) p[x] = find(p[x]);

		return p[x];

	};

	while(q -- ) {

		int x, y; cin >> x >> y;

		p[find(x - 1)] = find(y);

	}

	puts(find(0) == find(n) ? "Yes" : "No");

	return 0;

}

F - Two Exams

题意

有两个关于城市的测试 $P$ 和 $Q$ ，二者的结果都是 $1-n$ 的一个排列

现在我们要再 $n$ 个城市中选择 $k$ 个城市并且满足一下条件

如果 $X$ 被选择了而且 $Y$ 没有被选择，那么 $P_X > P_Y $ 并且 $Q_X > Q_Y$

Solution

我们可以先把两个测试分数处理一下

定义一个 $v$ 数组， $v_i = j$ 代表测试$P$分数为 $i$ 的人测试 $Q$ 为 $j$

对于 $v$ 数组我们可以进行一个 $DP$

$Dp[i][j][k]$ 代表在测试 $P$ 分数区间为 $1-i$ 的人中选择 $j$ 个人, 并且在已选择的人中测试 $Q$ 的分数最低为 $k$

那么我们可以进行一个 $O(n^3)$ 的 $DP$
constexpr int MOD = 998244353;

dp[0][0][n] = 1;

for(int i = 1; i <= n; i ++) {

    for(int j = 0; j <= k; j ++ ) {

        for(int val = 1; val <= n; val ++ ) {

            if(j < k && v[i] < val) { //如果可以选择这个城市

                dp[i][j + 1][val] = (dp[i][j + 1][val] + dp[i - 1][j][k]) % MOD;

            }

            //如果不选这个城市  也是需要更新的

            //如果这个城市不选,那么我们所选的合法方案中最小的值一定也比 val 大

            dp[i][j][min(v[i], val)] = (dp[i][j][min(v[i], val)] + dp[i - 1][j][k]) % MOD;

        }

    }

}

int ans = 0;

for(int &x: dp[n][k]) ans = (ans + x) % MOD;

cout << ans << "\n";
在实际写的过程中 $dp$ 数组的第一维可以用滚动数组优化

Code

#include <bits/stdc++.h>

#define rep(i, a, b) for(int i = (a); i <= (b); i ++ )

using namespace std;

typedef long long LL;

typedef pair<int, int> PII ;

template <typename T> void chkmax(T &x, T y) { x = max(x, y); }

template <typename T> void chkmin(T &x, T y) { x = min(x, y); }

constexpr int MOD = 998244353;

int main() {

    int n, k;

    cin >> n >> k;

    vector<int> a(n), b(n);

    for(int &x: a) cin >> x;

    for(int &x: b) cin >> x;

    vector<int> v(n);

	rep(i, 0, n - 1) v[a[i] - 1] = b[i] - 1;

	vector dp(k + 1, vector<int>(n + 1, 0));

	dp[0][n] = 1;

	rep(i, 0, n - 1) {

		vector ndp(k + 1, vector<int>(n + 1, 0));

		rep(x, 0, k) {

			rep(y, 0, n) {

				if(x < k && v[i] < y) { //如果可以选

					ndp[x + 1][y] += dp[x][y];

					ndp[x + 1][y] %= MOD;

				}

				ndp[x][min(y, v[i])] += dp[x][y];

				ndp[x][min(y, v[i])] %= MOD;

			}

		}

		dp.swap(ndp);

	}

    int res = 0;

    for(int &x: dp[k]) {

    	res = (res + x) % MOD;

    }

    cout << res << "\n";

	return 0;

}

AtCoder Beginner Contest 238 A - F 题解

AtCoder Beginner Contest 238

A - Exponential or Quadratic

题意

Solution

Code

B - Pizza

题意

Solution

Code

C - digitnum

题意

Solution

Code

D - AND and SUM

题意

Solution

Code

E - Range Sums

题意

Solution

Code

F - Two Exams

题意

Solution

Code