A - Buy the String
贪心
int main() {
IOS;
for (cin >> _; _; --_) {
ll x, y, z; cin >> n >> x >> y >> z;
string s; cin >> s;
if (y > x + z) y = x + z;
if (x > y + z) x = y + z;
ll ans = 0;
for (auto &i : s) if (i - '0') ans += y; else ans += x;
cout << ans <<'
';
}
return 0;
}
B - Sum of Medians
倒着取
int main() {
IOS;
for (cin >> _; _; --_) {
cin >> n >> m; k = n * m;
rep (i, 1, k) cin >> a[i];
ll ans = 0, c = n - (n + 1) / 2;
for (int i = k - c, j = 1; j <= m; i -= c + 1, ++j) ans += a[i];
cout << ans << '
';
}
return 0;
}
C1 & C2 - Binary Table
先全部处理到最后的2*2的格子, 然后枚举
int n, m, _, k, t;
char s[105][105];
struct node { int a1, b1, a2, b2, a3, b3; };
void cal(char& c) { c = c == '0' ? '1' : '0'; }
int main() {
IOS;
for (cin >> _; _; --_) {
cin >> n >> m; t = 0;
rep(i, 1, n) cin >> s[i] + 1;
vector<node> ans;
rep(i, 1, n - 2) rep(j, 1, m) if(s[i][j] == '1')
ans.pb({ i, j, i + 1, j, i + 1, j < m ? j + 1 : j - 1 }),
cal(s[i][j]), cal(s[i + 1][j]), cal(s[i + 1][j < m ? j + 1 : j - 1]);
rep(j, 1, m - 2) rep(i, n - 1, n) if (s[i][j] == '1')
ans.pb({i, j, i, j + 1, i == n ? i - 1 : n, j + 1}),
cal(s[i][j]), cal(s[i][j + 1]), cal(s[i == n ? i - 1 : n][j + 1]);
if (s[n - 1][m - 1] == '1') t ^= 1 << 3;
if (s[n - 1][m] == '1') t ^= 1 << 2;
if (s[n][m - 1] == '1') t ^= 1 << 1;
if (s[n][m] == '1') t ^= 1;
if (t == 15) ans.pb({n - 1, m, n, m - 1, n, m}), t = 8;
if (t == 1) ans.pb({n - 1, m - 1, n - 1, m, n, m}), t = 12;
if (t == 2) ans.pb({n - 1, m - 1, n - 1, m, n, m - 1}), t = 12;
if (t == 4) ans.pb({n - 1, m, n, m - 1, n, m}), t = 3;
if (t == 8) ans.pb({n - 1, m - 1, n, m - 1, n, m}), t = 3;
if (t == 3) ans.pb({n - 1, m - 1, n - 1, m, n, m - 1}), t = 13;
if (t == 5) ans.pb({n - 1, m - 1, n - 1, m, n, m - 1}), t = 11;
if (t == 6) ans.pb({n - 1, m - 1, n - 1, m, n, m}), t = 11;
if (t == 9) ans.pb({n - 1, m, n, m - 1, n, m}), t = 14;
if (t == 10) ans.pb({n - 1, m, n, m - 1, n, m}), t = 13;
if (t == 12) ans.pb({n - 1, m, n, m - 1, n, m}), t = 11;
if (t == 7) ans.pb({n - 1, m, n, m - 1, n, m}), t = 0;
if (t == 11) ans.pb({n - 1, m - 1, n, m - 1, n, m}), t = 0;
if (t == 13) ans.pb({n - 1, m - 1, n - 1, m, n, m}), t = 0;
if (t == 14) ans.pb({n - 1, m - 1, n - 1, m, n, m - 1}), t = 0;
cout << ans.size() << '
';
for (auto& i : ans) cout << i.a1 << ' ' << i.b1 << ' ' << i.a2 << ' ' << i.b2 << ' ' << i.a3 << ' ' << i.b3 << '
';
}
return 0;
}
E
线段树, 搞上区间的 min 和 max 和区间 长度与和, 打上标记
const int N = 2e5 + 5;
struct BIT {
struct node {
int l, r, len;
ll val, tag, mi, mx;
} tr[N << 2];
void push_up(int rt) {
tr[rt].val = tr[rt << 1].val + tr[rt << 1 | 1].val;
tr[rt].mi = min(tr[rt << 1].mi, tr[rt << 1 | 1].mi);
tr[rt].mx = max(tr[rt << 1].mx, tr[rt << 1 | 1].mx);
}
void push_down(int rt) {
ll tag = tr[rt].tag; tr[rt].tag = 0;
if (!tag) return;
tr[rt << 1].val = tag * tr[rt << 1].len;
tr[rt << 1 | 1].val = tag * tr[rt << 1 | 1].len;
tr[rt << 1].mi = tr[rt << 1].mx = tag;
tr[rt << 1 | 1].mi = tr[rt << 1 | 1].mx = tag;
tr[rt << 1].tag = tr[rt << 1 | 1].tag = tag;
}
void build(int rt, int l, int r, ll* a) {
tr[rt].l = l; tr[rt].r = r; tr[rt].len = r - l + 1;
if (l == r) { tr[rt].val = tr[rt].mi = tr[rt].mx = a[l]; return; }
int mid = l + r >> 1;
build(rt << 1, l, mid, a);
build(rt << 1 | 1, mid + 1, r, a);
push_up(rt);
}
void change(int rt, int l, int r, ll k) {
if (tr[rt].mi >= k) return;
if (tr[rt].l >= l && tr[rt].r <= r && tr[rt].mx <= k) {
tr[rt].val = k * tr[rt].len;
tr[rt].mx = tr[rt].mi = k;
tr[rt].tag = k; return;
}
push_down(rt);
int mid = tr[rt].l + tr[rt].r >> 1;
if (mid >= l) change(rt << 1, l, r, k);
if (mid < r) change(rt << 1 | 1, l, r, k);
push_up(rt);
}
int ask(int rt, int l, int r, ll& m) {
if (tr[rt].mi > m) return 0;
if (tr[rt].l >= l && tr[rt].r <= r && tr[rt].val <= m) {
m -= tr[rt].val; return tr[rt].len;
}
push_down(rt);
int mid = tr[rt].l + tr[rt].r >> 1, ans = 0;
if (mid >= l) ans += ask(rt << 1, l, r, m);
if (r > mid) ans += ask(rt << 1 | 1, l, r, m);
push_up(rt);
return ans;
}
} bit;
int n, m, _, k;
ll a[N];
int main() {
IOS; cin >> n >> m;
rep(i, 1, n) cin >> a[i];
bit.build(1, 1, n, a);
rep(i, 1, m) {
ll op, x, y; cin >> op >> x >> y;
if (op == 1) bit.change(1, 1, x, y);
else cout << bit.ask(1, x, n, y) << '
';
}
return 0;
}