注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

A + B Problem 题解  

2013-06-08 15:41:48|  分类: 奇葩 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
A + B Problem 题解 - vfleaking - vfleaking的博客 
A + B Problem 题解 - vfleaking - vfleaking的博客

【算法一】
对于30%的数据 n <= 20。
于是可以直接O(2^n)枚举答案,然后O(n^2)求出答案进行更新。
期望得分30分

【算法二】
对于30%的数据 maxA <= 10。
于是可以用状压DP来解。记f[i][status]表示考虑前i个格子,每个数的状态为status的情况下的好看度最大是多少。status的第j位为1表示之前出现了白色的这个数,否则表示没出现。dp方程很简单就不写了。不过好像内存有点压力,所以用滚动数组搞一下就行了。O(n * 2^maxA)
期望得分30分。

【算法三】
对于60%的数据 n <= 500。
对于每个格子有黑白两种状态,可以联想到最小割。一个格子有在S割和在T割两种状态。

我们来回忆一下最小割。如果v向u连一条容量为w的有向边,表示v如果在S割,那么u不在S割会产生w的代价。
一个等价的表述是,u如果在T割,那么v不在T割会产生w的代价。
注意v如果在T割,那么u在S割是不会产生代价的。
特别的,如果v向u连一条容量为正无穷大的有向边,表示v如果在S割,那么u一定也要在S割。
一个等价的表述是,u如果在T割,那么v一定也要在T割。

考虑要最大化的式子。发现又有加法又有减法,而我们是最小割不是最大割,这样就很坑。
于是可以这样想:对于每个格子,先拿到b[i]和w[i]的好看度。
然后如果这个格子是黑色,那么付出w[i]的代价,如果这个格子是白色,付出b[i]的代价。
这样就全统一成了代价,最小化这个代价即可。

