AtCoder Beginner Contest 349 A~F

本文主要是介绍AtCoder Beginner Contest 349 A~F，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A. Zero Sum Game（思维）

题意

有$N$个人一起参加游戏，开始时每个人均拥有$0$点分数。每轮游戏只会在两个人之间进行，胜者将得到$1$分，败者将失去$1$分。已知结束游戏后前$N-1$个人的分数$A_1,A_2,\dots ,A_{N-1}$，问，最后一个人的分数是多少？

分析

既然每轮游戏将会产生两个分数$1$和$-1$，那么对于$N$个人来说，总分总是固定为$0$的，因此想要知道$A_N$，可以使用总分减去每个人的分数，即$A_N=0-\sum _{i=1}^{N-1}{A}_i$。

代码

#include<bits/stdc++.h>
using namespace std;void solve() {int n;cin >> n;int sum = 0;for (int i = 2; i <= n; i++) {int a;cin >> a;sum += a;}cout << -sum << endl;
}int main() {solve();return 0;
}

B. Commencement(桶数组)

题意

给出一个仅包含小写字母的字符串$S$，定义一个字符串是一个好字符串需要对于每一个大于等于$1$的$i$均满足以下要求：

• 出现次数为$i$次的字母只可以有$0$个或$2$个。

问：给出的字符串是否为好字符串？

分析

可以使用$cnt$数组记录每个字母的出现次数，然后再使用桶数组或$map$记录每个出现次数的字母个数。

最后检查一遍，是否每个出现次数$i$对应的字母个数，如果均为$0$个或$2$个，那么就输出Yes，否则，输出No。

代码

#include<bits/stdc++.h>
using namespace std;int cnt[130];
vector<int> V[105];void solve() {string s;cin >> s;for (auto i : s) {cnt[i - 'a']++;}for (int i = 0; i <= 25; i++) {if (cnt[i]) {V[cnt[i]].push_back(i);}}int n = s.size();for (int i = 1; i <= n; i++) {if (V[i].size() != 0 && V[i].size() != 2) {cout << "No" << endl;return;}}cout << "Yes" << endl;
}int main() {solve();return 0;
}

C.Airport Code(思维)

题意

Airport Code：如果从字符串$S$中按以下两种方法获得一个新的字符串，那么这个新获得的字符串就叫做Airport Code：

• 1. 从字符串$S$中取出一个长为$3$的子序列，并把这个子序列中所有字母变成大写字母。
• 2. 从字符串$S$中取出一个长为$2$的子序列，并把这个子序列中所有字母变成大写字母，然后在这个子序列后加上一个大写字母$X$。

给出两个字符串$S$和$T$，问字符串$T$是不是字符串$S$的Airport Code。

分析

对两个字符串进行字符串匹配（注意大小写），然后根据匹配上的数量进行判断：

• 1. 三个字母都匹配上了，必然成立
• 2. 匹配上前两个字母，且最后一个未被匹配的字母为$X$，也成立
• 3. 其他情况均不成立

代码

#include<bits/stdc++.h>
using namespace std;void solve() {string s, t;cin >> s >> t;int len_t = t.size();int maxn = 2;if (t[2] == 'X') maxn--;int j = 0;for (auto i : s) {if (j <= maxn && i - 32 == t[j]) {j++;}}if (j > maxn) cout << "Yes" << endl;else cout << "No" << endl;
}int main() {solve();return 0;
}

D.Divide Interval(贪心)

题意

对于两个非负整数$l,r(l<r)$，定义序列$S(l,r)=l,l+1,\dots ,r-1$。而一个序列为好的序列需要满足$S(l,r)$中的$l=2^{i}j,r=2^i(j+1)$。

给出两个非负整数$L,R(L<R)$，问，最少使用多少个好的序列$S(l_i,r_i)$，才能组成$L\sim R-1$之间的所有数字。

分析

由于好的序列的$l=2^{i}j,r-l=2^i$，那么为了序列数量尽可能少，取的$2^i$就要尽可能大，而$l=2^{i}j$，则$l$必须为$2^i$的倍数，因此，可以对$i$从大到小进行枚举，当$l$是$2^i$倍数时，就可以继续检查$l+2^i$后是否会超过右边界$R$，如果也没有超过右边界，那么就表示当前序列能当前能选的所有序列中最长的一个，将当前序列的起点$l$和终点$l+2^i$记录到vector中，并将起点修改为$l+2^i$继续寻找下一个序列。

