放个代码，F提供一个不动态开点的方法
A题：
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::string s;
std::cin >> s;
int ans = 0;
for (int i = 1; i < s.size(); i ++ ) {
if (s[i] != s[i - 1]) {
ans ++;
}
}
std::cout << ans << '\n';
return 0;
}
B题：
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::string s;
std::cin >> s;
int len = 0;
i64 ans = 0;
for (int i = 1; i < s.size(); i ++ ) {
if (s[i] != s[i - 1]) {
if (len == 0) {
len = 2;
}else {
len ++;
}
}else {
if (len) {
ans += (i64)(len - 1) * len / 2;
}
len = 0;
}
}
if (len) {
ans += (i64)(len - 1) * len / 2;
}
std::cout << ans << '\n';
return 0;
}
C题：
#include <bits/stdc++.h>
using i64 = long long;
void solve() {
int a, b, k;
std::cin >> a >> b >> k;
if (k == 0) {
if (a && b) {
std::cout << -1 << '\n';
}else {
if (a) {
std::cout << std::string(a, '0') << '\n';
}else {
std::cout << std::string(b, '1') << '\n';
}
}
return;
}
if (k >= 2 * std::min(a, b) + (a != b)) {
std::cout << -1 << '\n';
return;
}
//101010111111111
std::vector<int> cnt(2 * std::min(a, b) + 3, 1);
cnt[2 * std::min(a, b) + 1] = std::max(a, b) - std::min(a, b);
cnt[2 * std::min(a, b) + 2] = 0;
int ed = 2 * std::min(a, b) + 1;
while (ed - 1 > k) {
cnt[ed - 2] += cnt[ed];
cnt[ed] = 0;
ed --;
}
for (int i = 1; cnt[i]; i ++ ) {
if (i & 1) {
if (a >= b) {
std::cout << std::string(cnt[i], '0');
}else {
std::cout << std::string(cnt[i], '1');
}
}else {
if (a >= b) {
std::cout << std::string(cnt[i], '1');
}else {
std::cout << std::string(cnt[i], '0');
}
}
}
std::cout << '\n';
return;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int tt = 1; std::cin >> tt;
while (tt -- ) solve();
return 0;
}
D题：
#include <bits/stdc++.h>
using i64 = long long;
constexpr i64 inf = 1E15;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, x, y;
std::cin >> n >> x >> y;
std::string s;
std::cin >> s;
std::vector<i64> dp(n, inf);
std::vector<int> next1(n), next0(n);
int one = n, zero = n;
for (int i = n - 1; i >= 0; i -- ) {
next1[i] = one, next0[i] = zero;
if (s[i] == '1') {
one = i;
}else {
zero = i;
}
}
dp[0] = 0;
for (int i = 0; i < n; i ++ ) {
if (next1[i] < n) {
if (s[i] == '1') {
dp[next1[i]] = std::min(dp[next1[i]], dp[i] + x);
}else {
dp[next1[i]] = std::min(dp[next1[i]], dp[i] + y);
}
}
if (next0[i] < n) {
if (s[i] == '0') {
dp[next0[i]] = std::min(dp[next0[i]], dp[i] + x);
}else {
dp[next0[i]] = std::min(dp[next0[i]], dp[i] + y);
}
}
}
std::cout << dp[n - 1] << '\n';
return 0;
}
E题：
#include <bits/stdc++.h>
using i64 = long long;
template<class T>
constexpr T power(T a, i64 b) {
T res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
constexpr i64 mul(i64 a, i64 b, i64 p) {
i64 res = a * b - i64(1.L * a * b / p) * p;
res %= p;
if (res < 0) {
res += p;
}
return res;
}
template<int P>
struct MInt {
int x;
constexpr MInt() : x{} {}
constexpr MInt(i64 x) : x{norm(x % getMod())} {}
static int Mod;
constexpr static int getMod() {
if (P > 0) {
return P;
} else {
return Mod;
}
}
constexpr static void setMod(int Mod_) {
Mod = Mod_;
}
constexpr int norm(int x) const {
if (x < 0) {
x += getMod();
}
if (x >= getMod()) {
x -= getMod();
}
return x;
}
constexpr int val() const {
return x;
}
explicit constexpr operator int() const {
return x;
}
constexpr MInt operator-() const {
MInt res;
res.x = norm(getMod() - x);
return res;
}
constexpr MInt inv() const {
assert(x != 0);
return power(*this, getMod() - 2);
}
constexpr MInt &operator*=(MInt rhs) & {
x = 1LL * x * rhs.x % getMod();
return *this;
}
constexpr MInt &operator+=(MInt rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr MInt &operator-=(MInt rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr MInt &operator/=(MInt rhs) & {
return *this *= rhs.inv();
}
friend constexpr MInt operator*(MInt lhs, MInt rhs) {
MInt res = lhs;
res *= rhs;
return res;
}
friend constexpr MInt operator+(MInt lhs, MInt rhs) {
MInt res = lhs;
res += rhs;
return res;
}
friend constexpr MInt operator-(MInt lhs, MInt rhs) {
MInt res = lhs;
res -= rhs;
return res;
}
friend constexpr MInt operator/(MInt lhs, MInt rhs) {
MInt res = lhs;
res /= rhs;
return res;
}
friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
i64 v;
is >> v;
a = MInt(v);
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
return os << a.val();
}
friend constexpr bool operator==(MInt lhs, MInt rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MInt lhs, MInt rhs) {
return lhs.val() != rhs.val();
}
};
constexpr int P = 1000000007;
using Z = MInt<P>;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::string s;
std::cin >> s;
int n = s.size();
std::vector<std::vector<Z>> dp(2, std::vector<Z>(13));
if (s[0] != '?') {
dp[s[0] - '0'][s[0] - '0'] = 1;
}else {
dp[1][1] = dp[0][0] = 1;
}
for (int i = 1; i < n; i ++ ) {
std::vector<std::vector<Z>> ndp(2, std::vector<Z>(13));
for (int j = 0; j < 2; j ++ ) {
for (int k = 0; k < 13; k ++ ) {
ndp[j][k * 10 % 13] += dp[j][k];
dp[j][k] = 0;
}
}
if (s[i] == '0') {
for (int j = 0; j < 13; j ++ ) {
dp[0][j] += ndp[0][j] + ndp[1][j];
}
}else if (s[i] == '1') {
for (int j = 0; j < 13; j ++ ) {
dp[1][(j + 1) % 13] += ndp[1][j] + ndp[0][j];
}
}else {
for (int j = 0; j < 13; j ++ ) {
dp[0][j] += ndp[0][j] + ndp[1][j];
}
for (int j = 0; j < 13; j ++ ) {
dp[1][(j + 1) % 13] += ndp[1][j] + ndp[0][j];
}
}
}
if (s.back() != '?') {
std::cout << dp[s.back() - '0'][0] << '\n';
}else {
std::cout << (dp[0][0] + dp[1][0]) << '\n';
}
return 0;
}
F题：
做法：离线线段树 首先我们将所有要用到的点进行离散化，这样就可以缩水到4e5个来进行线段树
然后对于1，3，5，9，1000，以下述方式放入线段树
我们放入[1,1],(1,3),[3,3],(3,5),[5,5],(5,9),[9,9],(9,1000),[1000,1000]
然后分成最后变成01010或者1010进行分析，其实是一样的，我们只需统计一个same即可，same是和0101上数字相同的个数，之后就是纯懒标记线段树了
#include <bits/stdc++.h>
using i64 = long long;
constexpr int inf = 1E9 + 7;
template<class Info, class Tag>
struct LazySegmentTree {
int n;
std::vector<Info> info;
std::vector<Tag> tag;
LazySegmentTree() : n(0) {}
LazySegmentTree(int n_, Info v_ = Info()) {
init(n_, v_);
}
template<class T>
LazySegmentTree(std::vector<T> init_) {
init(init_);
}
void init(int n_, Info v_ = Info()) {
init(std::vector(n_, v_));
}
template<class T>
void init(std::vector<T> init_) {
n = init_.size();
info.assign(4 << (int)std::log2(n), Info());
tag.assign(4 << (int)std::log2(n), Tag());
std::function<void(int, int, int)> build = [&](int p, int l, int r) {
if (r - l == 1) {
info[p] = init_[l];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m, r);
pull(p);
};
build(1, 0, n);
}
void pull(int p) {
info[p] = info[2 * p] + info[2 * p + 1];
}
void apply(int p, const Tag &v) {
info[p].apply(v);
tag[p].apply(v);
}
void push(int p) {
apply(2 * p, tag[p]);
apply(2 * p + 1, tag[p]);
tag[p] = Tag();
}
void modify(int p, int l, int r, int x, const Info &v) {
if (r - l == 1) {
info[p] = v;
return;
}
int m = (l + r) / 2;
push(p);
if (x < m) {
modify(2 * p, l, m, x, v);
} else {
modify(2 * p + 1, m, r, x, v);
}
pull(p);
}
void modify(int p, const Info &v) {
modify(1, 0, n, p, v);
}
Info rangeQuery(int p, int l, int r, int x, int y) {
if (l >= y || r <= x) {
return Info();
}
if (l >= x && r <= y) {
return info[p];
}
int m = (l + r) / 2;
push(p);
return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
}
Info rangeQuery(int l, int r) {
return rangeQuery(1, 0, n, l, r);
}
void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
if (l >= y || r <= x) {
return;
}
if (l >= x && r <= y) {
apply(p, v);
return;
}
int m = (l + r) / 2;
push(p);
rangeApply(2 * p, l, m, x, y, v);
rangeApply(2 * p + 1, m, r, x, y, v);
pull(p);
}
void rangeApply(int l, int r, const Tag &v) {
return rangeApply(1, 0, n, l, r, v);
}
void half(int p, int l, int r) {
if (info[p].act == 0) {
return;
}
if ((info[p].min + 1) / 2 == (info[p].max + 1) / 2) {
apply(p, {-(info[p].min + 1) / 2});
return;
}
int m = (l + r) / 2;
push(p);
half(2 * p, l, m);
half(2 * p + 1, m, r);
pull(p);
}
void half() {
half(1, 0, n);
}
template<class F>
int findFirst(int p, int l, int r, int x, int y, F &&pred) {
if (l >= y || r <= x) {
return -1;
}
if (l >= x && r <= y && !pred(info[p])) {
return -1;
}
if (r - l == 1) {
return l;
}
int m = (l + r) / 2;
push(p);
int res = findFirst(2 * p, l, m, x, y, pred);
if (res == -1) {
res = findFirst(2 * p + 1, m, r, x, y, pred);
}
return res;
}
template<class F>
int findFirst(int l, int r, F &&pred) {
return findFirst(1, 0, n, l, r, pred);
}
template<class F>
int findLast(int p, int l, int r, int x, int y, F &&pred) {
if (l >= y || r <= x) {
return -1;
}
if (l >= x && r <= y && !pred(info[p])) {
return -1;
}
if (r - l == 1) {
return l;
}
int m = (l + r) / 2;
push(p);
int res = findLast(2 * p + 1, m, r, x, y, pred);
if (res == -1) {
res = findLast(2 * p, l, m, x, y, pred);
}
return res;
}
template<class F>
int findLast(int l, int r, F &&pred) {
return findLast(1, 0, n, l, r, pred);
}
void maintainL(int p, int l, int r, int pre) {
if (info[p].difl > 0 && info[p].maxlowl < pre) {
return;
}
if (r - l == 1) {
info[p].max = info[p].maxlowl;
info[p].maxl = info[p].maxr = l;
info[p].maxlowl = info[p].maxlowr = -inf;
return;
}
int m = (l + r) / 2;
push(p);
maintainL(2 * p, l, m, pre);
pre = std::max(pre, info[2 * p].max);
maintainL(2 * p + 1, m, r, pre);
pull(p);
}
void maintainL() {
maintainL(1, 0, n, -1);
}
void maintainR(int p, int l, int r, int suf) {
if (info[p].difr > 0 && info[p].maxlowr < suf) {
return;
}
if (r - l == 1) {
info[p].max = info[p].maxlowl;
info[p].maxl = info[p].maxr = l;
info[p].maxlowl = info[p].maxlowr = -inf;
return;
}
int m = (l + r) / 2;
push(p);
maintainR(2 * p + 1, m, r, suf);
suf = std::max(suf, info[2 * p + 1].max);
maintainR(2 * p, l, m, suf);
pull(p);
}
void maintainR() {
maintainR(1, 0, n, -1);
}
};
struct Tag {
int t1 = 0, t2 = 0;
Tag() {};
Tag(int a, int b) : t1(a), t2(b) {};
void apply(const Tag &t) & {
if (t.t2) {
t1 = t.t1;
t2 = t.t2;
}else {
t1 += t.t1;
}
}
};
struct Info {
int st = 0;
int len = 0;
int same = 0;
Info() {};
Info(int a, int b, int c) : st(a), len(b), same(c) {};
void apply(const Tag &t) & {
if (t.t2) {
if (st & 1) {
same = len / 2;
}else {
same = (len + 1) / 2;
}
if (t.t1 & 1) {
same = len - same;
}
}else if (t.t1 & 1) {
same = len - same;
}
}
};
Info operator+(const Info &a, const Info &b) {
Info c;
c.st = std::min(a.st, b.st);
c.len = a.len + b.len;
c.same = a.same + b.same;
return c;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, q;
std::cin >> n >> q;
std::vector<std::array<int, 5>> query(q);
std::vector<int> s;
for (int i = 0; i < q; i ++ ) {
int op, l, r;
std::cin >> op >> l >> r;
query[i] = {op, l, r, l, r};
s.push_back(l);
s.push_back(r);
}
std::sort(s.begin(), s.end());
s.erase(std::unique(s.begin(), s.end()), s.end());
for (int i = 0; i < q; i ++ ) {
query[i][3] = std::lower_bound(s.begin(), s.end(), query[i][3]) - s.begin();
query[i][4] = std::lower_bound(s.begin(), s.end(), query[i][4]) - s.begin();
}
std::vector<Info> to;
std::map<int, int> lsh;
for (int i = 0, j = 0; i < s.size(); i ++ ) {
if (i) {
if (s[i] - s[i - 1] > 1) {
int len = s[i] - 1 - s[i - 1], same = 0;
if ((s[i - 1] + 1) % 2 == 1) {
same = (len + 1) / 2;
}else {
same = len / 2;
}
to.push_back({s[i - 1] + 1, len, same});
j ++;
}
}
to.push_back({s[i], 1, (s[i] & 1)});
lsh[s[i]] = j ++;
}
for (int i = 0; i < q; i ++ ) {
query[i][1] = lsh[query[i][1]];
query[i][2] = lsh[query[i][2]];
}
LazySegmentTree<Info, Tag> seg(to);
for (auto [op, l, r, l1, r1] : query) {
if (op == 1) {
seg.rangeApply(l, r + 1, {0, 1});
}else if (op == 2) {
seg.rangeApply(l, r + 1, {1, 0});
}else {
int t = seg.rangeQuery(l, r + 1).same;
std::cout << s[r1] - s[l1] + 1 - std::max(t, s[r1] - s[l1] + 1 - t) << '\n';
}
}
return 0;
}
京公网安备 11010502036488号