A – Arithmetic Progression (abc340 A)
题目大意
给定等差数列的首项
、末项
、公差
。
输出这个等差数列。
解题思路
从首相
依次累加公差
到末项
即可。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int a, b, d;
cin >> a >> b >> d;
while (a
B – Append (abc340 B)
题目大意
依次进行(Q)次操作,分两种。
-
1 x
,将x
放到数组(a)的末尾。 -
2 k
,输出数组(a)的倒数第 (k)项。
解题思路
用vector
模拟即可,操作2
可快速寻址访问。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int q;
cin >> q;
vector a;
while (q--) {
int op;
cin >> op;
if (op == 1) {
int x;
cin >> x;
a.push_back(x);
} else {
int k;
cin >> k;
cout
C – Divide and Divide (abc340 C)
题目大意
黑板一个数(x),依次进行以下操作,直到黑板上的数全是(1)。
- 将 (x)擦去,写上 (lfloor x rfloor)和 (lceil x rceil),耗费 (x)精力。
问最后耗费精力的和。
解题思路
朴素做法就一个简单的队列模拟即可。
但这会超时,因为对于同一个数可能会出现多次,而上述做法会对每个数都进行一次操作,这样之后的数的个数是指数增长的。
如何优化呢?那就是对于出现多次的同一个数,我们一次全部做完。
即记录(cnt[x])表示黑板上 (x) 的出现次数,然后我们分解它,(cnt[lfloor x rfloor] += cnt[x], cnt[lceil x rceil] += cnt[x])。为了不重复分解,每次取最大的数进行分解即可。
感觉上这样分解的次数不会超过 (O(log))或者 (O(log^2)) 次。
神奇的代码
#include
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;
set team;
map cnt;
cnt[n] = 1;
team.insert(n);
LL ans = 0;
while (!team.empty()) {
LL u = *team.rbegin();
if (u == 1)
break;
team.erase(u);
if (cnt[u] > 0) {
ans += u * cnt[u];
team.insert(u / 2);
cnt[u / 2] += cnt[u];
team.insert(u - u / 2);
cnt[u - u / 2] += cnt[u];
cnt[u] = 0;
}
}
cout
D – Super Takahashi Bros. (abc340 D)
题目大意
(n)个关卡,初始只能打第一关卡。
对于第 (i)关卡,可以花 (a_i)代价解锁第 (i+1)关卡,或花 (b_i)代价解锁第 (x_i)关卡。
问解锁第 (n)关卡的最小代价。
解题思路
虽然说是解锁,但很显然打的下一关肯定是刚刚解锁的关卡。
根据上述解锁关系建一张图,边权就是解锁代价,原问题就是问点(1)到点 (n)的最短距离,跑一遍 dijkstra
即可。
神奇的代码
#include
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>> edge(n);
for (int i = 0; i > a >> b >> d;
--d;
edge[i].push_back({i + 1, a});
edge[i].push_back({d, b});
}
priority_queue, vector>, greater>>
pq;
vector dis(n, 1e18);
dis[0] = 0;
pq.push({0, 0});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dis[u])
continue;
for (auto [v, w] : edge[u]) {
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
pq.push({dis[v], v});
}
}
}
cout
E – Mancala 2 (abc340 E)
题目大意
(n)个盒子,第 (i)个盒子有 (a_i)个球。
依次进行以下 (m)次操作:
- 第 (i)次操作,将第 (b_i)个盒子的所有球均分,多余的球从第(b_i + 1)个盒子依次放一个。
问最后每个盒子的球数量。
解题思路
朴素做法为(O(nm)),考虑优化每次操作的复杂度。
注意到均分
和放一个
都是区间加法,用线段树维护即可,时间复杂度是(O(mlog n))。
神奇的代码
#include
using namespace std;
using LL = long long;
const int N = 5e5 + 10;
class segment {
#define lson (root & a) {
if (l == r) {
sum[root] = a[l - 1];
lazy[root] = 0;
return;
}
int mid = (l + r) >> 1;
build(lson, l, mid, a);
build(rson, mid + 1, r, a);
lazy[root] = 0;
}
void pushdown(int root) {
if (lazy[root]) {
sum[lson] += lazy[root];
sum[rson] += lazy[root];
lazy[lson] += lazy[root];
lazy[rson] += lazy[root];
lazy[root] = 0;
}
}
void update(int root, int l, int r, int L, int R, LL val) {
if (L > 1;
if (L mid)
update(rson, mid + 1, r, L, R, val);
}
LL query(int root, int l, int r, int pos) {
if (l == r) {
return sum[root];
}
pushdown(root);
int mid = (l + r) >> 1;
if (pos > n >> m;
vector a(n);
for (auto& i : a)
cin >> i;
sg.build(1, 1, n, a);
for (int i = 0; i > b;
++b;
LL cnt = sg.query(1, 1, n, b);
sg.update(1, 1, n, b, b, -cnt);
LL div = cnt / n;
if (div)
sg.update(1, 1, n, 1, n, div);
LL mo = cnt % n;
if (mo) {
if (b + mo
F – S = 1 (abc340 F)
题目大意
给定点((x_0, y_0)),求一整数点 ((a,b)),使得 ((0,0), (a, b), (x_0,y_0)) 形成的三角形的面积为(1)。
解题思路
考虑将((0,0) to (x_0,y_0)) 作为三角形的底,高的长度(h) 需满足(frac{1}{2} h sqrt{x_0^2 + y_0^2} = 1)
即将直线((0,0) to (x_0,y_0)) 平移一下,距离其为(h)的直线即为 ((a,b))所处的位置。
直线 ((0,0) -> (x_0,y_0)) 的直线方程为(y_0 x – x_0 y = 0)
根据两平行直线的方程,得((a,b))所处的直线为 (y_0 x – x_0 y + c = 0)。
根据俩平行直线距离公式,得其距离为(frac{|c|}{sqrt{x_0^2 + y_0^2}}),其为三角形的高 (h),代入上述公式得 (|c| = 2)。
因此得到了 ((a,b))所处的直线方程为 (y_0 x – x_0 y + 2 = 0)以及(y_0 x – x_0 y – 2 = 0) 。
现在的问题就是找到一组整数解((x,y)),满足上述方程。
注意到上述即为一个不定方程,用扩展欧几里德
解得即可。
神奇的代码
#include
using namespace std;
using LL = long long;
template T extgcd(T a, T b, T& x, T& y) {
if (a == 0) {
x = 0;
y = 1;
return b;
}
T p = b / a;
T g = extgcd(b - p * a, a, y, x);
x -= p * y;
return g;
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
LL a, b;
cin >> a >> b;
auto ok = [](LL a, LL b) {
LL x, y;
LL d = extgcd(b, a, x, y);
if (2 % d != 0) {
return false;
}
cout
G – Leaf Color (abc340 G)
题目大意
给定一棵树,点有颜色。
问子树的数量,其叶子颜色相同。
解题思路
神奇的代码
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net