神题专练(一)

%^&#!*&#*艹!

BZOJ 3218

题目大意:不存在的自己看…

解题报告

好神啊! 网络流竟然还可以和可持久化线段树一起玩! 要不是前几天听说后面有道这种鬼畜题要用PST和网络流就根本不可能想到正解。
首先这个应该是可以直接暴力网络流建图的, 但是不仅边数可以达到N^2级别而且还会爆内存(40MB)。
怎么优化呢?在可持久化线段树上建立需求关系, 优化就好了!
这样可持久化线段树上边数为NlogN级别, 每次节点连出去的边数也变成NlogN级别了。
写题。
自己zz先是写爆网络流(dis!=INF才加点…)然后又把主席树新建层放到了查询前面(什么都查不到QAQ)结果不停对样例输出56…调了1h+败了…
这题写起来还是有一点坑点的, 比如主席树叶子节点要在网络流离指向上一个叶子节点(INF)。
感谢Ender的样例:
Input:
4
0 0 10 0 0 0
0 0 10 0 0 0
0 0 10 0 0 0
0 100 0 0 0 31
Output:
100


代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
typedef long long LL;
const int MAXN = 5050;
const int INF  = 0x3f3f3f3f;
namespace MaxFlow {
    const int MAXE = MAXN*120;
    const int MAXD = MAXN*20;
    struct Node {
        int v, w, nxt, bk;
    } d[MAXE];
    int head[MAXD], etot;
    inline void addEdge (int a, int b, int w) {
        //printf("edge:%d->%d: %d\n", a, b, w);
        etot ++;
        d[etot].v = b;
        d[etot].w = w;
        d[etot].bk = etot + 1;
        d[etot].nxt = head[a];
        head[a] = etot;
        etot ++;
        d[etot].v = a;
        d[etot].w = 0;
        d[etot].bk = etot - 1;
        d[etot].nxt = head[b];
        head[b] = etot;
    }
    int S, T, N;
    int dis[MAXD], vd[MAXD];
    queue<int> que;
    void bfs (int s) {
        que.push(s);
        memset(dis, 0x3f, sizeof dis);
        dis[s] = 0;
        while(!que.empty()) {
            int u = que.front();
            que.pop();
            for(int e = head[u]; e; e = d[e].nxt)
                if(dis[d[e].v] == INF) {
                    dis[d[e].v] = dis[u]+1;
                    que.push(d[e].v);
                }
        }
    }
    int dfs (int u, int val) {
        if(u == T) return val;
        int rest = val;
        for(int e = head[u]; e; e = d[e].nxt)
            if(d[e].w && dis[d[e].v]+1 == dis[u]) {
                int t = dfs(d[e].v, min(d[e].w, rest));
                d[e].w -= t;
                d[d[e].bk].w += t;
                rest -= t;
                if(!rest || dis[S] >= N) return val-rest;
            }
        if(val == rest) {
            if(!(--vd[dis[u]])) {dis[S] = N; return 0;}
            dis[u] = N;
            for(int e = head[u]; e; e = d[e].nxt)
                if(d[e].w) dis[u] = min(dis[u], dis[d[e].v]+1);
            ++vd[dis[u]];
            return 0;
        }
        return val-rest;
    }
    inline int execute (int s, int t, int n) {
        S = s, T = t, N = n;
        memset(vd, 0, sizeof vd);
        bfs(T);
        for(int i = 1; i<=N; i++)
            if(dis[i] < N) ++vd[dis[i]];
        int flow = 0;
        while(dis[S] < N) flow += dfs(S, INF);
        return flow;
    }
}
int N;
namespace PST {
    const int MAXD = MAXN*20;
    int lc[MAXD], rc[MAXD], dtot;
    int roots[MAXD], tot = 1;
    int ipos, ival;
    void insert (int & u, int lb, int rb, int r) {
        if(lb > ipos || rb < ipos) {u = r; return ;}
        if(!u) u = ++dtot;
        if(lb == rb) {
            //printf("lnk!\n");
            MaxFlow::addEdge(u+N*2, ival, INF);
            if(r) MaxFlow::addEdge(u+N*2, r+N*2, INF);
            return ;
        }
        int mid = (lb+rb)>>1;
        insert(lc[u], lb, mid, lc[r]);
        insert(rc[u], mid+1, rb, rc[r]);
        if(lc[u]) MaxFlow::addEdge(u+N*2, lc[u]+N*2, INF); // 全部到S集
        if(rc[u]) MaxFlow::addEdge(u+N*2, rc[u]+N*2, INF);
    }
    int ql, qr;
    vector<int> * qret;
    void query (int u, int lb, int rb) {
        if(!u || lb > qr || rb < ql) return ;
        if(ql <= lb && rb <= qr) {
            //printf("qry:[%d, %d], ret:[%d, %d]\n", ql, qr, lb, rb);
            qret->push_back(u+N*2); return ;
        }
        int mid = (lb+rb)>>1;
        query(lc[u], lb, mid), query(rc[u], mid+1, rb);
    }
    inline int & cRoot () {return roots[tot];}
    inline int & lRoot () {return roots[tot-1];}
    inline void newFloor () {++tot;}
}
int A[MAXN], B[MAXN], W[MAXN], L[MAXN], R[MAXN], P[MAXN];
int linrA[MAXN];
/*
S: black, T: white
[1, 2*N]: points
[2*N+1, N+PST::dtot]: PST
*/
vector<int> buf;
int main () {
    scanf("%d", &N);
    for(int i = 1; i<=N; i++)
        scanf("%d%d%d%d%d%d", A+i, B+i, W+i, L+i, R+i, P+i);
    memcpy(linrA, A, sizeof A);
    sort(linrA+1, linrA+N+1);
    int linrLen = unique(linrA+1, linrA+N+1)-linrA;
    PST::qret = &buf;
    for(int i = 1; i<=N; i++) {
        PST::ql = lower_bound(linrA+1, linrA+linrLen, L[i])-linrA;
        PST::qr = upper_bound(linrA+1, linrA+linrLen, R[i])-linrA-1;
        buf.clear();
        PST::query(PST::cRoot(), 1, linrLen-1);
        for(int j = 0; j<(int)buf.size(); j++)
            MaxFlow::addEdge(N+i, buf[j], INF);
        MaxFlow::addEdge(i, N+i, P[i]);
        PST::newFloor();
        PST::ipos = lower_bound(linrA+1, linrA+linrLen, A[i])-linrA;
        PST::ival = i;
        PST::insert(PST::cRoot(), 1, linrLen-1, PST::lRoot());
    }
    int S = N*2+PST::dtot+1, T = S+1, sum = 0;
    for(int i = 1; i<=N; i++) {
        MaxFlow::addEdge(S, i, B[i]);
        MaxFlow::addEdge(i, T, W[i]);
        sum += W[i]+B[i];
    }
    printf("%d\n", sum-MaxFlow::execute(S, T, T));
}

BZOJ 4104

题目大意: 自己看..

解题报告

太神了! 还没理解, 留坑!

代码

#include <cstdio>
#include <algorithm>
struct Pr {int x, y;} inp[300030];
inline bool operator < (const Pr & a, const Pr & b) {
	return (a.x == b.x)?(a.y < b.y):(a.x < b.x);
}
int main () {
	int N;
	scanf("%d%*d", &N);
	for(int i = 0; i<=N; i++) {
		scanf("%d", &inp[i].x);
		inp[i].y = i;
	}
	std::sort(inp, inp+N+1);
	int cur = inp[0].y;
	for(int i = 0; i<N; i++) {
		printf("%d ", inp[cur].x);
		cur = inp[cur].y;
	}
}

九连环

具体请移步: 这篇博客中的第一题