ZJOI 2016

ZJOI OI BZOJ 2016

BZOJ-4455 ~ BZOJ-4456

[Zjoi2016]小星星

讲道理这是T3，不知道为什么BZOJ上把T2T3倒着放QAQ
考场上只写了暴力，裸暴力QAQ
容斥&DP
枚举所有点和图中集合为$T$的点对应的情况，然后答案就是和$U$一一对应的情况

#include <bits/stdc++.h>
using namespace std;
int read()
{
    int x=0; bool f=0; char ch;
    for (ch=getchar();ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=1;
    for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; if (f) x=-x;
    return x;
}
typedef long long LL;
const int NN = 20;
int all,bin[NN],p[NN],head[NN],n,m,tot;
bool v[NN][NN];
LL f[NN][NN],ans;
struct E
{
    int ne,v;
}e[NN<<1];
void Build(int xx,int yy)
{
    e[++tot].ne = head[xx], head[xx] = tot, e[tot].v = yy;
    e[++tot].ne = head[yy], head[yy] = tot, e[tot].v = xx;
}
void DFS(int xx,int fa)
{
    LL sum;
    for (int i=head[xx];i;i=e[i].ne)
    if (e[i].v != fa) DFS(e[i].v,xx);
    for (int i=1;i<=all;++i)
    {
        f[xx][i] = 1;
        for (int j=head[xx];j;j=e[j].ne)
        if (e[j].v != fa)
        {
            sum = 0ll;
            for (int k=1;k<=all;++k) if (v[p[i]][p[k]]) sum += f[e[j].v][k];
            f[xx][i] *= sum;
        }
    }
}
int main()
{
    bin[1] = 1; for (int i=2;i<=18;++i) bin[i] = bin[i-1] << 1;
    n = read(), m = read();
    int x,y;
    for (int i=1;i<=m;++i) x = read(), y = read(), v[x][y] = v[y][x] = 1;
    for (int i=1;i<n;++i) x = read(), y = read(), Build(x,y);
    ans = 0ll;
    for (int i=0;i<(1<<n)-1;++i)
    {
        all = 0;
        for (int j=1;j<=n;++j)
            if (!(i&bin[j])) p[++all] = j;
        DFS(1,0);
        LL sum = 0;
        for (int j=1;j<=all;++j) sum += f[1][j];
        if ((n-all)&1) ans -= sum; else ans += sum;
    }
    printf("%lld\n",ans);
    return 0;
}

[Zjoi2016]旅行者

感觉当时想到过一块一块来但完全不知道怎么搞QAQ
分治
有两种情况：
1.如果询问的起点和终点在不同的块，那么一定会经过中轴线上的一点；
2.如果在同一块，那么有可能经过中轴线；也有可能全部在那一块中；
这样就可以递归分治了
听说SPFA会被卡就难得写了次Dijkstra
每天STL用用没希望了，联赛被卡了还用QAQ

#include <bits/stdc++.h>
using namespace std;
int read()
{
    int x=0; bool f=0; char ch;
    for (ch=getchar();ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=1;
    for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; if (f) x=-x;
    return x;
}
const int NN = 20010, MM = 100010, INF = 0x3f3f3f3f;
struct Q
{
    int x,len;
    friend bool operator < (Q xx,Q yy) { return xx.len > yy.len; }
};
priority_queue<Q> que;
int px[NN],py[NN],dis[NN],head[NN],ans[MM],n,m,tot,QQ,w;
bool vis[NN];
struct E
{
    int v,w,ne;
}e[NN<<2];
struct POI
{
    int xa,xb,ya,yb,num;
}p[MM],t[MM];
void Build(int xx,int yy,int zz)
{
    e[++tot].ne = head[xx], head[xx] = tot, e[tot].v = yy, e[tot].w = zz;
    e[++tot].ne = head[yy], head[yy] = tot, e[tot].v = xx, e[tot].w = zz;
}
int P(int xx,int yy) { return (xx-1)*m+yy; }
void DIJ(int xx,int nl,int nr,int ml,int mr)
{
    int t;
    for (int i=nl;i<=nr;++i)
        for (int j=ml;j<=mr;++j) t = P(i,j), dis[t] = INF, vis[t] = 0;
    dis[xx] = 0, que.push((Q){xx,0});
    while (!que.empty())
    {
        int now = que.top().x; que.pop();
        if (vis[now]) continue;
        vis[now] = 1;
        for (int i=head[now];i;i=e[i].ne)
        if (px[e[i].v]>=nl && px[e[i].v]<=nr && py[e[i].v]>=ml && py[e[i].v]<=mr)
        {
            if (dis[e[i].v] > dis[now] + e[i].w) dis[e[i].v] = dis[now] + e[i].w, que.push((Q){e[i].v,dis[e[i].v]});
        }
    }
}
void Solve(int nl,int nr,int ml,int mr,int ql,int qr)
{
    if (ql > qr) return;
    if (nr-nl > mr-ml)
    {
        int mid = (nl+nr) >> 1;
        for (int i=ml;i<=mr;++i)
        {
            DIJ(P(mid,i),nl,nr,ml,mr);
            for (int j=ql;j<=qr;++j) ans[p[j].num] = min(ans[p[j].num],dis[P(p[j].xa,p[j].ya)]+dis[P(p[j].xb,p[j].yb)]);
        }
        int l = ql-1, r = qr+1;
        for (int i=ql;i<=qr;++i)
            if (p[i].xa<mid && p[i].xb<mid) t[++l] = p[i];
                else if (p[i].xa>mid && p[i].xb>mid) t[--r] = p[i];
        for (int i=ql;i<=l;++i) p[i] = t[i];
        for (int i=r;i<=qr;++i) p[i] = t[i];
        Solve(nl,mid-1,ml,mr,ql,l), Solve(mid+1,nr,ml,mr,r,qr);
    }
    else
    {
        int mid = (ml+mr) >> 1;
        for (int i=nl;i<=nr;++i)
        {
            DIJ(P(i,mid),nl,nr,ml,mr);
            for (int j=ql;j<=qr;++j) ans[p[j].num] = min(ans[p[j].num],dis[P(p[j].xa,p[j].ya)]+dis[P(p[j].xb,p[j].yb)]);
        }
        int l = ql-1, r = qr+1;
        for (int i=ql;i<=qr;++i)
            if (p[i].ya<mid && p[i].yb<mid) t[++l] = p[i];
                else if (p[i].ya>mid && p[i].yb>mid) t[--r] = p[i];
        for (int i=ql;i<=l;++i) p[i] = t[i];
        for (int i=r;i<=qr;++i) p[i] = t[i];
        Solve(nl,nr,ml,mid-1,ql,l), Solve(nl,nr,mid+1,mr,r,qr);
    }
}
int main()
{
    n = read(), m = read();
    int x,y,z;
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j) x = P(i,j), px[x] = i, py[x] = j;
    for (int i=1;i<=n;++i)
        for (int j=1;j<m;++j)
        {
            x = P(i,j), y = P(i,j+1), z = read();
            Build(x,y,z);
        }
    for (int i=1;i<n;++i)
        for (int j=1;j<=m;++j)
        {
            x = P(i,j), y = P(i+1,j), z = read();
            Build(x,y,z);
        }
    QQ = read();
    for (int i=1;i<=QQ;++i)
    {
        ++w;
        p[w].xa = read(), p[w].ya = read(), p[w].xb = read(), p[w].yb = read();
        if (p[w].xa==p[w].xb && p[w].ya==p[w].yb) --w, ans[i] = 0; else p[w].num = i, ans[i] = INF;
    }
    Solve(1,n,1,m,1,w);
    for (int i=1;i<=QQ;++i) printf("%d\n",ans[i]);
    return 0;
}