「题解」蓝书第〇章 - 例题
2025/3/6大约 10 分钟
「题解」蓝书第〇章 - 例题
「中国有句古话，叫做『闷声大发财』，我觉得是最好的。」
0x01 位运算
i64 pow(int a, int b, int p) {
i64 ans = 1 % p;
while (b) {
if (b & 1) {
ans = ans * a % p;
}
a = (i64)a * a % p;
b >>= 1;
}
return ans;
}
void solve() {
int a, b, p;
cin >> a >> b >> p;
cout << format("{}^{} mod {}={}\n", a, b, p, pow(a, b, p));
}i64 mul(i64 a, i64 b, i64 p) {
i64 ans = 0;
while (b) {
if (b & 1) {
ans = (ans + a) % p;
}
a = a * 2 % p;
b >>= 1;
}
return ans;
}
void solve() {
i64 a, b, p;
cin >> a >> b >> p;
cout << mul(a, b, p) << "\n";
}void solve() {
int n, m;
cin >> n >> m;
vector<int> op(n);
vector t(n, array<int, 31>{});
for (int i = 0; i < n; i ++) {
string top;
int tt;
cin >> top >> tt;
if (top == "AND")
op[i] = 0;
else if (top == "OR")
op[i] = 1;
else
op[i] = 2;
int pos = 0;
while (tt) {
t[i][pos] = tt & 1;
tt >>= 1;
pos ++;
}
}
auto calc = [&](int pos, int val) {
for (int i = 0; i < n; i ++) {
if (op[i] == 0)
val &= t[i][pos];
else if (op[i] == 1)
val |= t[i][pos];
else
val ^= t[i][pos];
}
return val;
};
int val = 0, ans = 0;
for (int i = 30; i >= 0; i --) {
int r0 = calc(i, 0);
int r1 = calc(i, 1);
if (val + (1 << i) <= m and r0 < r1) {
val += 1 << i, ans += r1 << i;
} else {
ans += r0 << i;
}
}
cout << ans << "\n";
}0x02 递推与递归
void solve() {
int n;
cin >> n;
vector<int> ans;
function<void(int)> dfs = [&](int x) {
if (x == n + 1) {
vector<bool> ref(n);
for (auto v : ans)
ref[v - 1] = true;
for (int v : ref)
if (v)
cout << "Y";
else
cout << "N";
cout << "\n";
return;
}
dfs(x + 1);
ans.push_back(x);
dfs(x + 1);
ans.pop_back();
};
dfs(1);
}void solve() {
int n, m;
cin >> n >> m;
vector<int> ans;
function<void(int)> dfs = [&](int x) {
if (ans.size() > m or ans.size() + (n - x + 1) < m)
return;
if (x == n + 1) {
for (auto x : ans)
cout << x << " ";
cout << "\n";
return;
}
ans.push_back(x);
dfs(x + 1);
ans.pop_back();
dfs(x + 1);
};
dfs(1);
}void solve() {
int n, k;
cin >> n >> k;
vector<int> ans(n + 1), vis(n + 1);
function<void(int)> dfs = [&](int x) {
if (x == k + 1) {
for (int i = 1; i <= k; i ++)
cout << ans[i] << " ";
cout << "\n";
return;
}
for (int i = 1; i <= n; i ++) {
if (vis[i])
continue;
ans[x] = i;
vis[i] = true;
dfs(x + 1);
vis[i] = false;
ans[x] = 0;
}
};
dfs(1);
}using grid = array<array<bool, 5>, 5>;
grid calc(grid a, int x, int y) {
a[x][y] = not a[x][y];
if (x < 4) {
a[x + 1][y] = not a[x + 1][y];
}
if (x > 0) {
a[x - 1][y] = not a[x - 1][y];
}
if (y < 4) {
a[x][y + 1] = not a[x][y + 1];
}
if (y > 0) {
a[x][y - 1] = not a[x][y - 1];
}
return a;
}
struct grid_hash {
size_t operator()(const grid& g) const {
u64 res = 0;
for (int i = 0; i < 5; i ++) {
for (int j = 0; j < 5; j ++) {
res += g[i][j];
res <<= 1;
}
}
return res;
}
};
unordered_map<grid, int, grid_hash> path;
auto init() {
grid a;
for (int i = 0; i < 5; i ++) {
for (int j = 0; j < 5; j ++) {
a[i][j] = true;
}
}
queue<grid> q;
q.push(a);
while (not q.empty()) {
grid x = q.front(); q.pop();
if (path[x] >= 6)
break;
for (int i = 0; i < 5; i ++) {
for (int j = 0; j < 5; j ++) {
grid y = calc(x, i, j);
if (not path[y] and y != a) {
path[y] = path[x] + 1;
q.push(y);
}
}
}
}
return a;
}
grid b;
void solve() {
array<array<bool, 5>, 5> a = {};
for (int i = 0; i < 5; i ++) {
for (int j = 0; j < 5; j ++) {
char x;
cin >> x;
a[i][j] = x != '0';
}
}
if (path[a] == 0) {
cout << (a == b ? 0 : -1) << "\n";
} else {
cout << path[a] << "\n";
}
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int t = 1;
b = init();
cin >> t;
while (t --) {
solve();
}
return 0;
}using i64 = long long;
using u64 = unsigned long long;
i64 power(i64 a, i64 b, int p = INT_MAX) {
i64 res = 1;
a %= p;
while (b) {
if (b & 1) {
(res *= a) %= p;
}
(a *= a) %= p;
b >>= 1;
}
return res;
}
const i64 mod = 9901;
i64 sum(i64 p, i64 c) {
if (p == 0)
return 0;
if (c == 0)
return 1;
i64 ans = 0;
if (c % 2 == 0) {
return ((1 + power(p, c / 2, mod)) * sum(p, c / 2 - 1) % mod + power(p, c, mod)) % mod;
}
return (1 + power(p, (c + 1) / 2, mod)) * sum(p, c / 2) % mod;
}
void solve() {
i64 a, b;
cin >> a >> b;
vector<pair<i64, i64>> fact;
for (i64 i = 2; i * i <= a; i ++) {
if (a % i)
continue;
i64 c = 0;
while (a % i == 0) {
c ++;
a /= i;
}
fact.push_back({i, c});
}
if (a != 1)
fact.push_back({a, 1});
i64 ans = 1;
for (auto [p, c] : fact) {
(ans *= sum(p, b * c)) %= mod;
}
cout << ans << "\n";
}0x03 前缀和与差分
const int maxn = 5e3 + 10;
array<array<int, maxn + 10>, maxn + 10> s = {};
void solve() {
int m, n;
cin >> n >> m;
for (int i = 0; i < n; i ++) {
int x, y, z;
x = y = z = 0;
cin >> x >> y >> z;
s[x + 1][y + 1] += z;
}
for (int i = 1; i <= maxn; i ++) {
for (int j = 1; j <= maxn; j ++) {
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
}
}
int ans = 0;
for (int i = m; i <= maxn; i ++) {
for (int j = m; j <= maxn; j ++) {
int cur = s[i][j] - s[i - m][j] - s[i][j - m] + s[i - m][j - m];;
ans = max(ans, cur);
}
}
cout << ans << "\n";
}P4552 [Poetize6] IncDec Sequence - 洛谷
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (auto& x : a)
cin >> x;
vector<int> b(n);
b[0] = a[0];
for (int i = 1; i < n; i ++) {
b[i] = a[i] - a[i - 1];
}
int p = 0, q = 0;
for (int i = 1; i < n; i ++) {
if (b[i] > 0)
p += b[i];
else if (b[i] < 0)
q -= b[i];
}
cout << max(p, q) << "\n";
cout << abs(p - q) + 1 << "\n";
}P2879 [USACO07JAN] Tallest Cow S - 洛谷
void solve() {
int n, ith, h, r;
cin >> n >> ith >> h >> r;
vector<int> d(n + 2);
vector<int> c(n + 2);
set<pair<int, int>> vis;
for (auto _ : views::iota(0, r)) {
int a, b;
cin >> a >> b;
if (a > b)
swap(a, b);
if (vis.count({a, b}))
continue;
vis.insert({a, b});
d[a + 1] --, d[b] ++;
}
for (int i = 1; i <= n; i ++) {
c[i] = c[i - 1] + d[i];
cout << h + c[i] << "\n";
}
}0x04 二分
P10450 [USACO03MAR] Best Cow Fences G - 洛谷
void solve() {
int n, l;
cin >> n >> l;
vector<double> a(n + 1);
for (auto& x : a | views::drop(1))
cin >> x;
const double eps = 1e-5;
auto check = [&](double t) {
auto b = a;
for (auto& x : b | views::drop(1))
x -= t;
for (int i = 1; i <= n; i ++) {
b[i] += b[i - 1];
}
double ans = -1e10;
double min_val = 0;
for (int i = l; i <= n; i ++) {
min_val = min(min_val, b[i - l]);
ans = max(ans, b[i] - min_val);
}
return ans >= 0;
};
double lo = -1e6, hi = 1e6;
while (hi - lo > eps) {
double x = (lo + hi) / 2;
if (check(x))
lo = x;
else
hi = x;
}
cout << int(hi * 1000) << "\n";
}P10451 Innovative Business - 洛谷
void solve() {
int n;
cin >> n;
vector<int> a(n);
iota(a.begin(), a.end(), 1);
ranges::stable_sort(a, [](int l, int r) {
return compare(l, r);
});
cout << "! ";
for (auto x : a)
cout << x << " ";
cout << "\n";
}0x05 排序
void solve() {
int n;
cin >> n;
unordered_map<int, int> lan;
for (int i = 0; i < n; i ++) {
int x;
cin >> x;
lan[x] ++;
}
int m;
cin >> m;
vector<tuple<int, int, int>> film(m);
for (int i = 0; i < m; i ++) {
get<0>(film[i]) = i;
cin >> get<1>(film[i]);
}
for (int i = 0; i < m; i ++) {
cin >> get<2>(film[i]);
}
ranges::sort(film, [&](auto l, auto r) {
auto [la, lb, lc] = l;
auto [ra, rb, rc] = r;
lb = lan[lb], lc = lan[lc];
rb = lan[rb], rc = lan[rc];
if (lb == rb) {
if (lc == rc)
return la < ra;
return lc > rc;
}
return lb > rb;
});
cout << get<0>(film.front()) + 1 << "\n";
}void solve() {
int n;
cin >> n;
vector<int> a(n);
for (auto& x : a)
cin >> x;
ranges::sort(a);
int mid = a[(n + 1) / 2];
int ans = 0;
for (auto x : a)
ans += abs(x - mid);
cout << ans << "\n";
}void solve() {
int n, m, t;
i64 sumr = 0, sumc = 0;
std::cin >> n >> m >> t;
std::vector<int> row(n);
std::vector<int> col(m);
for (auto i : rep(t)) {
int x, y;
std::cin >> x >> y;
x --, y --;
row[x] ++, col[y] ++;
sumr ++, sumc ++;
}
bool modr = sumr % n, modc = sumc % m;
sumr /= n, sumc /= m;
if (modr and modc) {
std::cout << "impossible" << endl;
return;
}
std::vector<i64> prer(n + 1), prec(m + 1);
for (auto i : rep(n)) {
prer[i + 1] = prer[i] + row[i] - sumr;
}
for (auto i : rep(m)) {
prec[i + 1] = prec[i] + col[i] - sumc;
}
prer.erase(prer.begin());
rgs::sort(prer);
auto midr = prer[n / 2];
i64 ansr = 0;
for (auto x : prer)
ansr += std::abs(x - midr);
prec.erase(prec.begin());
rgs::sort(prec);
auto mic = prec[m / 2];
i64 ansc = 0;
for (auto x : prec)
ansc += std::abs(x - mic);
if (modc)
std::cout << "row " << ansr << endl;
else if (modr)
std::cout << "column " << ansc << endl;
else
std::cout << "both " << ansr + ansc << endl;
}void solve() {
std::priority_queue<int, std::vector<int>,
std::less<int>> big;
std::priority_queue<int, std::vector<int>,
std::greater<int>> small;
int n, x, mid = 0;
std::cin >> n;
std::cin >> x;
big.emplace(x);
std::cout << big.top() << endl;
for (auto i : rep(n) | vws::drop(1)) {
std::cin >> x;
if (x > big.top())
small.emplace(x);
else
big.emplace(x);
while (std::abs<i64>(big.size() - small.size()) > 1) {
if (big.size() > small.size()) {
small.emplace(big.top());
big.pop();
} else {
big.emplace(small.top());
small.pop();
}
}
if (i % 2 == 0) {
std::cout << (big.size() > small.size() ?
big.top() : small.top()) << endl;
}
}
}auto solve() {
int n;
std::cin >> n;
std::vector<int> a(n), b(n);
for (auto& x : a)
std::cin >> x;
i64 ans = 0;
std::function<void(int,int)> merge = [&](auto l, auto r) -> void {
if (r - l == 1)
return;
auto mid = (l + r) / 2;
auto i = l, j = mid, k = l;
merge(l, mid), merge(mid, r);
while (i < mid and j < r) {
if (a[i] <= a[j]) {
b[k++] = a[i++];
} else {
b[k++] = a[j++];
ans += mid - i;
}
}
while (i < mid)
b[k++] = a[i++];
while (j < r)
b[k++] = a[j++];
for (auto t = l; t < r; t ++)
a[t] = b[t];
};
merge(0, n);
std::cout << ans << endl;
}auto solve(int n) {
std::vector<int> a(n * n), b(n * n);
for (auto& x : a)
std::cin >> x;
for (auto& x : b)
std::cin >> x;
a.erase(rgs::find(a, 0));
b.erase(rgs::find(b, 0));
std::function<void(int,int,std::vector<int>&,std::vector<int>&,i64&)> merge = [&merge](int l, int r, std::vector<int>& a, std::vector<int>& b, i64& ans) -> void {
if (r - l <= 1)
return;
auto mid = (l + r) / 2;
auto i = l, j = mid, k = l;
merge(l, mid, a, b, ans), merge(mid, r, a, b, ans);
while (i < mid and j < r) {
if (a[i] <= a[j]) {
b[k++] = a[i++];
} else {
b[k++] = a[j++];
ans += mid - i;
}
}
while (i < mid)
b[k++] = a[i++];
while (j < r)
b[k++] = a[j++];
for (auto t = l; t < r; t ++)
a[t] = b[t];
};
auto cnta = 0ll, cntb = 0ll;
auto tmpa = std::vector<int>(a.size());
auto tmpb = std::vector<int>(b.size());
merge(0, a.size(), a, tmpa, cnta);
merge(0, b.size(), b, tmpa, cntb);
if (cnta % 2 == cntb % 2)
std::cout << "TAK" << endl;
else
std::cout << "NIE" << endl;
}0x06 倍增
void solve() {
i64 n, m, k;
std::cin >> n >> m >> k;
std::vector<i64> p(n), m1(2 * n), m2(2 * n);
for (i64& x : p)
std::cin >> x;
auto check = [&k, &m, &p, &m1, &m2](i64 l, i64 mid, i64 r) -> bool {
for (i64 i = mid; i < r; i++)
m1[i] = p[i];
std::sort(m1.begin() + mid, m1.begin() + r);
i64 lp = l, rp = mid, idx = 0, res = 0;
while (lp < mid and rp < r) {
if (m1[lp] <= m1[rp])
m2[idx++] = m1[lp++];
else
m2[idx++] = m1[rp++];
}
while (lp < mid)
m2[idx++] = m1[lp++];
while (rp < r)
m2[idx++] = m1[rp++];
for (i64 i = 0; i < m and i < idx; i++, idx--) {
res += (m2[i] - m2[idx - 1]) * (m2[i] - m2[idx - 1]);
}
return res <= k;
};
i64 l = 0, r = 0, ans = 0;
while (r < n) {
i64 d = 1;
while (d > 0) {
if (r + d <= n and check(l, r, r + d)) {
r += d, d <<= 1;
if (r >= n)
break;
for (i64 i = l; i < r + d; i++)
m1[i] = m2[i - l];
} else {
d >>= 1;
}
}
ans++, l = r;
}
std::cout << ans << endl;
}0x07 贪心
P2887 [USACO07NOV] Sunscreen G
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<std::pair<int, int>> cow(n);
for (auto& [l, r] : cow)
std::cin >> l >> r;
rgs::sort(cow, [](auto l, auto r) {
return l.first > r.first;
});
std::multiset<int> lot;
for (auto i : rep(m)) {
int l, r;
std::cin >> l >> r;
for (auto j : rep(r))
lot.insert(l);
}
int ans = 0;
for (auto [l, r] : cow) {
auto itl = lot.lower_bound(l);
auto itr = lot.upper_bound(r);
if (std::distance(itl, itr) < 1)
continue;
lot.erase(std::max_element(itl, itr));
ans++;
}
std::cout << ans << endl;
}P2859 [USACO06FEB] Stall Reservations S
void solve() {
int n;
std::cin >> n;
std::vector<std::tuple<int, int, int>> vec(n);
auto cnt = 0;
for (auto& [l, r, idx] : vec) {
std::cin >> l >> r;
idx = cnt++;
}
rgs::sort(vec);
std::vector<int> ans(n);
std::vector<int> s;
for (auto i : rep(n)) {
ans[get<2>(vec[i])] = -1;
for (auto j : rep(s.size())) {
if (get<1>(vec[s[j]]) < get<0>(vec[i])) {
ans[get<2>(vec[i])] = j;
break;
}
}
if (ans[get<2>(vec[i])] == -1)
ans[get<2>(vec[i])] = s.size(), s.emplace_back(i);
else
s[ans[get<2>(vec[i])]] = i;
}
std::cout << s.size() << endl;
for (auto x : ans)
std::cout << x + 1 << endl;
}template <size_t N>
struct BigInt {
int a[N];
BigInt(int x = 0) : a {} {
for (int i = 0; x; i ++) {
a[i] = x % 10;
x /= 10;
}
}
auto &operator*=(int x) {
for (int i = 0; i < N; i ++) {
a[i] *= x;
}
for (int i = 0; i < N - 1; i ++) {
a[i + 1] += a[i] / 10;
a[i] %= 10;
}
return *this;
}
auto &operator/=(int x) {
for (int i = N - 1; i >= 0; i --) {
if (i) {
a[i - 1] += a[i] % x * 10;
}
a[i] /= x;
}
return *this;
}
auto &operator+=(const BigInt &x) {
for (int i = 0; i < N; i ++) {
a[i] += x.a[i];
if (a[i] >= 10) {
a[i + 1] += 1;
a[i] -= 10;
}
}
return *this;
}
auto operator<(const BigInt &x) {
int l = N - 1;
while (a[l] == 0)
l --;
int r = N - 1;
while (x.a[r] == 0)
r --;
if (l > r)
return false;
if (l < r)
return true;
for (int i = l; i >= 0; i --) {
if (a[i] > x.a[i])
return false;
if (a[i] < x.a[i])
return true;
}
return false;
}
};
template<size_t N>
auto &operator<<(ostream &o, const BigInt<N> &a) {
int t = N - 1;
while (a.a[t] == 0)
t --;
if (t < 0) {
o << 0;
return o;
}
for (int i = t; i >= 0; i --)
o << a.a[i];
return o;
}
void solve() {
int n;
cin >> n;
int a, b;
cin >> a >> b;
vector<pair<int, int>> vec(n);
for (auto &[l, r] : vec)
cin >> l >> r;
ranges::sort(vec, [](auto l, auto r) {
return l.first * l.second < r.first * r.second;
});
BigInt<10000> mul = 1, tmp, ans;
mul *= a;
for (int i = 0; i < n; i ++) {
tmp = mul;
tmp /= vec[i].second;
if (ans < tmp)
ans = tmp;
mul *= vec[i].first;
}
cout << ans << endl;
}