A - 猫抓老鼠
经典的逆序对问题，这里就不过多阐述了
有递归和树状数组两种写法，自行百度即可
B - 字符变换
查看 \((S[i]-T[i])\%26\) 是否相同即可
#include <bits/stdc++.h>
using namespace std;
int main() {
string S, T; cin >> S >> T;
set<int> st;
for (int i = 0; i < S.size(); i++) {
int cz = (S[i] - T[i] + 26) % 26;
st.insert(cz);
}
cout << (st.size() == 1 ? "Yes" : "No") << endl;
return 0;
}
C - 7777777
首先，如果我们删除了一些 7，如果仍然存在从原点看不到的 7，则我们也可以删除这些 7，而不会改变从原点看到的 7 的数量。
因此，问题可以重新表述如下：
给定 \(N\) 个 7，你可以删除其中一些，以便所有剩余的 7 都可以从原点看到。找到剩余 7 的最大数量。
此外，我们可以把每个 7 视为一个开区间，区间的两端对应于其两个端点的极角，这样问题就可以重新表述如下：
给定 \(N\) 个开放区间。第 \(i\) 个区间的左端点为 \(f(x_i,y_i-1)\)，右端点为 \(f(x_i-1,y_i)\)，其中 \(f(i,j)\) 是一个由两个实数 \((i,j)\) 表示坐标 \((i,j)\) 极角的函数。
最多可以选择多少个区间，使得任意两个区间不重叠？
这就是著名的区间调度问题。可以通过以下贪心算法解决，同样可以应用于这个问题。
重复以下操作。
- 让 \(R_{\max}\) 成为已选择区间中（右端点的）最大坐标。如果存在尚未选择的区间，其左端点坐标大于或等于 \(R_{\max}\)，则选择其中右端点最小的区间。
- 否则，如果不存在左端点坐标大于等于 \(R_{\max}\) 的区间，则终止过程。
在实现时，将 \(N\) 个区间按其右端点坐标的递增顺序排序。然后维护 \(R_{\max}\)，如果某个区间的左端点大于等于 \(R_{max}\)，那么直接把 \(R_{\max}\) 更新成当前区间的右端点
时间复杂度为 \(O(N \log N)\)。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Frac {
ll p, q; // p / q
Frac(ll p = 0, ll q = 1) : p(p), q(q) {}
bool operator < (const Frac &f) const { return p * f.q < q * f.p; }
bool operator <= (const Frac &f) const { return p * f.q <= q * f.p; }
};
int main() {
int N; cin >> N;
vector<ll> x(N), y(N);
for (int i = 0; i < N; i++) cin >> x[i] >> y[i];
vector<pair<Frac, Frac>> que(N);
for (int i = 0; i < N; i++) que[i] = make_pair(Frac(y[i], x[i] - 1), Frac(y[i] - 1, x[i]));
sort(que.begin(), que.end());
int cnt = 0;
Frac R_max = Frac(0, 1);
for (auto cur : que) {
if (R_max <= cur.second) { // cur.second 是左端点
cnt += 1;
R_max = cur.first; // 更新右端点
}
}
cout << cnt << endl;
return 0;
}
D - 武术大师
可以使用记忆化 DFS，当然，由于满足 \(A_{i,j} < i\) 说明需要在 \(i\) 之前学的招式都是在 \(i\) 之前出现过的，所以我们从后往前，记录一个数组 \(used[i]\) 表示 \(i\) 是否需要学习，如果 \(used[i]=1\) 表示需要学习，那么把 \(i\) 之前需要学的招式 \(j\) 都标记为 \(1\)
注意，这里的 \(A_{i,j}\) 最好使用 \(vector\) 来存储
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
int n; cin >> n;
vector<vector<int>> p(n, vector<int>());
vector<int> T(n), K(n);
for (int i = 0; i < n; i++) {
cin >> T[i] >> K[i];
for (int j = 0; j < K[i]; j++) {
int x; cin >> x;
p[i].push_back(x);
}
}
vector<int> used(n, 0); used[n - 1] = 1;
for (int i = n - 1; i >= 0; i--) {
if (used[i]) {
for (int j = 0; j < K[i]; j++) {
used[p[i][j] - 1] = 1;
}
}
}
long long ans = 0;
for (int i = 0; i < n; i++)
ans += T[i] * used[i];
cout << ans << endl;
return 0;
}
E - 扫雷
因为 \(N\) 很小，直接暴力 dfs 就可以了
但是正解是使用 DP 来做的
定义 \(F[i]\) 表示以第 \(i\) 节点结束的最大值，则
\[f[i]=\max{f[j]}+a[i](g[i][j]=1) \]对于输出，使用 \(pre[i]\) 记录 \(i\) 的前驱节点，然后递归输出即可
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen ("E.in", "r", stdin);
int n; cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
vector<vector<int>> g(n + 1, vector<int>(n + 1, 0));
vector<int> f(n + 1, 0), pre(n + 1, 0);
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
int x; cin >> x;
g[i][j] = x;
}
}
int ans = -1, ans_i;
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (g[j][i] == 1 && f[j] > f[i]) {
f[i] = f[j];
pre[i] = j;
}
}
f[i] += a[i];
if (f[i] > ans) {
ans = f[i];
ans_i = i;
}
}
auto print = [&](auto && print, int x) -> void {
if (pre[x] == 0) {
cout << x << " ";
return;
}
print(print, pre[x]);
cout << x << " ";
};
print(print, ans_i);
cout << endl;
cout << ans << endl;
return 0;
}
F - 整除(middle)
还是容斥原理
定义 \(A=\{\text{能被2整除}\},B=\{\text{能被3整除}\},C=\{能被7整除\},U=\text{全集}\)
那么所求的就是 \((U-A)(U-B)C=U^2C-UAC-UBC+UABC=C-AC-BC+ABC\)
写成式子的形式就是：
\[\frac{n}{7}-\frac{n}{2\times 7}-\frac{n}{3\times 7} +\frac{n}{2\times 3\times 7} \]#include<bits/stdc++.h>
using namespace std;
int main() {
long long n;
cin>>n;
long long sum= (n/7)-(n/14)-(n/21)+(n/42);
cout<<sum<<endl;
return 0;
}