【UOJ502】汉堡肉
思考过程很有趣，写起来很吐。
先观察最左边的点，将这个点不断往右平移，直到碰到某个右边界所在的直线，平移后一定合法。同时这个点一定不会在某个右边界的右边，否则这个右边界对应的矩形导致答案不合法。即，一定存在一个方案，使得最左边的右边界，最右边的左边界，最上边的下边界，最下边的上边界所在直线上都有一个点。
对于 \(K \le 3\) 的情况，一定会把某个点放到这些边界的直线的某个交点上，枚举 \(4\) 种情况，删去已经合法的矩形，往下搜索得到新一轮的四个边界。一共 \(4^K\) 种情况，每种情况可以线性判，复杂度 \(O(4^KN)\)。
对于 \(K = 4\) 的情况，可能在每个边界上都放一个点。如果某个矩形只包含一条边界，直接在这条边界上缩小范围；如果包含两条边界，选其中之一缩小范围；包含三条或以上边界，由于一定完整包含其中一条，可以忽略它。
此时 2-SAT 的模型就出来了，对于每个包含两条边界的矩形拆成两个布尔变量 \(x_1,x_2\) 表示第一条边界是否选，第二条边界是否选。限制有三种：每个矩形内部有限制，两个恰好选一个；对于骑在同一条边界上且没有交集的矩形，不可以同时选这一条边界；处理只包含一条边界的矩形后，如果某个有两条边界的矩形和其中某条边界的合法范围没有交，则钦定某个变量为假。
第二种连边排序后前后缀优化建图，第一三种是简单的，复杂度是 \(O(4^KN+N \log N)\)，因为要排序。
Code
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
const int N=1600005,Del=400005;
int n,K;
array<int,4> rec[N];
bool in(pii p,array<int,4> r)
{
return r[0]<=p.fi&&p.fi<=r[1]&&r[2]<=p.se&&p.se<=r[3];
}
struct BF
{
bool vis[N];
vector <pii > nw;
void dfs(int cnt)
{
int L=inf,R=-1,D=inf,U=-1;
for(int i=1;i<=n;i++) if(!vis[i])
L=min(L,rec[i][1]),R=max(R,rec[i][0]),D=min(D,rec[i][3]),U=max(U,rec[i][2]);
if(L==inf)
{
for(int i=0;i<nw.size();i++) cout<<nw[i].fi<<" "<<nw[i].se<<endl;
for(int i=0;i<K-nw.size();i++) puts("1 1");
exit(0);
}
if(cnt==K+1) return;
vector <pii > p;
p.clear();
p.pb(mp(L,D)),p.pb(mp(L,U)),p.pb(mp(R,D)),p.pb(mp(R,U));
for(int i=0;i<p.size();i++)
{
vector <int> add;
add.clear();
for(int j=1;j<=n;j++) if(!vis[j]&&in(p[i],rec[j])) add.pb(j),vis[j]=1;
nw.pb(p[i]);
dfs(cnt+1);
for(int j=0;j<add.size();j++) vis[add[j]]=0;
nw.pop_back();
}
}
}bf;
struct SAT2
{
int L=inf,R=-1,D=inf,U=-1;
vector <array<int,3> > vec[4];
vector <int> g[N];
void add(int x,int y)
{
g[x].pb(y);
}
int times,dfn[N],low[N],scccnt,scc[N],instk[N],stk[N],top,uidx,id[N],idr[N];
int ok[N];
pii lim[4];
void tarjan(int u)
{
dfn[u]=low[u]=++times;
stk[++top]=u,instk[u]=1;
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
else if(instk[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
scccnt++;
do
{
scc[stk[top]]=scccnt;
instk[stk[top]]=0;
}while(stk[top--]!=u);
}
}
void work()
{
for(int i=1;i<=n;i++) L=min(L,rec[i][1]),R=max(R,rec[i][0]),D=min(D,rec[i][3]),U=max(U,rec[i][2]);
for(int i=0;i<4;i++) lim[i]=mp(1,1000000000);
for(int i=1;i<=n;i++)
{
vector <array<int,3> > good;
good.clear();
if(rec[i][0]<=L&&L<=rec[i][1]) good.pb({0,rec[i][2],rec[i][3]});
if(rec[i][0]<=R&&R<=rec[i][1]) good.pb({1,rec[i][2],rec[i][3]});
if(rec[i][2]<=D&&D<=rec[i][3]) good.pb({2,rec[i][0],rec[i][1]});
if(rec[i][2]<=U&&U<=rec[i][3]) good.pb({3,rec[i][0],rec[i][1]});
ok[i]=1;
if(good.size()==1) lim[good[0][0]].fi=max(lim[good[0][0]].fi,good[0][1]),lim[good[0][0]].se=min(lim[good[0][0]].se,good[0][2]);
else if(good.size()==2)
{
vec[good[0][0]].pb({good[0][1],good[0][2],++uidx});
vec[good[1][0]].pb({good[1][1],good[1][2],++uidx});
add(uidx-1,uidx+Del),add(uidx,uidx-1+Del);
idr[uidx]=idr[uidx-1]=i;
add(uidx+Del,uidx-1),add(uidx-1+Del,uidx);
ok[i]=0;
}
}
uidx+=Del;
for(int d=0;d<4;d++) if(vec[d].size())
{
for(int i=0;i<vec[d].size();i++) if(max(vec[d][i][0],lim[d].fi)>min(vec[d][i][1],lim[d].se)) add(vec[d][i][2],vec[d][i][2]+Del);
vector <pii > tmp;
tmp.clear();
for(int i=0;i<vec[d].size();i++) tmp.pb(mp(vec[d][i][1],vec[d][i][2]));//,cout<<vec[d][i][0]<<" "<<vec[d][i][1]<<" "<<vec[d][i][2]<<endl;
sort(tmp.begin(),tmp.end());
int lst=-1;
for(int i=0;i<tmp.size();i++)
{
id[i]=++uidx;
if(lst!=-1) add(uidx,lst);
add(uidx,tmp[i].se+Del);
lst=id[i];
}
for(int i=0;i<vec[d].size();i++)
{
int bd=vec[d][i][0],u=vec[d][i][2];
int p=lower_bound(tmp.begin(),tmp.end(),mp(bd,-1))-tmp.begin()-1;
if(p>=0) add(u,id[p]);
}
tmp.clear();
for(int i=0;i<vec[d].size();i++) tmp.pb(mp(vec[d][i][0],vec[d][i][2]));
sort(tmp.begin(),tmp.end());
lst=-1;
for(int i=tmp.size()-1;i>=0;i--)
{
id[i]=++uidx;
if(lst!=-1) add(uidx,lst);
add(uidx,tmp[i].se+Del);
lst=id[i];
}
for(int i=0;i<vec[d].size();i++)
{
int bd=vec[d][i][1],u=vec[d][i][2];
int p=lower_bound(tmp.begin(),tmp.end(),mp(bd+1,-1))-tmp.begin();
if(p<tmp.size()) add(u,id[p]);
}
}
for(int i=1;i<=uidx;i++) if(!dfn[i]) top=0,tarjan(i);
for(int i=0;i<4;i++) for(int j=0;j<vec[i].size();j++)
{
int u=vec[i][j][2];
if(scc[u]<scc[u+Del]) ok[idr[u]]=1,lim[i].fi=max(lim[i].fi,vec[i][j][0]),lim[i].se=min(lim[i].se,vec[i][j][1]);
}
cout<<L<<" "<<lim[0].fi<<endl;
cout<<R<<" "<<lim[1].fi<<endl;
cout<<lim[2].fi<<" "<<D<<endl;
cout<<lim[3].fi<<" "<<U<<endl;
}
}sat2;
void solve()
{
scanf("%d%d",&n,&K);
for(int i=1;i<=n;i++) scanf("%d%d%d%d",&rec[i][0],&rec[i][2],&rec[i][1],&rec[i][3]);
bf.dfs(1);
sat2.work();
}
signed main()
{
int _=1;
// cin>>_;
while(_--) solve();
return 0;
}
【UOJ506】遗迹
先拆解地震的过程，从后往前做，不断将一个数减少，直到后面没出现过它，如果减到非正数就消失，否则保留。
\(dp(i,j)\) 表示，考虑确定后 \(i\) 个数的高度，\(j\) 是最大的满足 \([1,j]\) 都出现过的数的方案数。为了方便转移，令相同高度柱子是可区分的，算出来后除以 \(2^n\)。
令 \(x\) 为后 \(i-1\) 个数中要求消失的数，\(y\) 为要求出现的数，转移分讨一下：
- \(i\) 要求消失，此时一共有 \(j-x\) 个可选的数，将 \((j-x)dp(i-1,j)\) 转移到 \(dp(i,j)\)。
- \(i\) 要求出现，我们只在 \(A_i=j+1\) 的时候做转移，枚举 \(j\) 的增量 \(k\)，考虑将 \(dp(i-1,j-k)\) 转移到 \(dp(i,j)\)，这个位置有 \(k-1\) 种取值，中间那一段选的数有 \(\binom{y-j+k}{k-1}\) 种方案，还要乘上一个系数 \(g(x)\)，表示经过若干次地震，震成连续的一段的排列方式。
对于 \(g\) 的计算可以设 \(dp2(i,j)\) 表示用 \(i\) 个高度占据了 \(j\) 个位置的方案数，转移是简单的，每种高度最多用两次，显然 \(g(x)=dp2(x,x)\)，复杂度 \(O(n^3)\)。
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<long long,long long>
#define mp make_pair
#define pb push_back
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
const int INF=1e18;
int fpow(int x,int b){
if(x==0) return 0;
if(b==0) return 1;
int res=1;
while(b>0){
if(b&1) res=res*x%mod;
x=x*x%mod;
b>>=1;
}
return res;
}
int fac[300005],ifac[300005];
int C(int x,int y)
{
if(y>x) return 0;
if(x==y||y==0) return 1;
return fac[x]*ifac[x-y]%mod*ifac[y]%mod;
}
int n;
bool bad[1205];
int dp[1205][605],g[605][605];
void solve()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
int x;
scanf("%lld",&x);
bad[2*n-x+1]=1;
}
g[0][0]=1;
for(int i=1;i<=n;i++) for(int j=0;j<=i;j++)
g[i][j]=(g[i][j]+g[i-1][j]+(j>=1?g[i-1][j-1]*2LL*j%mod:0LL)+(j>=2?2LL*g[i-1][j-2]*C(j,2)%mod:0LL))%mod;
/* for(int i=1;i<=n;i++)
{
for(int j=0;j<=i;j++) cout<<g[i][j]<<" ";
puts("");
}
puts("");*/
dp[0][0]=1;
int dis=0,app=0;
for(int i=1;i<=2*n;i++)
{
if(!bad[i])
{
for(int j=0;j<=app;j++) dp[i][j]=dp[i-1][j]*max(0LL,j-dis)%mod;
dis++;
}
else
{
for(int j=0;j<=app+1;j++)
{
dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;
for(int k=1;k<=j;k++) dp[i][j]=(dp[i][j]+dp[i-1][j-k]*C(app-j+k,k-1)%mod*(k+1)%mod*g[k-1][k-1]%mod)%mod;
}
app++;
}
// for(int j=0;j<=app;j++) cout<<dp[i][j]<<" ";
// puts("");
}
printf("%lld\n",dp[2*n][n]*fpow(fpow(2,n),mod-2)%mod);
}
signed main()
{
fac[0]=fac[1]=1;
for(int i=2;i<=1000;i++) fac[i]=fac[i-1]*i%mod;
for(int i=0;i<=1000;i++) ifac[i]=fpow(fac[i],mod-2);
int _=1;
// cin>>_;
while(_--) solve();
return 0;
}
【UOJ618】聚会 2
先观察确定参会者之后，开会地址长什么样，容易发现是一条链，链的两端有相等数量的参会者。奇数的答案一定是 \(1\)，为了方便，下文中将所有偶数答案的下标除以 \(2\)。
考虑枚举这一条链，令一端所挂的子树有 \(x\) 个节点，另一端有 \(y\) 个，则会将链长贡献到所有 \(\le \min\{x,y\}\) 的答案。
点分治，在当前分治中心的每一个子树中，对于每个 \(size\) 求出有着子树大小 \(\ge size\) 的最大点的深度，可以搞出来总共 \(n\) 个区间（\(n\) 是目前分治到的树大小），将这些区间挂到线段树上，每个节点维护最大深度和次大深度，然后 dfs 一遍线段树更新答案，这个答案可以用类似差分的思想维护，复杂度 \(O(n \log^2 n)\)。
Code
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
int ans[200005];
struct Segtree
{
pii t[800005];
void upd(pii &tmp,int x)
{
if(x>tmp.fi) tmp.se=tmp.fi,tmp.fi=x;
else if(x>tmp.se) tmp.se=x;
}
void init(int id,int l,int r)
{
t[id]=mp(-inf,-inf);
if(l==r) return;
int mid=(l+r)>>1;
init(id<<1,l,mid),init(id<<1|1,mid+1,r);
}
void update(int id,int l,int r,int x,int y,int d)
{
if(x<=l&&r<=y)
{
upd(t[id],d);
return;
}
int mid=(l+r)>>1;
if(x<=mid) update(id<<1,l,mid,x,y,d);
if(y>mid) update(id<<1|1,mid+1,r,x,y,d);
}
void getans(int id,int l,int r,pii nw)
{
upd(nw,t[id].fi),upd(nw,t[id].se);
if(l==r)
{
ans[l]=max(ans[l],nw.fi+nw.se+1);
return;
}
int mid=(l+r)>>1;
getans(id<<1,l,mid,nw),getans(id<<1|1,mid+1,r,nw);
}
}st;
vector <int> g[200005];
int n;
int dep[200005],sz[200005],maxsz[200005],vis[200005],rt,tot;
void dfs0(int u,int fa)
{
sz[u]=1,maxsz[u]=0;
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(v==fa||vis[v]) continue;
dep[v]=dep[u]+1;
dfs0(v,u),sz[u]+=sz[v],maxsz[u]=max(maxsz[u],sz[v]);
}
maxsz[u]=max(maxsz[u],tot-sz[u]);
if(maxsz[u]<maxsz[rt]) rt=u;
}
vector <pii > vec[200005];
void dfs1(int u,int fa,int id)
{
sz[u]=1;
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(v==fa||vis[v]) continue;
dep[v]=dep[u]+1;
dfs1(v,u,id),sz[u]+=sz[v];
}
vec[id].pb(mp(sz[u],dep[u]));
if(dep[u]>1) ans[min(sz[u],n-sz[u]-dep[u]+2)]=max(ans[min(sz[u],n-sz[u]-dep[u]+2)],dep[u]+1);
}
void calc(int u)
{
vis[u]=1;
vector <int> ss;
ss.clear();
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(vis[v]) continue;
ss.pb(v),dep[v]=1,vec[ss.size()-1].clear(),dfs1(v,-1,ss.size()-1);
}
st.init(1,1,tot);
// cout<<u<<endl;
for(int i=0;i<ss.size();i++)
{
sort(vec[i].begin(),vec[i].end());
for(int j=(int)vec[i].size()-2;j>=0;j--) vec[i][j].se=max(vec[i][j].se,vec[i][j+1].se);
int lst=0;
for(int j=0;j<vec[i].size();j++)
{
int l=j;
while(l<vec[i].size()&&vec[i][l].fi==vec[i][j].fi) l++;
l--;
// cout<<lst+1<<" "<<vec[i][l].fi<<" "<<vec[i][l].se<<endl;
st.update(1,1,tot,lst+1,vec[i][l].fi,vec[i][l].se);
j=l,lst=vec[i][l].fi;
}
// system("pause");
}
// system("pause");
st.getans(1,1,tot,mp(-inf,-inf));
for(int i=0;i<ss.size();i++)
{
int v=ss[i];
tot=sz[v],rt=0;
dfs0(v,-1);
calc(rt);
}
}
void solve()
{
memset(ans,-1,sizeof(ans));
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
g[u].pb(v),g[v].pb(u);
}
maxsz[0]=n,rt=0,tot=n;
dfs0(1,-1);
for(int i=2;i<=n;i++) ans[min(sz[i],n-sz[i])]=max(ans[min(sz[i],n-sz[i])],2);
calc(rt);
for(int i=n;i>=1;i--) ans[i]=max(ans[i],ans[i+1]);
for(int i=1;i<=n;i++)
{
if(i%2==1) puts("1");
else printf("%d\n",max(1,ans[i/2]));
}
}
signed main()
{
int _=1;
// cin>>_;
while(_--) solve();
return 0;
}