特色

HDU 6438 Buy and Resell

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6438

n(1<=n<=1e5)个城市连成的一条链,商品在第i个城市交易的价格为ai,你从第一个城市不回头的走到第n个城市,在每个城市你可以:

  1. 以ai的价格买入1个商品
  2. 以ai的价格卖出1个商品
  3. 什么也不做

一开始你带着无限多的钱,并且你可以同时携带多个商品。

问你两个问题:

  1. 最大收益
  2. 最大收益前提下的最小交易次数

有点类似于网络流的反向边思想,这个之后再说。

思路:

  1. 前提1:假如在一个城市既买入商品,又卖出商品,相当于什么也没做。所以从1到n讨论每个城市,我要做的是决策怎么交易:买,卖,不买不卖。
  2. 前提2:每走到一个城市,我都买商品,直到我走完所有城市,手上还有囤积的货物,说明当初这些货物本来不该购买。
  3. 前提3:收益=卖价和-买价和=累计收益+囤积货物成本
  4. 我的第一个想法是:讨论到第i个城市时,如果手里买价最低的商品(优先队列维护)价格低于ai时,我就卖出(累加收益),否则我就买入(累加成本)(因为我觉得既买又卖是没有意义的)。显然这是一个错误的算法,甚至连样例1都过不了。错在在第i个城市并不是该卖出商品的地方,说不定最优解并不是在第i个城市卖出商品呐。
  5. 我的第二个想法是:假如在第i个城市卖出商品获得一些收益,我还是要在第i个城市买入1个商品,说不定之后就能转手又赚一笔呐。显然这又是一个错误的算法,甚至还是连样例1都过不了。错在在第i个城市又买又买相当于什么也没做,说不定最优解是在第i个城市买入商品呐。
  6. 我的第三个想法是:假如在第i个城市卖出商品获得一些收益,我在第i个城市买2个商品。这样做的灵感源于网络流问题的反向边思想,在搜索的时候假如反向边,假如决策错误,可以在后面把这个错误决策抵消(反悔)掉。假如我在之后总共卖出了1个现在买入的商品,说明我在这个城市本来该不买也不卖,假如我在之后总共卖出了2个现在买入的商品,说明我在这个城市本来该买入1个商品,假如我在之后没有卖出任何现在买入的商品,说明我在这个城市本来该卖出1个商品。

跑一下样例。bought[i]表示最终在第i个城市买入的商品数量,值可能为0,1,2。sold[i]表示在第i个城市卖出的商品数量,值可能为0,1。

……(没图)

样例2过不了,我这样算出的交换次数是4,错误在于把既买入了9,又卖出了9,然而这两个9还不在同一个城市。我的解决方法是,在优先队列的比较函数上做文章。当两个城市的商品价格相同时,我优先选择卖出过商品的城市的商品(因为这样可以抵消交换次数)

然后我开心地写程序了:

然后WA了……。

错误数据为:

正解为 7 4

我输出 7 6。

问题处在计算最小交换次数上。

输出中间结果

……(没图)

发现这组数据中两个8各卖出1次商品,买入2次商品,然而到达价格10,9两个城市后,都选择了卖出第2各8的商品。正确的选择方法显然是再两个8各买一次商品,抵消掉两个8买入的商品,交换次数为4。然而我这样抵消不了,所有输出6。

考虑为什么发生这种情况,回想之前买入两个商品的原因,就是为了提供一个挽回的途径,但仔细一想,其实这两个商品本质上的意义是有区别的。 也就是之前说的:

假如我在之后总共卖出了1个现在买入的商品,说明我在这个城市本来该不买也不卖,假如我在之后总共卖出了2个现在买入的商品,说明我在这个城市本来该买入1个商品,假如我在之后没有卖出任何现在买入的商品,说明我在这个城市本来该卖出1个商品。

所以考虑标记区分这两个商品,添加一个formiko变量(值为1或2)标记这个商品的种类。之后卖出一个现在买入的商品,会抵消两次交易次数,所以我们把其中一个商品的formiko赋值为2,其他所有商品的formiko赋值为1。

这样,这组样例中,就能分别买入两个8的一个商品,抵消掉多余的交换次数。

以下是AC程序。

 

【树】Red alert

一棵n节点的树,取三个节点,要求节点不在一条路径上,求取法总数。

竟然是一遍深搜O(n)大水题。

思路:不在一条路径的取法=总取法-在一条路径的取法=C(n,3)-?。

怎么求这个?呢。

画了图就懒得写字了,直接上程序。

 

【POJ 2157】Maze

题目链接:http://poj.org/problem?id=2157

拿钥匙开门的迷宫搜索题,15年做的。

 

【POJ 2992】Divisors

题目链接:http://poj.org/problem?id=2992

求C(n,k)的约数个数。

这道题是多组数据,并且数量不少,写得不优会被卡常。

 

【POJ 1182】【并查集】食物链

题目链接:http://poj.org/problem?id=1182

食物链
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 93015 Accepted: 28066

Description

动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。A吃B, B吃C,C吃A。
现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述:
第一种说法是”1 X Y”,表示X和Y是同类。
第二种说法是”2 X Y”,表示X吃Y。
此人对N个动物,用上述两种说法,一句接一句地说出K句话,这K句话有的是真的,有的是假的。当一句话满足下列三条之一时,这句话就是假话,否则就是真话。
1) 当前的话与前面的某些真的话冲突,就是假话;
2) 当前的话中X或Y比N大,就是假话;
3) 当前的话表示X吃X,就是假话。
你的任务是根据给定的N(1 <= N <= 50,000)和K句话(0 <= K <= 100,000),输出假话的总数。

Input

第一行是两个整数N和K,以一个空格分隔。
以下K行每行是三个正整数 D,X,Y,两数之间用一个空格隔开,其中D表示说法的种类。
若D=1,则表示X和Y是同类。
若D=2,则表示X吃Y。

Output

只有一个整数,表示假话的数目。

Sample Input

Sample Output

Source

题目大意:如题。
解法一:带权并查集。
解法二:用集合关系表示同类和捕食关系。
为了便于理解,这三类动物可以解释为分解者,消费者,生产者。
假设消费者捕食生产者,生产者捕食分解者,分解者捕食消费者。(实际上不是这样,这样说只是为了确立三者之间的捕食顺序关系)
n个动物,每个动物可能是三者之一,不妨用[1,n]表示分解者,[n+1, 2n]表示消费者,[2n+1,3n]表示生产者。
定义(a,b)表示动物a和b再同一个集合。
定义a,b为同类的集合关系表现为:(a,b)
定义a捕食b的集合关系表现为:(a,b+n)
定义merge(a,b)为使得a,b 在同一个集合
逐条读入k句话(排除掉显然错误的话),然后:
  • 若断言a,b是同类。我们先判断a,b是否存在捕食或者反捕食关系:是否(a,b+n)和(b,a+n)由于我们不知道a,b是分解者,消费者还是生产者,但是我们知道a,b一定是同一种类型的。所以不妨认为:1,a,b都是分解者;2,a,b都是消费者,3,a,b都是生产者。
  • 若断言a捕食b。我们要判断a,b是否是同类和b是否捕食a。

 

【模板】makedata

 

【模板】树状数组

单点更新,区间查找

 

【卡常】Ascending Rating

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6319

一句话:取模是很耗时的,生成a[i]的时候,不需要因为防爆int而取模3次,大胆地爆int,反正还在longlong范围内,然后取模1次就OK,从4200MS降到了2400MS。

再加个取模优化和输入挂就更快了。(然而我的有限次地实验证再此题加输入优化是负优化)