%^&#!*&#*艹!
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; } }
九连环
具体请移步: 这篇博客中的第一题
Join the discussion