Tips

1. $2^i$可以通过位运算$1<<i$快速得到
2. 由于本题数据范围较大$R\le 2^{60}$，而C++程序中写下的数字$1$默认是int类型，那么直接使用$1<<i$会因为数据溢出导致程序出现错误，需要使用$1ll$代替数字$1$，写作$1ll<<i$。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;vector<pair<ll, ll>  > ans;void solve() {ll l, r;cin >> l >> r;while (l < r) {for (ll i = 60; i >= 0; i--) {if (l % (1ll << i) == 0 && (l / (1ll << i) + 1) * (1ll << i) <= r) {ans.push_back({l, (l / (1ll << i) + 1) * (1ll << i)});l = (l / (1ll << i) + 1) * (1ll << i);break;}}}cout << ans.size() << endl;for (auto i : ans) {cout << i.first << ' ' << i.second << endl;}
}int main() {solve();return 0;
}

E.Weighted Tic-Tac-Toe(博弈)

题意

给出一个$3\times 3$的网格，每个网格中包含着一个数字，其中第$i$行第$j$列的数字为$A_{i,j}$，保证$\sum _{i=1}^3\sum _{j=1}^3{A}_{i,j}$是个奇数。

开始时，网格上每个位置上均为空着的的，高桥和Aoki将在这个网格上玩井字棋。

如果谁赢下了这场井字棋，谁就是胜者。

如果出现平局，则看两名选手放置棋子的方格数字之和，谁的数字之和更大，那么谁就赢下了这局游戏。

高桥为先手，假设两人均采取最优策略，问谁将会赢下这场游戏。

分析

考虑贪心，发现局部最优解无法推出全局最优解，当前最优的策略可能会将自己推入必败点，因此不能使用贪心思维来解决本题。

考虑进行博弈，使用dfs枚举操作，看两名选手操作后能否将对手推入必败点，如果可以，那么当前状态就是必胜点，而如果没有任何办法使对手进入必败点，那么说明自己当前状态已经是必败点了。

使用$dfs(i)$表示$i$操作后的胜负情况，$dfs(i)=1$表示先手获胜，$dfs(i)=0$表示后手获胜。

每轮搜索时，由于都可能出现已经决出胜负的情况，因此，在搜索开头就需要检查胜负情况，当出现以下情况时，说明已经决出胜负了：

• 1. 某一行某一列某一对角线已经出现放置了连续的三个同色棋子
• 2. 网格中已经被棋子放满了

对于情况1，根据放置的棋子颜色返回本局游戏的结果

对于情况2，检查比赛双方的数字之和，数字之和较大的选手获胜

而如果情况1，2均为出现，则继续搜索并放置棋子。

hint

• 本题数据范围较大，需要使用long long类型存储数据

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;ll a[5][5], vis[5][5], score[5];int check() {for (int i = 1; i <= 3; i++) {if (vis[i][1] != 0 && vis[i][1] == vis[i][2] && vis[i][2] == vis[i][3]) return vis[i][1];if (vis[1][i] != 0 && vis[1][i] == vis[2][i] && vis[2][i] == vis[3][i]) return vis[1][i];}if (vis[1][1] != 0 && vis[1][1] == vis[2][2] && vis[2][2] == vis[3][3]) return vis[1][1];if (vis[1][3] != 0 && vis[1][3] == vis[2][2] && vis[2][2] == vis[3][1]) return vis[1][3];for (int i = 1; i <= 3; i++) {for (int j = 1; j <= 3; j++) {if (vis[i][j] == 0) return 0;}}return 3;
}int dfs(int op) {int ans = check();if (ans == 3) return score[1] > score[2];//平局，由分数else if (ans != 0) return ans % 2;for (int i = 1; i <= 3; i++) {for (int j = 1; j <= 3; j++) {if (vis[i][j] == 0) {score[op] += a[i][j];vis[i][j] = op;int res = dfs(op == 1 ? 2 : 1);score[op] -= a[i][j];vis[i][j] = 0;if (op % 2 == res) {//返回的结果也需根据当前选手来进行判断return res;}}}}return op == 1 ? 0 : 1;//op为1，则表示先手没有必胜策略，先手必败//反之，后手必败
}void solve() {for (int i = 1; i <= 3; i++) {for (int j = 1; j <= 3; j++) {cin >> a[i][j];}}int ans = dfs(1);if (ans == 1) cout << "Takahashi" << endl;else cout << "Aoki" << endl;
}int main() {solve();return 0;
}

