A
Đầu tiên, hãy xem xét trường hợp đặc biệt khi \(t = 2\).
Không khó nhận thấy thao tác này khá không trực quan, vì vậy có thể xem xét việc nối một cạnh vô hướng giữa mỗi cặp đỉnh \(u, v\) trong thao tác \((u, v)\).
Rõ ràng các thành phần liên thông cần được xem xét riêng biệt. Với cùng một thành phần liên thông, tổng giá trị của các đỉnh trong thành phần đó không thay đổi sau mỗi thao tác.
Vì vậy, hãy đặt \(c_i = a_i - b_i\). Khi đó, việc biến đổi dãy \(a\) thành dãy \(b\) tương đương với việc biến đổi dãy \(c\) thành dãy toàn số 0.
Từ đây, điều kiện cần để một thành phần liên thông có thể biến thành toàn số 0 là tổng giá trị trong thành phần đó bằng 0, và điều này cũng là điều kiện đủ. Chứng minh đơn giản như sau:
Từ đồ thị liên thông đơn giản nhất - cây, ta có thể thấy rằng để loại bỏ một nút lá, ta cần thực hiện một số thao tác xác định.
Khi đó, có thể trước tiên làm cho toàn bộ cây con trở thành số 0, và cuối cùng chỉ còn lại nút gốc. Vì tổng giá trị bằng 0, nên giá trị của nút gốc lúc này chắc chắn là 0.
Đối với đồ thị liên thông tổng quát, ta có thể chọn bất kỳ cây DFS nào.
Điều này gợi ý rằng khi giải quyết các vấn đề phân loại trên đồ thị liên thông, ta thường có thể bắt đầu từ cây đơn giản nhất, sau đó xét đơn vòng, rồi đến cây có chu trình cơ bản...
Do đó, có thể sử dụng cấu trúc tập hợp rời rạc (DSU) để quá trình này, với độ phức tạp \(\mathcal{O(Tn \log n)}\).
Quay lại vấn đề ban đầu, không khó thấy rằng thông qua cách làm trên (chứng minh), ta có thể nhận thấy rằng giá trị có thể được chuyển giữa các đỉnh trong cùng một thành phần liên thông được nối bởi thao tác 2. Vì vậy, có thể thu gọn thành phần liên thông này để thuận tiện cho việc xét tiếp.
Sau đó, chúng ta tiếp tục nối các thành phần đã thu gọn lại với nhau bằng thao tác 1.
Lại xét từ trường hợp đặc biệt và đơn giản nhất là cây, ta bắt đầu xét từ các nút lá.
Khi đó, đóng góp của mỗi nút đến nút gốc đều là \((-1) ^ {dep} \times c_i\), và nếu nút gốc cuối cùng bằng 0 thì điều kiện được thỏa mãn.
Nếu có thể thay đổi gốc, thì điều kiện cần và đủ sẽ là: chọn một gốc và tô màu đen-trắng, tổng giá trị các nút đen bằng tổng giá trị các nút trắng.
Điều này gợi ý rằng chúng ta nên hướng đến tư duy đồ thị hai màu, và không khó chứng minh: đồ thị hai màu hợp lệ khi và chỉ khi tổng giá trị hai tập bằng nhau.
Đối với một đồ thị không hai màu, có thể đưa toàn bộ giá trị đến một chu kỳ lẻ và loại bỏ, nhưng điều kiện tiên quyết là tổng giá trị phải là số chẵn.
Tóm tắt lại giải pháp cho bài này:
- Đầu tiên, thu gọn các đỉnh bằng cách nối cạnh theo thao tác 2, sau đó nối các thành phần đã thu gọn bằng thao tác 1.
- Xét riêng từng thành phần liên thông. Nếu là đồ thị hai màu, điều kiện là tổng giá trị hai tập bằng nhau; nếu không, điều kiện là tổng giá trị các đỉnh là số chẵn.
Độ phức tạp \(\mathcal{O(Tn \log n)}\).
#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define Next(i, u) for (int i = h[u]; i; i = e[i].next)
const int N = 1e5 + 5;
struct canh { int v, next;} e[N << 1];
struct nut { int u, v;} p[N];
int T, n, m, u, v, F, ans, opt, tong, cnt, w[3], a[N], b[N], h[N], mau[N];
int doc() {
char c; int x = 0, f = 1;
c = getchar();
while (c > '9' || c < '0') { if(c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
namespace dtk {
int gt[N], cha[N], kichthuoc[N];
void khoitao() { rep(i, 1, n) cha[i] = i, gt[i] = a[i] - b[i], kichthuoc[i] = 1;}
int tim(int x) { return cha[x] == x ? cha[x] : cha[x] = tim(cha[x]);}
void gop(int x, int y) {
int a = tim(x), b = tim(y);
if(a == b) return ;
if(kichthuoc[a] > kichthuoc[b]) swap(a, b);
cha[a] = b, gt[b] += gt[a], kichthuoc[b] += kichthuoc[a];
}
}
void them(int u, int v) {
e[++tong].v = v, e[tong].next = h[u], h[u] = tong;
e[++tong].v = u, e[tong].next = h[v], h[v] = tong;
}
void dfs(int u, int mau) {
w[mau] += dtk :: gt[u], mau[u] = mau;
Next(i, u) {
int v = e[i].v;
if(!mau[v]) dfs(v, 3 - mau);
else if(mau[v] != 3 - mau) F = true;
}
}
int main () {
T = doc();
while (T--) {
n = doc(), m = doc();
rep(i, 1, n) a[i] = doc();
rep(i, 1, n) b[i] = doc();
cnt = 0, ans = 1, dtk :: khoitao();
rep(i, 1, m) {
opt = doc(), u = doc(), v = doc();
if(opt == 1) p[++cnt] = (nut){u, v};
else dtk :: gop(u, v);
}
tong = 0, memset(h, 0, sizeof(h));
memset(mau, 0, sizeof(mau));
rep(i, 1, cnt) them(dtk :: tim(p[i].u), dtk :: tim(p[i].v));
rep(i, 1, n) if(dtk :: tim(i) == i && !mau[i]) {
F = w[1] = w[2] = 0, dfs(i, 1);
if(!F) ans &= (w[1] == w[2]);
else ans &= !((w[1] + w[2]) & 1);
}
printf(ans ? "YES\n" : "NO\n");
}
return 0;
}
B
Có thể thấy rằng bản chất của sắp xếp bong bóng là ở vòng thứ \(i\), phần tử thứ \(n - i + 1\) được di chuyển về sau cho đến khi được sắp xếp đúng.
Vì vậy, sau mỗi vòng sắp xếp bong bóng, xét số lượng cặp nghịch biến có kết thúc tại vị trí \(i\) là \(f_i\), tương đương với việc dịch chuyển \(f\) sang trái một vị trí rồi giảm đi 1 tại các vị trí không bằng 0.
Do đó, sau \(k\) vòng sắp xếp bong bóng, số lượng cặp nghịch biến về bản chất là \(\sum\limits_{i > k} f_i(f_i > k) - k \times \sum\limits_{i > k} [f_i > k]\).
Lưu ý rằng chắc chắn có \(f_i < k(i \le k)\), nên tương đương với việc tính \(\sum f_i(f_i > k) - k \times \sum [f_i > k]\).
Có thể sử dụng cây chỉ số (Fenwick tree) để duy trì điều này, thao tác sửa chỉ cần sửa điểm đơn.
Độ phức tạp \(\mathcal{O((n + m) \log n)}\).
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; ++i)
const int N = 2e5 + 5;
int n, m, x, opt, p[N], a[N];
struct CayBit {
#define lowbit(x) (x & (-x))
int c[N];
void them(int pos, int gt) { if(!pos) return ; for (int i = pos; i <= n; i += lowbit(i)) c[i] += gt;}
int truyvan(int pos) { int ans = 0; for (int i = pos; i; i -= lowbit(i)) ans += c[i]; return ans;}
}C[3];
int doc() {
char c; int x = 0, f = 1;
c = getchar();
while (c > '9' || c < '0') { if(c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
signed main () {
n = doc(), m = doc();
rep(i, 1, n) {
p[i] = doc(), a[i] = C[0].truyvan(n) - C[0].truyvan(p[i]);
C[0].them(p[i], 1), C[1].them(a[i], 1), C[2].them(a[i], a[i]);
}
while (m--) {
opt = doc(), x = doc();
if(opt == 1) {
C[1].them(a[x], -1), C[1].them(a[x + 1], -1);
C[2].them(a[x], -a[x]), C[2].them(a[x + 1], -a[x + 1]);
if(p[x] > p[x + 1]) --a[x + 1];
else ++a[x];
swap(p[x], p[x + 1]), swap(a[x], a[x + 1]);
C[1].them(a[x], 1), C[1].them(a[x + 1], 1);
C[2].them(a[x], a[x]), C[2].them(a[x + 1], a[x + 1]);
}
else {
if(x >= n) { puts("0"); continue ;}
int sl = C[1].truyvan(n) - C[1].truyvan(x);
printf("%lld\n", C[2].truyvan(n) - C[2].truyvan(x) - sl * x);
}
}
return 0;
}
C
Đầu tiên, xét trường hợp đặc biệt \(k = 1\), có thể phỏng đoán rằng việc nhân các số lớn với nhau sẽ tối ưu hơn.
Bằng chứng dưới đây được học từ phương pháp của EI:
Chỉ từ góc độ đại số, ta thấy không có lối thoát, vì vậy có thể xem xét kết hợp số-hình để biểu diễn trực quan.
Thông qua tích có thể liên tưởng đến diện tích, nhưng tích của hai số khó biểu diễn trực tiếp. Tuy nhiên ta biết: \(\frac{a_i ^ 2 + a_j ^ 2 - (a_i - a_j) ^ 2}{2} = a_i \times a_j\). Vì vậy vấn đề ban đầu tương đương với việc tìm giá trị lớn nhất của \(\sum a_i ^ 2 - \frac{\sum\limits (a_i - a_{i + 1}) ^ 2}{2}\), trong đó phần đầu là một hằng số, chỉ cần làm cho phần sau nhỏ nhất là được.
Không khó thấy rằng phần sau có thể được xem như là diện tích của hình vuông tạo bởi \((a_i, a_i) \sim (a_{i + 1}, a_{i + 1})\).
Do đó, vấn đề được chuyển hóa thành: bắt đầu từ \(p_1\) trên vòng, đi hết một vòng, mỗi lần thêm vào diện tích của hình vuông tạo bởi \((a_{p_i}, a_{p_i}) \sim (a_{p_{i + 1}}, a_{p_{i + 1}})\), làm cho tổng diện tích các hình vuông nhỏ nhất.
Dưới đây chúng ta định nghĩa \(a - b\) là phần loại bỏ \(b\) khỏi \(a\), và \((a_i, a_j)\) biểu diễn hình vuông tạo bởi \((a_i, a_i) \sim (a_j, a_j)\).
Phân tích kỹ có thể thấy rằng sau khi đi qua một điểm một lần chắc chắn sẽ quay lại, nên \(\forall i, (a_i, a_{i + 1})\) ít nhất được tính hai lần.
Đồng thời, vì các điểm không thể đi qua hai lần, nên nếu có lần nào đi qua \((a_i, a_{i + 1})\) thì chắc chắn sẽ đi qua \((a_i, a_{i + 2})\), do đó \((a_i, a_{i + 2}) - (a_i, a_{i + 1}) - (a_{i + 1}, a_{i + 2})\) ít nhất được tính một lần.
Lúc này có thể thấy rằng tham lam ở trên chính xác đạt đến cận dưới của phân tích trên.
Đối với trường hợp \(k > 1\), phân tích kỹ có thể thấy rằng nếu bắt đầu từ 1 và đi qua một số lần nhất định sẽ quay lại 1 bắt đầu vòng lặp, số lần này là số nguyên nhỏ nhất \(x\) thỏa mãn \(kx \equiv 0\pmod{n}\), không khó thấy là \(\frac{n}{\gcd(n, k)}\). Vì vậy đồ thị này tương đương với việc bị chia thành \(\gcd(n, k)\) vòng có kích thước \(\frac{n}{\gcd(n, k)}\), do đó chỉ có \(d(n)\) đồ thị khác nhau về bản chất.
Vấn đề hiện tại được chuyển hóa thành việc phân bổ giá trị hợp lý cho \(x(x \mid n)\) vòng có kích thước \(\frac{n}{x}\) sao cho mỗi vòng bên trong thực hiện tham lam với \(k = 1\) đạt tổng giá trị lớn nhất.
Dựa trên quan sát từ việc chứng minh tham lam trên, có thể nhận thấy:
- Bất kể phân bổ như thế nào, \(\sum a_i ^ 2\) luôn là một hằng số, do đó chỉ cần làm cho giá trị \(\frac{\sum\limits (a_i - a_{i + 1}) ^ 2}{2}\) trong mỗi vòng nhỏ nhất.
- Dựa trên 1 và chứng minh tham lam trên, việc loại bỏ giá trị lớn nhất hoặc nhỏ nhất nhất định sẽ tối ưu hơn.
- Dựa trên 1 và chứng minh tham lam trên, việc thêm một giá trị không lớn hơn giá trị lớn nhất hoặc không nhỏ hơn giá trị nhỏ nhất nhất định sẽ làm cho kết quả tốt hơn.
Do đó có thể thấy rằng hai vòng phân bổ giá trị chắc chắn không có giao nhau về miền giá trị, nếu không có thể trao đổi điểm cuối (thỏa mãn tính chất 2, 3 trên) để kết quả tốt hơn.
Tóm tắt lại giải pháp cho bài này:
- Bản chất các phương án khác nhau chỉ có \(d(n)\) loại, \(\forall k\) sẽ chia vòng thành \(\gcd(n, k)\) vòng có kích thước \(\frac{n}{\gcd(n, k)}\) là trường hợp đặc biệt với \(k = 1\).
- Phương án phân bổ giá trị vào mỗi vòng tối ưu nhất chắc chắn là \(a_1 \sim a_{\frac{n}{\gcd(n, k)}}, a_{\frac{n}{\gcd(n, k)} + 1} \sim a_{\frac{n}{\gcd(n, k)} \times 2} \cdots\) lần lượt phân bổ vào mỗi vòng.
- Với mỗi vòng bên trong trường hợp đặc biệt \(k = 1\), cách sắp xếp tối ưu nhất là \(a_1 \cdots a_{n - 1}, a_n, a_{n - 2} \cdots a_2(a_1 \le a_2 \le \cdots \le a_n)\.
Tiếp theo, với mỗi \(d \mid n\), mô phỏng quy trình trên là được, độ phức tạp \(\mathcal{O(nd(n))}\).
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; ++i)
const int N = 2e5 + 5;
int n, m, k, a[N], ketqua[N];
int doc() {
char c; int x = 0, f = 1;
c = getchar();
while (c > '9' || c < '0') { if(c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int UCLN(int a, int b) { return !b ? a : UCLN(b, a % b);}
int giai(int k) {
int len = n / k, ans = 0;
rep(i, 1, k) {
ans += a[(i - 1) * len + 1] * a[(i - 1) * len + 2];
ans += a[i * len] * a[i * len - 1];
rep(j, 1, len - 2) ans += a[(i - 1) * len + j] * a[(i - 1) * len + j + 2];
}
return ans;
}
signed main () {
n = doc(), m = doc();
rep(i, 1, n) a[i] = doc(), ketqua[0] += a[i] * a[i];
sort(a + 1, a + n + 1);
rep(i, 1, n / 2) if(n % i == 0) ketqua[i] = giai(i);
rep(i, 1, m) {
k = doc();
printf("%lld\n", !k ? ketqua[k] : ketqua[UCLN(k, n)]);
}
return 0;
}