T1
显然,若 \(t[l,r]\) 均为 \(\texttt1\),会让 \(s[l,r]\) 可以任意重排。
从左到右按位匹配,考虑让一位匹配的代价,可能会让其后面缺少一个数进行匹配,也就是后面的答案最多减少 \(1\)。而匹配一位已经有了 \(1\) 的贡献,故贪心匹配一定不劣。
预处理后暴力匹配即可,附上赛时代码。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=100007;
ll n,ans,a1[maxn],a2[maxn],b1[maxn],b2[maxn],v1[maxn],v2[maxn],s1[maxn][2],s2[maxn][2],c1,c2;
int main(void){
//freopen("edit.in","r",stdin);
//freopen("edit.out","w",stdout);
ll T=1; cin>>T;
for(;T--;){
cin>>n; char t; ans=0;
for(int i=1;i<=n;i++) cin>>t,a1[i]=(t=='1');
for(int i=1;i<=n;i++) cin>>t,a2[i]=(t=='1');
for(int i=1;i<=n;i++) cin>>t,b1[i]=(t=='1');
for(int i=1;i<=n;i++) cin>>t,b2[i]=(t=='1');
memset(s1,0,sizeof(s1)),memset(s2,0,sizeof(s2)),memset(v1,0,sizeof(v1)),memset(v2,0,sizeof(v2));
c1=1,s1[c1][0]=s1[c1][1]=0;
for(int i=1;i<=n;i++){
if(!b1[i]) c1++,s1[c1][0]=s1[c1][1]=0;
else v1[i]=c1,s1[c1][a1[i]]++;
}
c2=1,s2[c2][0]=s2[c2][1]=0;
for(int i=1;i<=n;i++){
if(!b2[i]) c2++,s2[c2][0]=s2[c2][1]=0;
else v2[i]=c2,s2[c2][a2[i]]++;
}
//for(int i=1;i<=n;i++) cout<<v1[i]<<" "; cout<<"\n";
for(int i=1;i<=n;i++){
if(b1[i]==0&&b2[i]==0) ans+=(a1[i]==a2[i]);
else if(b1[i]==1&&b2[i]==0){
if(s1[v1[i]][a2[i]]) s1[v1[i]][a2[i]]--,ans++;
}else if(b1[i]==0&&b2[i]==1){
if(s2[v2[i]][a1[i]]) s2[v2[i]][a1[i]]--,ans++;
}else{
if(s1[v1[i]][0]&&s2[v2[i]][0]){
s1[v1[i]][0]--,s2[v2[i]][0]--;
ans++;
}else if(s1[v1[i]][1]&&s2[v2[i]][1]){
s1[v1[i]][1]--,s2[v2[i]][1]--;
ans++;
}
}
}
cout<<ans<<"\n";
}
return 0;
}
T2
首先给一元限制按 \(c\) 排序,对于两个相邻的一元限制 \((p,x),(q,y)\),计数安排 \(a[p,q-1],b[p,q-1]\) 的不合法方案数。
可以发现,一个不合法的方案形如 \(a_p=x,a_{p+1}=b_p,a_{p+2}=b_{p+1},\ldots,a_{q-1}=b_{q-2},b_{q-1}\neq y\)。其中有 \(b_{p},b_{p+1},\ldots,b_{q-2} \) 可以取 \([1,V]\) 中任意值,\(b_{q-1}\) 可以取 \([1,V]/\{y\}\) 中任意值,于是总共有 \(V^{p-q-1}(V-1)\) 中不合法方案。
容斥回来,共有 \(V^{2(p-q)}-V^{p-q-1}(V-1)\) 种合法方案。
排序后直接计数即可,注意第一个和最后一个一元限制。
附上赛时代码。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=100007,p=1e9+7;
ll n,m,v;
pair<ll,ll> a[maxn];
ll qpow(ll a,ll b){ll E=1; for(;b;b>>=1,a=a*a%p)if(b&1) E=E*a%p; return E;}
ll solve(void){
for(int i=1;i<m;i++){
if(a[i].first==a[i+1].first&&a[i].second!=a[i+1].second) return 0;
}
m=unique(a+1,a+1+m)-a-1;
ll res=qpow(v,2*(a[1].first-1))*qpow(v,2*(n-a[m].first))%p;
for(int i=1;i<m;i++) res=res*(qpow(v,2*(a[i+1].first-a[i].first))-(qpow(v,a[i+1].first-a[i].first-1)*(v-1)%p+p)%p+p)%p;
return res;
}
int main(void){
//freopen("assign.in","r",stdin);
//freopen("assign.out","w",stdout);
ll T=1; cin>>T;
for(;T--;){
cin>>n>>m>>v;
for(int i=1;i<=m;i++) cin>>a[i].first>>a[i].second;
sort(a+1,a+1+m);
cout<<solve()<<"\n";
}
return 0;
}
T3
\(k=1\) 时,考虑走到原树上一个点的出边,则这个点的其他出边可以任意安排顺序,总方案数为 \(\prod{(d_i-1)!}\)。
\(k>1\) 时,容斥不好做,于是观察一个新树能被原树上的哪些边走出来。
对于新树上某个原树上点的出边,必然有 \([1,2]\) 条边和另一条原树上不是这个点出边的边相连。只有这 \([1,2]\) 条边才能作为可行的起点。
把每个点的这些边连起来,发现形成了一条原树上叶子到叶子的链,我们将这个链称之为这颗新树的关键链。
对于一条链,能够生成的以这条链为关键链的新树数量为 \(\prod(d_i-1)!\times\prod_{x\in S}(d_x-1)^{-1}\),其中 \(S\) 为这条链的点集。
总方案就是 \(\prod(d_i-1)!\times\sum_{S\text{ is valid}}{\prod_{x\in S}(d_x-1)^{-1}}\),只需要计数合法 \(S\) 的权值之和即可。
可以通过树形 dp 解决。设 \(f_{u,0/1}\),表示考虑 \(u\) 的子树,没有/有关键边的 \(u\) 到叶子的链的 \(\prod(d_x-1)\) 之和,转移是简单的。
#include<bits/stdc++.h>
#define pb emplace_back
#define pob pop_back
#define mp make_pair
using namespace std;
typedef unsigned long long ll;
typedef double db;
const ll maxn=100007,ee=1e18,p=1e9+7;
struct Edge{ll to,id,nxt;}edge[maxn<<1];
ll n,k,ans,frac[maxn],inv[maxn],deg[maxn],f[maxn][2],fs[maxn],head[maxn],ent,vis[maxn];
void addedge(ll u,ll v,ll id){edge[++ent]=Edge{v,id,head[u]},head[u]=ent;}
void ups(ll &a,ll b){a=(a+b>=p?a+b-p:a+b);}
ll qpow(ll a,ll b){ll E=1; for(;b;b>>=1,a=a*a%p)if(b&1) E=E*a%p; return E;}
void init(void){
frac[0]=1;
for(int i=1;i<maxn;i++) frac[i]=frac[i-1]*i%p;
inv[maxn-1]=qpow(frac[maxn-1],p-2);
for(int i=maxn-1;i>=1;i--) inv[i-1]=inv[i]*i%p;
for(int i=maxn-1;i>=1;i--) inv[i]=inv[i]*frac[i-1]%p; inv[0]=1;
}
void dfs(ll u,ll fa){
if(deg[u]<=1) f[u][0]++;
ll s=0;
for(ll i=head[u],v,id;i;i=edge[i].nxt){
v=edge[i].to,id=edge[i].id;
if(v==fa) continue;
dfs(v,u);
if(vis[id]) ups(f[v][1],f[v][0]),f[v][0]=0;
ups(s,f[u][1]*f[v][0]%p),ups(s,(f[u][0]+f[u][1])*f[v][1]%p);
ups(f[u][1],f[v][1]),ups(f[u][0],f[v][0]);
}
ups(ans,s*inv[deg[u]-1]%p);
f[u][0]=f[u][0]*inv[deg[u]-1]%p;
f[u][1]=f[u][1]*inv[deg[u]-1]%p;
}
ll solve(void){
for(int i=1;i<=n;i++) deg[i]=head[i]=vis[i]=f[i][0]=f[i][1]=0; ent=0; ans=0;
cin>>n>>k;
for(int i=1,u,v;i<n;i++) cin>>u>>v,deg[u]++,deg[v]++,addedge(u,v,i),addedge(v,u,i);
for(int i=1,x;i<=k;i++) cin>>x,vis[x]=1;
if(n==2) return 1;
ll rt=0;
for(int i=1;i<=n;i++)if(deg[i]>1){rt=i; break;}
dfs(rt,0);
for(int i=1;i<=n;i++) ans=ans*frac[deg[i]-1]%p;
return ans;
}
int main(void){
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
ll id,T; cin>>id>>T; init();
for(;T--;) cout<<solve()<<"\n";
return 0;
}
T4
观察 \(\text{LCA}^{*}(l,r)\to\text{LCA}^*(l,r+1)\),只需要看 \(\text{LCA}^*(l,r)\) 与 \(\text{LCA}^*(r,r+1)\) 哪个深度更小即可。
推而广之,得到 \(\text{dep}_{\text{LCA}^*(l,r)}=\min_{i=l}^{r-1}\text{dep}_{\text{LCA}^*(i,i+1)}\)。
用单调栈求出 \(\text{dep}_{\text{LCA}^*(i,i+1)}\) 能够取为最小值的最大左端点和右端点 \([L_i,R_i]\)。若这个区间与查询区间的交的大小大于等于 \(k\),则其一定能贡献一个小于等于 \(\text{dep}_{\text{LCA}^*(i,i+1)}\) 的值。
对于询问 \([l,r,k]\) 能够覆盖 \([l,l+k-1],[l+1,l+k],\ldots,[r-k+1,r]\) 中的任意一个区间的 \([L_i,R_i]\),其 \(\text{dep}_{\text{LCA}^*(i,i+1)}\) 能够被贡献。
转化为二维偏序问题,变成求在线段 \((l,l+k-1)\to(r-k+1,r)\) 上方或左方的点的权值最大值。分成查询 \((l,l+k-1),(r-k+1,r)\) 两个点左上方点权最大值,以及坐标系顺时针旋转 \(45\) 度时的一个矩形内点权最大值即可。
#include<bits/stdc++.h>
#define pb emplace_back
#define pob pop_back
#define mp make_pair
using namespace std;
typedef unsigned long long ll;
typedef double db;
const ll maxn=500007,ee=1e18;
struct Qry{ll l,r,id;};
ll n,q,dep[maxn],fs[maxn],top[maxn],son[maxn],siz[maxn],val[maxn],L[maxn],R[maxn];
ll ql[maxn],qr[maxn],qk[maxn],ans[maxn];
vector<ll> edge[maxn],st;
vector<Qry> Q[maxn];
vector<pair<ll,ll> > P[maxn];
void ups(ll &a,ll b){a=(a<b?b:a);}
struct Tree{
ll val[maxn<<3];
void init(void){memset(val,0,sizeof(val));}
void upd(ll l,ll r,ll x,ll z,ll rt){
ups(val[rt],z);
if(l==r) return; ll mid=(l+r)>>1;
if(x<=mid) upd(l,mid,x,z,rt<<1); else upd(mid+1,r,x,z,rt<<1|1);
}
ll qry(ll l,ll r,ll x,ll y,ll rt){
if(l>r||r<x||y<l) return 0;
if(x<=l&&r<=y) return val[rt]; ll mid=(l+r)>>1;
return max(qry(l,mid,x,y,rt<<1),qry(mid+1,r,x,y,rt<<1|1));
}
}tree;
void pre1(ll u,ll fa){
dep[u]=dep[fa]+1,fs[u]=fa,siz[u]=1;
for(auto v:edge[u]){
if(v==fa) continue;
pre1(v,u),siz[u]+=siz[v];
if(siz[son[u]]<siz[v]) son[u]=v;
}
}
void pre2(ll u,ll tp){
top[u]=tp;
if(son[u]) pre2(son[u],tp);
for(auto v:edge[u]){
if(v==fs[u]||v==son[u]) continue;
pre2(v,v);
}
}
ll LCA(ll x,ll y){
for(;top[x]!=top[y];){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fs[top[x]];
}
return (dep[x]>dep[y]?y:x);
}
int main(void){
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for(int i=1,u,v;i<n;i++) cin>>u>>v,edge[u].pb(v),edge[v].pb(u);
pre1(1,0),pre2(1,1);
for(int i=1;i<n;i++) val[i]=dep[LCA(i,i+1)],L[i]=1,R[i]=n;
for(int i=1;i<n;i++){
for(;!st.empty()&&val[st.back()]>=val[i];) R[st.back()]=i,st.pob();
st.pb(i);
}
st.clear();
for(int i=n-1;i>=1;i--){
for(;!st.empty()&&val[st.back()]>val[i];) L[st.back()]=i+1,st.pob();
st.pb(i);
}
cin>>q;
for(ll i=1;i<=q;i++){
cin>>ql[i]>>qr[i]>>qk[i];
Q[ql[i]].pb(Qry{ql[i]+qk[i]-1,n,i});
Q[qr[i]-qk[i]+1].pb(Qry{qr[i],n,i});
}
for(ll i=1;i<n;i++) P[L[i]].pb(R[i],val[i]);
for(int i=1;i<=n;i++){
for(auto x:P[i]) tree.upd(1,n,x.first,x.second,1);
for(auto x:Q[i]) ups(ans[x.id],tree.qry(1,n,x.l,x.r,1));
}
tree.init();
for(int i=1;i<=n;i++) Q[i].clear(),P[i].clear();
for(ll i=1;i<=q;i++) Q[qk[i]-1].pb(Qry{ql[i]*2+qk[i]-1,qr[i]*2-qk[i]+1,i});
for(int i=1;i<n;i++) P[R[i]-L[i]].pb(L[i]+R[i],val[i]);
for(int i=1;i<=n;i++) P[0].pb(2*i,dep[i]);
for(int i=n;i>=0;i--){
for(auto x:P[i]) tree.upd(1,2*n,x.first,x.second,1);
for(auto x:Q[i]) ups(ans[x.id],tree.qry(1,2*n,x.l,x.r,1));
}
for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
return 0;
}
标签:int,text,ll,st,maxn,LCA,NOIP2024
From: https://www.cnblogs.com/aeiouaoeiu/p/18606639