建立结点1, 2, ..., n。结点i在S割表示格子i染黑,在T割表示格子i染白。
根据前面算代价的方式,那么结点i在S割需要付出w[i]的代价,在T割需要付出b[i]的代价。
所以连边:(用(起始点,终点,容量)表示一条有向边
(S, i, b[i])
(i, T, w[i])

接下来就是奇怪的格子的问题,如果格子i是奇怪的格子,就要付出p[i]的代价。
于是我们希望能有一个结点i',使得如果存在白色的格子j满足 1 <= j < i, l[i] <= a[j] <= r[i],那么i'就在T割,否则在S割。
这样如果构造出来了这样的i',我们希望当且仅当i在S割,i'在T割时付出p[i]的代价。发现这个很好搞。
连边:
(i, i', p[i])

现在来考虑构造i'。
对于每个白色的格子j满足 1 <= j < i, l[i] <= a[j] <= r[i],我们希望j如果在T割,那么i'也一定要在T割。发现这个很好搞。
连边:
(i', j, 正无穷大)

这样是不是完了呢?其实这样构造出来的i',如果存在白色的格子j满足 1 <= j < i, l[i] <= a[j] <= r[i],那么i'一定在T割。如果不存在,那么i'可能在S割也可能在T割。
注意到此时i'在T割肯定比i'在S割的代价大,由于我们求的是最小割,所以这样构造i'是正确的。

如此以来网络流图的点数V = O(n), 边数E = O(n^2)。足以通过这60%的数据。
期望得分60分。

【算法四】
使用算法二和算法三,可以拿下前8个测试点。
期望得分80分。

【算法五】
为什么算法三不能通过最后两个点呢?原因是边数过多,MLE了。(而且会TLE)
那么有没有办法能减少边的数量呢?
答案是有的。

考虑一个这样的问题:现在给你一个染色方案,请在O(n log n)时间内求出这个方案的好看度。
离散化 + 线段树或树状数组的裸题。

既然如此,我们能不能将线段树嵌入到网络流的图里去呢?
首先简化问题,假设没有1 <= j < i这个限制,且所有a的值互不相等。
关键是看i'的构造。如前所述,我们只要构造出来 "如果存在满足条件的j,那么i'一定在T割。如果不存在,那么i'可能在S割也可能在T割" 就行了。
考虑一棵线段树,用线段树查询[l[i], r[i]]这个区间能得到一些结点,这些结点每个代表一个区间,这些不相交的区间的并集就是[l[i], r[i]]。
那么这些区间里面,只要有一个白色的结点,i'都必须在T割。
连边:
(i', 查询到的结点, 正无穷大)

接下来就是保证线段树结点一定满足这样的性质:它所代表的区间中有在T割的,那么它也一定在T割。
连边:
(线段树的非叶结点, 左儿子, 正无穷大)
(线段树的非叶结点, 右儿子, 正无穷大)
(a[i]对应的线段树叶结点, i, 正无穷大)

这样就成功嵌入进去了。

现在考虑加上1 <= j < i这个限制呢?所有a的值仍然互不相等。
只要用可持久化线段树就行了。每次在a[i]这个位置插入构造出来新的线段树。

如果a值有相等呢?
我们希望满足的是,"它所代表的区间中有在T割的,那么它也一定在T割。"
于是此时线段树叶结点就要向所有的k满足k <= i, a[k] = a[i]的连边了?
显然是不必要的。
只要多加一条这个就行了:
(当前新建的叶结点, 之前的叶结点, 正无穷大)

如此以来网络流图的点数V = O(n log n), 边数E = O(n log n)。
期望得分100分。


我觉得算法五好有趣的!
代码:

#include <iostream>
#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;

const int MaxN = 5000;
const int MaxLogN = 13;

const int MaxNSegNode = MaxN * (MaxLogN + 1);
const int MaxNSegRes = 2 * (MaxLogN + 1);

// getint
inline int getint()
{
char c;
while (c = getchar(), ('0' > c || c > '9') && c != '-');

if (c != '-')
{
int res = c - '0';
while (c = getchar(), '0' <= c && c <= '9')
res = res * 10 + c - '0';
return res;
}
else
{
int res = 0;
while (c = getchar(), '0' <= c && c <= '9')
res = res * 10 + c - '0';
return -res;
}
}

// adjust
template <class T>
inline bool relax(T &a, const T &b)
{
if (b > a)
{
a = b;
return true;
}
return false;
}
template <class T>
inline bool tension(T &a, const T &b)
{
if (b < a)
{
a = b;
return true;
}
return false;
}

// max flows
namespace NetworkFlows
{
const int MaxNVer = 1 + MaxN + MaxN + MaxNSegNode + 1;
const int MaxNE = MaxNSegNode * 2 + MaxN + MaxN + MaxN * (3 + MaxNSegRes);

struct halfEdge
{
int u, w;
halfEdge *next;
};
halfEdge adj_pool[MaxNE * 2], *adj_tail;

int nVer;
int source, terminal;
halfEdge *adj[MaxNVer];

inline void init()
{
fill(adj, adj + nVer, (halfEdge *)NULL);
adj_tail = adj_pool;
}
inline void addEdge(const int &v, const int &u, const int &w)
{
adj_tail->u = u, adj_tail->w = w, adj_tail->next = adj[v], adj[v] = adj_tail++;
adj_tail->u = v, adj_tail->w = 0, adj_tail->next = adj[u], adj[u] = adj_tail++;
}

inline halfEdge *opposite(halfEdge *e)
{
return adj_pool + ((e - adj_pool) ^ 1);
}

int outcome_flow;

int dist[MaxNVer];
int book[MaxNVer];

int dfs(const int &v, const int &delta)
{
if (v == terminal)
return delta;
int flow = 0;
for (halfEdge *i = adj[v]; i; i = i->next)
if (i->w > 0 && dist[v] == dist[i->u] + 1)
{
int add = dfs(i->u, min(i->w, delta - flow));
i->w -= add, opposite(i)->w += add;
flow += add;

if (flow == delta || dist[source] == INT_MAX)
return flow;
}
if (flow == 0)
{
if (--book[dist[v]] == 0)
{
dist[source] = INT_MAX;
return 0;
}

dist[v] = INT_MAX;
for (halfEdge *i = adj[v]; i; i = i->next)
if (i->w > 0 && dist[i->u] != INT_MAX)
tension(dist[v], dist[i->u] + 1);
if (dist[v] != INT_MAX)
book[dist[v]]++;
}
return flow;
}

inline void calcMaxFlows()
{
fill(dist, dist + nVer, 0);
fill(book, book + nVer, 0);
book[0] = nVer;

outcome_flow = 0;
while (dist[source] != INT_MAX)
outcome_flow += dfs(source, INT_MAX);
}
}

struct seg_node
{
seg_node *lc, *rc;
};
seg_node seg_pool[MaxNSegNode], *seg_tail = seg_pool;

seg_node *seg_add(seg_node *p, const int &pL, const int &pR, const int &val)
{
seg_node *np = seg_tail++;
if (p)
*np = *p;
else
np->lc = np->rc = NULL;

if (pL == pR)
return np;

int pMid = pL + pR >> 1;
if (val <= pMid)
np->lc = seg_add(np->lc, pL, pMid, val);
else
np->rc = seg_add(np->rc, pMid + 1, pR, val);
return np;
}

int seg_res_n;
seg_node *seg_res[MaxNSegRes];

void seg_query(seg_node *p, const int &pL, const int &pR, const int &qL, const int &qR)
{
if (!p)
return;
if (qL <= pL && pR <= qR)
{
seg_res[seg_res_n++] = p;
return;
}

int pMid = pL + pR >> 1;
if (qL <= pMid)
seg_query(p->lc, pL, pMid, qL, qR);
if (pMid < qR)
seg_query(p->rc, pMid + 1, pR, qL, qR);
}

int main()
{
int n;
static int a[MaxN + 1];
static int bVal[MaxN], wVal[MaxN + 1];
static int qL[MaxN + 1], qR[MaxN + 1];
static int penalty[MaxN + 1];

cin >> n;
for (int i = 1; i <= n; i++)
a[i] = getint(), bVal[i] = getint(), wVal[i] = getint(), qL[i] = getint(), qR[i] = getint(), penalty[i] = getint();

int seqA_n = 0;
static int seqA[MaxN];
for (int i = 1; i <= n; i++)
seqA[seqA_n++] = a[i];
sort(seqA, seqA + seqA_n);
seqA_n = unique(seqA, seqA + seqA_n) - seqA;

for (int i = 1; i <= n; i++)
{
a[i] = lower_bound(seqA, seqA + seqA_n, a[i]) - seqA;
qL[i] = lower_bound(seqA, seqA + seqA_n, qL[i]) - seqA;
qR[i] = upper_bound(seqA, seqA + seqA_n, qR[i]) - seqA - 1;
}

static seg_node *tr[MaxN + 1];
tr[0] = NULL;
for (int i = 1; i <= n; i++)
tr[i] = seg_add(tr[i - 1], 0, n - 1, a[i]);

int nSegNode = seg_tail - seg_pool;

namespace NF = NetworkFlows;

NF::nVer = 1 + n + n + nSegNode + 1;
NF::source = 0, NF::terminal = NF::nVer - 1;
NF::init();

int sum = 0;

int shSeg = 1 + n + n;

for (seg_node *p = seg_pool; p != seg_tail; p++)
{
if (p->lc)
NF::addEdge(shSeg + p - seg_pool, shSeg + p->lc - seg_pool, INT_MAX);
if (p->rc)
NF::addEdge(shSeg + p - seg_pool, shSeg + p->rc - seg_pool, INT_MAX);
}
for (int i = 1; i <= n; i++)
{
seg_res_n = 0;
seg_query(tr[i], 0, n - 1, a[i], a[i]);
seg_node *cur = seg_res[0];

seg_res_n = 0;
seg_query(tr[i - 1], 0, n - 1, a[i], a[i]);
seg_node *last = seg_res[0];

NF::addEdge(shSeg + cur - seg_pool, i, INT_MAX);
if (last)
NF::addEdge(shSeg + cur - seg_pool, shSeg + last - seg_pool, INT_MAX);
}
for (int i = 1; i <= n; i++)
{
sum += bVal[i];
NF::addEdge(NF::source, i, bVal[i]);

sum += wVal[i];
NF::addEdge(i, NF::terminal, wVal[i]);

NF::addEdge(i, n + i, penalty[i]);
if (qL[i] <= qR[i])
{
seg_res_n = 0;
seg_query(tr[i - 1], 0, n - 1, qL[i], qR[i]);

for (int j = 0; j < seg_res_n; j++)
NF::addEdge(n + i, shSeg + seg_res[j] - seg_pool, INT_MAX);
}
}

NF::calcMaxFlows();
cout << sum - NF::outcome_flow << endl;

return 0;
}


  评论这张
 
阅读(4079)| 评论(12)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017