A
。
#include "bits/stdc++.h"
using namespace std;
using i64 = int64_t;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int a, b, c, n;
cin >> a >> b >> c >> n;
int ans = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x > b && x < c) {
ans++;
}
}
cout << ans << '\n';
return 0;
}
B
考虑反面。
#include "bits/stdc++.h"
using namespace std;
using i64 = int64_t;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
if (n < 5) {
cout << "0.000\n";
return 0;
}
cout << fixed << setprecision(3) << 1. - pow(0.97, (n - 5) / 2) << '\n';
return 0;
}
C
。
#include "bits/stdc++.h"
using namespace std;
using i64 = int64_t;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int ans = 1E9;
for (int i = 0; i + 1 < n; i++) {
ans = min(ans, max(0, a[i + 1] - a[i] + 2) / 2);
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
D
原。
#include "bits/stdc++.h"
using namespace std;
using i64 = int64_t;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int a, b, c;
cin >> a >> b >> c;
if (a > b + c) {
if (a == 1) {
cout << "YES\n0\n";
} else {
cout << "YES\n" << 2 * (b + c) + 1 << '\n';
}
} else {
cout << "NO\n";
}
return 0;
}
E
。
#include "bits/stdc++.h"
using namespace std;
using i64 = int64_t;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
string s;
cin >> n >> k >> s;
vector<int> c(52);
for (int i = 0; i < n; i++) {
if (s[i] >= 'A' && s[i] <= 'Z') {
c[s[i] - 'A']++;
} else {
c[s[i] - 'a' + 26]++;
}
}
int ans = 0, more = 0;
for (int i = 0; i < 26; i++) {
more += abs(c[i] - c[i + 26]) / 2;
ans += min(c[i], c[i + 26]);
}
ans += min(more, k);
cout << ans << '\n';
return 0;
}
F
按题意说的写。
G
bitset。
。
#include "bits/stdc++.h"
using namespace std;
using i64 = int64_t;
constexpr int N = 2.5E7;
bitset<N + 1> f;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int sum = accumulate(a.begin(), a.end(), 0);
f[0] = 1;
for (int i = 0; i < n; i++) {
f |= (f << a[i]);
}
int ans = 2E9;
for (int i = 0; i <= N; i++) {
if (f[i]) {
ans = min(ans, abs(2 * i - sum));
}
}
cout << ans << '\n';
return 0;
}
H
双指针。
。
#include "bits/stdc++.h"
using namespace std;
using i64 = int64_t;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, d;
cin >> n >> d;
d--;
vector<int> s(n), p(n);
for (int i = 0; i < n; i++) {
cin >> s[i];
}
for (int i = 0; i < n; i++) {
cin >> p[i];
}
s[d] += p[0];
int ans = d;
for (int i = d - 1, j = 1; i >= 0; i--) {
while (j < n && p[j] + s[i] > s[d]) {
j++;
}
if (j < n && p[j] + s[i] <= s[d]) {
j++;
ans = i;
}
}
cout << ans + 1 << '\n';
return 0;
}
I
本质是对于两个字符串，比较最长匹配前缀的下一个字母。
这里使用二分哈希。
。
#include "bits/stdc++.h"
using namespace std;
using i64 = int64_t;
constexpr int B = 777;
constexpr int64_t P = 100000000000031;
int64_t *p;
void init(int N) {
p = new int64_t [N + 1];
p[0] = 1;
for (int i = 1; i <= N; i++) {
p[i] = p[i - 1] * B % P;
}
}
struct StringHash {
vector<int64_t> h;
StringHash() : h(1) {}
void push_back(char ch) {
h.push_back((h.back() * B + ch) % P);
}
long long get(int l, int r) {
return (h[r] + __int128(h[l]) * (P - p[r - l])) % P;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init(2E5);
int n, m, q;
string s, t;
cin >> n >> m >> q >> s >> t;
StringHash hs0, hs1;
for (int i = 0; i < n; i++) {
hs0.push_back(s[i]);
}
for (int i = 0; i < m; i++) {
hs1.push_back(t[i]);
}
while (q--) {
int l0, r0, l1, r1;
cin >> l0 >> r0 >> l1 >> r1;
l0--, l1--;
int l = 1, r = r0 - l0;
while (l <= r) {
int m0 = (l + r) >> 1;
if (hs0.get(l0, l0 + m0) == hs1.get(l1, l1 + m0)) {
l = m0 + 1;
} else {
r = m0 - 1;
}
}
int len = l - 1;
if (len == r0 - l0) {
cout << '=';
} else {
cout << (s[l0 + len] < t[l1 + len] ? '<' : '>');
}
cout << '\n';
}
return 0;
}
J
状态压缩，dp。
K
原。
可以 RMQ 进行 的预处理搞出区间
值，然后每次就可以
回答任意区间的
值。然后考虑
枚举区间左端点，然后每次右端点从左往右二分 + RMQ 找到第一个会让区间
变化的位置，并累加答案。
至多只会变化
次，复杂度为
。
#include "bits/stdc++.h"
using namespace std;
using i64 = int64_t;
constexpr int P = 998244353;
i64 power(i64 a, i64 b, int p = P) {
i64 res = 1;
for (; b; b >>= 1, a = a * a % p) {
if (b & 1) {
res = res * a % p;
}
}
return res;
}
i64 inv(i64 x) {
return power(x, P - 2);
}
template <class T, typename F = function<T(T, T)>>
struct SparseTable {
int n;
vector<vector<T>> a;
F func;
SparseTable(const vector<T> &init, const F &f) : n(init.size()), func(f) {
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) {
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;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
SparseTable<int> ag(a, [](int a, int b) {
return gcd(a, b);
});
i64 ans = 0;
for (int i = 0; i < n; i++) {
int g = 0;
for (int j = i; j < n; ) {
g = gcd(g, a[j]);
int l = j + 1, r = n;
while (l <= r) {
int m = (l + r) >> 1;
if (ag.get(i, m) == g) {
l = m + 1;
} else {
r = m - 1;
}
}
ans = (ans + i64(g) * (l - 1 - j) % P * (l + j - i - i) % P) % P;
j = l - 1;
}
}
ans = ans * inv(n) % P * inv(n + 1) % P;
cout << ans << '\n';
return 0;
}
京公网安备 11010502036488号