「ZJOI2016」解题报告
我大浙的省选题真是超级神仙……这套已经算是比较可做的了。
「ZJOI2016」旅行者
神仙分治题。
对于一个矩形，每次我们从最长边切开，最短边不会超过 \(\sqrt{n\times m}\)，所以对于每个点跑一遍最短路就行了。
时间复杂度 \(O(n\sqrt{n}\log n+q\sqrt{n})\)
\(Code\ Below:\)
#include <bits/stdc++.h>
#define id(i,j) (((i)-1)*m+(j))
using namespace std;
const int maxn=20000+10;
const int maxm=100000+10;
const int inf=0x3f3f3f3f;
int n,m,Q,val[maxn][4],dis[maxn],vis[maxn],ans[maxm];
int nx[4]={0,1,0,-1},ny[4]={1,0,-1,0};
struct node{
int x,y,dis;
node(int x=0,int y=0,int dis=0):x(x),y(y),dis(dis){}
};
inline bool operator < (const node &a,const node &b){
return a.dis>b.dis;
}
struct Query{
int x1,x2,y1,y2,id;
}q[maxm],q1[maxm],q2[maxm];
inline int read(){
register int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return (f==1)?x:-x;
}
inline void Dijkstra(int sx,int sy,int lx,int ly,int rx,int ry){
priority_queue<node> pq;
for(int i=lx;i<=rx;i++)
for(int j=ly;j<=ry;j++) dis[id(i,j)]=inf,vis[id(i,j)]=0;
dis[id(sx,sy)]=0;pq.push(node(sx,sy,0));
node u;int x,y;
while(!pq.empty()){
u=pq.top();pq.pop();
if(vis[id(u.x,u.y)]) continue;
vis[id(u.x,u.y)]=1;
for(int i=0;i<4;i++){
x=u.x+nx[i];y=u.y+ny[i];
if(x<lx||x>rx||y<ly||y>ry) continue;
if(dis[id(x,y)]>dis[id(u.x,u.y)]+val[id(u.x,u.y)][i]){
dis[id(x,y)]=dis[id(u.x,u.y)]+val[id(u.x,u.y)][i];
pq.push(node(x,y,dis[id(x,y)]));
}
}
}
}
void solve(int lx,int ly,int rx,int ry,int ql,int qr){
if(ql>qr) return ;
if(lx==rx&&ly==ry){
for(int i=ql;i<=qr;i++) ans[q[i].id]=0;
return ;
}
if(rx-lx>ry-ly){
int mid=(lx+rx)>>1,cnt1=0,cnt2=0;
for(int i=ly;i<=ry;i++){
Dijkstra(mid,i,lx,ly,rx,ry);
for(int j=ql;j<=qr;j++) ans[q[j].id]=min(ans[q[j].id],dis[id(q[j].x1,q[j].y1)]+dis[id(q[j].x2,q[j].y2)]);
}
for(int i=ql;i<=qr;i++){
if(q[i].x1<=mid&&q[i].x2<=mid) q1[++cnt1]=q[i];
if(q[i].x1>mid&&q[i].x2>mid) q2[++cnt2]=q[i];
}
for(int i=1;i<=cnt1;i++) q[ql+i-1]=q1[i];
for(int i=1;i<=cnt2;i++) q[ql+cnt1+i-1]=q2[i];
solve(lx,ly,mid,ry,ql,ql+cnt1-1);
solve(mid+1,ly,rx,ry,ql+cnt1,ql+cnt1+cnt2-1);
}
else {
int mid=(ly+ry)>>1,cnt1=0,cnt2=0;
for(int i=lx;i<=rx;i++){
Dijkstra(i,mid,lx,ly,rx,ry);
for(int j=ql;j<=qr;j++) ans[q[j].id]=min(ans[q[j].id],dis[id(q[j].x1,q[j].y1)]+dis[id(q[j].x2,q[j].y2)]);
}
for(int i=ql;i<=qr;i++){
if(q[i].y1<=mid&&q[i].y2<=mid) q1[++cnt1]=q[i];
if(q[i].y1>mid&&q[i].y2>mid) q2[++cnt2]=q[i];
}
for(int i=1;i<=cnt1;i++) q[ql+i-1]=q1[i];
for(int i=1;i<=cnt2;i++) q[ql+cnt1+i-1]=q2[i];
solve(lx,ly,rx,mid,ql,ql+cnt1-1);
solve(lx,mid+1,rx,ry,ql+cnt1,ql+cnt1+cnt2-1);
}
}
int main()
{
memset(val,inf,sizeof(val));
memset(ans,inf,sizeof(ans));
n=read(),m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<m;j++) val[id(i,j)][0]=val[id(i,j+1)][2]=read();
for(int i=1;i<n;i++)
for(int j=1;j<=m;j++) val[id(i,j)][1]=val[id(i+1,j)][3]=read();
Q=read();
for(int i=1;i<=Q;i++) q[i].x1=read(),q[i].y1=read(),q[i].x2=read(),q[i].y2=read(),q[i].id=i;
solve(1,1,n,m,1,Q);
for(int i=1;i<=Q;i++) printf("%d\n",ans[i]);
return 0;
}
「ZJOI2016」小星星
树形 \(dp\) + 容斥原理。
第一次见到对于排列容斥的题，大开眼界。（可能是我太弱）
那么 \(O(n^3)\) 的树形 \(dp\) 还是好打的嘛。
\(Code\ Below:\)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,e[20][20],sta[20],top;
vector<int> G[20];ll dp[20][20],ans;
void treedp(int x,int f){
vector<int>::iterator it;
int y;ll now;
for(it=G[x].begin();it!=G[x].end();it++)
if(*it!=f) treedp(*it,x);
for(int i=1;i<=top;i++){
dp[x][i]=1;
for(it=G[x].begin();it!=G[x].end();it++){
y=*it;
if(y==f) continue;
now=0;
for(int j=1;j<=top;j++)
if(e[sta[i]][sta[j]]) now+=dp[y][j];
dp[x][i]*=now;
}
}
}
inline void solve(){
treedp(1,0);
for(int i=1;i<=top;i++){
if((n-top)&1) ans-=dp[1][i];
else ans+=dp[1][i];
}
}
void dfs(int x){
if(x==n+1){solve();return;}
sta[++top]=x;dfs(x+1);
top--;dfs(x+1);
}
int main()
{
scanf("%d%d",&n,&m);
int x,y;
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
e[x][y]=e[y][x]=1;
}
for(int i=1;i<n;i++){
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1);
printf("%lld\n",ans);
return 0;
}
「ZJOI2016」线段树
神仙 \(dp\) 系列。
\(f[x][p][l][r]\) 表示经过 \(p\) 轮操作后 \(\text{max}_{i=l}^{r}{a_i}\leq x<\text{min}(a_{l-1},a_{r+1})\) 的方案数。
那么 \(x\) 可以枚举省掉一维，\(p\) 可以滚动数组，那么实际只有两位。我们先看 \(O(n^4)\) 的解法。
\(f[p][l][r]\) 可以由三项转移：
区间左右端点在 \([1,l-1]\) 或 \([l,r]\) 或 \([r+1,n]\)：\(f[p][l][r]=[{l-1\choose 2}+{r-l+1\choose 2}+{n-r\choose 2}]\times f[p-1][l][r]\)
区间右端点在 \(l-1\)：\(f[p][l][r]=\sum_{i=1}^{l-1}(i-1)\times f[p-1][i][r]\)
区间左端点在 \(r+1\)：\(f[p][l][r]=\sum_{i=r+1}^{n}(n-i)\times f[p-1][l][i]\)
现在看 \(O(n^3)\) 的解法。
不容易发现可以把 \(x\) 一起转移，然后就 \(O(n^3)\) 的解法了。
代码是 \(O(n^4)\) 的。
\(Code\ Below:\)
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=400+10;
const int mod=1e9+7;
int n,m,a[maxn],mp[maxn],cnt[maxn],C[maxn][maxn],sum[maxn][maxn],f[2][maxn][maxn],g[maxn][maxn];
bool is[maxn][maxn];
/*
cnt[i] = i * (i + 1) / 2
f(i, l, r) += f(i - 1, l, r) * (cnt[r - l + 1] + cnt[n - r] + cnt[l - 1]);
f(i, l, r) += \sum _ {u = 1} ^ {l - 1} f(i - 1, u, r) * (u - 1)
f(i, l, r) += \sum _ {v = r + 1} ^ {n} f(i - 1, l, v) * (n - v)
*/
inline void solve(int x,int L,int R){
memset(f[0],0,sizeof(f[0]));
for(int i=L;i<=R;i++) is[i][a[x]]=1;
f[0][L][R]=1;
int now,lst,val;
for(int i=1;i<=m;i++){
now=i&1;lst=i&1^1;
for(int l=L;l<=R;l++)
for(int r=l;r<=R;r++) f[now][l][r]=f[lst][l][r]*C[l][r]%mod;
for(int r=L;r<=R;r++){
val=0;
for(int l=L;l<=r;l++){
(f[now][l][r]+=val)>=mod?f[now][l][r]-=mod:0;
val=(val+f[lst][l][r]*(l-1))%mod;
}
}
for(int l=L;l<=R;l++){
val=0;
for(int r=R;r>=l;r--){
(f[now][l][r]+=val)>=mod?f[now][l][r]-=mod:0;
val=(val+f[lst][l][r]*(n-r))%mod;
}
}
}
//[L, i] [i, R]
for(int i=L-1;i<=R;i++)
for(int j=L-1;j<=R;j++) sum[i][j]=0;
for(int i=L;i<=R;i++)
for(int j=L;j<=R;j++) sum[i][j]=(sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+f[m&1][i][j])%mod;
for(int i=L;i<=R;i++) g[i][a[x]]=((g[i][a[x]]+sum[i][R]-sum[L-1][R]-sum[i][i-1]+sum[L-1][i-1])%mod+mod)%mod;
}
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]),mp[i]=a[i];
sort(mp+1,mp+n+1);
for(int i=1;i<=n;i++) a[i]=lower_bound(mp+1,mp+n+1,a[i])-mp;
for(int i=1;i<=n;i++) cnt[i]=1ll*i*(i+1)/2%mod;
for(int l=1;l<=n;l++)
for(int r=l;r<=n;r++) C[l][r]=(cnt[l-1]+cnt[n-r]+cnt[r-l+1])%mod;
int L,R;
for(int i=1;i<=n;i++){
L=i;R=i;
while(L>1&&a[L-1]<a[i]) L--;
while(R<n&&a[i]>=a[R+1]) R++;
solve(i,L,R);
}
int tmp,val,ans;
for(int i=1;i<=n;i++){
val=0;
for(int j=1;j<=n;j++){
if(!is[i][j]) continue;
tmp=g[i][j];g[i][j]-=val;
if(g[i][j]<0) g[i][j]+=mod;
val=tmp;
}
}
for(int i=1;i<=n;i++){
ans=0;
for(int j=1;j<=n;j++) ans=(ans+g[i][j]*mp[j])%mod;
printf("%lld ",ans);
}
printf("\n");
return 0;
}