250802总结
个人记录
模拟赛
100 + 30 + 70 + 100 + 0 = 300
挂分挂惨了qwq（挂了125分
A - 蛙跳蛙跳
直接模拟跳的过程即可（但是要小心k == n且刚好能跳到的情况
#include <bits/stdc++.h>
#define LL long long
using namespace std;
int t, n, k, a[300010];
int main () {
for (cin >> t; t--;) {
cin >> n >> k;
for (int i = 1; i < n; i++) {
cin >> a[i];
}
int tmp = 1, ans = 0;
a[n] = 1;
for (; tmp <= k; tmp += a[tmp]) {
if (tmp == k) {
ans = 1;
break;
}
}
if (ans) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
return 0;
}
B - 蜗蜗打怪
挂了70分qwq
明明不是单峰我偏要三分qwq，甚至看到数据范围还想到了枚举，就是不写枚举qwqwssb（所以有没有大佬能帮我证明它为什么不是单峰
补题过的屎山：
#include <bits/stdc++.h>
#define LL long long
using namespace std;
LL h1, a1, d1, h2, a2, d2, h, a, d, ans;
int main () {
cin >> h1 >> a1 >> d1 >> h2 >> a2 >> d2 >> h >> a >> d;
ans = 1e9;
int tmp = 0;
if (a1 <= d2) {
tmp = (d2 - a1 + 1) * a;
a1 = d2 + 1;
}
if (a2 <= d1) {
cout << tmp;
return 0;
}
for (LL i = a1; i <= h2 + d2; i++) {
for (LL j = d1; j <= a2; j++) {
LL h11 = (h2 / (i - d2) + (h2 % (i - d2) ? 1 : 0)) * (a2 - j) + 1;
ans = min(ans, (i - a1) * a + (j - d1) * d + max(0ll, h11 - h1) * h + tmp);
}
}
cout << ans;
return 0;
}
C - 蜗蜗再打怪
又挂30qwq （蜗蜗嫑再打怪了，快去写题！！
一眼二分，然后wyn这个sb在想到二分时间的范围之前想到了二分蜗蜗打的次数多范围，然后开始二分蜗蜗打的次数，于是漏了情况挂了qwqwqwqwq
考场的屎山：
#include <bits/stdc++.h>
#define LL long long
using namespace std;
LL n, x, y, a[100010];
int check (LL m, LL k) {
LL t = m * x, t1 = t / y;
if (t1 + m >= k) {
if (t % y == 0) {
return 3;
} else {
return 1;
}
}
t = (t1 + 1) * y;
if (t / x > m) return 0;
if (t1 + 1 + m < k) return 0;
return 2;
}
int main () {
cin >> n >> x >> y;
swap(x, y);
for (int i = 1; i <= n; i++) {
cin >> a[i];
LL l = 0, r = a[i], tmp;
while (l <= r) {
LL mid = l + r >> 1;
if (check(mid, a[i])) {
tmp = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
if (check(tmp, a[i]) == 1) {
cout << "Wowo\n";
} else if (check(tmp, a[i]) == 2) {
cout << "Momo\n";
} else {
cout << "Both\n";
}
}
return 0;
}
补题补出来的屎山：
#include <bits/stdc++.h>
#define LL long long
using namespace std;
LL n, x, y, a[100010];
int check (LL m, LL k) {
if (m / x + m / y < k) return 0;
if (m % x > m % y) return 2;
if (m % x < m % y) return 1;
return 3;
}
int main () {
cin >> n >> x >> y;
swap(x, y);
for (int i = 1; i <= n; i++) {
cin >> a[i];
LL l = 0, r = a[i] * x, tmp;
while (l <= r) {
LL mid = l + r >> 1;
if (check(mid, a[i])) {
tmp = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
if (check(tmp, a[i]) == 1) {
cout << "Wowo\n";
} else if (check(tmp, a[i]) == 2) {
cout << "Momo\n";
} else {
cout << "Both\n";
}
}
return 0;
}
D - 任意传送
出题人数论王吧！（我数论太菜了qwq
首先猜到如果一些数互质，那它们通过一些奇妙的加减就可以得到1（有没有大佬能告诉我怎么证明）。所以题目变成选一些数使它们的gcd为1，求最小的c的总和。不难想到dp，01背包板子，但是gcd太大所以用map存（考场上用unorderd_map样例一直出现抽象的错误，改用map就好了是怎么回事），就可以愉快地AC叻：）
#include <bits/stdc++.h>
#define LL long long
using namespace std;
int n, l[310], c[310];
map <int, int> f;
int gcd (int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int main () {
cin >> n;
int g = 0;
for (int i = 1; i <= n; i++) {
cin >> l[i];
g = gcd(g, l[i]);
}
if (g != 1) {
cout << -1;
return 0;
}
for (int i = 1; i <= n; i++) {
cin >> c[i];
}
f[0] = 0;
for (int i = 1; i <= n; i++) {
for (auto j : f) {
if (!f[gcd(j.first, l[i])] || f[gcd(j.first, l[i])] > j.second + c[i]) {
f[gcd(j.first, l[i])] = j.second + c[i];
}
}
}
cout << f[1];
return 0;
}
并查集
太好了，是并查集，我们有救了！
写了4个题，D是结束后补出来的：）
A - Graph Composition
写了42分钟，一遍过：）
出题人要我通过在F里面删边和加边来让F中的连通块跟G里的一样，那我就照它说的做呗：）先删边：如果有边连接的2个点在G中不在一个连通块就ans++然后把它删掉。因为加边相当于在G里面删边所以一样的操作再做一遍即可（因为整完这次就直接输出答案所以不需要把边删掉直接ans++就行）
#include <bits/stdc++.h>
#define LL long long
using namespace std;
int t, n, m[2], f[200010][2];
struct edge {
int x, y;
} a[200010][2];
int fd (int x, int t) {
return f[x][t] ? f[x][t] = fd(f[x][t], t) : x;
}
int main () {
for (cin >> t; t--;) {
cin >> n >> m[0] >> m[1];
fill(&f[0][0], &f[n + 1][0], 0);
for (int qwq = 0; qwq < 2; qwq++) {
for (int i = 1; i <= m[qwq]; i++) {
cin >> a[i][qwq].x >> a[i][qwq].y;
int x = fd(a[i][qwq].x, qwq), y = fd(a[i][qwq].y, qwq);
if (x != y) {
f[x][qwq] = y;
}
}
}
int ans = 0;
for (int i = 1; i <= m[0]; i++) {
if (fd(a[i][0].x, 0) == fd(a[i][0].y, 0) && fd(a[i][0].x, 1) != fd(a[i][0].y, 1)) {
ans++;
a[i][0].x = a[i][0].y = 0;
}
}
for (int i = 1; i <= n; i++) {
f[i][0] = 0;
}
for (int i = 1; i <= m[0]; i++) {
if (!a[i][0].x) continue;
int x = fd(a[i][0].x, 0), y = fd(a[i][0].y, 0);
if (x != y) {
f[x][0] = y;
}
}
for (int i = 1; i <= m[1]; i++) {
if (fd(a[i][1].x, 1) == fd(a[i][1].y, 1) && fd(a[i][1].x, 0) != fd(a[i][1].y, 0)) {
ans++;
f[fd(a[i][1].x, 0)][0] = fd(a[i][1].y, 0);
}
}
cout << ans << "\n";
}
return 0;
}
B - Round Dance
写了19分钟，一遍过
这道题我居然在21个月之前做过，但是我怎么连21个月前自己写的代码都看不懂qwq
挺板的并查集，首先连通块的个数肯定是最大的，然后如果有连通块里面有点还可以加边就把这些连通块全塞到一起变成1个，就是最小的。怎么找到这样的连通块呢，只要有2个点是a[a[i]] = i的那它们所在的连通块就是可以合并的。：）
#include <bits/stdc++.h>
#define LL long long
using namespace std;
int t, n, a[200010], fa[200010];
int fd (int x) {
return fa[x] ? fa[x] = fd(fa[x]) : x;
}
int main () {
for (cin >> t; t--;) {
cin >> n;
fill(fa + 1, fa + n + 1, 0);
for (int i = 1; i <= n; i++) {
cin >> a[i];
int x = fd(i), y = fd(a[i]);
if (x != y) {
fa[x] = y;
}
}
int ans1 = 0, ans2 = 0, tmp = 0;
for (int i = 1; i <= n; i++) {
if (!fa[i]) {
ans1++;
ans2++;
}
}
for (int i = 1; i <= n; i++) {
if (a[a[i]] == i && a[i] > i) {
ans1--;
tmp = 1;
}
}
ans1 += tmp;
cout << ans1 << ' ' << ans2 << "\n";
}
return 0;
}
C - pSort
写了不知道多久，一遍过
把能交换的点连边，如果在一个连通块内，那它们的顺序就是可以随便换的，不在就换不过去，所以用一个并查集整出那些连通块就行。
由于我第一个写的这个题而且题单的标题没说明是并查集所以我写了一个dfs
#include <bits/stdc++.h>
#define LL long long
using namespace std;
int n, p[110], f[110], d[110];
vector <int> v[110];
void dfs (int x, int t) {
f[x] = t;
for (int i : v[x]) {
if (f[i]) continue;
dfs(i, t);
}
}
int main () {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> p[i];
}
for (int i = 1; i <= n; i++) {
cin >> d[i];
if (i + d[i] <= n) {
v[i].emplace_back(i + d[i]);
v[i + d[i]].emplace_back(i);
}
if (i > d[i]) {
v[i].emplace_back(i - d[i]);
v[i - d[i]].emplace_back(i);
}
}
for (int i = 1; i <= n; i++) {
if (!f[i]) {
dfs(i, i);
}
}
for (int i = 1; i <= n; i++) {
if (f[p[i]] != f[i]) {
cout << "NO";
return 0;
}
}
cout << "YES";
return 0;
}
D - Point Divide and Conquer
写了1.5h，WA一发T一发qwq太难了qwq
把树拆开不好做就倒过来把树拼回去，从后往前遍历操作序列，对于每个点$u$再遍历与它相邻的点，如果那个相邻的点已经被拼出来了就把它的根的答案更新成$u$，然后合并。
#include <bits/stdc++.h>
#define LL long long
using namespace std;
int t, n, p[100010], fa[100010], ans[100010], f[100010];
vector <int> v[100010];
int fd (int x) {
return fa[x] ? fa[x] = fd(fa[x]) : x;
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
for (cin >> t; t--;) {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> p[i];
fa[i] = 0;
ans[i] = 0;
f[i] = 0;
v[i].clear();
}
for (int i = 1, x, y; i < n; i++) {
cin >> x >> y;
v[x].emplace_back(y);
v[y].emplace_back(x);
}
for (int i = n; i >= 1; i--) {
f[p[i]] = 1;
for (int j : v[p[i]]) {
if (!f[j]) continue;
ans[fd(j)] = p[i];
fa[fd(j)] = p[i];
}
}
for (int i = 1; i <= n; i++) {
cout << ans[i] << ' ';
}
cout << "\n";
}
return 0;
}
太好了，写完总结了！