在高铁上加训!
A - Same (abc324 A)
题目大意
给定\(n\)个数,问是否都相等。
解题思路
判断是不是全部数属于第一个数即可。或者直接拿set
去重。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (auto& i : a)
cin >> i;
cout << (set<int>(a.begin(), a.end()).size() == 1 ? "Yes" : "No") << '\n';
return 0;
}
B - 3-smooth Numbers (abc324 B)
题目大意
给定一个数\(N\),问是否能表示成 \(2^x3^y\)。
解题思路
指数范围不会超过\(64\),花 \(O(64^2)\)枚举判断即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
LL n;
cin >> n;
auto check = [&]() {
for (int i = 0; i < 64; ++i) {
LL x = (1ll << i);
for (int j = 0; j < 64; ++j) {
if (x > n)
break;
if (x == n)
return true;
x *= 3;
}
}
return false;
};
if (check())
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
C - Error Correction (abc324 C)
题目大意
给定一个字符串\(t\)和若干个字符串 \(s\)。问有哪些 \(s\),满足以下四个条件中的一个:
- \(s = t\)
- \(s\)在某处增加一个字母得到 \(t\)
- \(s\)在某处删除一个字母得到 \(t\)
- \(s\)在某处修改一个字母得到 \(t\)
解题思路
第一个就判断是否逐位相等。
第二个和第三个其实是一样的,就是两者长度是否差\(1\),且较小串是较大串的一个子序列。用子序列贪心逐位匹配即可。
第四个就判断是否只有一位不相等,
神奇的代码
#include <bits/stdc++.h>
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;
vector<int> ans;
auto check2 = [](const string& l, const string& r) {
if (r.size() - l.size() != 1)
return false;
int x = 0, y = 0;
while (x < l.size()) {
while (y < r.size() && r[y] != l[x])
++y;
if (y < r.size()) {
++x;
++y;
} else
break;
}
return x == l.size();
};
auto check = [&](const string& t) {
if (s.size() == t.size()) {
int cnt = 0;
for (int i = 0; i < s.size(); ++i)
cnt += (s[i] != t[i]);
return cnt <= 1;
}
if (s.size() < t.size())
return check2(s, t);
else
return check2(t, s);
};
for (int i = 1; i <= n; ++i) {
string t;
cin >> t;
if (check(t))
ans.push_back(i);
}
cout << ans.size() << '\n';
for (auto& i : ans)
cout << i << ' ';
cout << '\n';
return 0;
}
D - Square Permutation (abc324 D)
题目大意
给定一个数字串\(s\),将每一个数位排序,问能排出多少种数,其为平方数。
解题思路
注意到串长度只有\(13\),我们可以枚举每一个平方数\(x\),只有 \(\sqrt{10^{13}\)个,然后判断数字串 \(s\)能否表示出这个数\(x\)即可。
因为数字串 \(s\)可以排列,因此问数字串能否表示出这个数 \(x\),其实就是问这两个的每个数位数字的个数是否相等。
注意计算\(x\)的数位数字时要把前导零补上去。
神奇的代码
#include <bits/stdc++.h>
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;
vector<int> cnt(10, 0);
for (auto& i : s)
cnt[i - '0']++;
LL ans = 0;
int up = ceil(sqrt(9999999999999ll));
auto solve = [&](LL x) {
vector<int> num(10, 0);
int sz = 0;
while (x) {
num[x % 10]++;
x /= 10;
++sz;
}
if (sz > n)
return 0;
num[0] += (n - sz);
return int(num == cnt);
};
for (int i = 0; i < up; ++i) {
ans += solve(1ll * i * i);
}
cout << ans << '\n';
return 0;
}
E - Joint Two Strings (abc324 E)
题目大意
给定\(n\)个字符串 \(s_i\)和一个字符串 \(t\),长度为\(m\),问有多少组 \((i, j)\),使得拼接串 \(s_is_j\)包含 \(t\)这个子序列。
解题思路
我们先枚举\(s_i\),贪心匹配这个子序列 \(t\),它可能不能完全匹配上,但能匹配 \(t\)的前 \(x\)位。
那剩下的\(m-x\)位就交给 \(s_j\)匹配,如果 \(s_j\)能至少匹配 \(t\)的后面\(m-x\)位,则拼接串\(s_is_j\) 就包含\(t\)这个子序列。
因此对于字符串\(s_i\),它能匹配串 \(t\)的前 \(x\)位,我们要找出串 \(s_j\)的数量,可以匹配串 \(t\)的至少后\(m-x\)位,这个数量就是当前串\(s_i\)的贡献。即 \((i,*)\)的数量。
而对于字符串\(s_j\)能匹配 \(t\)的后面多少位,其实把它们反串一下贪心匹配即可。
因此就预处理每个串能匹配串\(t\)的 前缀位数和后缀位数,然后枚举每个串的匹配的前缀位数,找到要完全匹配\(t\)需要的后缀位数,大于该位数的都可以作为\(j\)的候选,累计数量即可。因此把后缀位数的个数预处理一下即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
string t;
cin >> n >> t;
int len = t.size() + 1;
vector<int> cnt(len, 0), invcnt(len, 0);
string invt = t;
reverse(invt.begin(), invt.end());
auto check = [](const string& s, const string& t, vector<int>& cnt) {
int l = 0, r = 0;
while (l < s.size()) {
while (r < t.size() && s[l] != t[r])
++r;
if (r < t.size()) {
++l;
++r;
} else
break;
}
cnt[l]++;
};
for (int i = 0; i < n; ++i) {
string s;
cin >> s;
check(t, s, cnt);
reverse(s.begin(), s.end());
check(invt, s, invcnt);
}
LL ans = 0;
reverse(invcnt.begin(), invcnt.end());
partial_sum(invcnt.begin(), invcnt.end(), invcnt.begin());
for (int i = 0; i < len; ++i) {
ans += 1ll * cnt[i] * invcnt[i];
}
cout << ans << '\n';
return 0;
}
F - Beautiful Path (abc324 F)
题目大意
给定一张有向无环图,边有两种边权\(b,c\),求一条从 \(1\)到 \(n\)的路径,使得 \(\frac{\sum b}{\sum c}\) 最大。
解题思路
初想时发现最短路的想法不太行,即时刻保留比值最大的往后扩展并不会最优的,比如此时同样是\(\frac{4}{2}, \frac{8}{4}\) ,后者值的变化的程度不如前者,又比如\(\frac{100}{99},\frac{1}{2}\),后者受\(b\)的权值影响更大 ,万一下一条边权是\((100,0)\),显然原先较小的权值会变得更大。
注意到这是一个分式形式,属于典型的\(0/1\)规划问题。我们可以二分答案\(l\),判断是否可行,即 \(\frac{\sum b}{\sum c} \geq l\),即\(\sum b - l\sum c \geq 0\),即边权为 \(b - lc\),问是否有条 \(1 \to n\)的路径,其边权和非负。
因为是有向无环图,设\(dp[i]\)表示到达 点\(i\)时的最大边权和 ,拓扑排序\(dp\)即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int inf = 2e9;
const double eps = 1e-10;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<array<int, 4>> edges;
vector<vector<int>> G(n);
vector<int> du(n);
vector<int> inque(n);
for (int i = 0; i < m; ++i) {
int u, v, b, c;
cin >> u >> v >> b >> c;
--u, --v;
G[u].push_back(edges.size());
edges.push_back({u, v, b, c});
}
queue<int> team;
team.push(0);
inque[0] = 0;
while (!team.empty()) {
int u = team.front();
team.pop();
for (auto& i : G[u]) {
int v = edges[i][1];
du[v]++;
if (!inque[v])
team.push(v);
inque[v] = 1;
}
}
auto check = [&](double x) {
vector<double> dp(n, -inf);
dp[0] = 0;
team.push(0);
auto dd = du;
auto B = [](int b) { return b; };
auto C = [&x](int c) { return c * x; };
while (!team.empty()) {
int u = team.front();
team.pop();
for (auto& i : G[u]) {
auto [_, v, b, c] = edges[i];
dp[v] = max(dp[v], dp[u] + B(b) - C(c));
--dd[v];
if (dd[v] == 0)
team.push(v);
}
}
return dp[n - 1] >= -eps;
};
double l = 0, r = 2e9;
while (l + eps < r) {
double mid = (l + r) / 2;
if (check(mid))
l = mid;
else
r = mid;
}
cout << fixed << setprecision(12) << l << '\n';
return 0;
}
G - Generate Arrays (abc324 G)
题目大意
给定一个关于\(n\)的排列,视为序列\(0\),依次执行 \(m\)次操作,分两种:
- \(1 s x\),将序列\(s\)的第 \(x\)个元素之后的元素(不包括第 \(x\)个)删除,放到一个新序列,相对位置不变。
- \(2 s x\),将序列\(s\)中比\(x\)大的元素删除,放到一个新序列,相对位置不变。
问每次操作后,新生成的序列的个数。
解题思路
<++>
神奇的代码
- Beginner AtCoder Contest 324beginner atcoder contest 324 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 315