A
并查集，求权值前 大的联通块。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
#define range(a) begin(a), end(a)
struct UnionFind {
int n;
vector<int> f;
UnionFind(const int &n = 0) : n(n), f(n) {
iota(f.begin(), f.end(), 0);
}
int get(int x) {
while (x != f[x]) {
x = f[x] = f[f[x]];
}
return x;
}
bool unite(int x, int y) {
x = get(x), y = get(y);
if (x != y) {
f[y] = x;
return 1;
}
return 0;
}
bool united(int x, int y) {
return get(x) == get(y);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k, w;
cin >> n >> m >> k >> w;
vector<int> a(n), b(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
cin >> b[i];
}
UnionFind f(n);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
u--, v--;
if (b[u] == b[v]) {
f.unite(u, v);
}
}
vector<i64> sz(n);
for (int i = 0; i < n; i++) {
int j = f.get(i);
if (b[j] == 1) {
sz[j] += a[i];
}
}
sort(range(sz), greater());
i64 ans = 0;
k = max(1, k);
for (int i = 0; i < k; i++) {
ans += sz[i];
}
cout << ans << '\n';
return 0;
}
B
对于 ，有
三种状态，没有被两个区间中的任何一个区间覆盖，只被两个区间中的一个区间覆盖，同时被两个区间覆盖，前缀和。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
constexpr int P = 1000000007;
constexpr int N = 5E5;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> pw(n + 1);
pw[0] = 1;
for (int i = 0; i < n; i++) {
pw[i + 1] = pw[i] * 2LL % P;
}
vector<int> l1(n), l2(n), r1(n), r2(n);
for (int i = 0; i < n; i++) {
cin >> l1[i] >> r1[i] >> l2[i] >> r2[i];
}
vector<vector<int>> d(3, vector<int>(N + 1));
for (int i = 0; i < n; i++) {
vector<array<int, 2>> f;
f.push_back({l1[i], 1});
f.push_back({r1[i] + 1, -1});
f.push_back({l2[i], 1});
f.push_back({r2[i] + 1, -1});
sort(f.begin(), f.end());
int lst = 0;
int val = 0;
for (auto [x, v] : f) {
if (lst < x) {
d[val][lst]++;
d[val][x]--;
}
val += v;
lst = x;
}
d[0][lst]++;
}
for (int i = 0; i < 3; i++) {
for (int j = 1; j <= N; j++) {
d[i][j] += d[i][j - 1];
}
}
i64 ans = 0;
for (int x = 0; x <= N; x++) {
if (d[0][x] == 0) {
ans = (ans + pw[d[2][x]]) % P;
}
}
cout << ans << '\n';
return 0;
}
D
先做一次指令，可以到达 ，然后再跑一次就是
。
。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
int x, y, k;
cin >> x >> y >> k;
string s;
cin >> s;
int n = s.size();
if (!x && !y) {
cout << "Yes\n";
return;
}
int sx = 0, sy = 0;
for (int i = 0; i < n; i++) {
if (s[i] == 'U') {
sy++;
} else if (s[i] == 'D') {
sy--;
} else if (s[i] == 'L') {
sx--;
} else {
sx++;
}
if (sx == x && sy == y) {
cout << "Yes\n";
return;
}
}
if (!sx && !sy) {
cout << "No\n";
return;
}
int tx = 0, ty = 0;
for (int i = 0; i < n; i++) {
if (s[i] == 'U') {
ty++;
} else if (s[i] == 'D') {
ty--;
} else if (s[i] == 'L') {
tx--;
} else {
tx++;
}
int dx = x - tx, dy = y - ty;
if (dx && (!sx || dx % sx)) {
continue;
}
if (dy && (!sy || dy % sy)) {
continue;
}
int cx = sx ? dx / sx : 0;
int cy = sy ? dy / sy : 0;
if ((!cx || !cy || cx == cy) && cx >= 0 && cx < k && cy >= 0 && cy < k) {
cout << "Yes\n";
return;
}
}
cout << "No\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
E
计算几何。
。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
using Point = complex<double>;
const double Pi = acos(-1.0);
constexpr double eps = 1E-9;
Point rotate(const Point &p, const double &rad) {
return p * Point(cos(rad), -sin(rad));
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(2);
int n;
cin >> n;
Point v = Point(0, n * (cos(0.1 * Pi) + sin(0.1 * Pi) / tan(0.2 * Pi)));
Point p = Point(0, -n * sin(0.1 * Pi) / tan(0.2 * Pi));
for (int i = 0; i < 5; i++) {
v = rotate(v, 0.4 * Pi);
cout << char('A' + i) << ": ";
auto a = p + v;
cout << real(a) + eps << ' ' << imag(a) + eps << '\n';
}
return 0;
}
F
可以用 表。
。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
template <class T>
struct SparseTable {
int n;
vector<vector<T>> a;
function<T(T, T)> func = [](const T &a, const T &b) {
return a | b;
};
SparseTable(const vector<T> &init) : n(init.size()) {
int lg = __lg(n);
a.assign(lg + 1, vector<T>(n));
a[0] = init;
for (int i = 1; i <= lg; i++) {
for (int j = 0; j <= n - (1 << i); j++) {
a[i][j] = func(a[i - 1][j], a[i - 1][(1 << (i - 1)) + j]);
}
}
}
T get(int l, int r) { // [l, r)
int lg = __lg(r - l);
return func(a[lg][l], a[lg][r - (1 << lg)]);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<i64> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
SparseTable<i64> st(a);
for (int i = 0; i < m; i++) {
int l, r;
i64 x;
cin >> l >> r >> x;
l--;
cout << (st.get(l, r) | x) << '\n';
}
return 0;
}
G
栈。
。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string a, b, s;
cin >> a >> b >> s;
int n = s.size();
unordered_map<char, char> mp, id;
for (int i = 0; i < 13; i++) {
mp[b[i]] = a[i];
id[b[i]] = i + 1;
}
vector<int> st;
int pre = 0;
int ans = 0;
for (int i = 0; i < n; i++) {
if (mp.count(s[i]) && !st.empty() && mp[s[i]] == s[st.back()] && id[s[i]] >= pre) {
int res = i - st.back() + 1;
if (res >= 4) {
ans = max(ans, res);
}
st.pop_back();
pre = id[s[i]];
} else {
if (!st.empty() && st.back() != i - 1) {
st = {};
}
st.push_back(i);
pre = 0;
}
}
cout << ans << '\n';
return 0;
}
I
，
素性测试。
K
线性筛，前缀和。
。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
#define range(a) begin(a), end(a)
vector<int> isprime, primes;
void sieve(int n) {
isprime.assign(n + 1, 1);
isprime[0] = isprime[1] = 0;
for (int i = 2; i <= n; i++) {
if (isprime[i]) {
primes.push_back(i);
}
for (auto p : primes) {
if (i * p > n) {
break;
}
isprime[i * p] = 0;
if (i % p == 0) {
break;
}
}
}
}
void solve() {
int l, r;
cin >> l >> r;
cout << isprime[r] - isprime[l - 1] << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
sieve(1E6);
partial_sum(range(isprime), isprime.begin());
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
京公网安备 11010502036488号