LibreOJ 是一个很好的 OJ，从现在（2019 年 2 月 20 日）开始我的刷题重心将从洛谷逐渐转向 LibreOJ。
这里按照编号排列列出我做过的题目的题解。
您可以通过浏览器的搜索功能找到对应题目。
最初的一题。
#include <cstdio>
int a, b;
int main() {
scanf("%d%d", &a, &b);
printf("%d\n", a + b);
return 0;
}你好，世界！
#include <cstdio>
int main() {
puts("Hello, World!");
return 0;
}人类的本质之一。
#include <cstdio>
const int MN = 1005;
int T;
char str[MN];
int main() {
freopen("copycat.in", "r", stdin);
freopen("copycat.out", "w", stdout);
scanf("%d", &T);
for (int i = 1; i <= T; ++i) {
scanf("%s", str);
printf("%s\n", str);
}
return 0;
}采用带有当前弧优化和多路增广的 Dinic 算法解决最大流问题。
Dinic 算法在一般图的最坏时间复杂度为 \(O(n^2m)\)。
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
const int MN = 105, MM = 5005;
const LL Inf = 0x7fffffffffffffff;
int N, M, S, T;
int h[MN], iter[MN], nxt[MM * 2], to[MM * 2], tot = 1; LL w[MM * 2];
inline void ins(int u, int v, LL x) {
nxt[++tot] = h[u], to[tot] = v, w[tot] = x, h[u] = tot;
}
int lv[MN], que[MN], l, r;
inline bool Lvl() {
memset(lv, 0, sizeof(lv));
lv[S] = 1;
que[l = r = 1] = S;
while (l <= r) {
int u = que[l++];
for (int i = h[u]; i; i = nxt[i]) if (w[i] && !lv[to[i]]) {
lv[to[i]] = lv[u] + 1;
que[++r] = to[i];
}
}
return lv[T] != 0;
}
LL Flow(int u, LL f) {
if (u == T) return f;
LL d = 0, s = 0;
for (int &i = iter[u]; i; i = nxt[i]) if (w[i] && lv[to[i]] == lv[u] + 1) {
d = Flow(to[i], std::min(f, w[i]));
f -= d, s += d;
w[i] -= d, w[i ^ 1] += d;
if (!f) break;
}
return s;
}
inline LL Dinic() {
LL Ans = 0;
while (Lvl()) {
memcpy(iter + 1, h + 1, N * sizeof(h[0]));
Ans += Flow(S, Inf);
}
return Ans;
}
int main() {
scanf("%d%d%d%d", &N, &M, &S, &T);
for (int i = 1; i <= M; ++i) {
int u, v; LL c;
scanf("%d%d%lld", &u, &v, &c);
ins(u, v, c), ins(v, u, 0ll);
}
printf("%lld\n", Dinic());
return 0;
}经典的可以使用平衡树维护的问题之一。使用无旋 Treap 解决此问题。
无旋 Treap 以分裂（Split）和合并（Merge）操作为基础，使用随机化作为复杂度保证。
优点是适用范围广，代码难度低，易可持久化。缺点是常数略微大（但是很少被卡），不能作为 Link-Cut Tree 的辅助数据结构（需使用 Splay）。
#include <cstdio>
inline unsigned ran() {
static unsigned x = 1;
return x ^= x << 13, x ^= x >> 17, x ^= x << 5;
}
const int MN = 100005;
int Root, val[MN], pri[MN], siz[MN], ls[MN], rs[MN], cnt;
inline int NewNode(int v) { val[++cnt] = v; pri[cnt] = ran(); siz[cnt] = 1; return cnt; }
inline void Comb(int rt) { siz[rt] = siz[ls[rt]] + siz[rs[rt]] + 1; }
int Merge(int rt1, int rt2) {
if (!rt1 || !rt2) return rt1 + rt2;
if (pri[rt1] > pri[rt2]) {
rs[rt1] = Merge(rs[rt1], rt2);
Comb(rt1);
return rt1;
}
else {
ls[rt2] = Merge(rt1, ls[rt2]);
Comb(rt2);
return rt2;
}
}
void Split(int rt, int k, int &rt1, int &rt2) {
if (!rt) { rt1 = rt2 = 0; return ; }
if (k <= siz[ls[rt]]) {
Split(ls[rt], k, rt1, rt2);
ls[rt] = rt2;
Comb(rt);
rt2 = rt;
}
else {
Split(rs[rt], k - siz[ls[rt]] - 1, rt1, rt2);
rs[rt] = rt1;
Comb(rt);
rt1 = rt;
}
}
int Rank(int rt, int x) {
if (!rt) return 0;
if (x <= val[rt]) return Rank(ls[rt], x);
else return siz[ls[rt]] + 1 + Rank(rs[rt], x);
}
int N;
int main() {
scanf("%d", &N);
for (int i = 1; i <= N; ++i) {
int opt, x;
scanf("%d%d", &opt, &x);
int rt1, rt2, rt3;
if (opt == 1) {
Split(Root, Rank(Root, x), rt1, rt2);
Root = Merge(rt1, Merge(NewNode(x), rt2));
}
if (opt == 2) {
Split(Root, Rank(Root, x), rt1, rt2);
Split(rt2, 1, rt2, rt3);
Root = Merge(rt1, rt3);
}
if (opt == 3) {
printf("%d\n", Rank(Root, x) + 1);
}
if (opt == 4) {
Split(Root, x - 1, rt1, rt2);
Split(rt2, 1, rt2, rt3);
printf("%d\n", val[rt2]);
Root = Merge(rt1, Merge(rt2, rt3));
}
if (opt == 5) {
Split(Root, Rank(Root, x) - 1, rt1, rt2);
Split(rt2, 1, rt2, rt3);
printf("%d\n", val[rt2]);
Root = Merge(rt1, Merge(rt2, rt3));
}
if (opt == 6) {
Split(Root, Rank(Root, x + 1), rt1, rt2);
Split(rt2, 1, rt2, rt3);
printf("%d\n", val[rt2]);
Root = Merge(rt1, Merge(rt2, rt3));
}
}
return 0;
}比较有难度的二进制数位 DP。
答案可以表示为 \(\sum_{0\le i<n}\sum_{0\le j<m}(i\:\mathrm{xor}\:j)[(i\:\mathrm{xor}\:j)\ge k]-k\sum_{0\le i<n}\sum_{0\le j<m}[(i\:\mathrm{xor}\:j)\ge k]\)。
使用 \(\mathrm{g}[b][x=0/1][y=0/1][z=0/1]\) 表示从高到低考虑到第 \(b\) 位，\(x=0\) 表示考虑的数 \(i\) 当前小于 \(n\)，\(x=1\) 表示等于 \(n\)，\(y=0\) 表示考虑的数 \(j\) 当前小于 \(m\)，\(y=1\) 表示等于 \(m\)，\(z=0\) 表示 \((i\:\mathrm{xor}\:j)\) 当前大于 \(k\)，\(z=0\) 表示等于 \(k\) 时的 \((i\:\mathrm{xor}\:j)\) 之和。
类似可以定义 \(\mathrm{f}[b][x=0/1][y=0/1][z=0/1]\) 表示同样条件下的满足条件的个数。
则答案等于 \(\mathrm{g}[0][0][0][0]+\mathrm{g}[0][0][0][1]-k(\mathrm{f}[0][0][0][0]+\mathrm{f}[0][0][0][1])\)。
转移时枚举上一位的 \(x,y,z\)，以及 \(i,j\) 在这一位的值，由此计算出这一位的 \(x,y,z\) 进行转移，注意判断是否合法。
#include <cstdio>
#include <cstring>
typedef long long LL;
const int B = 59;
LL N, M, K; int P;
inline void A(int &x, int y) { x += y; if (x >= P) x -= P; }
int f[61][2][2][2], g[61][2][2][2];
LL DP() {
memset(f, 0, sizeof f);
memset(g, 0, sizeof g);
f[B + 1][1][1][1] = 1;
for (int i = B; ~i; --i) {
int n = N >> i & 1;
int m = M >> i & 1;
int k = K >> i & 1;
#define F(i) for (int i = 0; i < 2; ++i)
F(ln) F(nn) if (!ln || n || !nn)
F(lm) F(nm) if (!lm || m || !nm)
F(lk) if (!lk || !k || (nn ^ nm)) {
int nk = nn ^ nm;
int nnn = ln & (n == nn), nnm = lm & (m == nm), nnk = lk & (k == nk);
A(f[i][nnn][nnm][nnk], f[i + 1][ln][lm][lk]);
A(g[i][nnn][nnm][nnk], (g[i + 1][ln][lm][lk] + ((nk ? 1ll : 0ll) << i) % P * f[i + 1][ln][lm][lk]) % P);
}
}
return (g[0][0][0][0] + g[0][0][0][1] - (LL)K % P * (f[0][0][0][0] + f[0][0][0][1]) % P + P) % P;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%lld%lld%lld%d", &N, &M, &K, &P);
printf("%lld\n", DP());
}
return 0;
}经典的使用分块或数据结构解决的问题之一。使用差分-前缀和技巧和树状数组可以通过此题。
#include <cstdio>
const int MN = 50005;
int N, A[MN], B[MN];
inline void Add(int i, int x) { for (; i <= N; i += i & -i) B[i] += x; }
inline int Qur(int i) { int a = 0; for (; i; i -= i & -i) a += B[i]; return a; }
int main() {
scanf("%d", &N);
for (int i = 1; i <= N; ++i) {
scanf("%d", &A[i]);
Add(i, A[i] - A[i - 1]);
}
for (int i = 1; i <= N; ++i) {
int opt, l, r, c;
scanf("%d%d%d%d", &opt, &l, &r, &c);
if (opt == 0) Add(l, c), Add(r + 1, -c);
if (opt == 1) printf("%d\n", Qur(r));
}
return 0;
}原文：https://www.cnblogs.com/PinkRabbit/p/LibreOJ.html