09day2

多米诺骨牌

递推+高精度

【问题描述】

Jzabc 对多米诺骨牌有很大兴趣,然而他的骨牌比较特别,只有黑色的和白色的两种。他觉得如果存在连续三个骨牌是同一种颜色,那么这个骨牌排列便是不美观的。现在他有 n 个骨牌要排列,他想知道不美观的排列的个数,由于数字较大,数学不好的他不会统计,所以他请你来帮忙。希望你在一秒内求出不美观的排列的个数

【输入】

只有一个正整数,即要排列的骨牌个数

【输出】

一个数,即不美观的排列个数。

【输入样例】

4

【输出样例】

6

【Hint】

有六种不美观的排列:

黑黑黑黑,白白白白,黑黑黑白,白白白黑,黑白白白,白黑黑黑

【数据范围】

20%的数据,n≤60;

50%的数据,n≤600;

100%的数据,n≤20000。

【解题过程】

一点思路都没有,就用搜索打了个表,发现了点规律。用 f(i) 表示有 i 个骨牌时的不美观的排列数,则可以发现 f(i)-2*f(i-1) = 2*fib(i-3)(fib 表示斐波那契数列,具体是 fib(i-3) 还是 fib(i-2) 我也忘了)。那么就可以递推了,但是由于 n 会达到 20000,所以不得不用高精度。如果用普通的高精度加法,由于最后结果长达 6000 位,很明显会 TLE。所以当然要用高大上的万进制。但是效果依然不好,于是我丧心病狂地开了 long long 并采用 10^18 进制。效率的提升是很明显的,即使是 20000 几乎也能马上出解。

但是在调的过程中发现一点不对劲,如果我用 10^16 进制,得到的答案和 10^18 进制得到的答案不一样,具体表现为漏了一些 0。然后恍然大悟,所有 10 的幂进制高精度都需要注意的地方,就是最后输出的时候,除了最前面的部分,后面的那些数字如果位数不够要补 0,比如对于万进制,某个数组元素存放的值是 1,其对应的值其实是 0001,这个值如果是在整个数的开头那么不必加 0,如果是在中间则必须加 0。

但是还是要写一下为什么存在这个规律。如果我们考虑美观的情况,f(i) 可以分两种情况:第 i 个与第 i-1个同色或不同色。则 f(i) = f(i-2)+f(i-1)。

第一次提交 AC。

 

超车

求逆序对

【问题描述】

Jzabc 除了对多米诺骨牌感兴趣外,对赛车也很感兴趣。上个周末他观看了一场赛车比赛。他总是能想出许多稀奇的问题。某一时刻,他看到有 n 辆车(总是匀速行驶)在同一直线上,并且处在一个无限长度的直道上。而且 n 辆车有严格的先后之分。他通过特殊的器材测出了每一辆车的速度。那么问题出现了,如果有两辆车 A 车和 B 车,A 车在 B 车的后面,并且 A 车的速度比 B 车快,那么经过一段时间后,A 车一定会超过 B 车。我们称之为一次超车。那么他想请你帮忙计算超车总数。我们记车道起点的坐标为 0,没有两辆车的坐标相同。

【输入】

第一行,一个数 n,车辆总数。以下 n 行为 n 辆车的信息:

第二行至第 n+1 行,每行两个正整数 x,y,分别表示车的坐标和车的速度。0<x,y≤1000000000。

【输出】

一行,超车总数。

【输入样例】

2

5 6

2 8

【输出样例】

1

【数据规模】

20%的数据,n≤300;

50%的数据,n≤3000;

100%的数据,n≤300000。

【解题过程】

好裸的逆序对。

但是写归并排序还是没有一次写对,后面发现循环里没有处理元素大小相同的情况。

注意做归并排序之前还要先按坐标对这些车进行排序。

 

最小奖励

动态规划

【问题描述】

Jzabc 更是一个*的旅游爱好者。这次他想去一个诡异的地方。这个地方有 n 个村庄,编号为1 到 n。此刻他在 1 号村庄,他想去 n 号村庄。这 n 个村庄之间有 m 条单向道路。通过某些道路时,可能会花费一些钱作为"买路钱",可是通过一些道路时,不仅不需要交"买路钱",而且会得到一些奖励(这就是诡异的地方?)。当然两个村庄之间可能有多条直接相连的道路,但是每一条道路只能通过一次。这些村庄有这样的特性,从任何一个村庄出发,沿着任一条路径走都不会回到出发点。找到一条路径从 1 号村庄到 n 号村庄后,他需要计算一共得到多少奖励,一共交了多少"买路钱"。如果得到的总奖励钱数大于交的"买路钱"数,那么称走这一条路径可以得到奖励;相反,如果前者小于后者,那么称走这一条路径需要花费。如果两者相等,那么 Jzabc 不会选这一条路(我也不知道他为什么不选这一条路径)。不会出现所有的路径两者都相等。他又需要你的帮助,让你找一条路径,使他得到的奖励最小(为什么不是最大的奖励?),并输出最小奖励。如果找不到一条路径能使他得到奖励,那么就找一条路径使他得到的花费最大(为什么就不是最小的花费?),并输出最大花费。

【输入】

第一行两个正整数 n 和 m,n 是村庄数,m 是道路数。

以下 m 行,每行三个数 x,y,w,表示 x 为起点,y 是终点,若 w 为正,则是通过此条道路得到的奖励;若 w 为负,则是通过此条道路交的"买路钱"。w≠0 且|w|≤10。

【输出】

一个整数。若有最小奖励,则输出。否则输出最大花费。

【输入样例】

09day2

【数据规模】

20%的数据,n≤20,m≤200;

50%的数据,n≤50,m≤2000;

100%的数据,n≤100,m≤20000。

【解题过程】

首先从题目描述上看是个 DAG。那么我们就可以用布尔型的 f(i, j) 表示从节点 1 走到节点 i 权值之和能否等于 j。由于存在负数,所以我们给它加一个偏移量,也就是说把「0」设置为 1001,则小于 1001 的数就表示负数。

一开始还想用拓扑排序先求一遍顺序再按拓扑序来 DP,但是发现可以直接记忆化搜索,它自然会按照拓扑序来完成。注意把边反向才能不用拓扑排序而直接记忆化搜索做。

第一次提交 AC(其实是爆0但那是数据问题)。

上一篇:python处理xml的常用包(lib.xml、ElementTree、lxml)


下一篇:C++第三篇--程序结构