A – ab (abc327 A)
题目大意
给定一个字符串(s),问是否包含 ab
或ba
。
解题思路
遍历判断即可。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
string s;
cin >> n >> s;
bool ok = false;
for (int i = 1; i
B – A^A (abc327 B)
题目大意
给定(b),问是否存在 (a)使得 (a^a = b)。
解题思路
由于指数爆炸的缘故,(a)的范围不会很大,枚举(a),看(b % a)是否为 (0),然后用(b)不断除以 (a) ,看最后除的次数是否等于(a)。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
LL b;
cin >> b;
int ans = -1;
for (int i = 2; i 1) {
x /= i;
++cnt;
}
if (cnt == i) {
ans = i;
break;
}
}
if (b == 1)
ans = 1;
cout
C – Number Place (abc327 C)
题目大意
给定一个(9 times 9)的网格,问是否符合数独局面。
数独局面,即每行 (1-9),每列 (1-9),每个 (3 times 3)的格子有 (1-9)。
解题思路
按照条件,逐行、逐列、逐格子分别判断即可。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
array, 9> a;
for (auto& i : a)
for (auto& j : i)
cin >> j;
auto ok = [&]() {
for (auto& i : a) {
if (set(i.begin(), i.end()).size() != 9)
return false;
}
for (int i = 0; i cnt;
for (int j = 0; j cnt;
for (int x = 0; x
D – Good Tuple Problem (abc327 D)
题目大意
给定两个数组长度为(m),仅包含(1-n)的(a,b),问它们是否是一对好数组。
若两个数组是一对好数组,则存在一个长度为(n)的(01)数组 (x),使得 (x_{a_i} neq x_{b_i}, forall i in [1, m])。
解题思路
将条件抽象成图,相当于是点(a_i)和点(b_i)连一条边,它们的颜色不能相同。
即最后是否是一张二分图,黑白染色即可。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector a(m), b(m);
for (auto& i : a) {
cin >> i;
--i;
}
for (auto& i : b) {
cin >> i;
--i;
}
vector> edge(n);
for (int i = 0; i col(n, -1);
bool ok = true;
auto BFS = [&](int st) {
queue team;
team.push(st);
col[st] = 0;
while (!team.empty()) {
int u = team.front();
team.pop();
int target = (col[u] ^ 1);
for (auto& v : edge[u]) {
if (col[v] == -1) {
col[v] = target;
team.push(v);
} else if (col[v] != target) {
ok = false;
return;
}
}
}
};
for (int i = 0; i
E – Maximize Rating (abc327 E)
题目大意
给定(n)场比赛的表现分(p_i),现在选择一些场比赛,使得这些场比赛的 (rating)最大。
如果选择了 (k)场比赛 ((q_1, q_2, …, q_k)),则 (rating)为
]
注意这里的(q)要按照原来的顺序排列。
解题思路
枚举(k),有几项就变成常数,唯一的变数就是最大化(sum_{i=1}^{k}(0.9)^{k-i}q_i),这其实就是个经典的背包问题。
设(dp[i][j])表示前 (i)场比赛,我选择了(j)场的(sum_{i=1}^{k}(0.9)^{k-i}q_i)的最大值。
转移就是考虑当前比赛选或不选,则(dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – 1] * 0.9 + p_i))
初始条件就是(dp[0][0] = 0)。
答案就是(max(frac{dp[n][k]}{sum_{i=1}^{k}(0.9)^{k-i}} – frac{1200}{sqrt{k}}))
时间复杂度是(O(n^2))
神奇的代码
#include
using namespace std;
using LL = long long;
const double inf = numeric_limits::max();
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector dp(n + 1, -inf);
dp[0] = 0;
for (int i = 0; i dp2 = dp;
int p;
cin >> p;
for (int j = 1; j
F – Apples (abc327 F)
题目大意
二维平面,给定若干个点,问一个长宽为(d times w)的矩形所能覆盖的点的数量的最大值。
解题思路
枚举一个维度(i)(时间),问题就是在([i, i + d))的范围内的另一维度(地点)的宽度为(w)的点数的最大值。
设数组(a[i])表示 (sum[i, i + w)),即当前时间范围内的一个区间的点数,随着时间的流逝,会有新的点加入,会有旧的点删去。其影响的都是一个长度为 (w)的(a)区间,用线段树维护这个数组 (a)即可。
时间复杂度为(O(nlog n))
神奇的代码
#include
using namespace std;
using LL = long long;
const int N = 2e5 + 8;
class segtree {
#define lson (root > 1;
if (L mid)
update(rson, mid + 1, r, L, R, val);
max[root] = std::max(max[lson], max[rson]);
}
int query(int root, int l, int r) { return max[root]; }
public:
int n;
void update(int L, int R, LL val) { update(1, 1, n, L, R, val); }
int query() { return query(1, 1, n); }
};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, d, w;
cin >> n >> d >> w;
vector> apple(n);
for (auto& i : apple)
cin >> i[0] >> i[1];
vector id(n);
iota(id.begin(), id.end(), 0);
ranges::sort(id, [&](int a, int b) { return apple[a][0]
G – Many Good Tuple Problems (abc327 G)
题目大意
若两个数组是一对好数组,则存在一个长度为(n)的(01)数组 (x),使得 (x_{a_i} neq x_{b_i}, forall i in [1, m])。
问所有的长度为(m),仅包含 (1-n)的共 (n^{2m})对数组中,好数组的数量。
解题思路
注意到一对数组是好数组,我们将每一位的数字连一条边,这意味着它们所形成的图是一张二分图。
考虑对这个二分图计数。
首先枚举左边部分的点的数量(k),注意到点取值多少不影响结果,因此方案数有 (C_n^k)。
然后考虑连边情况,每一条边都是从左边(k)个点选一个点,右边 (n-k)个点选一个点,然后连边。
但这里要考虑到边的顺序——因为数组有下标顺序,如果不考虑这个顺序的话,方案数就是 (O((k(n-k))^m)),但是这里面有很多重复的情况。考虑如何不计重。然后来写题解了
神奇的代码
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net