A – Zero Sum Game (abc349 A)
题目大意
(n)个人游戏,每局有一人 (+1)分,有一人 (-1)分。
给定最后前 (n-1)个人的分数,问第 (n)个人的分数。
解题思路
零和游戏,所有人总分是 (0),因此最后一个人的分数就是前 (n-1)个人的分数和的相反数。
神奇的代码
n = input()
print(-sum([int(i) for i in input().split()]))
B – Commencement (abc349 B)
题目大意
对于一个字符串,如果对于所有 (i geq 1),都有恰好 (0)或 (2) 个自负出现(i)次,则该串是好串。
给定一个字符串(s),问它是不是好串。
解题思路
(|s|)只有 (100),统计每个字符的出现次数,再枚举 (i)即可。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s;
cin >> s;
bool ok = true;
map cnt;
for (auto c : s)
cnt[c]++;
auto check = [&](int c) {
int cc = 0;
for (auto& [k, v] : cnt) {
cc += (v == c);
}
return cc == 0 || cc == 2;
};
for (int i = 1; i
C – Airport Code (abc349 C)
题目大意
给定一个字符串(s)和字符串 (t),问字符串 (t)能否从字符串 (s)得到。操作为:
- 从 (s)挑三个字母,不改变顺序变成 (t)。
- 从 (s)挑两个字母,加上(X),不改变顺序变成 (t)。
解题思路
就子序列匹配问题。就近匹配原则即可。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s, t;
cin >> s >> t;
if (t.back() == 'X')
t.pop_back();
auto pos = s.find_first_of(tolower(t[0]));
for (int i = 1; i
D – Divide Interval (abc349 D)
题目大意
给定([l,l+1,…,r-1,r))序列,拆分成最少的序列个数,使得每个序列形如 ([2^ij, 2^i(j+1)))。
给出拆分方案。
解题思路
拆分的序列个数最小,那肯定想让一个序列尽可能的长,而长的话,就是让(2^i)尽可能大。
因此就贪心地让(2^i)尽可能大,即 (l=2^i * j),这里的(i)是最大的 (i)(这意味着 (j)是奇数),并且 (r leq 2^i(j + 1)),如果 (r > 2^i(j + 1)),那说明 (2^i)太大了,就变成 (2^(i-1) 2j)来试试。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
LL l, r;
cin >> l >> r;
vector> ans;
while (l >= 1;
p2 r) {
p2 >>= 1;
bl
E – Weighted Tic-Tac-Toe (abc349 E)
题目大意
给定(3 times 3)的网格,高桥和青木画 (OX)。
每个格子有分数。
若存在同行同列或同对角线,则对应方赢,否则全部画满后,所画格子的分数和较大者赢。
问最优策略下,谁赢。
解题思路
朴素的博弈(dp),状态即为当前的棋盘样子,总状态数为 (3^9=2e4),直接搜索即可。
即设 (dp[i])表示当前局面 (i)的当前操作者(称为先手
)的必赢((dp[i] = 1))或必输 ((dp[i] = 0))。
转移,则枚举当前操作者的行为,即选择哪个格子,进入后继状态。
如果所有后继状态都是(先手)必赢,那么当前状态则是(先手)必输,即(dp[i] = 0)如果所有(dp[j] = 1), (j)是后继状态。
否则,如果有一个后继状态是先手必输,那么当前状态的先手就可以控制局面走向该状态,使得当前状态是必胜态,即(dp[i] = 1)如果存在一个(dp[j] = 0)。
转移显而易见是(O(9)),总状态数只有 (O(2e4)),因此朴素搜索就可以通过了。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
typedef array, 3> tu;
tu a;
for (auto& x : a)
for (auto& y : x)
cin >> y;
map dp;
auto check_end = [&](tu& pos) -> int {
LL p1 = 0, p2 = 0;
int left = 0;
for (int i = 0; i p2)
return 0;
else
return 1;
}
for (int i = 0; i bool {
int status = check_end(pos);
if (status != -1) {
return dp[pos] = status == role;
}
if (dp.find(pos) != dp.end())
return dp[pos];
bool lose = false;
for (auto& i : pos)
for (auto& j : i) {
if (j)
continue;
j = (role + 1);
lose |= (!self(self, pos, role ^ 1));
j = 0;
}
return dp[pos] = lose ? 1 : 0;
};
tu ini{};
bool win = dfs(dfs, ini, 0);
cout
F – Subsequence LCM (abc349 F)
题目大意
给定一个序列(a)和(m),问子序列的数量,使得其(lcm)(最小公倍数)为 (m)。
子序列之间的不同,当且仅当有元素在原位置不一样,即使它们的数字可能是一样的。
解题思路
我们可以依次考虑每个(a),选或不选,很显然是(O(2^n))。
我们不能维护每个数选择的状态,但是要维护怎样的状态呢?是怎样的中间状态能够导出它们的最小公倍数呢。
给定(n)个数,考虑怎么求它们的最小公倍数。
根据其定义,假设最小公倍数是(m),那就意味着 (m)是每个数的倍数。
从质因数的角度来思考倍数,那就是 (m)的每个质因子的幂 (geq)每个数对应质因子的幂。
因此 (m)的每个质因子的幂就是这些数对应质因子幂的最大值。(最大公因数对应的其实就是幂的最小值)
从上述求最小公倍数的做法,可以引出维护的中间状态。
即设(dp[i][j])表示考虑前 (i)个数,选择若干个后,每个质数幂的值的状态为 (j)的方案数。这样通过状态 (j)就可以知道最后的最小公倍数是不是 (m)。但很显然这一状态数是比较大的,稍加思考会发现我们不需要保留当前的幂值是多少,因为求最小公倍数时,我们是 取最大值
,我们只想让它最后为(m)对应的值即可,因此这里的数量状态可以变成二元状态。
设 (dp[i][j])表示考虑前 (i)个数,选择若干个后,其质数幂的最大值是否达到
(m)对应的质数幂的值的状态为 (j)(对于每个 (m)的质数,都有 未达到
或达到
这一(01) 状态,因此(j)是一个二进制压缩的状态)的选择方案数。初始条件是 (dp[0][0]=0)。
转移就考虑,选择当前数后,状态 (j)是否会变化。因此要事先预处理每个数选择后对这一状态的影响。即事先对(m)质因数分解,再预处理每个 (a_i)对转移的影响。
考虑时间复杂度, (m)为 (10^{16}),至多可能有15+个质数,总的复杂度是 (O(2^15 10^5)),粗略算也有 (1e9)了。当前的 (dp)还过不了。考虑进一步优化。
现在的问题已经变成,给定若干个 (010101)数,要求选若干个数,使得其与结果
为 (11111)的方案数。上述的 (dp)方式复杂度是 (1e9),会超时。
超时的1e9
#include
using namespace std;
using LL = long long;
const int mo = 998244353;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
LL m;
cin >> n >> m;
bool one = (m == 1);
vector> fac;
int up = 1e8;
for (int i = 2; i a;
for (int i = 0; i > x;
bool ok = true;
int sign = 0;
for (int j = 0; j dp(1 dp2 = dp;
for (int i = 0; i = mo)
dp2[i | x] -= mo;
}
dp.swap(dp2);
}
int ans = dp.back();
if (one) {
ans = (ans - 1 + mo) % mo;
}
cout
欲知后事如何,且等作业写完后再写
G – Palindrome Construction (abc349 G)
题目大意
解题思路
神奇的代码
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net