8月8日校内测试题解。

08/08/2014

这里是为了新开的BLOG 丧心病狂到宁愿少敲一道题也要骗访问量的草稿版题解。

若关于我对题目做法的叙述有何建议或疑问,欢迎在下方评论/w\。

 

A:  POJ 1417  True Liars

集合并查集+类背包dp

 

首先用并查集维护 坏蛋 与 好蛋 。

不难发现,无论一个人蛋的好坏,只要判断条件为YES,就说明这两个人在相同集合,否则在不同集合。

我们依靠输入给定的关系可以将蛋们分成若干个大集合,每个大集合有两种元素:①与根节点处于同一小集合(好坏立场相同) 。 ②与根节点不处于同一小集合(好坏立场不同)。

接下来,我们对于一个集合I,可以得到  SAME[I]:大集合I内与根节点立场相同的人数。

DIF[I]    :大集合I内与根节点立场不同的人数。

如此这般如此这般……

因为我们要判断的是“有P1个好蛋与P2个坏蛋的情况是否成立且唯一。”

所以由此可以通过类似于背包的动态规划来求解。

F[I][J]代表前I个集合有J个好蛋的情况,

P[I][J]记录状态[I][J]从哪里转移过来,即选的是SAME[I]还是DIF[I]。

不难得到:

{F[i][j]=F[i-1][j-SAME[i]]+F[i-1][j-DIF[i]]}

 

最后通过解的唯一性(个数)判断逻辑是否矛盾,如果可行的话通过P[I][J]搞输出就好了w。

 

B  同C。

C  同J。

 

D:POJ 2828   Buy Tickets

离线处理+线段树。

利用了自顶向下线段树的二分的性质,

对于线段树的某一个结点[l,r],我们维护 [l,r]有多少个空位置没有被人占用。

稍微脑补一下就不难发现,

倘若我们从后开始往队伍里塞人,将第 i 个人每次往[1,maxn]区间内的第 pos[i]+1 个位置塞,即可达到最终队伍的状态。

初始每个节点的权值设为0,每次塞人的时候自上而下递归寻找应该被塞的叶子节点,将叶子节点权值+1后Update即可。

 

E   Hdu 4893  标题太长懒得打字系列.

这道题我来做一下嘴巴选手……

首先我们要用线段树维护两个值:

SumA:区间内所有数字之和,

SumB:当区间内所有数字都为最近的斐波那契数时,区间内所有数字之和。

分别叙述3个操作的做法:

1号操作:将位置k的数字增加d 。维护SumA : 直接单点修改后UPDATE即可。

维护SumB : 寻找更改后的数字最近的斐波那契数,单点修改SumB的値,UpDate.

2号操作:直接求和,注意下传标记的姿势即可。

3号操作:给区间L,R打上标记,代表该节点的値将更新为SumB。

 

F 同B。

 

G 不会Q_Q字符串苦手。

 

H 并查集维护联通性即可,当遇到合并两个在相同集合内的元素时输出FALSE。

 

I  : ZOJ 2632   Watermelon Full of Water

优先队列维护DP。

 

首先我们容易得到这个式子:

{F[i]=MIN_{j=1}^{i}\{F[i],F[j-1]+V[j]\},(D[j]+j-1>=i)}.

其中F[I]代表到第I天为止都有西瓜吃(好开心)的最少花费。

身为一个O(N^2)复杂度的DP,显然会TLE。

那么我们该怎么办呢……

该怎么办呢……

怎么办呢……

么办呢……

办呢……

呢……

……

用priority_queue 维护一个结构体:

Node[i]=(F[i-1]+V[i] , i+D[i]-1)。

每次转移前Q.push(Node[i])入队,

再不停地Q.pop(),

直至Q.top()的天数满足支持到第i天,转移即可。

 

J 同F。

 

QQ图片20140808165630

 

不要问我B、C、F、J的题解在哪里,讲课的老师们会哭泣的。

 

这次又一次作为嘴巴选手手残了= =b