Hiện tại vẫn đang tập luyện ARC và CF.
ARC075E
Câu hỏi là tính số lượng khoảng区间的 trung bình lớn hơn hoặc bằng \(k\). Chúng ta có thể biến mỗi số thành tổng của nó và \(k \times độ dài\) của khoảng, sau đó排序. Nếu một phần tử trong danh sách sắp xếp trước vẫn nằm ở vị trí trước một phần tử khác trong danh sách đã sắp xếp, thì khoảng trung bình của chúng lớn hơn hoặc bằng \(k\), rõ ràng. Có thể sử dụng cây con đếm để xử lý.
Xem mã nguồn
#include<bits/stdc++.h>
using namespace std;
#define db long double
#define ll long long
#define mk make_pair
const ll N=3*114514,M=1919810,mod=92084931,inf=1e18;
ll n,k,tong[N],kq;
struct xx{
ll id,gt;
}mang[N];
bool cmp(xx x,xx y){
return x.gt^y.gt?x.gt<y.gt:x.id<y.id;
}
ll c[N];
ll bitNo(ll x){return x&-x;}
void capNhat(ll x,ll k){
while(x<=n){
c[x]+=k,c[x]%=mod;
x+=bitNo(x);
}
}
ll truyVan(ll x){
ll ans=0;
while(x){
ans+=c[x],ans%=mod;
x-=bitNo(x);
}
return ans;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;++i){
ll x; cin>>x;
tong[i]=tong[i-1]+x;
mang[i]=(xx){i,tong[i-1]-(i-1)*k};
}
mang[++n]=(xx){n,tong[n-1]-(n-1)*k};
sort(mang+1,mang+n+1,cmp);
for(int i=1;i<=n;++i){
kq+=(kq+truyVan(mang[i].id))%mod;
capNhat(mang[i].id,1);
}
cout<<kq;
return 0;
}
ARC074F
Minimum cut, xem xét \(S\) chỉ kết nối ra, \(T\) chỉ kết nối vào, các điểm khác kết nối đến các điểm có thể đến được. Để đảm bảo mỗi点 chỉ bị cắt một lần, có một mẹo: tách点 thành điểm vào và ra, kết nối chúng bằng một cạnh có lưu lượng \(1\). Các điểm khác kết nối đến và đi từ các điểm này với lưu lượng \(\text{inf}\). Tuy nhiên, cách này tạo ra \(n^3\) cạnh, cần tối ưu: kết nối các点 trong cùng hàng hoặc cột đến một điểm chung, giảm số lượng cạnh xuống \(n^2\). Không có lời giải nếu \(S, T\) cùng hàng hoặc cột, chạy thuật toán maximum flow.
Xem mã nguồn
#include<bits/stdc++.h>
using namespace std;
#define db long double
#define ll long long
#define mk make_pair
const ll N=3*114514,M=1919810,mod=1e9+7,inf=1e18;
struct xx{
ll next,to,val;
}e[2*N];
ll dau[2*N],dem=1;
void them(ll x,ll y,ll z){
e[++dem].next=dau[x];
e[dem].to=y;
e[dem].val=z;
dau[x]=dem;
e[++dem].next=dau[y];
e[dem].to=x;
e[dem].val=0;
}
ll dept[30005],cur[2*N];
queue<ll> q;
ll h,w,n,s,t,sx,sy,tx,ty;
char c[105][105];
bool bfs(){
memset(dept,0,sizeof(dept));
q.push(s);
dept[s]=1,cur[s]=dau[s];
while(!q.empty()){
ll u=q.front(); q.pop();
for(int i=dau[u];i;i=e[i].next){
ll v=e[i].to,w=e[i].val;
if(!dept[v]&&w){
q.push(v);
dept[v]=dept[u]+1;
cur[v]=dau[v];
}
}
}
return dept[t];
}
ll dfs(ll u,ll val){
if(u==t) return val;
ll use=0;
for(int i=cur[u];i&&use<val;i=e[i].next){
ll v=e[i].to,w=e[i].val; cur[u]=i;
if(dept[v]==dept[u]+1&&w){
ll res=dfs(v,min(w,val-use));
if(!res) dept[v]=0;
e[i].val-=res,e[i^1].val+=res;
val-=res,use+=res;
}
}
return use;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>h>>w; n=h*w;
for(int i=1;i<=h;++i)
for(int j=1;j<=w;++j){
ll id=(i-1)*w+j;
cin>>c[i][j];
if(c[i][j]!='.'){
if(c[i][j]!='S'&&c[i][j]!='T') them(id,id+n,1);
if(c[i][j]=='S') s=id+n,sx=i,sy=j;
if(c[i][j]=='T') t=id,tx=i,ty=j;
them(id+n,2*n+i,inf);
them(2*n+i,id,inf);
them(id+n,2*n+h+j,inf);
them(2*n+h+j,id,inf);
}
}
if(sx==tx||sy==ty){
cout<<-1;
return 0;
}
ll ans=0,res;
while(bfs())
while((res=dfs(s,inf))) ans+=res;
cout<<ans;
return 0;
}
ABC065D
Câu hỏi này nhìn ban đầu là hoàn chỉnh graph tìm最小生成树, nhưng không biết cách Boruvka. Xem xét giảm số lượng cạnh: mỗi点 chỉ cần kết nối với点 gần nhất theo các軸. Dùng Kruskal.
Xem mã nguồn
#include<bits/stdc++.h>
using namespace std;
#define db long double
#define ll long long
#define mk make_pair
const ll N=2*114514,M=1919810,mod=92084931,inf=1e18;
ll n,dem;
struct canh{
ll u,v,w;
}e[N];
struct xx{
ll x,y,id;
}diem[N];
bool cmp1(xx x,xx y){
return x.x^y.x?x.x<y.x:x.y<y.y;
}
bool cmp2(xx x,xx y){
return x.y^y.y?x.y<y.y:x.x<y.x;
}
bool cmp3(canh x,canh y){
return x.w<y.w;
}
ll parent[N];
ll find(ll x){return x==parent[x]?x:parent[x]=find(parent[x]);}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for(int i=1;i<=n;++i) cin>>diem[i].x>>diem[i].y,diem[i].id=i,parent[i]=i;
sort(diem+1,diem+n+1,cmp1);
for(int i=1;i<n;++i) e[++dem]=(canh){diem[i].id,diem[i+1].id,diem[i+1].x-diem[i].x};
sort(diem+1,diem+n+1,cmp2);
for(int i=1;i<n;++i) e[++dem]=(canh){diem[i].id,diem[i+1].id,diem[i+1].y-diem[i].y};
ll kq=0,tong=0;
sort(e+1,e+dem+1,cmp3);
for(int i=1;i<=dem;++i){
ll u=e[i].u,v=e[i].v,w=e[i].w;
ll x=find(u),y=find(v);
if(x!=y){
parent[y]=x;
kq+=w,++tong;
if(tong==n-1) break;
}
}
cout<<kq;
return 0;
}
ARC081E
wht giảng cho tôi. Xử lý chuỗi ngược lại, mỗi khi掃 một nhóm \(a\) đến \(z\) ghi lại vị trí bắt đầu của nhóm. Sau đó掃 từ đầu, mỗi lần thêm vào kết quả ký tự đầu tiên không có trong nhóm hiện tại, rồi tiếp tục đệ quy. Đúng không, nhưng tôi quên cách chứng minh.
Xem mã nguồn
#include<bits/stdc++.h>
using namespace std;
#define ll int
const ll N=500005,M=1919810,B=777;
inline ll read(){
ll x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
x=x*10+ch-'0',ch=getchar();
return x*f;
}
inline void write(ll x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
ll MAX(ll a,ll b){return a>=b?a:b;}
ll MIN(ll a,ll b){return a<=b?a:b;}
ll n,m,las,a[N],b[N];
ll ns,nq,bel[N],st[B],ed[B];
ll sum[B][B],dem[N],id[N];
vector<ll> g[N];
void xuLy(ll id,ll dem){
memset(xet,0,sizeof(xet));
for(int i=id;i<=vitri[dem];++i) xet[diem[i]-'a']=1;
ll kyTu;
for(int i=0;i<26;++i)
if(!xet[i]){
kyTu=i;
break;
}
kq[++m]=char(kyTu+'a');
for(int i=vitri[dem];i<=n;++i)
if(diem[i]-'a'==kyTu){
xuLy(i+1,dem-1);
break;
}
}
int main(){
scanf("%s",diem+1); n=strlen(diem+1);
ll dem=0;
for(int i=n;i>=1;--i){
if(!xet[diem[i]-'a']){
++dem;
if(dem==26){
dem=0;
memset(xet,0,sizeof(xet));
vitri[++m]=i;
}
else xet[diem[i]-'a']=1;
}
}
vitri[0]=n;
xuLy(1,m);
printf("%s",kq+1);
return 0;
}
ARC076E
Bạn sẽ nhận thấy nếu một cặp点 không có ít nhất một点 ở biên, thì đường thẳng kết nối chúng có thể quanh co tùy ý. Vì vậy chỉ cần xem xét các点 ở biên. Chúng ta có thể gán cho mỗi点 một khoảng cách thống nhất, ở đây là khoảng cách theo chiều kim đồng hồ đến góc trên trái \((1,1)\). After sorting, it becomes a matching problem with a stack.
Xem mã nguồn
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=2*114514,M=1919810;
ll r,c,n,dem,top;
ll stack[N];
struct xx{
ll x,y,id,gt;
}mang[N];
bool cmp(xx x,xx y){
return x.gt<y.gt;
}
ll tinh(ll x,ll y){
if(y==0) return x;
else if(x==r) return r+y;
else if(y==c) return r+c+(r-x);
else return r+c+r+(c-y);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>r>>c>>n;
for(int i=1;i<=n;++i){
ll x,y,u,v;
cin>>x>>y>>u>>v;
if((x>0&&x<r&&y>0&&y<c)||(u>0&&u<r&&v>0&&v<c)) continue;
mang[++dem]=(xx){x,y,i,tinh(x,y)};
mang[++dem]=(xx){u,v,i,tinh(u,v)};
}
sort(mang+1,mang+dem+1,cmp);
for(int i=1;i<=dem;++i)
if(stack[top]==mang[i].id) --top;
else stack[++top]=mang[i].id;
if(top) cout<<"NO";
else cout<<"YES";
return 0;
}
CF990G GCD Counting
Một cây \(n\)点, mỗi点 có trọng số \(a_i\). Định nghĩa \(g(x,y)\) là GCD của các trọng số trên con đường từ \(x\) đến \(y\). For each \(k \in [1, 2 \times 10^5]\), count the number of pairs \((x,y)\) where \(g(x,y)=k\).
Phương pháp điểm phân治. Duyệt các giá trị GCD và sử dụng set để quản lý. Mỗi sub-tree cần duy trì một cấu trúc dữ liệu để tính toán.
Xem mã nguồn
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define lxl long long
const ll N=2*114514,M=1919810,B=777;
ll gcd(ll a,ll b){return a?gcd(b%a,a):b;}
struct xx{
ll next,to;
}e[2*N];
ll dau[2*N],dem;
ll n,a[N],maxa;
ll rt,siz[N],maxp[N],tong;
ll mMax;
bool vis[N];
void findRt(ll u,ll fa){
siz[u]=1;
ll mMax=0;
for(int i=dau[u];i;i=e[i].next){
ll v=e[i].to;
if(v==fa||vis[v]) continue;
findRt(v,u);
siz[u]+=siz[v];
mMax=max(mMax,siz[v]);
}
mMax=max(mMax,tong-siz[u]);
if(mMax<msiz) msiz=mMax,rt=u;
}
lxl ans[N],kt[N],tong[N];
set<ll> s,se;
void dfsVal(ll u,ll fa,ll val){
if(!kt[val]++) s.insert(val);
++ans[val];
for(int i=dau[u];i;i=e[i].next){
ll v=e[i].to;
if(vis[v]) continue;
dfsVal(v,u,gcd(val,a[v]));
}
}
void xuLy(ll u){
++ans[a[u]];
for(int i=dau[u];i;i=e[i].next){
ll v=e[i].to;
if(vis[v]) continue;
dfsVal(v,u,gcd(a[u],a[v]));
for(auto y:se)
for(auto x:s)
ans[gcd(x,y)]+=kt[x]*tong[y];
for(auto x:s) se.insert(x),tong[x]+=kt[x],kt[x]=0;
s.clear();
}
for(auto x:se) tong[x]=0;
se.clear();
}
void solve(ll u){
xuLy(u);
vis[u]=1;
for(int i=dau[u];i;i=e[i].next){
ll v=e[i].to;
if(vis[v]) continue;
msiz=tong=siz[v];
findRt(v,u),solve(rt);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for(int i=1;i<=n;++i) cin>>a[i],maxa=max(maxa,a[i]);
for(int i=1;i<n;++i){
ll x,y; cin>>x>>y;
them(x,y),them(y,x);
}
tong=msiz=n;
findRt(1,0);
solve(rt);
for(int i=1;i<=maxa;++i)
if(ans[i]) cout<<i<<" "<<ans[i]<<'\n';
return 0;
}
ARC122C
Phát hiện thêm một và thao tác交替 \(3/4\) tạo ra một dãy Fibonacci. Dùng Fibonacci để cận \(n\). Mỗi thao tác \(1/2\) có đóng góp khác nhau tùy vào chẵn lẻ. Duyệt các vị Fibonacci để thêm thao tác.
Xem mã nguồn
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mk make_pair
const ll N=2*114514,M=1919810,inf=1145141919810;
ll n,s,f[N],xet[N];
vector<ll> g;
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
f[0]=0,f[1]=1;
for(int i=2;i<=88;++i) f[i]=f[i-1]+f[i-2];
for(int i=87;i>=1;--i){
if(n>=f[i]){
n-=f[i];
xet[i]=1;
if(!s) s=i;
}
}
if(s%2==1) g.push_back(1);
else g.push_back(2);
for(int i=s-1;i>=1;--i){
if(i%2==1) g.push_back(3);
else g.push_back(4);
if(xet[i]){
if(i%2==1) g.push_back(1);
else g.push_back(2);
}
}
cout<<g.size()<<'\n';
for(int i:g) cout<<i<<'\n';
return 0;
}
CF1004E
Kết luận then chinh: các点 được chọn nên nằm trên đường kính của cây. Sử dụng BFS và DFS để tìm đường kính, sau đó chọn \(k\) points liên tục trên đường kính, và tính khoảng cách đến các points khác.
Xem mã nguồn
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define mk make_pair
const ll N=114514,M=1919810,inf=2e9;
struct xx{
ll next,to,val;
}e[2*N];
ll dau[2*N],dem;
void them(ll x,ll y,ll z){
e[++dem].next=dau[x];
e[dem].to=y;
e[dem].val=z;
dau[x]=dem;
}
ll n,k;
ll ans=inf;
bool vis[N];
ll batDau,ketThuc,khoangCach[N],parent[N];
void dfs(ll u,ll fa){
for(int i=dau[u];i;i=e[i].next){
ll v=e[i].to,w=e[i].val;
if(v==fa||vis[v]) continue;
khoangCach[v]=khoangCach[u]+w;
parent[v]=u;
dfs(v,u);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>k;
for(int i=1;i<n;++i){
ll a,b,c;
cin>>a>>b>>c;
them(a,b,c),them(b,a,c);
}
dfs(1,0);
ll maxn=0;
for(int i=1;i<=n;++i)
if(khoangCach[i]>maxn) maxn=khoangCach[i],batDau=i;
memset(khoangCach,0,sizeof(khoangCach));
parent[batDau]=0;
dfs(batDau,0);
maxn=0;
for(int i=1;i<=n;++i)
if(khoangCach[i]>maxn) maxn=khoangCach[i],ketThuc=i;
for(int i=ketThuc;i;i=parent[i]) vis[i]=1;
ll l=ketThuc,r=ketThuc;
for(int i=1;i<k&&parent[r];++i) r=parent[r];
while(l&&r){
ans=min(ans,max(khoangCach[ketThuc]-khoangCach[l],khoangCach[r]));
l=parent[l],r=parent[r];
}
for(int i=ketThuc;i;i=parent[i]) khoangCach[i]=0,dfs(i,0);
for(int i=1;i<=n;++i)
if(!vis[i]) ans=max(ans,khoangCach[i]);
if(ans!=inf) cout<<ans;
else cout<<0;
return 0;
}
CF1032F
Tree counting, sử dụng DP. Để maximum matching duy nhất, sub-tree phải có số点 chẵn và có thể cặp đôi.
Xem mã nguồn
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define mk make_pair
const ll N=114514,M=1919810,inf=2e9;
struct xx{
ll next,to,val;
}e[2*N];
ll dau[2*N],dem;
void them(ll x,ll y,ll z){
e[++dem].next=dau[x];
e[dem].to=y;
e[dem].val=z;
dau[x]=dem;
}
ll n,k;
ll ans=inf;
bool vis[N];
ll batDau,ketThuc,khoangCach[N],parent[N];
void dfs(ll u,ll fa){
for(int i=dau[u];i;i=e[i].next){
ll v=e[i].to,w=e[i].val;
if(v==fa||vis[v]) continue;
khoangCach[v]=khoangCach[u]+w;
parent[v]=u;
dfs(v,u);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>k;
for(int i=1;i<n;++i){
ll a,b,c;
cin>>a>>b>>c;
them(a,b,c),them(b,a,c);
}
dfs(1,0);
ll maxn=0;
for(int i=1;i<=n;++i)
if(khoangCach[i]>maxn) maxn=khoangCach[i],batDau=i;
memset(khoangCach,0,sizeof(khoangCach));
parent[batDau]=0;
dfs(batDau,0);
maxn=0;
for(int i=1;i<=n;++i)
if(khoangCach[i]>maxn) maxn=khoangCach[i],ketThuc=i;
for(int i=ketThuc;i;i=parent[i]) vis[i]=1;
ll l=ketThuc,r=ketThuc;
for(int i=1;i<k&&parent[r];++i) r=parent[r];
while(l&&r){
ans=min(ans,max(khoangCach[ketThuc]-khoangCach[l],khoangCach[r]));
l=parent[l],r= parent[r];
}
for(int i=ketThuc;i;i=parent[i]) khoangCach[i]=0,dfs(i,0);
for(int i=1;i<=n;++i)
if(!vis[i]) ans=max(ans,khoangCach[i]);
if(ans!=inf) cout<<ans;
else cout<<0;
return 0;
}