T1

Description

Solution

• 有待填坑……

T2

Description

• 给定一个\(h(≤10)\)层、\(n(≤10)\)行、\(m(≤10)\)列的由泥土组成的立方体，挖开\((i,j,k)\)的泥土代价为\(a[i,j,k](\in[0,65536))\)，挖开后就可以随意走这个点。一开始在第0层随便一个点，每次可以挖开他正下方、以及他同一层的四连通相邻点。
• 第\(z\)层有\(K[z](≤9)\)个点必须经过。

• 求最小代价。

  Solution

• 分层斯坦纳树。但此题有些特殊，它是有向边，如果直接做则斯坦纳树的第一种转移（即状态不同的转移）应该是要枚举一条边的；因此我们可以不连边，而是走到一个点就加上它的点权。
• 注意到还要考虑其他层的影响；因此我们可以自上而下（自下而上也是一样）地做，每层都新建一个特殊必经点，表示它当前层上面所有层的总和，然后要根据它第一次走到的点来定夺附加点权。

• 这样做的话，时间复杂度就是\(O(nm\sum_{z=1}^h2^{K[z]})\)的了。

  Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MIN(x,y) if(x>y)x=y
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

const int H=11,N=H*H,inf=0x3f3f3f3f;
int h,n,m,n1,a[H][N],K,x,y,X[H],f[1024][N],g[N],hd,tl,d[N*N],ans;
bool p[N];

bool go(int x,int y) {return x%m^1&&y==x-1||x%m&&y==x+1||y==x-m||y==x+m;}

void spfa(int dep,int S)
{
    while(hd<tl)
    {
        int x=d[++hd];
        fo(y,1,n1)
            if(!x||go(x,y))
            {
                int len=a[dep][y]+(!x&&dep>1?g[y]:0);
                if(f[S][y]>f[S][x]+len)
                {
                    f[S][y]=f[S][x]+len;
                    if(!p[y])
                    {
                        p[d[++tl]=y]=1;
                        if(f[S][d[h+1]]>f[S][y]) swap(d[hd+1],d[tl]);
                    }
                }
            }
        p[x]=0;
    }
}

int main()
{
    freopen("treasure.in","r",stdin);
    freopen("treasure.out","w",stdout);
    scanf("%d%d%d",&h,&n,&m), n1=n*m;
    fo(dep,1,h) fo(i,1,n1) scanf("%d",&a[dep][i]);
    fo(dep,1,h)
    {
        memset(f,63,sizeof f);
        scanf("%d",&K);
        fo(i,1,K) scanf("%d%d",&x,&y), X[i]=(x-1)*m+y, f[0][X[i]]=f[1<<i-1][X[i]]=a[dep][X[i]];
        X[++K]=0, f[0][0]=f[1<<K-1][0]=0;
        fo(S,1,(1<<K)-1)
        {
            for(int s=(S-1)&S; 233; s=(s-1)&S)
            {
                fo(x,1,n1) MIN(f[S][x],f[s][x]+f[S^s][x]-a[dep][x]);
                if(!s) break;
            }
            hd=tl=0;
            fo(i,0,n1) if(f[S][i]<inf) p[d[++tl]=i]=1;
            spfa(dep,S);
        }
        fo(i,1,n1) g[i]=f[(1<<K)-1][i];
    }
    ans=inf;
    fo(i,1,n1) MIN(ans,g[i]);
    printf("%d",ans);
}

T3

Description

• 给定无限平面网格图上的\(N(≤100000)\)个黑格，其余格为白。保证所有黑格四连通，所有白格四连通。
• 在一个黑格时，一步可以走到与它四连通相邻的黑格。

• 求所有黑格两两间的最小步数。

  Solution

• 这是IOI2012T4，顾昱洲写的TJ里有一种DP解法，但那种方法有些繁琐；这里讲一种撵爆顾昱洲更为简单的方法。
• 考虑将黑格按横坐标剖分，即把一块横坐标相同且相邻的黑格压成一个点；如果有两块横坐标不同但相邻的黑格，就在它们对应的新点之间连边。这样一定会形成一棵树，我们可以直接在上面搞事情。
• 但如果直接遍历这棵重构树求答案，我们并不知道对于之前的黑格，它走下来需要左右移动多少次（即纵坐标更改多少次），强行记录的话又过于繁琐。有一个很妙的思路是：我们可以把横坐标和纵坐标对答案的贡献分开处理。比如处理横坐标对答案的贡献时，就不管它左右移动，每次只上下移动，那就很好做了。

• 时间复杂度的话，不算排序是\(O(n)\)的。

  Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#define fi first
#define se second
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef pair<int,int> P;

const int N=11e4,v[2]={-1,1};
int n,cnt,L[N],R[N],X[N],tot,a[N],sz[N];
P p[N];
struct edge{int v,t;}e[N<<1];
long long ans;

inline bool con(int x,int y) {return X[x]+1==X[y]&&L[x]<=R[y]&&L[y]<=R[x];}
inline void link(int x,int y)
{
    e[++tot]=(edge){y,a[x]}, a[x]=tot;
    e[++tot]=(edge){x,a[y]}, a[y]=tot;
}
void dfs(int x,int f)
{
    sz[x]=R[x]-L[x]+1;
    for(int i=a[x],y; y=e[i].v; i=e[i].t) if(y^f) dfs(y,x),sz[x]+=sz[y];
    ans+=1ll*sz[x]*(n-sz[x]);
}
void work()
{
    sort(p+1,p+n+1);
    cnt=0;
    fo(i,1,n) if(p[i-1].fi<p[i].fi||p[i-1].se+1<p[i].se) R[cnt]=p[i-1].se, L[++cnt]=p[i].se, X[cnt]=p[i].fi;
    R[cnt]=p[n].se;
    int j=1;
    memset(a,tot=0,sizeof a);
    fo(i,1,cnt)
    {
        if(j>cnt) break;
        for(; j<=cnt&&(X[j]<=X[i]||X[j]==X[i]+1&&!con(i+1,j)&&L[j]<=R[i]); j++) if(con(i,j)) link(i,j);
        if(con(i,j)) link(i,j);
    }
    dfs(1,0);
}

int main()
{
    freopen("city.in","r",stdin);
    freopen("city.out","w",stdout);
    scanf("%d",&n);
    fo(i,1,n) scanf("%d%d",&p[i].fi,&p[i].se);
    
    work();
    
    fo(i,1,n) swap(p[i].fi,p[i].se);
    work();
    
    printf("%lld",ans%int(1e9));
}