0821 复赛模拟
T1
裸的模拟，对得丑陋
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 50;
int ans;
string s;
bool vis[N];
int main() {
cin >> s;
for (int i = 0; i < s.size(); i++) {
if (s[i] >= 'a' && s[i] <= 'z') continue;
else {
int num;
if (s[i + 1] >= 'a' && s[i + 1] <= 'z') {
num = abs(s[i] - '0');
i += 0;
if (!vis[num]) ans++, vis[num] = true;
else continue;
} else {
if (s[i + 2] >= 'a' && s[i + 2] <= 'z') {
num = abs(s[i] - '0') * 10 + abs(s[i + 1] - '0');
i += 1;
if (!vis[num]) ans++, vis[num] = true;
else continue;
} else {
num = abs(s[i] - '0') * 100 + abs(s[i + 1] - '0') * 10 + abs(s[i + 2] - '0');
i += 2;
if (!vis[num]) ans++, vis[num] = true;
else continue;
}
}
}
}
cout << ans << endl;
return 0;
}
T2
考试的时候看到 \(1e10\) 的数据范围其实已经是慌了，想到的也不是正解，想用分块+二分但是不会写，最后写了份带前缀和的暴力却因为用优先队列维护有序还写挂了
正解是用等差数列知识推式子，将求和的过程转变为求因数，已知要求
\[\sum_{i = l}^{r}
\]
我们可以运用等差数列的求和公式：
\[\dfrac{l + r}{2} \times (r - l + 1) = N
\]
转化一下式子，两边同时 \(\times 2\) 易得
\[(l + r)(r - l + 1) = 2N
\]
那么通过求 \(2N\) 的因数来获取 \(l\) 和 \(r\) 的话，时间复杂度就会下降到 \(\sqrt{2N}\)
假设计算出来之后得出一对因数 \(x\) 和 \(y\) ， 且：
\[\begin{aligned}
l + r = x \\
r - l + 1 = y
\end{aligned}
\]
通过简单的加减消元不难得到：
\[\begin{cases}
r = \dfrac{x + y - 1}{2} \\
l = \dfrac{y - x + 1}{2}
\end{cases}
\]
最后是个坑点，需要注意判断奇偶性，我们最后得到的 \(x \times y\) 是个偶数（即 \(xy \mod{2} = 0\)） ，也就是说 \(r + l\) 和 \(r - l + 1\) 的奇偶性不相同，我们从加减消元的过程中可以得到， \(r\) 和 \(l\) 在相加相减后能被 \(2\) 整除，而满足这一性质的只可能两个数奇偶性相同，但是由于 \(r - l\) 之后还加上了 \(1\) 使得两者的奇偶性发生了改变，所以其实一开始 \(x\) 和 \(y\) 的奇偶性是相反的
那么我们打一下代码，
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
int main() {
scanf("%lld", &n);
n *= 2;
for (ll x = 1; x * x <= n; x++) {
if (n % x == 0) {
ll y = n / x;
ll l = (y - x + 1) / 2;
ll r = (x + y - 1) / 2;
if ((l != r) && ((x % 2) != (y % 2)))
printf("%lld %lld\n", l, r);
}
}
return 0;
}
T3
T3 暴露出自己很大的问题，就是码力严重不足，想出正解之后却没有能力实现，实现出来万紫千红
其实这题我没有想的什么二分和 DFS ，整道题制造金属无非只有 \(3\) 种情况：
- 本身已经有这种类型的金属
- 没有这种金属，且没有生产这种金属的配方
- 没有这种金属，有这种生产金属的配方，那么就询问是否有足够的原料生产所需金属
显然可以以此写出代码，考场我自己用的是数组套结构体套数组实现的，本身实现难度比较大，自己的代码能力又菜，所以死透了（实际上输入还读错了），就对了一个点，寄
使用 vector 写出代码如下
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 50;
int n, k, l, m, ans;
int a[N];
vector<int> v[N];
bool check(int x) {
if (a[x]) return a[x]--; // 有 x 金属
if (v[x].empty() && !a[x]) return false; // 没有配方，没有材料
for (int i = 0; i <= v[x].size() - 1; i++)
if (!check(v[x][i]))
return false;
return true;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
scanf("%d", &k);
while (k--) {
scanf("%d %d", &l, &m);
for (int i = 1, in; i <= m; i++) {
scanf("%d", &in);
v[l].push_back(in);
}
}
while (check(n)) // 能生产就生产
ans++;
printf("%d\n", ans);
return 0;
}