# Chữa bài 6-10-23
## Xor Range
#### Subtask 1
Với truy vấn $2$, nếu $x = 0$ thì không có sự thay đổi gì trên dãy. Nếu $x = 1$, tất cả các phần tử sẽ bị flip $(1 \rightarrow 0, 0 \rightarrow 1)$. Sử dụng segment tree kết hợp lazy propagation để thực hiện truy vấn trên
#### Subtask 2
Ta đưa bài toán về như subtask 1 với việc sử dụng $20$ segment tree để tính toán với mỗi bit.
Code
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
const int N = 100005;
const int LG = 21;
int n, m;
int a[N], st[LG][N << 2];
bool lz[LG][N << 2];
void push(int bit, int id, int tl, int tr) {
if (lz[bit][id]) {
int tm = tl + (tr - tl) / 2;
st[bit][id << 1] = (tm - tl + 1) - st[bit][id << 1];
st[bit][id << 1 | 1] = (tr - tm) - st[bit][id << 1 | 1];
}
lz[bit][id << 1] ^= lz[bit][id];
lz[bit][id << 1 | 1] ^= lz[bit][id];
lz[bit][id] = 0;
}
void update(int bit, int id, int tl, int tr, int l, int r) {
if (tr < l || r < tl) {
return;
}
if (l <= tl && tr <= r) {
st[bit][id] = (tr - tl + 1) - st[bit][id];
lz[bit][id] ^= 1;
return;
}
push(bit, id, tl, tr);
int tm = tl + (tr - tl) / 2;
update(bit, id << 1, tl, tm, l, r);
update(bit, id << 1 | 1, tm + 1, tr, l, r);
st[bit][id] = st[bit][id << 1] + st[bit][id << 1 | 1];
}
int query(int bit, int id, int tl, int tr, int l, int r) {
if (tr < l || r < tl) {
return 0;
}
if (l <= tl && tr <= r) {
return st[bit][id];
}
push(bit, id, tl, tr);
int tm = tl + (tr - tl) / 2;
return query(bit, id << 1, tl, tm, l, r) + query(bit, id << 1 | 1, tm + 1, tr, l, r);
}
void init() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
}
void solve() {
for (int i = 1; i <= n; i++) {
for (int bit = 0; bit < LG; bit++) {
if ((a[i] >> bit) & 1) {
update(bit, 1, 1, n, i, i);
}
}
}
cin >> m;
while (m--) {
int t, l, r, x;
int sum = 0;
cin >> t;
switch (t) {
case 1:
cin >> l >> r;
for (int bit = 0; bit < LG; bit++) {
sum += query(bit, 1, 1, n, l, r) * (1 << bit);
}
cout << sum << ' ';
break;
case 2:
cin >> l >> r >> x;
for (int bit = 0; bit < LG; bit++) {
if ((x >> bit) & 1) {
update(bit, 1, 1, n, l, r);
}
}
break;
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
init();
solve();
return 0;
}
```
## Bắc Thang Lên Hỏi Ông Trời
From AnhQuanMaster
#### Subtask 1:
backtrack idi ghêm
#### Subtask 2:
Đặt $f_i$ là số cách đi tới bậc thang thứ $i$:
- $f_i = f_{i-2} + f_{i-3}$ nếu ô $i$ được đi vào
- $f_i = 0$ nếu ô i không được đi vào
- $f_0 = 1$
#### Subtask 4:
Vì $n$ rất lớn và không có ô cấm nào, ta có thể sử dụng nhân ma trận để tăng tốc giải thuật quy hoạch động
Nếu không biết nó là gì, có thể tham khảo tại: [Nhân ma trận](https://vnoi.info/wiki/algo/trick/matrix-multiplication.md)
#### Subtask 5
Với các bài toán nhân ma trận cơ bản, ta hay thấy solution là tìm ma trận base, ma trận nhân và đập nhân ma trận $1$ lần là AC subtask này sinh ra để muốn các bạn thoát khỏi tư tưởng chỉ nhân $1$ lần là đủ.
Thay vì nhân ma trận $1$ lần, ta sẽ nhân $m+1$ lần, mỗi lần nhân ta sẽ tính số cách di chuyển từ ô cấm này sang ô cấm tiếp theo (do giữa chúng không có ô cấm nên công thức chuyển là giống nhau, vì thế ta mới có thể nhân ma trận được). Khi nhân tới ô cấm tiếp theo rồi, ta chỉ việc sửa $f_{a_i} = 0$ (vì đó là ô cấm nên không có cách đi vào) là được ma trận base mới để nhân tiếp.
ĐPT: $m \times 27 \times log(n)$.
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 998244353;
using mat = vector<vector<int>>;
mat grid(int m, int n) {
return mat(m, vector<int>(n));
}
mat operator * (const mat& a, const mat& b) {
if (a.empty() || b.empty() || a[0].size() != b.size()) assert(0);
int m = a.size();
int n = a[0].size();
int p = b[0].size();
mat c = grid(m, p);
for (int i = 0; i < m; i++)
for (int j = 0; j < p; j++)
for (int k = 0; k < n; k++)
c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
return c;
}
mat power_mat(const mat& a, int b) {
if (b == 1) return a;
mat k = power_mat(a, b / 2);
k = k * k;
if (b & 1) k = k * a;
return k;
}
const int maxM = 1e5 + 69;
int n, m;
int a[maxM];
mat F = {{0, 0, 1}};
mat C = {
{0, 0, 1},
{1, 0, 1},
{0, 1, 0}
};
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) cin >> a[i];
sort(a + 1, a + 1 + m);
for (int i = 1; i <= m; i++) {
F = F * power_mat(C, a[i] - a[i - 1]);
F[0][2] = 0;
}
if (a[m] < n) F = F * power_mat(C, n - a[m]);
cout << F[0][2];
}
```
## GCDIST
#### Subtask 1
Làm trâu $O(n^2)$.
#### Subtask 2
Do $a_i = 1$ nên ta quy nó về bài toán tìm Diameter.
#### Subtask 3
Ta có một cận về số ước của một số: $d(u) = \sqrt[3] u \times \alpha$, với $\alpha$ là hằng số nhỏ.
Ở đây ta có thể quy ước các số trong khoảng $[1,10^5]$ có không quá $100$ ước.
Từ đây ta có thể áp dụng Small To Large hoặc xây cây mới, với đỉnh được đẩy vào theo các ước của nó.
Subtask này khá có tình edu nên các bạn có thể code thử nhé!
Code:
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5;
vector<int> pp[N*5];
void sieve () {
int n = 5e5;
for (int i=1; i<=n; i++) {
for (int j=i; j<=n; j+=i) {
pp[j].push_back(i);
}
}
}
unordered_map<int,int> mp[N];
int lv[N];
int res = 0;
int n;
struct edge {
int v,w;
};
int a[N];
vector<edge> adj[N];
void dfs (int u, int p) {
for (auto val : pp[a[u]]) {
mp[u][val] = max (mp[u][val],lv[u]*val);
}
for (auto x : adj[u]) {
int v = x.v, w = x.w;
if (v == p) continue;
lv[v] = lv[u] + w;
dfs(v,u);
if (mp[v].size() > mp[u].size()) swap(mp[u],mp[v]);
for (auto it : mp[v]) {
if (mp[u].count(it.first)) {
res = max (res,it.second + mp[u][it.first] - 2*lv[u]*it.first);
}
mp[u][it.first] = max (mp[u][it.first],it.second);
}
}
}
void solve () {
if (n == 0) exit(0);
for (int i=1; i<=n; i++) {
cin >> a[i];
adj[i].clear();
mp[i].clear();
}
for (int i=2; i<=n; i++) {
int u,v,w; cin >> u >> v >> w;
adj[u].push_back({v,w});
adj[v].push_back({u,w});
}
res = 0;
dfs(1,1);
cout << res << '\n';
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
sieve();
cin >> n; solve();
}
```
#### Subtask 4
Vẫn dựa vào cận $d(u)$ ở trên.
Ta có tập $S(t)$ gồm các đỉnh $u$ với $t$ là ước của $a(u)$.
Dựa vào gợi ý từ subtask $2$, dễ thấy bài toán quy về, với mỗi tập $S(t)$, tìm Diameter của tập $S(t)$. Lúc ấy ta sẽ lấy $res = max (Diamter(S(t))\times t)$ (ta không cần quan tâm $gcd$ có đúng bằng $t$ không, bởi nếu nó không phải thì sau này xét các tập là bội của $t$ ta cũng sẽ xét tới).
Để tìm Diamter, bản chất ta không cần dựng cây DFS.
Ta vẫn sẽ làm theo tư tưởng DFS, đầu tiên là từ một đỉnh $u$ bất kì, tìm đỉnh $v$ sao cho $dist(u,v)$ lớn nhất, sau đó lại tìm đỉnh $t$ sao cho $dist(v,t)$ lớn nhất. Lúc này $dist(v,t)$ chính là Diameter của tập.
Để làm bước trên, ta cần tính được $dist(u,v)$ bất kì nhanh chóng, ta có thể nghĩ tới thuật toán $LCA$. Tuy nhiên, bài này ta cần tính $LCA$ trong $O(1)$ để không bị quá thời gian.
Đây là một kĩ thuật khá mới với một số bạn, [có thể tham khảo tại đây]([https://www.geeksforgeeks.org/lca-n-ary-tree-constant-query-o1/]).
Code
```cpp=
#include<bits/stdc++.h>
#pragma GCC diagnostic ignored "-Wunused-parameter"
using namespace std;
const int N = 1e5+5;
vector<int> pp[N*5];
void sieve () {
int n = 5e5;
for (int i=1; i<=n; i++) {
for (int j=i; j<=n; j+=i) {
pp[j].push_back(i);
}
}
}
long long lv[N];
long long res = 0;
int n;
struct edge {
int v,w;
};
int a[N];
vector<edge> adj[N];
const int Log = 18 ;
int h[N];
int ti[N],cnt;
pair<int,int> rmq[3*N][Log+1];
int LOG[2*N];
int lca(int u, int v) {
int L = ti[u], R = ti[v];
if (L > R) swap(L, R);
int k = LOG[R - L + 1];
int id = min(rmq[L][k], rmq[R - (1 << k) + 1][k]).second;
return id;
}
void build(){
int M = log2(2 * n);
int N = 2 * n - 1;
for (int i=2; i<=N; i++) LOG[i] = LOG[i/2]+1;
for (int k = 1; k <= M; k++) {
for (int i = 1; i + (1 << k) <= N + 1; i++) {
rmq[i][k] = min(rmq[i][k - 1], rmq[i + (1 << (k - 1))][k - 1]);
}
}
}
void dfs (int u, int p) {
ti[u] = ++cnt;
h[u] = h[p] + 1;
rmq[cnt][0] = {h[u], u};
for (auto x : adj[u]) {
int v = x.v, w = x.w;
if (v == p) continue;
lv[v] = lv[u] + w;
dfs(v,u);
rmq[++cnt][0] = {h[u], u};
}
}
long long dist (int u, int v) {
return lv[u] + lv[v] - 2*lv[lca(u,v)];
}
bool use[N*5];
vector<int> g[N*5];
bool maxi (long long &a, long long b) {
if (a < b) {
a = b;
return true;
}
return false;
}
long long cal (int val, vector<int> &a) {
int u = a[0];
long long len = 0, best = u;
for (auto v : a) {
if (maxi(len,dist(u,v))) {
best = v;
}
}
len = 0;
for (auto v : a) {
len = max (len,dist(best,v));
// cout << val << ' ' << best << ' ' << v << ' ' << dist(best,v) << '\n';
}
return len*val;
}
void solve () {
cnt = 0;
vector<int> Div;
if (n == 0) exit(0);
for (int i=1; i<=n; i++) {
cin >> a[i];
adj[i].clear();
for (auto val : pp[a[i]]) {
g[val].push_back(i);
if (use[val]) continue;
Div.push_back(val);
use[val] = true;
}
}
for (int i=2; i<=n; i++) {
int u,v,w; cin >> u >> v >> w;
adj[u].push_back({v,w});
adj[v].push_back({u,w});
}
res = 0;
dfs(1,1);
build();
for (auto val : Div) {
res = max (res, cal(val,g[val]));
g[val].clear();
use[val] = false;
}
cout << res << '\n';
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
sieve();
cin >> n; solve();
}
```
## Chăn cừu
#### Subtask 1
Bài toán tìm trung vị cơ bản.
#### Subtask 2
Bài toán đơn giản hóa thành cho $n$ số nguyên, cần chia ra làm $k$ đoạn sao cho $cost$ của chúng là bé nhất.
Gọi $cost(l,r)$ là chi phí tối thiểu để "chia" đoạn $[l,r]$:
- Bạn cần tìm một vị trí $k \in [l,r]$, sau đó ta sẽ chuyển các con cừu về vị trí $k$. Khi cố định $k$, ta cần biến đổi công thức một chút để tính trong $O(1)$.
Gọi $dp(i,j)$ là xét đoạn từ $[1,i]$ và ta đã chia ra được $j$ đoạn:
- $dp(i,j) = dp(x-1,j-1) + cost(x,i), \forall x \in [1,i]$.
Độ phức tạp: $O(n^3)$.
#### Subtask 3
Với $n \le 2000$, khá dễ thấy ta sẽ sử dụng chia để trị để tối ưu $dp$.
Cả hai hàm $cost(l,r)$ và $dp(i,j)$ đều có tính "đúng đắn" để ta chia để trị.
Việc chứng minh sẽ RẤT KHÓ, vậy nên cách tốt nhất trong phòng thi cho những subtask thế này là code trâu và sinh test để kiểm tra điều kiện chia để trị.
Code (Hùng S):
```cpp=
#include <bits/stdc++.h>
using namespace std;
int n, k;
int x[5005];
int w[5005];
int ord[5005];
long long sw[5005];
long long xw[5005];
long long f[2][5005];
long long cost[5005][5005];
inline void compute(short row, short l, short r, short optl, short optr) {
if (l > r) {
return;
}
short mid = (l + r) >> 1;
pair<long long, short> best = {LLONG_MAX, -1};
for (short k = optl; k <= min(mid, optr); k++) {
best = min(best, make_pair(f[(row & 1) ^ 1][k - 1] + cost[mid][k], k));
}
f[row & 1][mid] = best.first;
short opt = best.second;
compute(row, l, mid - 1, optl, opt);
compute(row, mid + 1, r, opt, optr);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k;
for (short i = 1; i <= n; i++) {
cin >> x[i] >> w[i];
}
iota(ord + 1, ord + n + 1, 1);
sort(ord + 1, ord + n + 1, [](int &u, int &v) -> bool {
return x[u] < x[v];
});
for (short i = 1; i <= n; i++) {
sw[i] = w[ord[i]] + sw[i - 1];
xw[i] = 1LL * x[ord[i]] * w[ord[i]] + xw[i - 1];
}
for (short i = 1; i <= n; i++) {
for (short j = i, mid = i; j <= n; j++) {
while (sw[mid] - sw[i - 1] < (sw[j] - sw[i - 1] + 1) / 2) {
mid++;
}
cost[j][i] = 1LL * x[ord[mid]] * (sw[mid] - sw[i - 1]) - (xw[mid] - xw[i - 1]);
if (mid + 1 <= j) {
cost[j][i] += (xw[j] - xw[mid]) - 1LL * x[ord[mid]] * (sw[j] - sw[mid]);
}
}
}
memset(f[0], 0x3f, sizeof(f[0]));
f[0][0] = 0;
for (short i = 1; i <= k; i++) {
compute(i, 1, n, 1, n);
}
cout << f[k & 1][n];
return 0;
}
```
#### Subtask 4
Để $AC$, các bạn cần một thuật toán tối ưu từ $O(n^3)$ xuống $O(n^2)$ khá kinh điển. Đó là [Knuth Optimization](https://cp-algorithms.com/dynamic_programming/knuth-optimization.html).
Việc chứng minh thuật toán này, như subtask $3$, rất khó, vậy nên chiến thuật tối ưu vẫn sẽ là sinh test để kiểm tra.
Limit bài này khá chặt, vậy nên ta có thể áp dụng phương pháp giảm bộ nhớ $dp$ (chỉ lưu $0/1$) cho hàm $dp$. Đồng thời ta nhận xét về hàm $cost(l,r)$, nếu gọi $opt(l,r)$ là vị trí $k$ tối ưu của hàm, ta sẽ có $opt(l,r) \le opt(l,r+1)$ và hàm $opt(l,r)$ là một hàm có dạng chữ $V$, tức là giá trị của nó sẽ giảm dần tới một điểm rồi chỉ tăng. Dựa vào đây ta có thể dùng hai con trỏ để tính toán.
Code (chưa tối ưu):
```cpp=
#include<iostream>
#include<algorithm>
#include<string.h>
#pragma GCC diagnostic ignored "-Wunused-parameter"
using namespace std;
#define int long long
const int N = 5005;
struct vcl {
int x,w;
bool operator < (const vcl &o) const {
return x < o.x;
}
}a[N];
int n,k;
long long cost[N][N];
long long dp[N][N];
short opt[N][N];
long long p[N],f[N]; // p = x*w, f = w
inline long long cal (int l, int r, int mid) {
return (1ll*a[mid].x*(f[mid-1]-f[l-1])-(p[mid-1]-p[l-1])) + ((p[r]-p[mid])-1ll*a[mid].x*(f[r]-f[mid]));
}
inline bool mini (long long &a, int b) {
if (a > b) {
a = b;
return true;
}
return false;
}
void precal() {
memset (cost,0x3f3f3f,sizeof(cost));
for (int i=1; i<=n; i++) {
cost[i][i] = 0;
opt[i][i] = i;
}
for (int len=2; len<=n; len++) {
for (int l=1; l+len-1<=n; l++) {
int r = l + len - 1;
for (int k = opt[l][r-1]; k<=opt[l+1][r]; k++) {
if (mini(cost[l][r], cal(l,r,k))) {
// cout << l << ' ' << r << ' ' << k << ' ' << cal(l,r,k) << '\n';
opt[l][r] = k;
}
}
// cout << l << ' ' << r << ' ' << cost[l][r] << '\n';
}
}
}
void solve () {
cin >> n >> k;
for (int i=1; i<=n; i++) {
cin >> a[i].x >> a[i].w;
}
sort (a+1,a+n+1);
for (int i=1; i<=n; i++) {
f[i] = f[i-1] + a[i].w;
p[i] = p[i-1] + 1ll*a[i].x*a[i].w;
}
precal();
memset (dp,0x3f3f3f,sizeof(dp));
memset (opt,-1,sizeof(opt));
dp[0][0] = 0;
for (int j=1; j<=n; j++) {
for (int i=n; i>=j; i--) {
if (j == 1) {
dp[i][j] = cost[1][i];
opt[1][i] = 0;
continue;
}
int L = 0, R = n-1;
if (opt[i][j-1] != -1) L = opt[i][j-1];
if (j+1 <= n && opt[i+1][j] != -1) R = opt[i+1][j];
for (int k=L; k<=R; k++) {
if (mini(dp[i][j], dp[k][j-1] + cost[k+1][i])) opt[i][j] = k;
}
}
}
cout << dp[n][k] << '\n';
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
solve();
}
```
Sign in with Wallet
Connect another wallet