F.Subsequence LCM(DP)

题意

给出一个包含$N$个数字的数组$A=A_1,A_2,\dots ,A_N$，以及一个正整数$M$，问，在数组$A$中有多少个子序列中，所有数字的最小公倍数恰好为$M$。

分析

由唯一分解定理可知，任何一个合数均可被分解成若干个素数的幂次相乘的形式，而$M\le 10^{16}$，而前14个素数的乘积约等于$1.3e16>10^{16}$，因此，$M$最多只可能被分成$13$个素数乘积的形式。

然后考虑哪些因素会影响到最小公倍数，不难想到，对于$M=p_1^{x_1}\times p_2^{x_2}\dots$，每个$p_i^{x_j}$，均取自包含子数组中包含$p_i$这个因子的最高次项，那么，如果想要组成数字$M$，就需要保证子数字对于$p_i^{x_j}$，均能至少取出其中一个数字包含该因子，同时该数字包含素因子$p_i$的次数不能超过$x_j$。

因此，可以将输入的数字转化为仅保留该数字包含数字$M$中$p_i^{x_j}$这些因子的形式，即如果包含因子$p_i$，但次数低于$x_j$，就将该因子去掉，因为该因子不会对最小公倍数产生贡献，然后将剩余的数字存储到数组中，即使用$cnt[i]$表示对答案产生$i$贡献的数字个数。

如果包含了其他因子，或因子次数过高，那么必然不能属于答案的一部分，可以将该数字直接舍去。

然后考虑初始方案，不难想到，对于$cnt[0]$，这些数字不会对答案产生贡献，但也不会影响到答案，因此，任取这些数字均能产生一种不同的答案，那么这些数字对于每组方案均能产生$2^{cnt[0]}$的贡献。

使用二进制枚举对组成数字$M$的素因子进行枚举，并使用背包算法记录方案数量（当二进制枚举枚举到的数字有$num$个，不难想到，只要结果中包含至少一个该数字，就能保证结果包含这些数字对应的因子，那么取这些数字的方案总数为$2^{num}-1$，减去的1为全部数字均不取的方案数）。

如$M$的素因子有$T$种，那么最后的答案即为$dp[(1<<T)-1]$，其中$(1<<T)-1$为长度为$T$的全$1$二进制串，表示包含了$M$的所有的素因子。

坑点

当$M=1$时，会多计算一个答案，需要将答案减去。

代码

#include <bits/stdc++.h>using namespace std;
typedef long long ll;ll n, m, a[200005], mod = 998244353;
ll p[20], fact[20], pw[200005], cnt[200005], dp[200005];int main() {cin >> n >> m;int id = 0;ll num = m;for (ll i = 2; i * i <= num; i++) {if (num % i == 0) {p[id] = i;fact[id] = 1;while (num % i == 0) {fact[id] *= i;num /= i;}id++;}}if (num != 1) {p[id] = num;fact[id++] = num;}for (int i = 1; i <= n; i++) {cin >> a[i];ll val = 0;//记录a[i]对答案的贡献for (int j = 0; j < id; j++) {if (a[i] % fact[j] == 0) {a[i] /= fact[j];if (a[i] % p[j] == 0) break;val |= (1 << j);}while (a[i] % p[j] == 0) {a[i] /= p[j];}}if (a[i] == 1) {cnt[val]++;}}pw[0] = 1;for (int i = 1; i <= n; i++) {pw[i] = pw[i - 1] * 2 % mod;}dp[0] = pw[cnt[0]];for (int i = 1; i < (1 << id); i++) {for (int j = (1 << id) - 1; j >= 0; j--) {dp[i | j] = (dp[i | j] + dp[j] * (pw[cnt[i]] - 1)) % mod;}}if (!id) dp[(1 << id) - 1]--;cout << dp[(1 << id) - 1] << endl;return 0;
}

赛后交流

在比赛结束后，会在交流群中给出比赛题解，同学们可以在赛后查看题解进行补题。

群号： 704572101，赛后大家可以一起交流做题思路，分享做题技巧，欢迎大家的加入。

这篇关于AtCoder Beginner Contest 349 A~F的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---