Home PageWeb BoardProblemsStandingStatusStatisticsAward Contest

Contest - POJ Monthly--2006.05.28

Start time:  2006-05-28 12:00:00  End time:  2006-05-28 17:00:00
Current System Time:  2024-03-28 20:42:35.867  Contest Status:   Ended

Problem ID Title
2827 Problem A Auto-Calculation Machine
2828 Problem B Buy Tickets
2829 Problem C How Many Free Dimensions?
2830 Problem D Max Sequence II
2831 Problem E Can We Build This One?
2832 Problem F How Many Pairs?
2833 Problem G The Average
2834 Problem H Where Are You?

[Standings]  [Status]  [Statistics]

Contest Report

Problem A: Auto-Calculation Machine

本题的考查点是并查集。对于给定的数组a,我们另外构造一个数组s,其中s[i]为数组a中前i个元素的和。对于给定的指令sum(i, j) (ij),正确的结果就是s[j] − s[i − 1]。用f[i]表示i所在集合的代表元,d[i]表示s[f[i]] − s[i]。那么,对于给定的v = sum(i, j) (ij),如果i − 1和j在同一集合中,只要检查d[i − 1] − d[j]是否与v相等即可;如果i − 1和j在不同的集合中,则此记录一定为真,令x = f[i − 1],y = f[j],此时只需要令f[y] = xd[y] = d[i − 1] − d[j] − v即可。注意操作过程中一定要保证有ij。注意到ij之间有意义的关系实际上是其相对位置,对于给定的可能很大的ij,只需要将其映射为其在给定操作序列的下标升序排列后的序号即可。

Problem B: Buy Tickets

本题的算法是利用线段树进行倒推。基本思想是拿一个N个1的序列,从最后一次插入开始倒推。设当前插入的是Pos Val,那么找到从左边数第Pos + 1个1的位置就是最终需要插入Val的位置,然后把那个1改成0。

Problem C: How Many Free Dimensions?

要求向量积的分量的自由度,只需用总分量数nk减去根据下标约束规则不独立的分量数即可。约束规则可分为两类。一类是等号左右的字母串类型相同,另一类是字母串类型不同。这里“类型相同”是指,若左边某两个位置上的字母相同,则右边对应位置上的字母也相同;若左边某两个位置上的字母不同,则右边对应位置上的字母也不同。设规则等号左边出现的不同字母数目是a。对等号两边类型不同的规则,不独立的分量数就是n! ⁄ (na)!。对等号两边类型相同的规则,规则本身可看作下标集上的一类置换,这类置换具有相同的形式和相同的阶。若两个下标可以从一个通过一次或多次应用置换得到另一个,那么它们就不是相互独立的。设置换的阶为r,那么具有符合规则的下标的分量中中可以定义为独立的分量是所有这些分量数的1 ⁄ r。因此应当减去的数目就是n! ⁄ (na)! * (r − 1) ⁄ r

Problem D: Max Sequence II

最大子段积问题是最大子段和问题的一个直接扩展。我们首先考虑序列中没有0的情况。对每一个i (1 ≤ iN),计算Pi = ∏ni = 1 ai,同时记录当前位置前正数积的最小值pi和负数积的最大值mi;当Pi > 0时用Pipi更新当前最大值,当Pi < 0时用Pimi更新当前最大值。对于序列中有0的情况,则以0位分界分别求出各子段的最大值,然后取最大的一个和0之间的较大者即可。对题目给定的数据范围直接运用浮点类型计算会导致溢出,应记录符号并对绝对值取对数进行计算。最后输出时需控制精度,并处理x四舍五入后变成10的情况。

Problem E: Can We Build This One?

本题的算法是先求出给出的带权图的一棵最小生成树,然后求出每一对顶点间在最小生成树上的路径的权最大的边的权。对于一个查询,若给出的权不大于之前求出的两端点间的最大权,那么回答为“YES”,否则为“NO”。

Problem F: How Many Pairs?

本题也可以用并查集解决。初始时,每个顶点自成一个集合。从小到大处理所有查询。处理一个查询A,则把所有权不大于A的边关联的两个顶点所在的集合合并,同时维护集合的大小,回答就是所有集合内部顶点对的个数总和。

Problem G: The Average

本题的算法是建立两个表L1L2,对它们进行动态维护,使得它们最终保存的数据是给定的数排序后的前n1个数和后n2个数,同时计算出其余的数的和S,最后计算平均值即可。首先读入n1 + n2个数初始化L1L2,使得L1中的数都不小于L2中的数,初始化S为0。对以后输入的每一个数a

  1. L1中的最小数小于a,则将其与a交换;
  2. L2中的最大数大于a,则将其与a交换;
  3. a加到S中。

这样即可得到排序后处在中间的n − (n1 + n2)个数的和S,再求平均就是答案。

Problem H: Where Are You?

本题只需用BFS求出从place 0出发到其他地方的距离,然后模拟Jon和Cely的行程即可。

Home Page Go Back To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator