• 欢迎光临~

# AtCoder Beginner Contest 254

A和B跳过。

## C - K Swap

AC代码
``````// Problem: C - K Swap
// Contest: AtCoder - AtCoder Beginner Contest 254
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//

#include <bits/stdc++.h>

#define CPPIO std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
#define freep(p) p ? delete p, p = nullptr, void(1) : void(0)

#ifdef BACKLIGHT
#include "debug.h"
#else
#define logd(...) ;
#endif

using i64 = int64_t;
using u64 = uint64_t;

void solve_case(int Case);

int main(int argc, char* argv[]) {
CPPIO;
int T = 1;
// std::cin >> T;
for (int t = 1; t <= T; ++t) {
solve_case(t);
}
return 0;
}

void solve_case(int Case) {
int n, k;
std::cin >> n >> k;

std::vector<int> a(n);
for (int i = 0; i < n; ++i)
std::cin >> a[i];

for (int i = 0; i < k; ++i) {
std::vector<int> b;
for (int j = i; j < n; j += k)
b.push_back(a[j]);
std::sort(b.begin(), b.end());
for (int j = i, p = 0; j < n; j += k)
a[j] = b[p++];
}

for (int i = 1; i < n; ++i)
if (a[i - 1] > a[i]) {
std::cout << "Non";
return;
}
std::cout << "Yesn";
}

``````

## D - Together Square

(x)的质因数分解为(x = prod {p_i}^{e_i})

(1)(n)中的数跑质因数分解求出所有(f(x))(O(n sqrt{n}))可以搞定。

AC代码
``````// Problem: D - Together Square
// Contest: AtCoder - AtCoder Beginner Contest 254
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//

#include <bits/stdc++.h>

#define CPPIO std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
#define freep(p) p ? delete p, p = nullptr, void(1) : void(0)

#ifdef BACKLIGHT
#include "debug.h"
#else
#define logd(...) ;
#endif

using i64 = int64_t;
using u64 = uint64_t;

void solve_case(int Case);

int main(int argc, char* argv[]) {
CPPIO;
int T = 1;
// std::cin >> T;
for (int t = 1; t <= T; ++t) {
solve_case(t);
}
return 0;
}

void solve_case(int Case) {
int n;
std::cin >> n;

std::vector<int> f(n + 1);
for (int i = 1; i <= n; ++i) {
f[i] = 1;
int x = i;
for (int j = 2; j * j <= i; ++j) {
if (x % j == 0) {
int e = 0;
while (x % j == 0) {
x /= j;
++e;
}
if (e & 1)
f[i] *= j;
}
}
if (x > 1)
f[i] *= x;
}

i64 ans = 0;
std::vector<int> cnt(n + 1);
for (int i = 1; i <= n; ++i) {
ans += 2 * cnt[f[i]] + 1;
++cnt[f[i]];
}

std::cout << ans << "n";
}

``````

## E - Small d and k

AC代码
``````// Problem: E - Small d and k
// Contest: AtCoder - AtCoder Beginner Contest 254
// Memory Limit: 1024 MB
// Time Limit: 3500 ms
//

#include <bits/stdc++.h>

#define CPPIO std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
#define freep(p) p ? delete p, p = nullptr, void(1) : void(0)

#ifdef BACKLIGHT
#include "debug.h"
#else
#define logd(...) ;
#endif

using i64 = int64_t;
using u64 = uint64_t;

void solve_case(int Case);

int main(int argc, char* argv[]) {
CPPIO;
int T = 1;
// std::cin >> T;
for (int t = 1; t <= T; ++t) {
solve_case(t);
}
return 0;
}

void solve_case(int Case) {
int n, m;
std::cin >> n >> m;

std::vector<std::vector<int>> g(n);
for (int i = 0; i < m; ++i) {
int u, v;
std::cin >> u >> v;
--u, --v;
g[u].push_back(v);
g[v].push_back(u);
}

auto Q = [&](int x, int k) -> i64 {
i64 ans = 0;

std::unordered_map<int, bool> vis;
std::queue<int> q;
q.push(x);
vis[x] = true;

for (int d = 0; d <= k; ++d) {
int size = q.size();
for (int i = 0; i < size; ++i) {
int u = q.front();
q.pop();

ans += u + 1;

for (int v : g[u]) {
if (vis.count(v))
continue;
vis[v] = true;
q.push(v);
}
}
}

return ans;
};

int q;
std::cin >> q;
for (int i = 0; i < q; ++i) {
int x, k;
std::cin >> x >> k;
--x;

std::cout << Q(x, k) << "n";
}
}

``````

## F - Rectangle GCD

AC代码
``````// Problem: F - Rectangle GCD
// Contest: AtCoder - AtCoder Beginner Contest 254
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//

#include <bits/stdc++.h>

#define CPPIO std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
#define freep(p) p ? delete p, p = nullptr, void(1) : void(0)

#ifdef BACKLIGHT
#include "debug.h"
#else
#define logd(...) ;
#endif

using i64 = int64_t;
using u64 = uint64_t;

void solve_case(int Case);

int main(int argc, char* argv[]) {
CPPIO;
int T = 1;
// std::cin >> T;
for (int t = 1; t <= T; ++t) {
solve_case(t);
}
return 0;
}

struct RMQ {
std::vector<int> lg;
std::vector<std::vector<int>> a;
RMQ(const std::vector<int>& d) {
int n = d.size();

lg = std::vector<int>(n + 1);
lg[1] = 0;
for (int i = 2; i <= n; ++i)
lg[i] = lg[i >> 1] + 1;

a = std::vector<std::vector<int>>(n, std::vector<int>(lg[n] + 1));
for (int i = 0; i < n; ++i)
a[i][0] = d[i];
for (int j = 1; j <= lg[n]; ++j) {
for (int i = 0; i + (1 << (j - 1)) < n; ++i) {
a[i][j] = std::gcd(a[i][j - 1], a[i + (1 << (j - 1))][j - 1]);
}
}
}

int query(int l, int r) {
int k = lg[r - l + 1];
return std::gcd(a[l][k], a[r - (1 << k) + 1][k]);
}
};

void solve_case(int Case) {
int n, q;
std::cin >> n >> q;

std::vector<int> a(n), b(n);
for (int i = 0; i < n; ++i)
std::cin >> a[i];
for (int i = 0; i < n; ++i)
std::cin >> b[i];

std::vector<int> da(n - 1), db(n - 1);
for (int i = 0; i + 1 < n; ++i) {
da[i] = a[i + 1] - a[i];
db[i] = b[i + 1] - b[i];
}

RMQ DA(da), DB(db);

for (int i = 0; i < q; ++i) {
int x1, y1, x2, y2;
std::cin >> x1 >> x2 >> y1 >> y2;
--x1, --y1, --x2, --y2;
int ans = a[x1] + b[y1];
logd(ans);
if (x2 > x1) {
ans = std::gcd(ans, DA.query(x1, x2 - 1));
}
if (y2 > y1) {
ans = std::gcd(ans, DB.query(y1, y2 - 1));
}
std::cout << ans << "n";
}
}

``````

## G - Elevators

(n)幢高为({10}^9)的大楼，你可以通过天桥以(1)的代价从某幢大楼的某一层走到另一幢大楼的同一层。

(m)台电梯((a_i, b_i, c_i))可以从第(a_i)幢大楼的第(x)层走到第(y)层，代价为(|x - y|)，其中(b_i le x, y le c_i)

AC代码
``````// Problem: G - Elevators
// Contest: AtCoder - AtCoder Beginner Contest 254
// Memory Limit: 1024 MB
// Time Limit: 6000 ms
//

#include <bits/stdc++.h>

#define CPPIO std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
#define freep(p) p ? delete p, p = nullptr, void(1) : void(0)

#ifdef BACKLIGHT
#include "debug.h"
#else
#define logd(...) ;
#endif

using i64 = int64_t;
using u64 = uint64_t;

void solve_case(int Case);

int main(int argc, char* argv[]) {
CPPIO;
int T = 1;
// std::cin >> T;
for (int t = 1; t <= T; ++t) {
solve_case(t);
}
return 0;
}

