M_sea

洛谷5332 [JSOI2019]精准预测
LuoguLOJ分析不会做,抄 memset0 题解每个人在每个时刻只有 $2$ 种状况,考虑 2-SAT 。设 ...
扫描右侧二维码阅读全文
16
2019/05

洛谷5332 [JSOI2019]精准预测

Luogu

LOJ

分析

不会做,抄 memset0 题解

每个人在每个时刻只有 $2$ 种状况,考虑 2-SAT 。

设 $(x,t,0/1)$ 表示 $x$ 在 $t$ 时刻活着/死了。那么直接连边就好了。

另外还有一个隐藏条件:如果 $x$ 在 $t$ 时刻活着,那么在 $t-1$ 时刻也活着;如果 $x$ 在 $t$ 时刻死了,那么 $x$ 在 $t+1$ 时刻也死了。这个同样要连边。

问题变为在建好的图上,从 $(i,T+1,0)$ 出发,可以到达多少个 $(j,T+1,1)$ 。假设有 $ans$ 个,那么答案为 $n-ans-1$ 。

这个东西怎么求呢?可以用 $\mathrm{bitset}$ 维护一下,然后拓扑排序转移。时间复杂度为 $O(\frac{Tnm}{\omega})$ 。

这样子显然过不去,原因是点数太多了。考虑怎么优化点数。

显然只有至多 $4m$ 个点是有用的(每个预言只和 $4$ 个点有关)。那么把这 $4m$ 个点拿出来建图就行了。

注意上面的隐藏条件也要建:对于 $x$ 相同的点,按 $t$ 排序,然后依次连边。

这样子 $\mathrm{bitset}$ 还是存不下,可以分段跑。

另外还有一些要注意的地方:

  • 如果从 $(i,T+1,0)$ 可以到达 $(i,T+1,1)$ ,那么说明 $i$ 必死。显然此时 $i$ 的答案为 $0$ 。另外这样的 $i$ 也不会对别的点产生贡献,注意判掉。
  • 对于某些人,可能没有与他有关的预言,那么他最后一定可以活着。注意处理这一部分。

具体实现和细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') c=getchar();
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=400000+10;
const int B=10000;

struct Edge { int v,nxt; } e[N<<1];
int head[N];

inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}

int n,m,T,tot;
bitset<B> bit[N],tmp;
map<pair<int,int>,int> mp;
vector<pair<int,int>> same[N];
queue<int> Q;
int lst[N],now[N],deg[N],tag[N],ans[N];

inline int id(int x,int y) { return (x<<1)+y-1; }
inline int calcid(int x,int y) {
    map<pair<int,int>,int>::iterator it=mp.find(make_pair(x,y));
    if (it==mp.end()) {
        int res=++tot;
        mp[make_pair(x,y)]=res;
        same[x].push_back(make_pair(y,res));
        return res;
    }
    else return it->second;
}

int main() {
    T=read(),n=read(),m=read();
    for (re int i=1;i<=m;++i) {
        int op=read(),t=read(),x=read(),y=read();
        if (!op) {
            x=calcid(x,t),y=calcid(y,t+1);
            addEdge(id(x,0),id(y,0)),++deg[id(y,0)];
            addEdge(id(y,1),id(x,1)),++deg[id(x,1)];
        } else {
            x=calcid(x,t),y=calcid(y,t);
            addEdge(id(x,1),id(y,0)),++deg[id(y,0)];
            addEdge(id(y,1),id(x,0)),++deg[id(x,0)];
        }
    }
    for (re int i=1;i<=n;++i) {
        sort(same[i].begin(),same[i].end());
        for (re int j=1;j<same[i].size();++j) {
            int u=same[i][j-1].second,v=same[i][j].second;
            addEdge(id(u,0),id(v,0)),++deg[id(v,0)];
            addEdge(id(v,1),id(u,1)),++deg[id(u,1)];
        }
        if (same[i].size()) lst[i]=(--same[i].end())->second;
        else lst[i]=-1;
    }
    for (re int l=1,r=min(B,n);l<=n;l=r+1,r=min(l+B-1,n)) {
        for (re int i=1;i<=(tot<<1);++i) bit[i].reset();
        for (re int i=l;i<=r;++i)
            if (~lst[i]) bit[id(lst[i],1)].set(i-l);
        for (re int i=1;i<=(tot<<1);++i) {
            now[i]=deg[i];
            if (!now[i]) Q.push(i);
        }
        while (!Q.empty()) {
            int u=Q.front(); Q.pop();
            for (re int i=head[u];i;i=e[i].nxt) {
                int v=e[i].v; bit[v]|=bit[u],--now[v];
                if (!now[v]) Q.push(v);
            }
        }
        tmp.reset();
        for (re int i=l;i<=r;++i)
            if (~lst[i]&&bit[id(lst[i],0)][i-l])
                tag[i]=1,tmp.set(i-l);
        for (re int i=1;i<=n;++i) {
            if (~lst[i]) ans[i]+=(bit[id(lst[i],0)]|tmp).count();
            else ans[i]+=tmp.count();
        }
    }
    for (re int i=1;i<=n;++i) printf("%d ",tag[i]?0:n-ans[i]-1);
    puts("");
    return 0;
}
最后修改:2019 年 05 月 29 日 07 : 57 PM

发表评论