Bài T1: Phép XOR Để giải quyết bài toán này, chúng ta sử dụng phương pháp chênh lệch. Mỗi lần thay đổi sẽ được chuyển đổi thành dạng chênh lệch như sau:
1
1 x
1 x x
x -1 -1 -1
Sau đó, chúng ta thực hiện tổng tiền tố theo đường chéo để tính kết quả cuối cùng. Dưới đây là mã nguồn C++ minh họa:
#include <bits/stdc++.h>
using namespace std;
const int Maxn = 1e3 + 5;
int n, q;
int a[Maxn][Maxn];
void add(int x1, int y1, int x2, int y2, int val) {
a[x1][y1] += val; a[x1][y2 + 1] -= val; a[x2 + 1][y1] -= val; a[x2 + 1][y2 + 1] += val;
}
int main() {
cin >> n >> q;
while (q--) {
int r, c, l, s;
cin >> r >> c >> l >> s;
add(r, c, min(r + l - 1, n), c, s);
if (r + l <= n && c + 1 <= n) add(r + l, c + 1, r + l, min(c + l, n), -s);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
a[i][j] += a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
a[i][j] += a[i - 1][j - 1];
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
ans ^= a[i][j];
}
}
cout << ans << endl;
return 0;
}
Bài T2: Trò chơi Qua việc thử nghiệm với một số dữ liệu, chúng ta nhận thấy rằng khi ( m > 2 \log n ), cả hai bên đều có thể đưa ra kết quả là tập rỗng, tức là ( 0 ). Vì vậy, chúng ta chỉ cần xem xét trường hợp ( m \leq 28 ).
Dưới đây là mã nguồn C++ minh họa:
#include <bits/stdc++.h>
using namespace std;
const int Maxn = 2e5 + 5;
int n, m, a[Maxn], b[Maxn];
int t[Maxn];
int dfs(int x, int l, int r) {
if (l > r) return 0;
if (x == m + 1) {
int sm = 0;
for (int i = l; i <= r; i++) sm += a[i];
return sm;
}
for (int i = l; i <= r; i++) t[i] = a[i];
int cnt = l, mid = 0;
for (int i = l; i <= r; i++) if (t[i] % b[x] == 0) a[cnt++] = t[i];
mid = cnt - 1;
for (int i = l; i <= r; i++) if (t[i] % b[x] != 0) a[cnt++] = t[i];
int res1 = dfs(x + 1, l, mid);
int res2 = dfs(x + 1, mid + 1, r);
if (x & 1) return min(res1, res2);
else return max(res1, res2);
}
int main() {
cin >> n >> m;
if (m > 28) {cout << 0 << endl; return 0;}
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= m; i++) cin >> b[i];
cout << dfs(1, 1, n) << endl;
return 0;
}
Bài T3: Liên thông khối Bài toán này yêu cầu chúng ta tối ưu hóa quá trình xây dựng đồ thị và tìm kiếm liên thông lớn nhất sau khi xóa một đỉnh. Chúng ta có thể sử dụng thuật toán Tarjan để tìm các điểm cắt và xây dựng cây tròn-bình thường.
Dưới đây là mã nguồn C++ minh họa:
#include <bits/stdc++.h>
using namespace std;
const int Maxn = 3e6 + 5, Maxm = 1e7 + 5;
int T, n, m, a[Maxn];
int fa[Maxn], sz[Maxn];
int prim[1000005], cnt, vis[Maxm], mnp[Maxm], id[Maxm];
int head[Maxn], edgenum;
struct node {
int nxt, to;
} edge[Maxm];
void init(int n) {
for (int i = 2; i <= n; i++) {
if (!vis[i]) prim[++cnt] = i, mnp[i] = i;
for (int j = 1, x; (x = i * prim[j]) <= n; j++) {
vis[x] = 1;
mnp[x] = prim[j];
if (i % prim[j] == 0) break;
}
}
for (int i = 2; i <= n; i++) if (vis[i] && !vis[i / mnp[i]]) id[i] = ++m;
}
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void merge(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
if (sz[x] > sz[y]) swap(x, y);
sz[y] += sz[x], fa[x] = y;
}
void add(int u, int v) {
edge[++edgenum] = {head[u], v}; head[u] = edgenum;
edge[++edgenum] = {head[v], u}; head[v] = edgenum;
}
int fac[Maxn], num[Maxn];
void Div(int x, int t) {
int tot = 0;
while (x > 1) {
int w = mnp[x];
fac[++tot] = w; num[tot] = 0;
while (x % w == 0) {
num[tot]++;
x /= w;
}
}
for (int i = 1; i <= tot; i++) {
for (int j = i + (num[i] <= 1); j <= tot; j++) {
if (fac[i] * fac[j] < Maxm) {
int p = id[fac[i] * fac[j]] + n;
add(p, t), merge(t, p);
}
}
}
}
int sum, ans;
int dfn[Maxn], low[Maxn], idx, stk[Maxn], top, siz[Maxn];
void tarjan(int x, int rt) {
dfn[x] = low[x] = ++idx;
stk[++top] = x;
int cld = 0, flg = 0, ret = 0;
siz[x] = (x <= n);
for (int i = head[x]; i; i = edge[i].nxt) {
int to = edge[i].to;
if (!dfn[to]) {
cld++;
tarjan(to, rt);
low[x] = min(low[x], low[to]);
if (low[to] >= dfn[x]) {
if (x != rt || cld > 1) flg = 1;
int s = 0;
while (1) {
int v = stk[top--];
siz[x] += siz[v]; s += siz[v];
if (v == to) break;
}
ret = max(ret, s);
}
} else low[x] = min(low[x], dfn[to]);
}
if (x <= n) {
if (flg) ans = min(ans, max(ret, sum - siz[x]));
else ans = min(ans, sum - 1);
}
}
void solve() {
read(n);
for (int i = 1; i <= n + m; i++) fa[i] = i, sz[i] = (i <= n);
for (int i = 1; i <= n; i++) read(a[i]);
for (int i = 1; i <= n; i++) Div(a[i], i);
int mx = 0, lmx = 0, pos = 0;
for (int i = 1; i <= n + m; i++) {
if (fa[i] == i) {
if (sz[i] >= mx) lmx = mx, mx = sz[i], pos = i;
else if (sz[i] > lmx) lmx = sz[i];
}
}
ans = sum = mx;
tarjan(pos, pos);
write(max(lmx, ans));
}
int main() {
cin >> T; init(1e7);
while (T--) solve();
return 0;
}
Bài T4: Đường đi xe buýt Bài toán này yêu cầu chúng ta tính số lượng đường đi không giao nhau. Chúng ta sử dụng kỹ thuật xây dựng cây ảo và sử dụng phương pháp chênh lệch trên cây.
Dưới đây là mã nguồn C++ minh họa:
#include <bits/stdc++.h>
using namespace std;
const int Maxn = 2e5 + 5;
int n, m, k, c[Maxn];
int head[Maxn], edgenum;
struct node {
int nxt, to;
} edge[Maxn];
void add(int u, int v) {
edge[++edgenum] = {head[u], v}; head[u] = edgenum;
edge[++edgenum] = {head[v], u}; head[v] = edgenum;
}
int dfn[Maxn], fa[Maxn], mn[18][Maxn], idx;
namespace T {
int get(int x, int y) { return dfn[x] < dfn[y] ? x : y; }
void dfs(int x, int fth) {
mn[0][dfn[x] = ++idx] = fa[x] = fth;
for (int i = head[x]; i; i = edge[i].nxt) {
int to = edge[i].to;
if (to == fth) continue;
dfs(to, x);
}
}
void init() {
for (int i = 1; i <= 17; i++) {
for (int j = 1; j + (1 << i) - 1 <= n; j++) {
mn[i][j] = get(mn[i - 1][j], mn[i - 1][j + (1 << (i - 1))]);
}
}
}
int lca(int u, int v) {
if (u == v) return u;
if ((u = dfn[u]) > (v = dfn[v])) swap(u, v);
int k = __lg(v - u); u++;
return get(mn[k][u], mn[k][v - (1 << k) + 1]);
}
}
int c1[Maxn], c2[Maxn];
int f[Maxn], F[Maxn], g[Maxn];
int sm = 0;
void dfs(int x) {
f[x] += c1[x]; sm += f[x];
F[x] = F[fa[x]] + f[x];
for (int i = head[x]; i; i = edge[i].nxt) {
int to = edge[i].to;
if (to == fa[x]) continue;
dfs(to); c2[x] += c2[to];
}
g[x] = f[x] + c2[x];
}
int ans[Maxn];
namespace VT {
int head[Maxn], edgenum;
struct node {
int nxt, to;
} edge[Maxn];
void add(int u, int v) {
edge[++edgenum] = {head[u], v};
head[u] = edgenum;
}
int s[Maxn], top = 0;
void build(vector<int> &v) {
edgenum = top = 0;
s[++top] = v[0]; head[v[0]] = 0;
for (int i = 1; i < v.size(); i++) {
int x = v[i], t = s[top], l = T::lca(x, t);
if (l == t) {
head[x] = 0; s[++top] = x;
continue;
}
while (dfn[s[top - 1]] > dfn[l]) add(s[top - 1], s[top]), top--;
if (s[top - 1] != l) {
head[l] = 0; add(l, s[top]); s[top] = l;
} else add(l, s[top--]);
head[x] = 0; s[++top] = x;
}
for (int i = 1; i < top; i++) add(s[i], s[i + 1]);
}
int sum, col, siz[Maxn], f1[Maxn], g1[Maxn];
void dfs1(int x, int fth) {
siz[x] = (c[x] == col);
f1[x] = g1[x] = 0;
for (int i = head[x]; i; i = edge[i].nxt) {
int to = edge[i].to;
dfs1(to, x);
f1[x] += siz[x] * siz[to];
siz[x] += siz[to];
}
g1[x] = siz[x] * (sum - siz[x]);
c1[x] += f1[x], c2[fth] -= g1[x], c2[x] += g1[x];
}
void solve1(int cc, vector<int> &v) {
col = cc;
sum = v.size();
build(v); int rt = s[1];
dfs1(rt, 0);
}
int ct[Maxn];
void dfs2(int x) {
siz[x] = (c[x] == col);
for (int i = head[x]; i; i = edge[i].nxt) {
int to = edge[i].to;
dfs2(to);
siz[x] += siz[to];
}
if (c[x] == col) ans[x] += (2 * F[x] - g[x]) * (siz[x] - 1);
for (int i = head[x]; i; i = edge[i].nxt) {
int to = edge[i].to;
ct[to] += (2 * F[x] - g[x]) * (siz[x] - siz[to]);
}
}
void dfs3(int x, int w) {
w += ct[x];
if (c[x] == col) ans[x] += w;
ct[x] = 0;
for (int i = head[x]; i; i = edge[i].nxt) {
int to = edge[i].to;
dfs3(to, w);
}
}
void solve2(int cc, vector<int> &v) {
col = cc;
sum = v.size();
int ret = 0;
for (auto p : v) ret += F[p];
for (auto p : v) ans[p] += (sm - F[p]) * (sum - 1) - (ret - F[p]);
build(v); int rt = s[1];
dfs2(rt); dfs3(rt, 0);
}
}
vector<int> nod[Maxn];
int main() {
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) cin >> c[i], nod[c[i]].push_back(i);
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
add(u, v);
}
T::dfs(1, 0), T::init();
for (int i = 1; i <= k; i++) {
if (nod[i].empty()) continue;
sort(nod[i].begin(), nod[i].end(), [](int x, int y) { return dfn[x] < dfn[y]; });
VT::solve1(i, nod[i]);
}
dfs(1);
for (int i = 1; i <= k; i++) {
if (nod[i].empty()) continue;
VT::solve2(i, nod[i]);
}
int res = 0;
for (int i = 1; i <= n; i++) res += ans[i];
res >>= 2;
cout << res << endl;
while (m--) {
int x; cin >> x;
cout << res - ans[x] << endl;
}
return 0;
}