void solve_case(int Case) {
// Merge elevator with intersection.
auto merge = [](std::vector<std::array<int, 2>> a) -> std::vector<std::array<int, 2>> {
if (a.empty())
return {};

std::sort(a.begin(), a.end());
std::vector<std::array<int, 2>> temp;
temp.push_back(a[0]);
for (int i = 1; i < (int)a.size(); ++i) {
auto [l1, r1] = temp.back();
auto [l2, r2] = a[i];

if (l2 <= r1) {
temp.back()[1] = std::max(r1, r2);
} else {
temp.push_back({l2, r2});
}
}

return temp;
};

// Sort the elevators by r, and filter out elevators that covered completely by another elevator.
auto filter = [](std::vector<std::array<int, 2>> a) -> std::vector<std::array<int, 2>> {
if (a.empty())
return {};

std::sort(a.begin(), a.end());
std::vector<std::array<int, 2>> temp;
temp.push_back(a[0]);
for (int i = 1; i < (int)a.size(); ++i) {
auto [l1, r1] = temp.back();
auto [l2, r2] = a[i];

if (r2 <= r1)
continue;

if (l1 == l2)
temp.pop_back();

temp.push_back({l2, r2});
}

return temp;
};

// dp[i][j] means the highest elevator you can reach that starting from the i-th elevator and then
// use 2^j skybridge.
auto DP = [](const std::vector<std::array<int, 2>>& a) -> std::vector<std::vector<int>> {
int n = a.size();
int lg = std::__lg(n) + 1;
std::vector<std::vector<int>> dp(n, std::vector<int>(lg));

for (int i = 0, j = 0; i < n; ++i) {
while (j + 1 < n && a[j + 1][0] <= a[i][1])
++j;
dp[i][0] = j;
}

for (int j = 1; j < lg; ++j) {
for (int i = 0; i < n; ++i) {
dp[i][j] = dp[dp[i][j - 1]][j - 1];
}
}
return dp;
};

int n, m, q;
std::cin >> n >> m >> q;

std::vector<std::vector<std::array<int, 2>>> elev_in(n);
std::vector<std::array<int, 2>> elev_all;
for (int i = 0; i < m; ++i) {
int a, b, c;
std::cin >> a >> b >> c;
--a;
elev_in[a].push_back({b, c});
}
for (int i = 0; i < n; ++i) {
elev_in[i] = merge(elev_in[i]);
for (auto [l, r] : elev_in[i])
elev_all.push_back({l, r});
}
elev_all = filter(elev_all);

auto dp = DP(elev_all);
int lg = dp[0].size();

for (int _ = 0; _ < q; ++_) {
int x, y, z, w;
std::cin >> x >> y >> z >> w;
--x, --z;

// Make it always move from lower floor to higher floor.
if (y > w) {
std::swap(x, z);
std::swap(y, w);
}

// Split the answer into 2 parts, one part is cost of using elevator, the other is cost of using
// skybridges.

// The first part will always be w - y.
int ans = w - y;

// Try get closer to target by using elevator in the beginning building and the ending building.
// After this, it can not get higher without using skybridges.
{
auto it = std::lower_bound(elev_in[x].begin(), elev_in[x].end(),
std::array<int, 2>{y, 1'000'000'001});
if (it != elev_in[x].begin()) {
--it;
if (y <= (*it)[1])
y = (*it)[1];
}
}
{
auto it = std::lower_bound(elev_in[z].begin(), elev_in[z].end(),
std::array<int, 2>{w, 1'000'000'001});
if (it != elev_in[z].begin()) {
--it;
if (w <= (*it)[1])
w = (*it)[0];
}
}

// The second part.
if (y >= w) {
// Only need to use 1 skybridge. Or no need to use skybridge.
if (x != z)
++ans;
} else {
// Find the elevator that cover the the y-th floor and with **largest** r.
auto it =
std::lower_bound(elev_all.begin(), elev_all.end(), std::array<int, 2>{y, 1'000'000'001});
if (it == elev_all.begin()) {
// No such elevator and then there is no elevator can be used.
ans = -1;
} else {
--it;

if (y > (*it)[1]) {
// No such elevator and then there is no elevator can be used.
ans = -1;
} else {
// Found an elevator and move to building where the elevator located.
y = (*it)[1];
++ans;

if (y >= w) {
// Target achieved, move to the ending building (and use exatly 2 skybridges in total).
++ans;
} else {
// Optimized process using binary lifting. After this, y can reach the highest floor
// below w.
int p = it - elev_all.begin();
for (int i = lg - 1; i >= 0; --i) {
if (elev_all[dp[p][i]][1] < w) {
p = dp[p][i];
ans += (1 << i);
}
}

// One more jump.
p = dp[p][0];
++ans;

y = elev_all[p][1];
if (y < w) {
// Can not reach w.
ans = -1;
} else {
// Target achieved, move to the ending building.
++ans;
}
}
}
}
}

std::cout << ans << "n";
}
}

``````

TBA。