ABC340 A-F题解

A

题目

模拟即可，会循环都能写。

AC Code：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
int a, b, d;int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> a >> b >> d;for (int i = a; i <= b; i += d) cout << i << ' ';return 0;
}

B

题目

这个也是根据题面模拟，存一下序列的长度即可。

AC Code：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
int q, a[100100];
int n;int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> q;while (q --) {int op, x;cin >> op >> x;if (op == 1) {n++;a[n] = x;}else {cout << a[n - x + 1] << '\n';}}return 0;
}

C

题目

可以用递归加优化来完成此题。我们让 $f(x)$ 表示要擦除 $x$ 和擦除它产生的数的代价。然后得到：

$$f(x)=f(x/2)+f(x-x/2)+x$$

然后为了避免重复计算，用 map 存储 $f(x)$ 的值。如果这个答案没有被计算就计算这个答案，否则直接返回之前存储的答案。

AC Code：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
long long n;
map<long long, long long> m;
long long f(long long x) {if (x < 2) return 0;if (!m[x]) {if (x % 2) {long long tmp1 = f(x / 2), tmp2 = f(x - x / 2);m[x] = tmp1 + tmp2 + x;}else {long long tmp = f(x / 2);m[x] = tmp + tmp + x;}}return m[x];
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;cout << f(n);return 0;
}

D

题目

把游戏抽象化为一个图，每一个阶段就是一个点，那么连接 $i$ 和 $i+1$ 的边的权值就是 $A_i$，连接 $i$ 和 $X_i$ 的边的权值就是 $B_i$，然后跑一遍最短路即可。如果没有负权边就不要用 SPFA，容易被卡。

AC Code：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
int n, a[200100], b[200100], x[200100];
struct edge{int u, v, w, nxt;
};
edge ed[400100];
int edcnt, head[200100];
void addedge(int u, int v, int w){edcnt++;ed[edcnt].u = u;ed[edcnt].v = v;ed[edcnt].w = w;ed[edcnt].nxt = head[u];head[u] = edcnt;
}
long long dis[200100];
struct node {int x;long long dis;node(int x_, long long dis_) {x = x_;dis = dis_;}
};
bool operator <(node a, node b) {return a.dis > b.dis;
}
bool vis[514114];
void dijkstra() {priority_queue<node> pq;pq.push(node(1, 0));while (!pq.empty()) {int now = pq.top().x;pq.pop();if (vis[now]) {continue;}if (now == n) break;vis[now] = 1;for (int j = head[now]; j; j = ed[j].nxt) {int v = ed[j].v;if (dis[v] > dis[now] + ed[j].w) {dis[v] = dis[now] + ed[j].w;pq.push(node(v, dis[v]));}}}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;for (int i = 1; i < n; i ++) {cin >> a[i] >> b[i] >> x[i];addedge(i, i + 1, a[i]);addedge(i, x[i], b[i]);}memset(dis, 0x3f, sizeof(dis));dis[1] = 0;dijkstra();cout << dis[n];return 0;
}

E

题目

思路

我们发现，如果序列头尾相连，那么我们每次要放的都是一个连续的区间，可以看题目的 GIF 图自行理解。那么这个题就是区间修改，单点查询，一个典型的线段树或树状数组维护差分数组，我用的线段树。

做法

首先，如果我们的球数大于等于 $n$，那么就可以先放 $kn$ 个球，将每一个盒子都放 $k$ 个，对于剩下不足 $n$ 个球，设有 $p$ 个球，如果往后 $p$ 个盒子没有超过 $n$，就把后 $p$ 个盒子每一个盒子放一个球，否则，一直放到第 $n$ 个盒子，再从第一个盒子开始，放完剩下的球。

时间复杂度

$O(n{\log }_2(n))$，合格。

AC Code：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
long long n, m, a[200100], b[200100];
struct node{long long l, r;long long sum;
};
node t[1600100];
long long maketree(long long l, long long r, long long p) {t[p].l = l;t[p].r = r;if (l < r) {t[p].sum = maketree(l, (l + r) / 2, p * 2);t[p].sum += maketree((l + r) / 2 + 1, r, p * 2 + 1);}else {if (l) t[p].sum = a[l] - a[l - 1];else t[p].sum = 0;}return t[p].sum;
}
void add(long long i, long long k, long long p) {if (t[p].l <= i && t[p].r >= i) t[p].sum += k;else return;add(i, k, p * 2);add(i, k, p * 2 + 1);
}
long long get(long long l, long long r, long long p) {if (l <= t[p].l && t[p].r <= r) return t[p].sum;if (l > t[p].r || t[p].l > r) return 0;return get(l, r, p * 2) + get(l, r, p * 2 + 1);
}
void add1(long long l, long long r, long long k) {add(l, k, 1);if (r + 1 <= n) add(r + 1, -k, 1);
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m;for (long long i = 1; i <= n; i++) cin >> a[i];for (long long i = 1; i <= m; i++) cin >> b[i];for (long long i = 1; i <= m; i++) b[i]++;maketree(1, n, 1);for (long long i = 1; i <= m; i ++) {long long tmp = get(1, b[i], 1);add1(b[i], b[i], -tmp);long long tmp1 = tmp / n;add1(1, n, tmp1);long long tmp2 = tmp % n;if (tmp2 > n - b[i]) {add1(b[i] + 1, n, 1);add1(1, tmp2 - (n - b[i]), 1);}else {add1(b[i] + 1, b[i] + tmp2, 1);}}for (long long i = 1; i <= n; i ++) {cout << get(1, i, 1) << ' ';}cout << '\n';return 0;
}

F

题目

如果你知道了以 $(0,0),(A,B),(C,D)$ 为顶点的三角形的面积为 $\frac{|AD-BC|}{2}$，那么这个问题就很好解决了。

思路

题目给定了 $X,Y$，然后吧唧吧唧一大堆，就是想让我们求出一个 $A,B$，使得 $\frac{|AY-BX|}{2}$ 为 $1$，转换一下，就是 $|AY+(-B)X|=1$，这不就是典型的扩展欧几里得吗？

我们设 $g$ 为 $\gcd (X,Y)$，如果 $g\ge 3$ 那么说明无解，因为当 $AX+BY=\gcd (A,B)$ 时该方程才有解。将 $-Y,X$ 带入上述方程求出 $A,B$，将 $A,B$ 分别乘上 $\frac{2}{g}$ 就可以得到正确的答案。因为我们要求 $AX+BY=2$，而现在是 $AX+BY=g$，左右两边同时乘上 $\frac{2}{g}$ 即可。

AC Code：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
long long x, y;
long long e_gcd(long long a, long long b, long long &x, long long &y) {if (!b) {x = 1ll;y = 0ll;return a;}long long gcd = e_gcd(b, a % b, y, x);y -= a / b * x;return gcd;
}
long long a, b;
long long gcd(long long x, long long y) {if (y == 0ll) return x;return gcd(y, x % y);
}int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> x >> y;          long long g = gcd(x, y);e_gcd(y, -x, a, b);if (abs(g) >= 3ll) {cout << -1ll;return 0;}a *= 2ll / g, b *= 2ll / g;cout << a << ' ' << b;return 0;
}