Giải các bài tập luyện tập (Phần 15)
\(\text{Bởi DaiRuichen007}\)
Vòng #69 - 20250409
A. [QOJ5091] Bài toán mùa đông
Liên kết đề bài
Tóm tắt đề bài
Cho \(n,k\), với \(n\) là số chẵn, cho \(l_1\sim l_k,r_1\sim r_k\), trong đó \(l_i=n-2i+1,r_i=n+2i-1\), tìm một bộ ghép hoàn hảo \(p\) sao cho số cặp \((l_i,r_{p_i})\) nguyên tố cùng nhau là nhiều nhất.
Phạm dữ liệu: \(k\le 10^6\).
Phân tích cách tiếp cận
Đầu tiên, \(l_i,r_i\) đều là số lẻ, khi đó nếu \(r_j-l_i\) là \(2^t\) thì cặp \([l,r]\) chắc chắn nguyên tố cùng nhau.
Xem xét giá trị \(t\) lớn nhất sao cho \(l_k+2^t\le r_k\), ta thấy giá trị \(t\) này thỏa mãn \(l_k+2^t\ge r_1\), vì trong khoảng \([[2k,4k-2]\] có ít nhất một lũy thừa của 2.
Tìm được \(2^t\) như vậy, đặt \(l_k+2^t=r_{m}\), ta có thể ghép thêm \((l_{k-1},r_{m+1}),\dots,(l_m,r_k)\), từ đó chuyển thành bài con với \(k=m-1\) và đệ quy giải.
Dễ thấy ta không cần quan tâm đến giá trị \(n\), và lúc này mỗi cặp phần tử đều nguyên tố cùng nhau.
Độ phức tạp thời gian \(\mathcal O(k)\).
Mã nguồn
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int MAXN=1e6+5;
int n,k,gh[MAXN];
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
string _; cin>>_>>k,n=2*k;
for(int m=k;m;) {
LL v=1<<__lg(4*m-2);
for(LL r=n+2*m-1;m;--m) {
LL t=n-2*m+1+v;
if(t>r) break;
gh[(t-n+1)/2]=m;
}
}
cout<<k<<"\n";
for(int i=1;i<=k;++i) cout<<gh[i]<<"\n";
return 0;
}
B. [CF793E] Vấn đề văn phòng
Liên kết đề bài
Tóm tắt đề bài
Cho cây \(n\) đỉnh, và \(4\) lá \(a,b,c,d\), thỏa mãn bất hai lá nào đều nằm trong các cây con khác nhau của gốc.
Xem xét có tồn tại một dãy dfs của cây, khi lấy tất cả các lá \(e_1\sim e_k\), khoảng cách giữa \((a,b)\) và \((c,d)\) đều bằng \(\dfrac k2\).
Phạm dữ liệu: \(n\le 5000\).
Phân tích cách tiếp cận
Đầu tiên xem xét trường hợp chỉ có một cặp điểm, ta có thể tùy ý sắp xếp các cây con của nút gốc trừ \(a,b\) và các cây con khác của mỗi tổ tiên của \(a,b\).
Các cây con này có thể chọn đưa vào giữa \(a,b\) hoặc không, và mỗi cây con có quyết định độc lập, tối ưu bằng dp với Bitset.
Sau đó xem xét thứ tự tương đối của bốn lá, rõ ràng chỉ có thể là \((a,c,b,d),(a,d,b,c),(b,c,a,d),(b,d,a,c)\) trong bốn trường hợp.
Xem xét trường hợp \((a,c,b,d)\), trước hết xem xét yêu cầu giữa \((a,b)\), thì cây con chứa \(c\) phải đưa vào giữa.
Sau đó là yêu cầu giữa \(c,d\), cây con chứa \(b\) phải đưa vào giữa.
Sau đó ta cần hợp nhất các phương án hai bên, rõ ràng chỉ cần xem xét cách sắp xếp các cây con khác của gốc, điều này có thể thực hiện được:
- Một cây con nếu chỉ đưa vào giữa \(a,b\), thì dfs sequence đặt giữa \((a,c)\).
- Nếu chỉ đưa vào giữa \((c,d)\), thì dfs sequence đặt giữa \((b,d)\).
- Nếu đồng thời đưa vào giữa \(a,b\) và \(c,d\), thì dfs sequence đặt giữa \((c,b)\).
Do đó \((a,c,b),(c,b,d)\) có thể tách thành hai bài con độc lập, đều có thể giải bằng dp tối ưu với Bitset.
Độ phức tạp thời gian \(\mathcal O\left(\dfrac{n^2}{\omega}\right)\).
Mã nguồn
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5005;
int n,la[4],cha[MAXN],k[MAXN];
vector <int> d[MAXN];
bitset <MAXN> f,dp,o;
bool kt(int l,int r,int d) {
int w=k[1]/2-1-k[h[d]];
if(w<0) return false;
dp=f;
for(int s:{l,r}) for(int x=cha[q[s]],y=q[s];x!=1;y=x,x=cha[x]) {
for(int u:d[x]) if(u^y) o=dp,o<<=k[u],dp|=o;
}
return dp[w];
}
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>la[0]>>la[1]>>la[2]>>la[3];
for(int i=2;i<=n;++i) cin>>cha[i],d[cha[i]].push_back(i);
for(int i=n;i>1;--i) k[i]+=d[i].empty(),k[cha[i]]+=k[i];
if(k[1]&1) return cout<<"NO\n",0;
for(int k:{0,1,2,3}) for(int &u=h[k]=la[k];cha[u]!=1;u=cha[u]);
f[0]=1;
for(int i:d[1]) if(i!=h[0]&&i!=h[1]&&i!=h[2]&&i!=h[3]) o=f,o<<=k[i],f|=o;
if((kt(0,1,2)||kt(0,1,3))&&(kt(2,3,0)||kt(2,3,1))) cout<<"YES\n";
else cout<<"NO\n";
return 0;
}
C. [CF1707E] Thay thế
Liên kết đề bài
Tóm tắt đề bài
Cho \(a_1\sim a_n\), định nghĩa một lần lặp của khoảng \([l,r\]\) là \([l,r\]\gets f(l,r)=[\min a_{l\sim r},\max a_{l\sim r}]\), \(q\) truy vấn \([l,r\]\to [1,n\]\) cần ít lần lặp nhất.
Phạm dữ liệu: \(n,q\le 10^5\).
Phân tích cách tiếp cận
Trước hết chắc chắn cần dùng phương pháp nhân đôi để duy trì \(f^{2^k}(l,r)\), vấn đề là các khoảng \([l,r\]\) ban đầu quá nhiều, khó duy trì, ta cần giảm số lượng cặp khoảng cần duy trì.
Có thể thấy nếu hai khoảng \([l_1,r_1],[l_2,r_2]\) có giao điểm \(i\), thì \(f(l_1,r_1),f(l_2,r_2)\) có giao điểm \(a_i\).
Do đó với hai khoảng có giao điểm \(X,Y\), ta có \(f(X\cup Y)=f(X)\cup f(Y)\).
Vậy ta chỉ cần duy trì tất cả \(f^{2^k}(i,i+1)\), khi chuyển đổi đặt \([l,r]=f^{2^{k-1}}(i,i+1)\), tính \(\bigcup_{j=l}^{r-1} f^{2^{k-1}}(j,j+1)\), truy vấn cũng tương tự.
Với mỗi lớp mở bảng ST để duy trì là được.
Độ phức tạp thời gian \(\mathcal O(n\log^2n+q\log n)\).
Mã nguồn
#include<bits/stdc++.h>
using namespace std;
typedef array<int,2> khoang;
const int MAXN=1e5+5;
f[18][18][MAXN];
inline khoang operator +(const khoang &x,const khoang &y) { return {min(x[0],y[0]),max(x[1],y[1])}; }
int bit(int x) { return 1<<x; }
khoang truy(int k,int l,int r) {
int t=__lg(r-l+1);
return f[k][t][l]+f[k][t][r-bit(t)+1];
}
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int n,q; cin>>n>>q;
for(int i=1,x;i<=n;++i) cin>>x,f[0][0][i]={x,x};
for(int j=1;j<18;++j) for(int i=1;i+bit(j)-1<=n;++i) {
f[0][j][i]=f[0][j-1][i]+f[0][j-1][i+bit(j-1)];
}
for(int k=1;k<18;++k) for(int j=0;j<18;++j) for(int i=1;i+bit(j)-1<=n;++i) {
f[k][j][i]=truy(k-1,f[k-1][j][i][0],f[k-1][j][i][1]);
}
for(int l,r,s;q--;) {
cin>>l>>r,s=0;
if(l==1&&r==n) { cout<<"0\n"; continue; }
for(int k=17;~k;--k) {
auto i=truy(k,l,r);
if(1<i[0]||i[1]<n) l=i[0],r=i[1],s+=1<<k;
}
auto i=truy(0,l,r);
if(1<i[0]||i[1]<n) cout<<"-1\n";
else cout<<s+1<<"\n";
}
return 0;
}
D. [CF1483E] Vabank
Liên kết đề bài
Tóm tắt đề bài
Có một biến số ẩn \(w\), mỗi lần bạn có thể hỏi một số \(x\) có \(\le m\) không.
Ban đầu bạn có một giá trị \(c=1\), mỗi lần hỏi nếu trả lời đúng thì \(c\gets c+x\), sai thì \(c\gets c-x\).
Bạn cần đảm bảo \(c\) luôn không âm, và tìm ra lời giải tối ưu trong 105 lần hỏi.
Phạm dữ liệu: \(w\le 10^{14}\).
Phân tích cách tiếp cận
Nếu dùng nhị phân trực tiếp, thì \(c\) chắc chắn không đủ, ta cần hỏi điểm trái của khoảng nhị phân để lấy \(c\), nhưng lúc này có thể tốn quá nhiều lần.
Một ý tưởng đơn giản là trước hết nhân đôi, hỏi $20,21,\dots $, cuối cùng xác định được một khoảng \([2^x,2^{x+1})\) của \(c\), lúc này \(\dfrac rl\le 2\), do đó hai lần hỏi là đủ.
Nhưng lúc này tốn quá nhiều bước, lưu ý rằng nếu \(w\ge x\) ta có thể nhận được \(c\), do đó không妨 lấy điểm giữa của khoảng hỏi nhỏ một chút.
Nếu thất bại thì \(c\) giảm, nhưng khoảng hỏi cũng ngắn lại, ngược lại khoảng hỏi lại dài ra.
Vậy ta cần chọn điểm hỏi thích hợp dựa trên \(c\) hiện tại, trước hết nếu \(c=0\), và mỗi lần đều thất bại.
Giả sử trong trường hợp này độ dài khoảng mỗi lần trở thành \(p\) lần, thì số lần hỏi có thể xấp xỉ \(s\log_{1/p}(r-l)\), \(s\) là hằng số trong khoảng \([2,3]\).
Trong trường hợp này tổng số \(c\) tiêu tốn \(c_0\) có thể ước lượng bằng \(l\log_{1/p}(r-l)+\dfrac{p}{1-p}(r-l)\), ta có thể dùng \(c_0\) để xấp xỉ lượng \(c\) tiêu tả tối đa, vì các trường hợp khác không thể tốn kém hơn.
Vậy \(\dfrac c{c_0}\) đại khái cho thấy sự dư dả của \(c\), nếu \(c\) đủ lớn thì lấy tỷ lệ nhị phân \(q=0.5\) là tối ưu, ngược lại khi \(c=0\) phải lấy \(q=p\).
Dùng một hàm tuyến tính xấp xỉ \(q\), tức \(q=p+\dfrac c{c_0}(0.5-p)\), lấy \(p=0.25\) có thể đạt trong 101 lần hỏi.
Độ phức tạp thời gian \(\mathcal O(\log w)\).
Mã nguồn
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1e14;
ll C;
bool hoi(ll z) {
cout<<"? "<<z<<endl;
string o; cin>>o;
if(o=="Lucky!") return C+=z,true;
else return C-=z,false;
}
const double p=0.25;
void giai() {
C=1; ll l=0,r=1;
while(hoi(r)) {
if(r==inf) return cout<<"! "<<r<<endl,void();
l=r,r=min(r*2,inf);
}
while(r>l+1) {
double z=min(1.,C/(l*(log(r-l)/-log(p))+p/(1-p)*(r-l)));
ll mid=(p+(0.5-p)*z)*(r-l)+l;
while(C<mid) hoi(l);
hoi(mid)?l=mid:r=mid;
}
cout<<"! "<<l<<endl;
}
signed main() {
int _; cin>>_;
while(_--) giai();
return 0;
}
*E. [QOJ7793] Trùng lặp
Liên kết đề bài
Tóm tắt đề bài
Cho \(n\) phần tử \((w_i,h_i)\), ban đầu \(h_i=0\), gộp hai phần tử \((w_i,h_i),(w_j,h_j)\) với giá bằng \(h_i+w_i+w_j\), sinh ra một phần tử mới \((w_i+w_j,2\max(h_i,h_j)+1)\).
Phạm dữ liệu: \(n\le 10^4\).
Phân tích cách tiếp cận
Xây quá trình gộp của các phần tử thành cây, thì đóng góp của \(w\) chính là \(w_i\times dep_i\).
Sau đó xem xét đóng góp của \(h\): mỗi điểm đóng góp là \(2^{s}-1\), trong đó \(s\) là độ sâu cây con lớn nhất của các con nhẹ.
Do đó đóng góp tổng của \(h\) là \(\sum 2^s-1\), cũng có thể biểu thị thành \((\sum 2^s)-n+1\), vì có \(n\) đường nặng.
Mục tiêu là cực tiểu hóa \(w_i\times dep_i+\sum 2^s\).
Không妨 định mảng \(dep\), sau đó tìm cực tiểu điểm \(\sum 2^s\).
Từ dưới lên gộp, giả sử đang xử lý điểm với độ sâu \(d\), mỗi điểm có độ sâu hiện tại \(h_0\sim h_q\).
Đặt \(h\) giảm dần, thì ghép \((h_0,h_1)\) chắc chắn là tối ưu, nếu không thì \(h_1\) truyền lên trên, sinh ra một điểm có \(h\) lớn hơn, và chi phí ít nhất là \(2^{h_1+1}\), rõ ràng không tối ưu.
Do đó chiến lược tối ưu là ghép tất cả \(h_{2i},h_{2i+1}\).
Rõ ràng điểm sâu hơn thì \(w\) chắc chắn nhỏ hơn, do đó sắp xếp theo \(w\), việc xử lý theo thứ tự giảm sâu tương đương với xử lý một tiền缀 của \(w\).
Giả sử khi thêm \(w_k\) thì tầng hiện tại đã có \(t\) lá, thì độ dài đường đi chứa \(k\) chính là bit thấp nhất của \(t\), đóng góp là \(\mathrm{lowbit}(t)\).
Vậy \(f_{k,i}\) biểu thị sau khi chèn \([1,k-1]\] tầng hiện tại có \(t\) lá, chuyển thành:
- Thêm lá: \(f_{k-1,i}\to f_{k,i+1}+\mathrm{lowbit}(i)\).
- Gộp lên một tầng: \(f_{k,2x}\to f_{k,x}+\sum_{j\le k} w_j\).
Dùng dp trực tiếp là được.
Độ phức tạp thời gian \(\mathcal O(n^2)\).
Mã nguồn
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=10005;
const ll inf=1e18;
int n;
ll w[MAXN],f[MAXN];
void giai() {
cin>>n;
for(int i=1;i<=n;++i) cin>>w[i];
sort(w+1,w+n+1);
for(int i=1;i<=n;++i) w[i]+=w[i-1];
for(int i=0;i<=n;++i) f[i]=i>1?inf:0;
for(int d=1;d<=n;++d) {
for(int i=n-1;~i;--i) f[i+1]=f[i]+(i&-i),f[i]=inf;
for(int i=n;~i;--i) if(~i&1) f[i/2]=min(f[i/2],f[i]+w[d]);
}
cout<<f[1]-n+1<<"\n";
}
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int _; cin>>_;
while(_--) giai();
return 0;
}
*F. [QOJ7837] Thách thức tổng tích
Liên kết đề bài
Tóm tắt đề bài
Cho \(a_1\sim a_n\), chọn \(k\) phần tử \(b_1\sim b_k\) sao cho \(\sum a_{b_i}-\prod b_i\) lớn nhất.
Phạm dữ liệu: \(k,n\le 10^6,a_i\le 10^9\).
Phân tích cách tiếp cận
Đầu tiên đặt hiện tại \(\sum a=A,\prod b=B\), thì khi thêm một phần tử mới \(x\) lợi nhuận thu được là \(a_x-(x-1)B\), dễ thấy khi \(B>a_x\) thì \(x>1\) chắc chắn không tối ưu.
Do đó các phần tử \(x>1\) chỉ có \(\mathcal O(\log V)\) cái, chỉ cần xem xét trường hợp \(k\le \log V\).
Lúc này có thể thiết lập trạng thái \(f_{i,B}\) chọn \(i\) phần tử, \(\prod b=B\) thì tổng \(\sum a\) lớn nhất.
Chuyển là \(f_{i,x}+f_{j,y}\to f_{i+j,x\times y}\), độ phức tạp \(\mathcal O(V\log V)\).
\(V\) quá lớn không thể chấp nhận, có thể chia để trị: chia các phần tử thành hai phần, sao cho tích của mỗi phần đều nhỏ.
Có thể chứng minh với một số phần tử \(\le \dfrac 23\) và tổng \(=1\), có thể chia thành hai phần kích thước \(\le \dfrac 23\):
Nếu giá trị lớn nhất \(\ge \dfrac 12\) thì tách riêng, các phần tử còn lại tách thành một phần.
Ngược lại số phần tử chắc chắn \(\ge 3\), giá trị lớn nhất \(\ge \dfrac 13\), lấy hai phần tử nhỏ nhất \(x,y\), thì \(x+y\le \dfrac 23\), thay \(x,y\) bằng \(x+y\), rồi quy nạp là được.
Đặt \(w=V^{2/3}\), do \(n\le w\), ta có thể chia tất cả các phần tử thành hai phần tích \(\le w\).
Do đó chỉ cần xử lý trường hợp \(B\le w\), độ phức tạp trở thành \(\mathcal O(w\log w\log V)\).
Cuối cùng ta cần hợp nhất tất cả \(f_i,f_{k-i}\), tức tìm \(\max f_{i,x}+f_{k-i,y}-xy\), có thể tối ưu bằng phương pháp độ dốc.
Nhưng vẫn chưa đủ, chúng ta thử giảm tính toán một số \(f_i\) không cần thiết, quan sát thêm:
Với các giá trị \(\le \dfrac 13\) và tổng \(=1\), có thể chia thành hai phần bằng nhau, và mỗi phần tổng \(\le\dfrac 23\):
Giả sử sắp xếp các phần tử tăng dần là \(x_1\sim x_{n}\) và \(2\mid n\) (nếu không thêm một \(x_1=0\) là được).
Khi đó chọn \(x_2,x_4\dots ,x_n\), trước hết \(x_2+x_4+\cdots +x_n\ge x_1+x_3+\cdots+x_{n-1}\).
Lại vì \(x_2+x_4+\cdots +x_{n-2}\le x_1+x_3+x_5+\cdots +x_{n-1}\), do đó \(x_2+x_4+\cdots +x_{n-2}\le \dfrac 12(1-x_n)\).
Khi đó \(x_2+x_4+\cdots +x_n\le \dfrac {1+x_n}2\le \dfrac 23\), chứng minh xong.
Do đó khi tất cả các phần tử \(\le V^{1/3}\) thì chỉ cần tính \(f_{k/2}\), câu trả lời chắc chắn là \(f_{k/2,x}+f_{k/2,y}-xy\).
Nếu giá trị lớn nhất \(>\dfrac 13\), thì có thể chia thành \(f_1\) và \(f_{k-1}\) hợp nhất.
Do đó dùng nhân nhanh tối ưu, chỉ cần tính \(\mathcal O(\log\log V)\) cái \(f_i\), có thể chấp nhận được.
Độ phức tạp thời gian \(\mathcal O(w\log w\log\log V)\).
Mã nguồn
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e6+5,V=1e6;
int n,m,M,q[MAXN],st[MAXN];
ll f[32][MAXN],ans=0;
bool e[32];
void nhan(ll *a,ll *b,ll *c) {
for(int i=1;i<=V;++i) for(int j=1;i*j<=V;++j) c[i*j]=max(c[i*j],a[i]+b[j]);
}
void dp(ll *a,ll *b) {
int t=0;
for(int i=1;i<=V;++i) {
while(t>1&&(a[q[t]]-a[q[t-1]])*(i-q[t])<(a[i]-a[q[t]])*(q[t]-q[t-1])) --t;
q[++t]=i;
}
for(int i=V,j=1;i;--i) {
while(j<t&&1ll*i*(q[j+1]-q[j])<(a[q[j+1]]-a[q[j]])) ++j;
ans=max(ans,a[q[j]]+b[i]-1ll*i*q[j]);
}
}
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>M,m=min(M,30),e[0]=e[1]=true;
for(int i=1;i<=n;++i) cin>>f[1][i];
for(int i=m-1;i>1;i>>=1) e[i]=1;
for(int i=m/2;i>1;i>>=1) e[i]=1;
for(int i=m/2+1;i>1;i>>=1) e[i]=1;
for(int i=2;i<m;++i) if(e[i]) {
int j=i/2;
nhan(f[j],f[j],f[j*2]),e[j*2]=true;
if(i&1) nhan(f[j*2],f[1],f[i]);
}
dp(f[1],f[m-1]),dp(f[m/2],f[(m+1)/2]);
cout<<ans+f[1][1]*(M-m)<<"\n";
return 0;
}
Vòng #70 - 20250410
A. [QOJ4212] Dấu ngoặc
Liên kết đề bài
Tóm tắt đề bài
Cho chuỗi độ dài \(2n\), ghép cặp tất cả các vị trí, các vị trí ghép cặp phải điền ký tự giống nhau, xây dựng một chuỗi ngoặc hợp lệ thỏa mãn yêu cầu.
Phạm dữ liệu: \(n\le 2\times 10^5\).
Phân tích cách tiếp cận
Một ý tưởng đơn giản là chọn \(n/2\) cặp ghép gần nhất nhất để điền ngoặc trái.
Nhưng có thể làm cho số ngoặc trái hậu tố quá nhiều, do đó mỗi lần cần kiểm tra số ngoặc trái hậu tố: chú ý rằng một chuỗi hợp lệ khi và chỉ khi vị trí ngoặc thứ \(i\) \(\le 2i-1\), do đó ghép mỗi ngoặc trái với vị trí số lẻ gần nhất, nếu có thể ghép thì tham lam thêm vào.
Độ phức tạp thời gian \(\mathcal O(n\log n)\).
Mã nguồn
#include<bits/stdc++.h>
using namespace std;
const int MAXN=4e5+5;
int n,a[MAXN],b[MAXN],t[MAXN];
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
if(n&1) return cout<<"(\n",0;
n*=2;
for(int i=1,c;i<=n;++i) cin>>c,b[c]?a[b[c]]=i:b[c]=i;
set <int> S;
for(int i=1;i<n;i+=2) S.insert(i);
for(int i=1;i<=n;++i) if(a[i]&&S.size()) {
if(*S.begin()<i) return cout<<"(\n",0;
auto it=S.lower_bound(a[i]);
if(it!=S.end()) S.erase(it),S.erase(S.begin()),t[i]=t[a[i]]=1;
}
if(S.size()) return cout<<"(\n",0;
for(int i=1;i<=n;++i) cout<<")("[t[i]];
return 0;
}
B. [QOJ4213] Các tròn
Liên kết đề bài
Tóm tắt đề bài
Định nghĩa giá trị của mảng \(b_0\sim b_{m-1}\) là: tổng \(\sum x_i\) lớn nhất sao cho \(x_i+x_{(i+1)\bmod m}\le b_i\).
Cho \(a_1\sim a_n\), với mỗi tiền tố tính giá trị của nó.
Phạm dữ liệu: \(n\le 10^5\).
Phân tích cách tiếp cận
Xem xét quy hoạch tuyến tính đối偶: ta nhận được \(\min \sum b_iy_i\) sao cho \(y_i+y_{(i-1)\bmod m}\ge 1\).
Có thể chứng minh mỗi \(y_i\in \{0,0.5,1\}\), do đó dùng dp trực tiếp, \(f_{i,c,d}\) biểu thị \(y_1=c,y_i=d\) chi phí nhỏ nhất, khi tính tổng cộng thì ghép \(c,d\) lại là được.
Độ phức tạp thời gian \(\mathcal O(n)\).
Mã nguồn
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e5+5;
int n,a[MAXN]; ll f[MAXN][3][3];
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) ;
cin>>n;
for(int i=1;i<=n;++i) cin>>a[i];
memset(f,0x3f,sizeof(f));
for(int c:{0,1,2}) f[1][c][c]=a[1]*c;
for(int i=2;i<=n;++i) for(int x:{0,1,2}) for(int y:{0,1,2}) for(int z:{0,1,2}) if(y+z>=2) {
f[i][x][z]=min(f[i][x][z],f[i-1][x][y]+z*a[i]);
}
for(int i=3;i<=n;++i) {
ll ans=1e18;
for(int x:{0,1,2}) for(int y:{0,1,2}) if(x+y>=2) ans=min(ans,f[i][x][y]);
cout<<ans/2<<"."<<"05"[ans&1]<<" \n"[i==n];
}
return 0;
}
C. [CF1710D] Phục hồi cây
Liên kết đề bài
Tóm tắt đề bài
Bạn cần xây dựng một cây \(n\) đỉnh, sao cho với mỗi khoảng con \([l,r\]\), tính liên thông của các điểm trên cây giống với đầu vào \(a_{l,r\}\).
Phạm dữ liệu: \(n\le 2000\), đảm bảo có lời giải.
Phân tích cách tiếp cận
Xem xét từng bước thêm điểm, sau khi thêm \([1,n-1]\] sẽ tạo thành một rừng.
Xem xét tất cả khoảng \([x,n\]\) có \(a_{x,n}=1\), theo thứ tự \(x\) giảm dần lần lượt thêm vào.
Trước hết \([x,n-1]\] các điểm tạo thành một số khối liên thông, yêu cầu nối chúng lại, và bất kỳ khoảng con nào cũng không liên thông.
Nếu \([x,n-1]\] chỉ có một điểm, thì nối trực tiếp với \(n\), ngược lại đặt các khối liên thông sau khi sắp xếp là \(b_1\sim b_q\).
Khi đó \(q=2\) thì không có lời giải, ngược nối \(b_1,b_2\) với \(n\), \(b_{3}\sim b_q\) với \(b_1\) là được.
Độ phức tạp thời gian \(\mathcal O(n^2)\).
Mã nguồn
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2005;
int n,cha[MAXN];
char f[MAXN][MAXN];
void giai() {
cin>>n,iota(cha+1,cha+n+1,1);
for(int i=1;i<=n;++i) for(int j=i;j<=n;++j) cin>>f[i][j];
for(int r=1;r<=n;++r) for(int l=r-1;l;--l) if(f[l][r]=='1'&&l<cha[r]) {
cout<<l<<" "<<r<<"\n";
if(cha[cha[r]-1]>l) {
cout<<cha[r]-1<<" "<<l<<"\n";
for(int i=cha[cha[r]-1]-1;cha[i]>l;i=cha[i]-1) cout<<i<<" "<<r<<"\n";
}
for(int i=r;i>l;--i) cha[i]=cha[l];
}
}
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int _; cin>>_;
while(_--) giai();
return 0;
}
D. [QOJ7979] Cờ vua
Liên kết đề bài
Tóm tắt đề bài
Trên mặt phẳng hai chiều vô hạn, chọn ra \(\le X\) ô vuông, phải chứa \((1,1)\), định nghĩa giá trị của mỗi ô là số cách đi từ \((1,1)\) đến ô đó chỉ đi qua các ô đã chọn.
Nhiều truy vấn \(n\), yêu cầu có thể biểu diễn \(n\) thành tổng giá trị của \(\le Y\) ô vuông khác nhau.
Phạm dữ liệu: \(n\le 10^{100},X=960,Y=240\).
Phân tích cách tiếp cận
Ý tưởng đơn giản là giải trong hệ nhị phân: xây dựng các ô có giá trị \(2^1,2^2,\dots\), một phương pháp như sau:
1 1
1 2 2
2 4 4
4 8
Cách này tốn \(X=3\log_2n=996,Y=\log_2 n=332\), cần tối ưu.
Sau đó có thể nghĩ đến đổi cơ số, ví dụ cơ số 3 và 6, có thể có các phương pháp khác nhau, nhưng không thể qua được bài này.
Một ý tưởng là sử dụng một số cơ số không tầm thường, ví dụ cơ số Fibonacci:
1 1 1
1 2 3 3
2 5 8 8
5 13 21
Có thể thấy như vậy có thể xây dựng tất cả số Fibonacci, đặt \(\varphi=\dfrac{\sqrt 5+1}2\).
Khi đó \(X=2\log_{\varphi}n\), do \(\mathrm{Fib}_{480}>10^{100}\), do đó \(X\le 960\).
Sau đó xem xét phân tích trong cơ số Fibonacci, dễ thấy trong dạng phân tích không có hai \(1\) liền kề, nếu có thì có thể nâng cấp, do đó \(Y=\dfrac 12\log_{\varphi}n\), tức \(Y\le 240\), thỏa mãn đề bài.
Mã nguồn
#include<bits/stdc++.h>
using namespace std;
const int k=480;
struct bi {
static const int B=1e8;
int a[16];
bi() { memset(a,0,sizeof(a)); }
inline friend bi operator +(const bi &u,const bi &v) {
bi w;
for(int i=0;i<15;++i) {
w.a[i]+=u.a[i]+v.a[i];
if(w.a[i]>=B) ++w.a[i+1],w.a[i]-=B;
}
return w;
}
inline friend bi operator -(const bi &u,const bi &v) {
bi w;
for(int i=0;i<15;++i) {
w.a[i]+=u.a[i]-v.a[i];
if(w.a[i]<0) --w.a[i+1],w.a[i]+=B;
}
return w;
}
inline friend bool operator >=(const bi &u,const bi &v) {
for(int i=15;~i;--i) if(u.a[i]!=v.a[i]) return u.a[i]>v.a[i];
return true;
}
void read() {
memset(a,0,sizeof(a));
string _; cin>>_;
for(int i=0;_.size();++i) {
int w=_.size(),t=min(8,w);
for(int j=t;j;--j) a[i]=a[i]*10+_[w-j]-'0';
_.resize(w-t);
}
}
} f[k+5];
int K,q,X,Y,g[k+5];
bool e[32];
void nhan(bi *a,bi *b,bi *c) {
for(int i=1;i<=V;++i) for(int j=1;i*j<=V;++j) c[i*j]=max(c[i*j],a[i]+b[j]);
}
void dp(bi *a,bi *b) {
int t=0;
for(int i=1;i<=V;++i) {
while(t>1&&(a[q[t]]-a[q[t-1]])*(i-q[t])<(a[i]-a[q[t]])*(q[t]-q[t-1])) --t;
q[++t]=i;
}
for(int i=V,j=1;i;--i) {
while(j<t&&1ll*i*(q[j+1]-q[j])<(a[q[j+1]]-a[q[j]])) ++j;
ans=max(ans,a[q[j]]+b[i]-1ll*i*q[j]);
}
}
signed main() {
cin>>K>>q>>X>>Y;
f[0].a[0]=f[1].a[0]=1;
for(int i=2;i<k;++i) f[i]=f[i-1]+f[i-2];
vector <array<int,2>> a;
a.push_back({1,1}),a.push_back({1,2}),g[0]=0,g[1]=1;
for(int i=1;i<k/2;++i) {
a.push_back({i,i+2});
a.push_back({i+1,i});
a.push_back({i+1,i+1}),g[2*i]=a.size()-1;
a.push_back({i+1,i+2}),g[2*i+1]=a.size()-1;
}
int n=a.size(); cout<<n<<"\n";
for(auto o:a) cout<<o[0]<<" "<<o[1]<<"\n";
for(bi w;q--;) {
w.read(); string z(n,'0');
for(int i=k-1;~i;--i) if(w>=f[i]) w=w-f[i],z[g[i]]='1';
cout<<z<<"\n";
}
return 0;
}
*E. [CF1630F] Làm thành đồ thị hai phân
Liên kết đề bài
Tóm tắt đề bài
Cho \(n\) đỉnh, có giá trị \(a_1\sim a_n\), nếu \(a_i\mid a_j\) thì nối cạnh \((i,j)\), xóa ít đỉnh nhất để đồ thị là đồ thị hai phân.
Phạm dữ liệu: \(n,a_i\le 5\times 10^4\).
Phân tích cách tiếp cận
Nếu \(a_i\mid a_j\mid a_k\) thì tạo thành tam giác \((i,j,k)\), do đó chúng ta yêu cầu mỗi điểm hoặc chỉ là ước số, hoặc chỉ là bội số.
Dùng \(i_0,i_1\) biểu thị một điểm chỉ là ước số hoặc chỉ là bội số.
Khi đó nếu \(a_i\mid a_j\), thì chỉ có \((i_0,j_1)\) hợp lệ.
Nối cạnh giữa các trạng thái không hợp lệ: \(i_1\to i_0,i_0\to j_0,i_1\to j_0,i_1\to j_1\), dễ chứng minh đồ thị này là DAG đóng.
Chúng ta thấy một phương án hợp lệ tương ứng một phản xích trên đồ thị này, bài toán tương đương tìm phản xích dài nhất, định lý Dilworth chuyển thành tìm bao phủ xích nhỏ nhất.
Độ phức tạp thời gian \(\mathcal O((n\log V)^{1.5})\).
Mã nguồn
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e4+5,inf=1e9;
namespace F {
const int MAXV=2e5+5,MAXE=5e6+5,inf=1e9;
struct Edge {
int v,f,lst;
} G[MAXE];
int S,T,tot=1,hd[MAXV],cur[MAXV],dep[MAXV];
inline void init() { tot=1,memset(hd,0,(T+1)<<2); }
inline void adde(int u,int v,int w) { G[++tot]={v,w,hd[u]},hd[u]=tot; }
inline void link(int u,int v,int w) { adde(u,v,w),adde(v,u,0); }
inline bool BFS() {
memcpy(cur,hd,(T+1)<<2),memset(dep,-1,(T+1)<<2);
queue <int> Q;
Q.push(S),dep[S]=0;
while(!Q.empty()) {
int u=Q.front(); Q.pop();
for(int i=hd[u];i;i=G[i].lst) if(G[i].f&&dep[G[i].v]==-1) {
dep[G[i].v]=dep[u]+1,Q.push(G[i].v);
}
}
return ~dep[T];
}
inline int dfs(int u,int f) {
if(u==T) return f;
int r=f;
for(int i=cur[u];i;i=G[i].lst) {
int v=G[cur[u]=i].v;
if(G[i].f&&dep[v]==dep[u]+1) {
int g=dfs(v,min(r,G[i].f));
if(!g) dep[v]=-1;
G[i].f-=g,G[i^1].f+=g,r-=g;
}
if(!r) return f;
}
return f-r;
}
inline int Dinic() {
int f=0;
while(BFS()) f+=dfs(S,inf);
return f;
}
}
int a[MAXN],id[MAXN];
inline void solve() {
int n;
scanf("%d",&n),F::init();
for(int i=1;i<=n;++i) scanf("%d",&a[i]),id[a[i]]=i;
int S=F::S=4*n+1,T=F::T=4*n+2;
for(int i=1;i<=n;++i) {
F::link(S,i,1),F::link(S,i+n,1);
F::link(i+2*n,T,1),F::link(i+3*n,T,1);
F::link(i+n,i+2*n,1);
for(int v=2*a[i];v<MAXN;v+=a[i]) if(id[v]) {
F::link(i,id[v]+2*n,1);
F::link(i+n,id[v]+2*n,1);
F::link(i+n,id[v]+3*n,1);
}
}
printf("%d\n",n-(2*n-F::Dinic()));
for(int i=1;i<=n;++i) id[a[i]]=0;
}
signed main() {
int T;
scanf("%d",&T);
while(T--) solve();
}
*F. [QOJ7650] Tên bài sáng tạo
Liên kết đề bài
Tóm tắt đề bài
Cho \(a_0\sim a_n\), hỏi có bao nhiêu \(f_0\sim f_n\) thỏa mãn \(f_i\in[0,a_i]\), và \(\forall i+j\le n,f_{i+j}=f_{f_i+f_j}\).
Phạm dữ liệu: \(n\le 2000\).
Phân tích cách tiếp cận
Đầu tiên đánh giá cho thấy dãy hợp lệ chắc chắn có dạng: tiền缀 là \(f_i=i\), từ một thời điểm nào đó bắt đầu tạo chu kỳ.
Có thể chứng minh chặt chẽ: tìm vị trí đầu tiên xuất hiện \(f_i=f_j\), thì \(f_{i+1}=f_{f_i+f_1}=f_{f_j+f_1}=f_{j+1}\), do đó sau đó sẽ tạo thành chu kỳ.
Đầu tiên giả sử \(f_0=0\), lúc này \(f_i=f_{f_i+f_0}=f_{f_i}\), do đó liệt kê vị trí đầu tiên \(f_i\ne i\) là \(p\), thì \(f_0\sim f_{p-1}=[0,1,\dots,p-1]\).
Xem xét giá trị của \(f_p\), lúc này \(f_{f_p}=f_p\), do đó chu kỳ \(k\mid f_p-p\), sau đó $f_{p+1}=f_{f_p+1},\dots $ suy ra tất cả \(f_i-i\) đều là bội số của \(k\).
Do đó \(f_i=f_{i\bmod k}\), thì \(f_{f_i+f_j}=f_{f_i+f_j\bmod k}=f_{i+j\bmod k}=f_{i+j}\), trong hầu hết trường hợp dãy đã hợp lệ.
Chúng ta còn một yêu cầu: nếu \(i+j\le n\), thì \(f_i+f_j\le n\): lấy \(i=j\) được nếu \(i\le n/2\) thì \(f_i\le n/2\), đủ tính.
Do đó liệt kê \(k,p\), thì \([p,p+k)\] các phần tử \(f_j\) có thể điền \(\le \min(n/2,\min a_{j+tk})\), và các phần tử \(=j+rk\), nếu \(j>\dfrac n2\) thì \(f_j=j\).
Duy trì động thái tích khoảng là được.
Sau đó là trường hợp \(f_0\ne 0\), lúc này \(f_{f_0+f_0}=f_0\), do đó chu kỳ \(k\mid 2f_0\), thì \(f_0\bmod k\in\{0,k/2\}\).
Nếu \(f_0\bmod k=0\), thì tất cả \(f_i\bmod k=i\), ngược lại \(f_i\bmod k=i+\dfrac k2\), liệt kê \(k\) rồi tính toán từng \(f\) là được.
Độ phức tạp thời gian \(\mathcal O(n^2)\).
Mã nguồn
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2005,MOD=998244353;
int n,m,a[MAXN],f[MAXN];
ll c[MAXN],inv[MAXN],ans=0;
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n,inv[1]=1;
for(int i=2;i<=n;++i) inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
for(int i=0;i<=n;++i) cin>>a[i];
while(m<=a[m]) ++m;
if(m>n) ++ans;
for(int k=1;k<=n;++k) {
for(int i=n;i>=1;--i) f[i]=i+k>n?a[i]:min(a[i],f[i+k]);
c[0]=1;
for(int i=1;i<=n;++i) {
if(f[i]<i) c[i]=0;
else if(i>n/2) c[i]=1;
else c[i]=(min(f[i],n/2)-i)/k+1;
}
ll p=1;
for(int i=n,c0=0;~i;--i) {
c[i]?p=p*c[i]%MOD:++c0;
if(i+k>n) continue;
c[i+k]?p=p*inv[c[i+k]]%MOD:--c0;
if(i<=m&&!c0) ans=(ans+p)%MOD;
}
}
for(int k=1;k*2<=n;++k) {
ll p=1;
for(int i=0;i<k;++i) {
int up=n/2;
for(int j=i;j<=n;j+=k) up=min(up,a[j]);
if(up<i) { p=0; break; }
p=p*((up-i)/k+(i>0))%MOD;
}
ans=(ans+p)%MOD;
}
for(int k=2;k<=n;k+=2) {
ll p=1;
for(int i=0;i<k;++i) {
int up=n/2;
for(int j=i;j<=n;j+=k) up=min(up,a[j]);
int lo=i<k/2?i+k/2:i-k/2;
if(up<lo) { p=0; break; }
p=p*((up-lo)/k+1)%MOD;
}
ans=(ans+p)%MOD;
}
cout<<ans<<"\n";
return 0;
}
Vòng #71 - 20250416
A. [UOJ181] Khóa mật
Liên kết đề bài
Tóm tắt đề bài
Cho đồ thị đầy đủ \(n\) đỉnh, mỗi đỉnh sẽ được định hướng ngẫu nhiên, có $m $ cạnh được định hướng với xác suất cho trước, các cạnh còn lại có hai hướng với xác suất \(\dfrac 12\) mỗi hướng, tính kỳ số lượng thành phần liên thông mạnh.
Phạm dữ liệu: \(n\le 38,m\le 19\).
Phân tích cách tiếp cận
Đầu tiên trong đồ thị thi đấu số lượng thành phần liên thông mạnh tương đương với tính số cặp \((S,T)\) cắt sao cho không tồn tại cạnh \(T\to S\).
Do đó liệt kê \(S\) có thể đạt \(\mathcal O(2^n)\).
Chúng ta cần tính tích trọng số của các cạnh \(S\to T\), chú ý rằng trọng số của hầu hết các cạnh đều là \(\dfrac 12\), do đó trước hết nhân với \(2^{-|S|\times |T|}\), sau đó mỗi cạnh đặc biệt nhân thêm một trọng số là được.
Vậy chúng ta chỉ cần quan tâm các cạnh đặc biệt giữa các \(S,T\) này.
Do số lượng cạnh đặc biệt ít, do đó với mỗi thành phần liên thông do các cạnh đặc biệt tạo ra, kích thước \(\le m+1\), trong đó liệt kê \(S\) độ phức tạp là có thể chấp nhận được, sau đó dùng dp để ghi nhớ tổng trọng số tương ứng với mỗi \(|S|\) là được.
Độ phức tạp thời gian \(\mathcal O(n2^m)\).
Mã nguồn
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MOD=998244353,i2=(MOD+1)/2,Q=10000;
ll luythua(ll a,ll b=MOD-2) { ll s=1; for(;b;a=a*a%MOD,b>>=1) if(b&1) s=s*a%MOD; return s; }
int n,m,dsu[45],u[45],v[45],rk[45];
int find(int x) { return dsu[x]^x?dsu[x]=find(dsu[x]):x; }
vector <int> p[45];
ll f[45],g[45],w[45],ans;
signed main() {
ios::sync_with_stdio(false);
cin>>n>>m,iota(dsu+1,dsu+n+1,1);
for(int i=1;i<=m;++i) cin>>u[i]>>v[i]>>w[i],w[i]=w[i]*luythua(Q)%MOD,dsu[find(u[i])]=find(v[i]);
for(int i=1;i<=n;++i) p[find(i)].push_back(i);
f[0]=1;
for(int i=1;i<=n;++i) if(p[i].size()) {
int k=p[i].size();
memset(g,0,sizeof(g)),memset(rk,-1,sizeof(rk));
for(int j=0;j<k;++j) rk[p[i][j]]=j;
for(int s=0;s<(1<<k);++s) {
ll z=1; int c=__builtin_popcount(s);
for(int e=1;e<=m;++e) if(~rk[u[e]]&&~rk[v[e]]&&(s>>rk[u[e]]&1)!=(s>>rk[v[e]]&1)) {
z=z*2*(s>>rk[u[e]]&1?w[e]:1+MOD-w[e])%MOD;
}
for(int j=c;j<=n;++j) g[j]=(g[j]+f[j-c]*z)%MOD;
}
memcpy(f,g,sizeof(f));
}
for(int i=1;i<n;++i) ans=(ans+f[i]*luythua(i2,i*(n-i)))%MOD;
ans=(ans+1)*luythua(Q,n*(n-1))%MOD;
printf("%lld\n",ans);
return 0;
}
B. [P6782] rplexq
Liên kết đề bài
Tóm tắt đề bài
Cho cây \(n\) đỉnh, \(m\) truy vấn \((l,r,x)\) có bao nhiêu cặp \(l\le i<j\le r\) sao cho \(\mathrm{LCA}(i,j)=x\).
Phạm dữ liệu: \(n,m\le 2\times 10^5\).
Phân tích cách tiếp cận
Cần tính số lượng \(x\) trong cây con có bao nhiêu điểm trong \([l,r\]\), và số lượng điểm trong cây con của mỗi con của \(x\) trong \([l,r\]\).
Ý tưởng đơn giản là chia theo thứ tự dfn, rồi dùng tiền缀, tương đương với việc động thái thêm điểm, truy vấn số lượng điểm trong \([l,r\]\).
Nếu dùng暴力 truy vấn đáp án cho mỗi con, khi \(\deg_x\) lớn thì không thể xử lý, do đó có thể dùng căn chia.
Với các truy vấn \(\deg_x\le B\), dùng Sqrt-Tree có thể đạt \(\mathcal O(1)\) truy vấn.
Sau đó với các truy vấn \(\deg_x>B\), xử lý riêng cho từng \(x\).
Sắp xếp tất cả điểm trong cây con của \(x\) theo số thứ tự, tô màu thuộc cây con của con nào, truy vấn là số lượng cặp điểm cùng màu trong khoảng.
Có thể dùng Mo's algorithm duy trì, độ phức tạp \(n\sqrt m\), nhưng \(\sum n\) vẫn không thể chấp nhận.
Có thể nghĩ với các \(x\) như vậy, cây con có kích thước lớn nhất đầu tiên \(B\) dùng Sqrt-Tree như trên, thì \(\sum n\) có thể chấp nhận được.
Lưu ý khi offline cần đạt không gian tuyến tính.
Độ phức tạp thời gian chắc chắn không vượt quá \(\mathcal O((n+m)\sqrt n)\).
Mã nguồn
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5,B=100;
int n,m,rt,ql[MAXN],qr[MAXN],lst[MAXN],pre[MAXN],ed[MAXN];
ll ans[MAXN];
basic_string <int> G[MAXN],Q[MAXN],at[MAXN];
int sz[MAXN],dfn[MAXN],efn[MAXN],dcnt,rk[MAXN];
struct SqrtTree {
int s1[MAXN],s2[MAXN],s3[MAXN];
void add(int x,int y) {
for(int i=((x>>7)<<7);i<=x;++i) s1[i]+=y;
for(int i=((x>>14)<<7);i<(x>>7);++i) s2[i]+=y;
for(int i=0;i<(x>>14);++i) s3[i]+=y;
}
int qry(int x) { return s1[x]+s2[x>>7]+s3[x>>14]; }
int qry(int l,int r) { return qry(l)-qry(r+1); }
} T;
void dfs1(int u,int fz) {
siz[u]=1;
for(int v:G[u]) if(v^fz) dfs1(v,u),siz[u]+=siz[v];
if(fz) G[u].erase(find(G[u].begin(),G[u].end(),fz));
sort(G[u].begin(),G[u].end(),[&](int x,int y){ return siz[x]>siz[y]; });
}
void dfs2(int u) {
dfn[u]=++dcnt,rk[dcnt]=u;
for(int v:G[u]) if(v) dfs2(v);
efn[u]=dcnt;
}
bitset <MAXN> vis;
int a[MAXN],tp,cl[MAXN],ct[MAXN];
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m>>rt;
for(int i=1,u,v;i<n;++i) cin>>u>>v,G[u].push_back(v),G[v].push_back(u);
for(int i=1,x;i<=m;++i) cin>>ql[i]>>qr[i]>>x,Q[x].push_back(i);
dfs1(rt,0),dfs2(rt);
for(int u=1;u<=n;++u) {
at[dfn[u]-1].push_back(u);
at[dfn[u]].push_back(u);
if((int)G[u].size()<=B) {
for(int v:G[u]) at[efn[v]].push_back(u);
} else {
for(int i=0;i<B;++i) at[efn[G[u][i]]].push_back(u);
at[efn[u]].push_back(u);
}
}
for(int i=1;i<=n;++i) {
T.add(rk[i],1);
for(int u:at[i]) for(int x:Q[u]) {
int c=T.qry(ql[x],qr[x])-lst[x];
if(i>=dfn[u]) ans[x]+=1ll*pre[x]*c,pre[x]+=c;
lst[x]+=c,ed[x]=c;
}
}
for(int u=1;u<=n;++u) if((int)G[u].size()>B+1) {
for(int x:Q[u]) ans[x]+=1ll*ed[x]*(ed[x]-1)/2;
for(int i=B;i<(int)G[u].size();++i) {
for(int v=G[u][i],j=dfn[v];j<=efn[v];++j) cl[rk[j]]=i-B,vis.set(rk[j]);
}
for(int i=vis._Find_first();i<=n;i=vis._Find_next(i)) a[++tp]=i;
vector <int> op;
for(int x:Q[u]) {
ql[x]=lower_bound(a+1,a+tp+1,ql[x])-a;
qr[x]=upper_bound(a+1,a+tp+1,qr[x])-a-1;
if(ql[x]<=qr[x]) op.push_back(x);
}
int D=tp/sqrt(op.size()+1)+1;
sort(op.begin(),op.end(),[&](int x,int y){
int dx=(ql[x]-1)/D,dy=(ql[y]-1)/D;
if(dx^dy) return dx<dy;
return dx&1?qr[x]>qr[y]:qr[x]<qr[y];
});
int L=1,R=0; ll tot=0;
auto add=[&](int x) { tot+=ct[cl[x]]++; };
auto del=[&](int x) { tot-=--ct[cl[x]]; };
for(int x:op) {
while(L>ql[x]) add(a[--L]);
while(R<qr[x]) add(a[++R]);
while(L<ql[x]) del(a[L++]);
while(R>qr[x]) del(a[R--]);
ans[x]-=tot;
}
tp=0,memset(ct,0,(G[u].size()-B)<<2),vis.reset();
}
for(int i=1;i<=m;++i) cout<<ans[i]<<"\n";
return 0;
}
C. [CF1163F] Phí taxi không quyết định
Liên kết đề bài
Tóm tắt đề bài
Cho đồ thị vô hướng \(n\) đỉnh \(m\) cạnh, \(q\) truy vấn sửa đổi trọng số một cạnh sau đó đường đi ngắn nhất từ \(1\to n\) (các truy vấn độc lập).
Phạm dữ liệu: \(n,m,q\le 2\times 10^5\).
Phân tích cách tiếp cận
Trước hết cạnh sửa đổi không nằm trên đường đi ngắn nhất là đơn giản, vấn đề cốt lõi là với một cạnh \(e\) trên đường đi ngắn nhất, tìm đường đi ngắn nhất không đi qua \(e\).
Chúng ta có thể chứng minh với mỗi \(e\), chiến lược tối ưu là tìm một cạnh \(f=(u,v)\) không nằm trên đường đi ngắn nhất, sau đó đi theo đường đi ngắn nhất \(1\to u,v\to n\).
Do đó với mỗi điểm không nằm trên đường đi ngắn nhất, tính đường đi ngắn nhất \(1\to u,1\to n\) lcp và \(v\to n,1\to n\) lcs.
Khi đó mỗi cạnh sẽ cập nhật một khoảng trên đường đi ngắn nhất \(1\to n\), dùng cấu trúc dữ liệu duy trì là được.
Độ phức tạp thời gian \(\mathcal O(m\log m+q)\).
Mã nguồn
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5;
int n,m,q,a[MAXN],b[MAXN],c[MAXN];
struct Edge { int v,w,id; };
vector <Edge> G[MAXN];
ll ds[MAXN],dt[MAXN];
bool vis[MAXN];
void dijk(int S,ll *d) {
memset(d,0x3f,sizeof(ds));
memset(vis,0,sizeof(vis));
priority_queue <array<ll,2>,vector<array<ll,2>>,greater<array<ll,2>>> Q;
Q.push({d[S]=0,S});
while(Q.size()) {
int u=Q.top()[1]; Q.pop();
if(vis[u]) continue; vis[u]=true;
for(auto e:G[u]) if(d[e.v]>d[u]+e.w) {
Q.push({d[e.v]=d[u]+e.w,e.v});
}
}
}
int st[MAXN],tp,L[MAXN],R[MAXN],rk[MAXN];
const int N=1<<18;
ll tr[N<<1];
void upd(int l,int r,ll z) {
for(l+=N-1,r+=N+1;l^r^1;l>>=1,r>>=1) {
if(~l&1) tr[l^1]=min(tr[l^1],z);
if(r&1) tr[r^1]=min(tr[r^1],z);
}
}
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m>>q;
for(int i=1;i<=m;++i) {
cin>>a[i]>>b[i]>>c[i];
G[a[i]].push_back({b[i],c[i],i});
G[b[i]].push_back({a[i],c[i],i});
}
dijk(1,ds),dijk(n,dt);
st[++tp]=1;
for(int u=1;u!=n;) {
for(auto e:G[u]) if(dt[e.v]+e.w==dt[u]) {
rk[e.id]=tp,u=e.v; break;
}
st[++tp]=u;
}
memset(L,0x3f,sizeof(L));
for(int i=1;i<=tp;++i) L[st[i]]=i,R[st[i]]=i-1;
vector <int> ord;
for(int i=1;i<=n;++i) ord.push_back(i);
sort(ord.begin(),ord.end(),[&](int x,int y){ return ds[x]<ds[y]; });
for(int u:ord) for(auto e:G[u]) if(!rk[e.id]&&ds[e.v]==ds[u]+e.w) L[e.v]=min(L[e.v],L[u]);
sort(ord.begin(),ord.end(),[&](int x,int y){ return dt[x]<dt[y]; });
for(int u:ord) for(auto e:G[u]) if(!rk[e.id]&&dt[e.v]==dt[u]+e.w) R[e.v]=max(R[e.v],R[u]);
memset(tr,0x3f,sizeof(tr));
for(int i=1;i<=m;++i) if(!rk[i]) {
if(L[a[i]]<=R[b[i]]) upd(L[a[i]],R[b[i]],ds[a[i]]+c[i]+dt[b[i]]);
if(L[b[i]]<=R[a[i]]) upd(L[b[i]],R[a[i]],ds[b[i]]+c[i]+dt[a[i]]);
}
for(int i=1;i<N;++i) tr[i<<1]=min(tr[i<<1],tr[i]),tr[i<<1|1]=min(tr[i<<1|1],tr[i]);
for(int e,x;q--;) {
cin>>e>>x;
if(rk[e]) cout<<min(tr[rk[e]+N],ds[n]-c[e]+x)<<"\n";
else cout<<min({ds[n],ds[a[e]]+x+dt[b[e]],ds[b[e]]+x+dt[a[e]]})<<"\n";
}
return 0;
}
D. [CF1458D] Lật và Đảo ngược
Liên kết đề bài
Tóm tắt đề bài
Cho chuỗi nhị phân \(S\), mỗi lần có thể chọn một xâu con \(S\) có số lượng \(0,1\) bằng nhau, lấy nghịch đảo rồi đảo ngược, tìm chuỗi \(S\) có thứ tự từ điển nhỏ nhất có thể nhận được.
Phạm dữ liệu: \(|S|\le 5\times 10^5\).
Phân tích cách tiếp cận
Xem xét \(\texttt {‘0’}\to -1,\texttt {‘1’}\to +1\), đặt đảo ngược \(S[l,r]\), quan sát mảng tiền缀 của nó \(d_i\) thay đổi.
Do \(S[l,r]\) có số lượng \(0,1\) bằng nhau, do đó \(d_{l-1}=d_r\), quan sát thấy mảng \(d_i\) mới chính là mảng \(d_{r+l-1-i}\) cũ.
Điều này tương đương với đảo ngược \(d[l,r-1]\).
Nếu chúng ta xem tất cả \(d_i\) là đỉnh, nối cạnh có hướng giữa các \(d_i\to d_{i+1}\).
Khi đó \(S\) chính là một đường Euler trên đồ thị này, và các thao tác đảo ngược lần lượt tương đương với việc đảo ngược một vòng \(d_{l-1}\to d_r\) (hai giá trị này bằng nhau), quy nạp có thể chứng minh thao tác của chúng ta có thể đảo ngược bất kỳ vòng nào trên đồ thị này.
Hơn nữa chúng ta có thể chứng minh: xem đồ thị này là đồ thị vô hướng, bất kỳ đường Euler nào đều có thể nhận được chuỗi \(S\) tương ứng.
Sau đó chúng ta có thể tham lam, nếu bước tiếp đi \(-1\) có thể quay lại, hoặc điểm hiện tại không có cạnh \(+1\) thì tham lam đi.
Độ phức tạp thời gian \(\mathcal O(|S|)\).
Mã nguồn
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5;
int w[MAXN*2];
char str[MAXN];
void giai() {
scanf("%s",str+1);
int n=strlen(str+1);
for(int i=1,x=n;i<=n;++i) {
if(str[i]=='0') ++w[--x];
else ++w[x++];
}
for(int i=1,x=n;i<=n;++i) {
if(w[x-1]>1||(w[x-1]&&!w[x])) printf("0"),--w[--x];
else printf("1"),--w[x++];
}
puts("");
}
signed main() {
int T;
scanf("%d",&T);
while(T--) giai();
return 0;
}
*E. [P9394] Bạch Lan
Liên kết đề bài
Tóm tắt đề bài
Chia đồ thị \(G\) \(n\) đỉnh \(m\) cạnh thành các tập hợp \(V_1\sim V_k\), sao cho bất kỳ \(V_1\cup\dots\cup V_i\) liên thông, bất kỳ \(V_{i+1}\cup\cdots\cup V_k\) liên thông.
Cực tiểu hóa \(\max |V_i|\).
Phạm dữ liệu: \(n\le 2\times 10^5,m\le 2.3\times 10^5\).
Phân tích cách tiếp cận
Nếu \(|V_i|=1\), đây chính là định hướng hai cực, khi \(G\) liên thông điểm thì chắc chắn có lời giải.
Nếu \(G\) không liên thông điểm, xây cây tròn - phương:
- Nếu cây tròn - phương là đường, thì với mỗi thành phần liên thông điểm hai cực định hướng, điểm cuối cùng đặt thành điểm cắt với thành phần liên thông điểm tiếp theo là được.
- Ngược lại xem xét đường \(V_1\to V_k\), tìm một điểm phương không nằm trên đường này, điểm phương này chứa các điểm tròn chắc chắn ít nhất một bên không hợp lệ.
Do đó có thể xây dựng khi và chỉ khi \(G\) là thành phần liên thông điểm.
Dễ chứng minh \(V_i\) nội bộ liên thông, nếu không thì có thể tách thành các khối liên thông nhỏ hơn sẽ tốt hơn.
Khi đó chúng ta liệt kê \(V_1,V_k\), lời giải tối ưu chính là xóa các điểm phương trên đường đi, sau đó mỗi điểm tròn tương ứng một khối liên thông, chính là một \(V_i\).
Liệt kê \(\mathrm{LCA}(V_1,V_k)\), đường đi tối ưu chắc chắn mỗi lần đi cây con có kích thước lớn nhất, vậy đơn giản dp trên cây là có thể tìm được phương án, sau đó mỗi thành phần liên thông điểm chạy một lần định hướng hai cực là được.
Độ phức tạp thời gian \(\mathcal O(n+m)\).
Mã nguồn
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5;
vector <int> G[MAXN],E[MAXN];
int n,m,tot;
int dfn[MAXN],low[MAXN],dcnt,stk[MAXN],tp;
bool ins[MAXN];
void lien(int x,int y) { E[x].push_back(y),E[y].push_back(x); }
void tarjan(int u) {
dfn[u]=low[u]=++dcnt,stk[++tp]=u,ins[u]=true;
for(int v:G[u]) {
if(!dfn[v]) {
tarjan(v),low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]) {
lien(u,++tot);
for(;ins[v];ins[stk[tp--]]=false) lien(tot,stk[tp]);
}
} else low[u]=min(low[u],dfn[v]);
}
}
int siz[MAXN],f[MAXN],ans,rt=0,to[MAXN][2];
void dfs1(int u,int fz) {
siz[u]=(u<=n);
vector <int> sn;
for(int v:E[u]) if(v^fz) dfs1(v,u),siz[u]+=siz[v],sn.push_back(v);
sort(sn.begin(),sn.end(),[&](int x,int y){ return siz[x]>siz[y]; });
if(sn.empty()) return f[u]=1,void();
int h=to[u][0]=sn[0],se=to[u][1]=(sn.size()>1?sn[1]:0),vl;
if(u<=n) {
f[u]=max(f[h],siz[u]-siz[h]);
vl=max({f[h],f[se],n-siz[h]-siz[se]});
} else {
f[u]=max(f[h],siz[se]);
vl=max({f[h],f[se],sn.size()>2?siz[sn[2]]:0,n-siz[u]});
}
if(ans>=vl) rt=u,ans=vl;
}
int st[MAXN],q;
bool vis[MAXN];
vector <int> grp[MAXN];
void dfs2(int u,int bl) {
vis[u]=true;
if(u<=n) grp[bl].push_back(u);
for(int v:E[u]) if(!vis[v]) dfs2(v,bl);
}
int fa[MAXN],rk[MAXN];
bool inq[MAXN],del[MAXN];
vector <int> ord,pat,Q[MAXN];
void dfs3(int u) {
low[u]=dfn[u]=++dcnt,rk[dcnt]=u;
for(int v:G[u]) if(inq[v]) {
if(!dfn[v]) fa[v]=u,dfs3(v),low[u]=min(low[u],low[v]);
else low[u]=min(low[u],dfn[v]);
}
Q[fa[u]].push_back(u),Q[rk[low[u]]].push_back(u);
}
void dfs4(int u) {
ord.push_back(u),vis[u]=true;
for(int v:Q[u]) if(!vis[v]&&!del[v]) dfs4(v);
}
vector<int> giai(vector<int>&V,int S,int T) {
dcnt=0,ord.clear(),pat.clear();
for(int u:V) fa[u]=dfn[u]=low[u]=vis[u]=0,inq[u]=1,Q[u].clear();
dfs3(S);
for(int u=T;u;u=fa[u]) pat.push_back(u),del[u]=1;
reverse(pat.begin(),pat.end());
for(int u:pat) dfs4(u);
for(int u:V) inq[u]=del[u]=0;
return ord;
}
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m,tot=n;
for(int i=1,u,v;i<=m;++i) cin>>u>>v,G[u].push_back(v),G[v].push_back(u);
tarjan(1),ans=n+1,dfs1(1,0);
for(int x=rt;x;x=to[x][0]) st[++q]=x;
reverse(st+1,st+q+1);
if(to[rt][1]) for(int x=to[rt][1];x;x=to[x][0]) st[++q]=x;
for(int i=2;i<q;i+=2) vis[st[i]]=true;
for(int i=2;i<q;i+=2) for(int u:E[st[i]]) if(!vis[u]) dfs2(u,u);
vector <int> wys;
for(int i=2;i<q;i+=2) {
auto o=giai(E[st[i]],st[i-1],st[i+1]);
if(wys.size()) wys.pop_back();
for(int u:o) wys.push_back(u);
}
cout<<ans<<" "<<wys.size()<<"\n";
for(int i:wys) {
cout<<grp[i].size()<<" ";
for(int x:grp[i]) cout<<x<<" "; cout<<"\n";
}
return 0;
}
*F. [P10790] Đồ thị có hướng
Liên kết đề bài
Tóm tắt đề bài
Cho đồ thị có hướng \(n\) đỉnh \(m\) cạnh.
- Một điểm \(u\) là loại I: khi và chỉ khi từ \(u\) đến mỗi điểm khác có đường đi đơn duy nhất.
- Một điểm \(u\) là loại II: sau khi xóa một số cạnh, \(u\) là loại I, và các điểm loại I ban đầu vẫn là loại I.
Ngược lại một điểm là loại III, xác định mỗi điểm thuộc loại nào.
Phạm dữ liệu: \(n\le 10^5,m\le 2\times 10^5\).
Phân tích cách tiếp cận
Đầu tiên thu hẹp các thành phần liên thông mạnh, điểm loại I chắc chắn là thành phần liên thông không có nửa bậc vào, nếu như vậy không duy nhất thì tất cả điểm là loại III.
Ngược lại chỉ cần xét thành phần liên thông này, tức xét đồ thị liên thông mạnh, nếu không có điểm loại I thì tất cả điểm là loại II.
Sau đó xác định một điểm là loại I: trước hết xây dfs tree, nếu có cạnh ngang, chắc chắn không phải loại I.
Ngược lại trên dfs tree chỉ có cạnh trả về, có thể quy nạp chứng minh điểm như vậy chắc chắn là loại I.
Giả sử chúng ta tìm được một điểm loại I, xem xét tìm tất cả điểm loại I:
Xem xét mỗi điểm được bao phủ bởi bao nhiêu cạnh trả về, do đồ thị liên thông mạnh, số lần bao phủ \(\ge 1\).
Nếu một điểm được bao phủ bởi \(>1\) cạnh trả về, thì đường đi đến cha nó không duy nhất.
Ngược lại đặt cạnh trả về là \(x\to y\), thì \(u\) là loại I khi và chỉ khi \(y\) là loại I, từ trên xuống dưới quy nạp là được.
Sau đó thử xác định điểm nào là loại II:
Trước hết chúng ta cần biết cạnh nào có thể xóa: trước hết cạnh trên dfs tree sau khi xóa sẽ làm thay đổi tính liên thông của gốc, chắc chắn không thể xóa.
Hơn nữa cạnh trả về \(x\to y\) nếu đi qua một điểm loại I thì không thể xóa, vì nếu xóa thì điểm này không còn là loại I.
Các cạnh khác đều có thể xóa, mục tiêu là xóa một số cạnh trả về có thể xóa, sao cho cạnh trả về còn lại \(x\to y\) duy nhất, và \(y\) là loại II.
Đầu tiên kiểm tra xem có bao nhiêu cạnh trả về không thể xóa đi qua mỗi điểm, sau đó trong quá trình dfs duy trì động thái xem cây con của mỗi điểm có có \(x\) như vậy không, dùng cây BIT là được.
Cuối cùng chúng ta cần tìm một điểm loại I hợp lệ làm gốc:
Xem xét lá, do không có cạnh ngang, nên mỗi lá nửa bậc vào là 1, do đó với mỗi lá \(u\), hợp nhất \(u\) vào điểm vào duy nhất của nó (loại bỏ tự vòng, không xóa cạnh trùng).
Thực chất đây là quá trình thu hẹp lá trên dfs tree, quá trình dừng lại khi đồ thị chắc chắn chỉ còn một điểm duy nhất, chính là một gốc hợp lệ, ngược chứng minh không tồn tại điểm loại I.
Dùng hợp nhất tham lam duy trì quá trình này.
Độ phức tạp thời gian \(\mathcal O(m\log n)\).
Mã nguồn
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int n,m;
vector <int> G[MAXN];
int dsu[MAXN];
int find(int x) { return x^dsu[x]?dsu[x]=find(dsu[x]):x; }
struct FenwickTree {
int tr[MAXN],s;
void init() { memset(tr,0,sizeof(tr)); }
void add(int x) { for(;x<=n;x+=x&-x) ++tr[x]; }
int qry(int x) { for(s=0;x;x&=x-1) s+=tr[x]; return s; }
} TR;
int dfn[MAXN],low[MAXN],dcnt,stk[MAXN],tp,col[MAXN],scnt;
bool ins[MAXN],ind[MAXN],inq[MAXN],vis[MAXN];
void tarjan(int u) {
dfn[u]=low[u]=++dcnt,ins[stk[++tp]=u]=true;
for(int v:G[u]) {
if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
else if(ins[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u) for(++scnt;ins[u];ins[stk[tp--]]=false) col[stk[tp]]=scnt;
}
int deg[MAXN];
vector <int> in[MAXN];
unordered_map <int,int> S[MAXN];
bool kt(int u) {
memset(ins,0,sizeof(ins));
memset(vis,0,sizeof(vis));
bool ok=1;
function<void(int)> dfs=[&](int x) {
vis[x]=ins[x]=true;
for(int y:G[x]) {
if(!vis[y]) dfs(y);
else ok&=ins[y];
}
ins[x]=false;
};
dfs(u);
for(int i=1;i<=n;++i) ok&=vis[i];
return ok;
}
int getrt() {
for(int i=1;i<=n;++i) dsu[i]=i;
for(int i=1;i<=n;++i) for(int j:G[i]) {
++S[i][j],in[j].push_back(i),++deg[j];
}
for(int i=1;i<=n;++i) if(!deg[i]) return kt(i)?i:0;
queue <int> Q;
for(int i=1;i<=n;++i) if(deg[i]==1) Q.push(i);
while(Q.size()) {
int x=0,y=Q.front(); Q.pop();
if(deg[y]!=1||dsu[y]!=y) continue;
for(int k:in[y]) if(find(k)!=y) {
x=find(k); break;
}
S[x].erase(y);
auto it=S[y].find(x);
if(it!=S[y].end()) {
deg[x]-=it->second,S[y].erase(it);
if(deg[x]==1) Q.push(x);
}
if(S[x].size()<S[y].size()) swap(S[x],S[y]);
for(auto e:S[y]) if(e.second) S[x][e.first]+=e.second;
dsu[y]=x;
}
for(int i=1;i<=n;++i) if(dsu[i]==i) return kt(i)?i:0;
return 0;
}
int fa[MAXN],L[MAXN],R[MAXN],k,x[MAXN<<1],y[MAXN<<1];
int dep[MAXN],cov[MAXN],del[MAXN];
vector <int> E[MAXN],T[MAXN];
void dfs0(int u) {
vis[u]=true,L[u]=++dcnt;
for(int v:G[u]) if(inq[v]) {
if(!vis[v]) fa[v]=u,dep[v]=dep[u]+1,T[u].push_back(v),dfs0(v);
else ++k,x[k]=u,y[k]=v,E[v].push_back(u);
}
R[u]=dcnt;
}
bool f[MAXN],g[MAXN],rsv[MAXN];
void dfs1(int u) {
if(cov[u]>0&&f[y[cov[u]]]) f[u]=g[u]=true,rsv[cov[u]]=true;
for(int v:T[u]) dfs1(v);
}
void dfs2(int u) {
if(~del[u]) {
if(del[u]) g[u]|=g[y[del[u]]];
else g[u]|=(TR.qry(R[u])>TR.qry(L[u]-1));
}
if(g[u]) for(int v:E[u]) TR.add(L[v]);
for(int v:T[u]) dfs2(v);
}
void giai() {
cin>>n>>m;
for(int i=1;i<=n;++i) {
G[i].clear(),E[i].clear(),T[i].clear();
S[i].clear(),in[i].clear();
dfn[i]=low[i]=cov[i]=del[i]=deg[i]=0;
ins[i]=ind[i]=f[i]=g[i]=0;
}
dcnt=scnt=tp=0;
for(int i=1;i<=m;++i) cin>>u>>v,G[u].push_back(v),G[v].push_back(u);
for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
int id=0;
for(int i=1;i<=scnt;++i) if(!ind[i]) id=(!id?i:-1);
if(id<=0) {
for(int i=1;i<=n;++i) cout<<"3"; cout<<"\n";
return ;
}
for(int i=1;i<=n;++i) inq[i]=(col[i]==id);
int rt=getrt();
if(!rt) {
for(int i=1;i<=n;++i) cout<<"32"[inq[i]]; cout<<"\n";
return ;
}
memset(vis,0,sizeof(vis));
memset(rsv,0,sizeof(rsv));
dcnt=k=0,dep[rt]=0,dfs0(rt);
for(int i=1;i<=n;++i) dsu[i]=i;
for(int e=1;e<=k;++e) {
for(int u=find(x[e]);dep[u]>dep[y[e]];u=find(fa[u])) {
if(!cov[u]) cov[u]=e;
else cov[u]=-1,dsu[u]=find(fa[u]);
}
}
f[rt]=g[rt]=true;
for(int u:T[rt]) dfs1(u);
for(int i=1;i<=n;++i) dsu[i]=i;
for(int e=1;e<=k;++e) if(rsv[e]) {
for(int u=find(x[e]);dep[u]>dep[y[e]];u=find(fa[u])) {
if(!del[u]) del[u]=e;
else del[u]=-1,dsu[u]=find(fa[u]);
}
}
TR.init();
for(int u:E[rt]) TR.add(L[u]);
for(int u:T[rt]) dfs2(u);
for(int i=1;i<=n;++i) {
if(inq[i]) cout<<"321"[f[i]+g[i]];
else cout<<"3";
}
cout<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
int id,cas; cin>>id>>cas;
while(cas--) giai();
return 0;
}
Vòng #72 - 20250417
A. [P3308] LIS
Liên kết đề bài
Tóm tắt đề bài
Cho \(n\) phần tử \((a_i,b_i,c_i)\), xóa một số phần tử để giảm độ dài dãy con tăng dài nhất của \(a\), và tổng \(\sum b\) của các phần tử xóa là nhỏ nhất, nếu có nhiều phương án, chọn phương án có tập \(\{c\}\) thứ tự từ điển nhỏ nhất.
Phạm dữ liệu: \(n\le 700\).
Phân tích cách tiếp cận
Đầu tiên tính \(\min \sum b\), chia các phần tử theo kết quả dp, một phương án hợp lệ tương đương với việc các điểm \(f_i=1\) và \(f_i=|\mathrm{LIS}|\) không liên thông.
Khi đó chỉ cần tìm cắt nhỏ nhất là được.
Sau đó thêm hạn chế \(\{c\}\), tức tìm cắt nhỏ nhất có thứ tự từ điển nhỏ nhất.
Trước hết xem xét cạnh nào có thể được thêm vào cắt nhỏ nhất.
Có một phương án làm cho các cạnh trong cắt đều đạt cực đại, hơn nữa nếu tồn tại một luồng cực đại không đi qua một cạnh nào đó, thì cạnh đó chắc chắn không thuộc cắt nhỏ nhất:
Giảm trọng số cạnh đó một lượng cực nhỏ \(\epsilon\), luồng cực đại không đổi, nhưng nếu tồn tại một cắt nhỏ nhất đi qua cạnh đó, thì trọng số cắt sẽ \(-\epsilon\), mâu thuẫn.
Do đó các cạnh không đạt cực đại hiện tại chắc chắn không thuộc cắt nhỏ nhất.
Đối với một cạnh đạt cực đại \(u\to v\), nếu có thể tìm được một vòng đi qua \((u,v)\) trên đồ thị dư, thì cạnh \(u\to v\) không còn đạt cực đại, các cạnh này cũng không thể chọn.
Do đó thu hẹp các thành phần liên thông mạnh trên đồ thị dư, cạnh trong cùng một thành phần chắc chắn không thuộc cắt nhỏ nhất.
Hơn nữa có thể chứng minh sau khi thu hẹp, lấy hai tập hợp liên thông \((S,T)\), cạnh giữa chúng chắc chắn tạo thành một cắt nhỏ nhất.
Trong bài này chúng ta cũng thu hẹp, sau đó xem xét mỗi cạnh \((u,v)\) theo thứ tự \(c\) tăng dần, nếu thêm vào cắt nhỏ nhất, thì tất cả tiền tố của \(u\) đều thuộc \(S\), tất cả hậu tố của \(v\) đều thuộc \(T\), đánh dấu theo cách này là được.
Độ phức tạp thời gian \(\mathcal O(\mathrm{Flow}(n,n^2))\).
Mã nguồn
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXV=1405,MAXE=2e5+5;
const ll inf=1e15;
struct Edge {
int v,lst; ll f;
} G[MAXE];
int S,T,tot=1,hd[MAXV],cur[MAXV],dep[MAXV];
void init() { tot=1,memset(hd,0,sizeof(hd)); }
void adde(int u,int v,ll w) { G[++tot]={v,hd[u],w},hd[u]=tot; }
void lien(int u,int v,ll w) { adde(u,v,w),adde(v,u,0); }
bool BFS() {
memcpy(cur,hd,sizeof(cur)),memset(dep,-1,sizeof(dep));
queue <int> Q;
Q.push(S),dep[S]=0;
while(!Q.empty()) {
int u=Q.front(); Q.pop();
for(int i=hd[u];i;i=G[i].lst) if(G[i].f&&dep[G[i].v]==-1) {
dep[G[i].v]=dep[u]+1,Q.push(G[i].v);
}
}
return ~dep[T];
}
ll dfs(int u,ll f) {
if(u==T) return f;
ll r=f;
for(int i=cur[u];i;i=G[i].lst) {
int v=G[cur[u]=i].v;
if(G[i].f&&dep[v]==dep[u]+1) {
ll g=dfs(v,min(r,G[i].f));
if(!g) dep[v]=-1;
G[i].f-=g,G[i^1].f+=g,r-=g;
}
if(!r) return f;
}
return f-r;
}
ll Dinic() {
ll f=0;
while(BFS()) f+=dfs(S,inf);
return f;
}
const int MAXN=705;
int n,a[MAXN],b[MAXN],c[MAXN],dp[MAXN],ed[MAXN];
int dfn[MAXV],low[MAXV],dcnt,stk[MAXV],tp,col[MAXV],scnt;
bool ins[MAXV],ind[MAXV],inq[MAXV],vis[MAXV];
void tarjan(int u) {
dfn[u]=low[u]=++dcnt,ins[stk[++tp]=u]=true;
for(int i=hd[u];i;i=G[i].lst) if(G[i].f) {
int v=G[i].v;
if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
else if(ins[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u) for(++scnt;ins[u];ins[stk[tp--]]=false) col[stk[tp]]=scnt;
}
void dfs(int u,int o) {
if(~cl[u]) return ; cl[u]=o;
for(int i=hd[u];i;i=G[i].lst) if(G[i^o].f||bl[G[i].v]==bl[u]) dfs(G[i].v,o);
}
void giai() {
scanf("%d",&n),init(),S=2*n+1,T=2*n+2;
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=n;++i) scanf("%d",&b[i]);
for(int i=1;i<=n;++i) scanf("%d",&c[i]);
int mx=0;
for(int i=1;i<=n;++i) {
dp[i]=0;
for(int j=1;j<i;++j) if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]);
mx=max(mx,++dp[i]);
}
for(int i=1;i<=n;++i) {
lien(i,i+n,b[i]),ed[i]=tot-1;
if(dp[i]==1) lien(S,i,inf);
if(dp[i]==mx) lien(i+n,T,inf);
for(int j=1;j<i;++j) if(a[j]<a[i]&&dp[j]==dp[i]-1) lien(j+n,i,inf);
}
printf("%lld ",Dinic());
for(int i=1;i<=2*n+2;++i) if(!dfn[i]) tarjan(i);
vector <int> ord,ans;
for(int i=1;i<=n;++i) ord.push_back(i);
sort(ord.begin(),ord.end(),[&](int x,int y){ return c[x]<c[y]; });
memset(cl,-1,sizeof(cl)),dfs(S,0),dfs(T,1);
for(int i:ord) if(!G[ed[i]].f&&bl[i]!=bl[i+n]&&cl[i]!=1&&cl[i+n]!=0) {
ans.push_back(i),dfs(i,0),dfs(i+n,1);
}
sort(ans.begin(),ans.end());
printf("%d\n",(int)ans.size());
for(int u:ans) printf("%d ",u); puts("");
memset(dfn,0,sizeof(dfn)),dcnt=scnt=0;
}
signed main() {
int _; scanf("%d",&_);
while(_--) giai();
return 0;
}
B. [AGC036D] Vòng tròn âm
Liên kết đề bài
Tóm tắt đề bài
Cho đồ thị có hướng \(n\) đỉnh, chứa cạnh \(i\to i+1\) trọng số \(0\), và với mỗi cặp \((i,j)\), cạnh \(i\to j\) trọng số \(\mathrm{sgn}(i-j)\).
Hiện tại xóa một số cạnh loại hai (xóa mỗi cạnh có chi phí tương ứng) để đồ thị không có vòng âm, cực tiểu hóa tổng chi phí.
Phạm dữ liệu: \(n\le 500\).
Phân tích cách tiếp cận
Không có vòng âm khó刻画, không妨 xem mô hình ràng buộc chênh lệch tương ứng có lời giải.
Khi đó viết lại mỗi cạnh tương ứng với ràng buộc:
- \(x_i\ge x_{i+1}\).
- Nếu \(i>j\), thì \(x_i+1\ge x_j\).
- Nếu \(i<j\), thì \(x_i-1\ge x_j\).
Chúng ta cần xây dựng một bộ \(\{x\}\) thỏa mãn ràng buộc sau hai điều kiện, tổng trọng số lớn nhất.
Chia các điểm theo giá trị bằng nhau thành các đoạn, thì các cạnh loại hai trong cùng một đoạn cần xóa, các cạnh loại ba chênh lệch \(>1\) đoạn cần xóa.
Khi đó \(f_{i,j}\) biểu thị đoạn cuối cùng là \([i,j]\) lời giải tối ưu, chuyển dịch liệt kê đoạn tiếp theo \([j+1,k]\), dùng tiền缀 nhanh tính toán trọng lượng là được.
Độ phức tạp thời gian \(\mathcal O(n^3)\).
Mã nguồn
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=505;
int n;
ll tot=0,a[MAXN][MAXN],S[MAXN][MAXN],w[MAXN][MAXN],f[MAXN][MAXN];
ll val(int i,int j,int k) { //(i,j] -> (j,k]
ll sum=w[j+1][k];
sum+=S[j][k]-S[j][j];
sum+=S[k][j]-S[j][j]-S[k][i]+S[j][i];
return sum;
}
signed main() {
scanf("%d",&n);
for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) {
if(i!=j) scanf("%lld",&a[i][j]),tot+=a[i][j];
S[i][j]=a[i][j]+S[i-1][j]+S[i][j-1]-S[i-1][j-1];
}
for(int l=1;l<=n;++l) for(int r=l;r<=n;++r) {
w[l][r]=w[l][r-1];
for(int i=l;i<=r;++i) w[l][r]+=a[r][i];
}
for(int i=1;i<=n;++i) f[0][i]=w[1][i];
for(int j=1;j<=n;++j) for(int i=0;i<j;++i) for(int k=j+1;k<=n;++k) {
f[j][k]=max(f[j][k],f[i][j]+val(i,j,k));
}
ll ans=0;
for(int i=0;i<n;++i) ans=max(ans,f[i][n]);
printf("%lld\n",tot-ans);
return 0;
}
C. [QOJ2070] Đá nặng
Liên kết đề bài
Tóm tắt đề bài
Cho \(n\) đống đá \(a_1\sim a_n\), bạn có thể đi từ một đống đá, mỗi lần gộp một đống đá liền kề bên trái hoặc bên phải, chi phí là tổng số đá sau khi gộp, với mỗi điểm xuất phát, tính tổng chi phí nhỏ nhất để gộp tất cả đá.
Phạm dữ liệu: \(n\le 10^6\).
Phân tích cách tiếp cận
Trước hết với một điểm xuất phát, đây là bài toán trên cây Exchange Argument, nhưng không thể làm cho từng điểm xuất phát.
Chú ý rằng cây là hai đường, có thể chia thành hai phần độc lập, chỉ có khi đi đến nút gốc mới có ảnh hưởng qua lại.
Chúng ta chỉ cần tìm các phần tử cần đi đến gốc trong Exchange Argument, sau đó sắp xếp hợp nhất các phần tử trên hai đường này là có thể được.
Xử lý các phần tử cần đi đến gốc trên một đường là cổ điển, dùng stack đơn điệu từ dưới lên, nếu phần tử trên cùng nhỏ hơn phần tử hiện tại thì hợp nhất.
Từ trước ra sau và từ sau ra trước xử lý ra các phần tử này, đều chỉnh sửa \(\mathcal O(n)\) lần, có thể dùng cây cân bằng duy trì, hoặc offline xuống cây đoạn.
Độ phức tạp thời gian \(\mathcal O(n\log n)\).
Mã nguồn
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5,N=1<<19;
struct info {
ll ct,su,vl;
inline info operator +(const info &o) { return {ct+o.ct,su+o.su,vl+su*o.ct+o.vl}; }
inline bool operator <(const info &o) { return su*o.ct<o.su*ct; }
} f[MAXN*2],tr[N<<1];
void upd(int x,info o) {
for(tr[x+=N]=o,x>>=1;x;x>>=1) tr[x]=tr[x<<1]+tr[x<<1|1];
}
vector <int> op[MAXN];
int n,a[MAXN],st[MAXN],id[MAXN*2],rk[MAXN*2];
signed main() {
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]),f[i]=f[i+n]={1,a[i],a[i]};
int tp=0;
for(int i=1;i<n;++i) {
while(tp&&f[st[tp]]<f[i]) op[i+1].push_back(-st[tp]),f[i]=f[i]+f[st[tp--]]);
op[i+1].push_back(i),st[++tp]=i;
}
tp=0;
for(int i=n;i>1;--i) {
while(tp&&f[st[tp]]<f[i+n]) op[i].push_back(st[tp]),f[i+n]=f[i+n]+f[st[tp--]];
op[i].push_back(-i-n),st[++tp]=i+n;
}
for(int i=1;i<=tp;++i) op[1].push_back(st[i]);
iota(id+1,id+2*n+1,1);
sort(id+1,id+2*n+1,[&](int x,int y){ return f[x]<f[y]; });
for(int i=1;i<=2*n;++i) rk[id[i]]=i;
for(int i=1;i<=n;++i) {
for(int x:op[i]) x<0?upd(rk[-x],{0,0,0}):upd(rk[x],f[x]);
printf("%lld ",tr[1].vl+1ll*(n-1)*a[i]);
}
puts("");
return 0;
}
D. [CF925F] Tuần hoàn tham số
Tóm tắt đề bài
Cho đồ thị có hướng \(n\) đỉnh \(m\) cạnh, mỗi cạnh lưu lượng trên và dưới đều là hàm bậc nhất của \(z\), tính xác suất \(z\in[0,1]\) ngẫu nhiên đồ thị có tuần hoàn có giới hạn trên dưới.
Phạm dữ liệu: \(n\le 1000,m\le 2000\).
Phân tích cách tiếp cận
Đầu tiên xây đồ thị tuần hoàn có giới hạn trên dưới tương ứng, yêu cầu luồng cực đại bằng tổng nửa bậc vào.
Chúng ta biết luồng cực đại bằng cắt nhỏ nhất, mà cấu trúc đồ thị không đổi, do đó các tập cắt có thể có trên đồ thị không đổi.
Các trọng số của các tập cắt này đều là hàm bậc nhất của \(z\), do đó đồ thị cắt nhỏ nhất (luồng cực đại) là giá trị nhỏ nhất của các hàm bậc nhất này, tức một hàm lồi.
Và tổng nửa bậc vào là hàm bậc nhất của \(z\), và luôn lớn hơn hoặc bằng luồng cực đại, do đó câu trả lời chính là độ dài tiếp xúc giữa hàm bậc nhất này và vỏ lồi.
Có thể chia ba độ dốc rồi nhị phân phạm vi.
Độ phức tạp thời gian \(\mathcal O(\mathrm{Flow}(n,m)\log\epsilon)\).
Mã nguồn
#include<bits/stdc++.h>
#define ll long long
using namespace std;
namespace F {
const int MAXV=1005,MAXE=10005;
const ll inf=1e18;
struct Edge {
int v,f,lst;
} G[MAXE];
int S,T,ec=1,vc,hd[MAXV],cur[MAXV],dep[MAXV];
void init() { ec=1,memset(hd,0,(vc+1)<<2); }
void adde(int u,int v,ll w) { G[++ec]={v,w,hd[u]},hd[u]=ec; }
void lien(int u,int v,ll w) { adde(u,v,w),adde(v,u,0); }
bool BFS() {
memcpy(cur,hd,(vc+1)<<2),memset(dep,-1,(vc+1)<<2);
queue <int> Q;
Q.push(S),dep[S]=0;
while(!Q.empty()) {
int u=Q.front(); Q.pop();
for(int i=hd[u];i;i=G[i].lst) if(G[i].f&&dep[G[i].v]==-1) {
dep[G[i].v]=dep[u]+1,Q.push(G[i].v);
}
}
return ~dep[T];
}
int dfs(int u,ll f) {
if(u==T) return f;
int r=f;
for(int i=cur[u];i;i=G[i].lst) {
int v=G[cur[u]=i].v;
if(G[i].f&&dep[v]==dep[u]+1) {
int g=dfs(v,min(r,G[i].f));
if(!g) dep[v]=-1;
G[i].f-=g,G[i^1].f+=g,r-=g;
}
if(!r) return f;
}
return f-r;
}
int Dinic() {
int f=0;
while(BFS()) f+=dfs(S,inf);
return f;
}
}
const int MAXN=2005,V=1e8;
int n,m,u[MAXN],v[MAXN];
ll a[MAXN],b[MAXN],c[MAXN],d[MAXN];
ll deg[MAXN];
ll chk(ll x) {
int s=F::S=n+1,t=F::T=n+2;
F::init();
memset(deg,0,sizeof(deg));
for(int i=1;i<=m;++i) {
ll l=a[i]*x+b[i],r=c[i]*x+d[i];
F::lien(u[i],v[i],r-l),deg[u[i]]-=l,deg[v[i]]+=l;
}
ll rs=0;
for(int i=1;i<=n;++i) {
if(deg[i]>0) F::lien(s,i,deg[i]),rs+=deg[i];
else F::lien(i,t,-deg[i]);
}
return rs-F::Dinic();
}
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;++i) cin>>u[i]>>v[i]>>a[i]>>b[i]>>c[i]>>d[i],b[i]*=V,d[i]*=V;
int l=0,r=V,p=-1,bg,ed;
while(r-l>=3) {
int mid=(l+r)>>1;
if(chk(mid)>chk(mid+1)) l=mid+1;
else r=mid;
}
for(int i=l;i<=r;i++) if(!chk(i)) p=i;
if(p==-1) return cout<<"0\n",0;
l=0,r=p-1,bg=p;
while(l<=r) {
int mid=(l+r)>>1;
if(!chk(mid)) bg=mid,r=mid-1;
else l=mid+1;
}
l=p+1,r=V,ed=p;
while(l<=r) {
int mid=(l+r)>>1;
if(!chk(mid)) ed=mid,l=mid+1;
else r=mid-1;
}
cout<<fixed<<setprecision(20)<<1.*(ed-bg)/V<<"\n";
return 0;
}
*E. [P7417] Giảm cạnh
Liên kết đề bài
Tóm tắt đề bài
Cho đồ thị vô hướng \(n\) đỉnh \(m\) cạnh, xây đồ thị có số cạnh ít nhất sao cho \(\forall (u,x)\), hai đồ thị cùng tồn tại hoặc không tồn tại đường đi dài \(x\) từ \(1\to u\).
Phạm dữ liệu: \(n\le 10^5,m\le 2\times 10^5\).
Phân tích cách tiếp cận
Do chúng ta có thể đi lại trên cùng một cạnh, thì chỉ cần đến mỗi điểm có độ dài đường đi lẻ và chằng bằng nhau là được.
Đặt hai đường đi ngắn nhất này là \((x,y)\), trong đó \(x<y\), thì một điểm như vậy chỉ có thể kết nối với \((x-1,y-1)\), hoặc đồng thời kết nối \((x+1,y-1),(x-1,y+1)\).
Đặc biệt, nếu \(y=x+1\), thì kết nối với \((x,y)\) khác và một \((x-1,y+1)\).
Chúng ta có thể chia các điểm theo \(x+y\), các vấn đề trong cùng một nhóm tương đối độc lập, quét theo \(x\) tăng dần:
Trước hết nếu tồn tại \((x-1,y-1)\) thì ưu tiên kết nối chắc chắn tốt hơn, ngược kết nối \((x-1,y+1)\) và \((x+1,y-1)\).
Nếu \((x+1,y-1)\) đã kết nối với điểm hiện tại, thì tiếp tục kết nối \((x-1,y+1)\) thay vì \((x-1,y-1)\), vì lúc này liên tục kết nối đến \((x,x+1)\), chỉ cần một cạnh là có thể giải quyết hai điểm.
Mô phỏng quá trình trên là được, chú ý trường hợp đồ thị hai phân và điểm \(1\) có tự vòng.
Độ phức tạp thời gian \(\mathcal O(n\log n)\).
Mã nguồn
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5,inf=1e9;
vector <int> G[MAXN];
map <int,int> f[MAXN],g[MAXN];
int n,m,d[MAXN][2];
void giai() {
scanf("%d%d",&n,&m);
for(int i=0;i<=n;++i) f[i].clear(),g[i].clear(),G[i].clear(),d[i][0]=d[i][1]=inf;
for(int i=1,u,v;i<=m;++i) scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);
queue <array<int,2>> Q; d[1][0]=0,Q.push({1,0});
while(Q.size()) {
int u=Q.front()[0],r=Q.front()[1]^1; Q.pop();
for(int v:G[u]) if(d[v][r]==inf) d[v][r]=d[u][r^1]+1,Q.push({v,r});
}
if(d[1][1]==inf) return printf("%d\n",n-1),void();
if(d[1][1]==1) return printf("%d\n",n),void();
vector <array<int,2>> P;
for(int i=1;i<=n;++i) {
int x=min(d[i][0],d[i][1]),y=max(d[i][0],d[i][1]);
if(!f[x][y]++&&i>1) P.push_back({x+y,x});
}
int ans=0;
sort(P.begin(),P.end());
for(auto it:P) {
int x=it[1],y=it[0]-it[1],sz=f[x][y],pr=g[x-1][y+1];
ans+=max(0,sz-pr); //to right or up
if(f[x-1][y-1]) sz=min(sz,pr);
ans+=(y==x+1?(sz+1)/2:g[x][y]=sz); //to left
}
printf("%d\n",ans);
}
signed main() {
int _; scanf("%d",&_);
while(_--) giai();
return 0;
}
*F. [P8501] Vấn đề quy hoạch nguyên bậc hai
Liên kết đề bài
Tóm tắt đề bài
Xây dựng \(x_1\sim x_n\), thỏa mãn \(x_i\in [l_i,r_i]\subseteq[1,k]\) và \(m\) ràng buộc dạng \(|x_u-x_v|\le w\).
\(q\) truy vấn cho \(v_1\sim v_k\), trong đó \(v_1=v_k=0\), cực đại hóa \(10^6\sum_{i,j}[|x_i-x_j|\le 1]+\sum v_i\sum_j [x_j=i]\).
Phạm dữ liệu: \(n\le 600,m\le 3n,q\le 3\times 10^5,k\le 5\).
Phân tích cách tiếp cận
Chỉ phân tích trường hợp \(k=5\).
Trước hết điền càng ít phần tử \(1,5\) càng tốt, có thể tiền xử lý các phần tử như vậy.
Các phần tử còn lại chọn trong \(2,3,4\), khi đó đáp án là \(\sum v_ic_i+10^6(n^2-2(c_2c_4-c_1c_4-c_2c_5-c_1c_5-c_3c_1-c_3c_5))\).
Khi đó đáp án có thể xem như một hàm về \(x=c_2,y=c_4\) dạng \(f(x,y)=axy+bx+cy+d\), với \(a=-2\times 10^6\).
Viết lại thành cực đại hóa \(a(x-x_0)(y-y_0)\), tức cực tiểu hóa \((x-x_0)(y-y_0)\).
Vẽ tất cả \((x,y)\) lên mặt phẳng, đặt phạm vi chúng chiếm là \([x_L,x_R]\times [y_L,y_R]\), do một số ràng buộc có thể điều chỉnh một số phần tử \(2,4\) thành \(3\), do đó chắc chắn có thể lấy được \((x_L,y_R)\) hoặc \((x_R,y_L)\).
Nếu hình chữ nhật này dịch chuyển \((-x_0,-y_0)\) đi qua các góc thứ hai và thứ tư, thì đáp án chắc chắn lấy tại \((x_L,y_R)\) hoặc \((x_R,y_L)\).
Ngược lại hoặc toàn bộ ở góc thứ nhất hoặc toàn bộ ở góc thứ ba, trường hợp đầu tiên đáp án lấy tại \((x_L,y_L)\).
Ngược lại tương đương với tìm \((x,y)\) vỏ lồi trên, tương tự cây cầu nhân nhỏ nhất, chia để trị xây dựng vỏ凸, mỗi lần tìm điểm xa nhất so với hai đầu của khoảng hiện tại, điểm này chắc chắn nằm trên vỏ凸.
Vấn đề này tương đương với tìm một lời giải cực đại hóa \(z_2c_2+z_4c_4\), trước hết chuyển thành cực tiểu hóa \(z_4c_2+(z_2+z_4)c_3+z_2c_4\).
Sau đó thu hẹp các thành phần liên thông có \(w=0\), ràng buộc là một số điểm không thể một điền \(2\) một điền \(4\), đây là mô hình cắt bánh cổ điển, dùng luồng mạng giải quyết.
Có thể chứng minh số điểm trên vỏ凸 không vượt quá \(\mathcal O(n^{2/3})\).
Độ phức tạp thời gian \(\mathcal O(n^{2/3}(q+\mathrm{Flow}(n,m)))\).
Mã nguồn
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=605,Z=1e6,inf=1e9;
int k,n,m,q,L[MAXN],R[MAXN],c[6];
int dsu[MAXN],bl[MAXN],id[MAXN],sz[MAXN],tot;
int find(int x) { return x^dsu[x]?dsu[x]=find(dsu[x]):x; }
vector <array<int,2>> vc,lim;
struct Flow {
static const int MAXV=1205,MAXE=2e5+5;
struct Edge {
int v,f,lst;
} G[MAXE];
int S,T,ec=1,vc,hd[MAXV],cur[MAXV],dep[MAXV];
void init() { ec=1,memset(hd,0,(vc+1)<<2); }
void adde(int u,int v,ll w) { G[++ec]={v,w,hd[u]},hd[u]=ec; }
void lien(int u,int v,ll w) { adde(u,v,w),adde(v,u,0); }
bool BFS() {
memcpy(cur,hd,(vc+1)<<2),memset(dep,-1,(vc+1)<<2);
queue <int> Q;
Q.push(S),dep[S]=0;
while(!Q.empty()) {
int u=Q.front(); Q.pop();
for(int i=hd[u];i;i=G[i].lst) if(G[i].f&&dep[G[i].v]==-1) {
dep[G[i].v]=dep[u]+1,Q.push(G[i].v);
}
}
return ~dep[T];
}
int dfs(int u,ll f) {
if(u==T) return f;
int r=f;
for(int i=cur[u];i;i=G[i].lst) {
int v=G[cur[u]=i].v;
if(G[i].f&&dep[v]==dep[u]+1) {
int g=dfs(v,min(r,G[i].f));
if(!g) dep[v]=-1;
G[i].f-=g,G[i^1].f+=g,r-=g;
}
if(!r) return f;
}
return f-r;
}
int Dinic() {
int f=0;
while(BFS()) f+=dfs(S,inf);
return f;
}
} F;
void build(array<int,2>a,array<int,2>b) {
int wx=a[1]-b[1],wy=b[0]-a[0];
int s=F::S=2*tot+1,t=F::T=F::vc=2*tot+2;
F::init();
for(int i=1;i<=tot;++i) {
F::lien(s,i,L[id[i]]==2?sz[i]*wy:inf);
F::lien(i,i+tot,sz[i]*(wy+wx));
F::lien(i+tot,t,R[id[i]]==4?sz[i]*wx:inf);
}
for(auto e:lim) F::lien(e[0]+tot,e[1],inf),F::lien(e[1]+tot,e[0],inf);
F::Dinic();
array<int,2>o{c[2],c[4]};
for(int i=1;i<=tot;++i) {
if(F::dep[i]==-1) o[0]+=sz[i];
if(~F::dep[i+tot]) o[1]+=sz[i];
}
if(o[0]*wx+o[1]*wy>a[0]*wx+a[1]*wy) vc.push_back(o),build(a,o),build(o,b);
}
void giai() {
cin>>k>>n>>m>>q;
for(int i=1;i<=n;++i) cin>>L[i]>>R[i];
vector <array<int,3>> edg;
for(int i=1,u,v,w;i<=m;++i) {
cin>>u>>v>>w,edg.push_back({u,v,w});
}
for(int t=1;t<=n;++t) for(auto e:edg) {
int u=e[0],v=e[1],w=e[2];
L[v]=max(L[v],L[u]-w),R[v]=min(R[v],R[u]+w);
L[u]=max(L[u],L[v]-w),R[u]=min(R[u],R[v]+w);
}
for(int i=1;i<=n;++i) {
if(R[i]>1&&L[i]<k) L[i]=max(L[i],2),R[i]=min(R[i],k-1);
if(L[i]==R[i]) ++c[L[i]];
}
if(k==3) vc={{n-c[1]-c[3],n-c[1]-c[3]}};
else if(k==4) vc={{c[2],n-c[1]-c[2]-c[4]},{n-c[1]-c[3]-c[4],c[3]}};
else {
int m2=0,m4=0;
for(int i=1;i<=n;++i) m2+=L[i]==2,m4+=R[i]==4;
vc={{c[2],c[4]},{c[2],m4},{m2,c[4]}};
tot=0,lim.clear(),iota(dsu+1,dsu+n+1,1);
for(auto e:edg) if(!e[2]) dsu[find(e[0])]=find(e[1]);
for(int i=1;i<=n;++i) if(L[i]!=R[i]&&dsu[i]==i) id[++tot]=i,bl[i]=tot;
for(int i=1;i<=n;++i) if(L[i]!=R[i]) ++sz[bl[find(i)]];
for(auto e:edg) if(e[2]==1) {
int x=bl[find(e[0])],y=bl[find(e[1])];
if(x&&y) lim.push_back({x,y});
}
build(vc[1],vc[2]);
}
while(q--) {
array <ll,6> vt={0,0,0,0,0,0};
for(int i=2;i<k;++i) cin>>vt[i];
ll ans=0;
for(auto o:vc) {
auto e=c;
e[2]=o[0],e[k-1]=o[1];
if(k==5) e[3]=n-e[1]-e[2]-e[4]-e[5];
ll s=0;
for(int i=1;i<=k;++i) s+=vt[i]*e[i]+1ll*(e[i]+2*e[i-1])*e[i]*Z;
ans=max(ans,s);
}
cout<<ans<<"\n";
}
memset(sz,0,sizeof(sz)),memset(c,0,sizeof(c)),memset(bl,0,sizeof(bl)),tot=0;
}
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int ty,_; cin>>ty>>_;
while(_--) giai();
return 0;
}