九省联考’18 IIIDX

只能想出 80% 的部分,细节处理一个也没想到

(废柴大哭)

代码

 

BZOJ2796 | POI2012 Fibonacci Representation

网上没什么正经题解。这篇是我从 POI 小书上扒下来译成英文的。用的 Google Trans + 人眼修正,可能有很多语法语义错误。

中间中文的部分是 alphaGem 大大的脑译。超级感谢他。


Problem Description

The Fibonacci number sequence is a sequence of integers defined recursively in the following way :

F_0=0 \,\, F_1=1 \,\, F_n=F_{n-1}+F_{n-2}

The initial elements of this string are : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,\cdots

Byteasar investigates how different numbers can be represented as sums or differences of Fibonacci numbers. Currently, he is wondering how to find the smallest term of Fibonacci numbers (not necessarily different) as the sum or difference of these numbers is a given positive integer k . For example, numbers 10, 19, 17 and 1070 can be represented minimally, respectively, by means of 2,2, 3 and 4 Fibonacci numbers :

10 = 5 + 5 19 = 21 - 2 17 = 13 + 5 - 1 1070 = 987 + 89 - 5 - 1

Help Byteasar! Write a program which for a given positive integer k determines the minimum number of Fibonacci numbers needed to represent the number k as their sum or difference.

The number of queries p \leqslant 10 , and for every p the given intager k \leqslant 4 \times 10^{17}.


Solution

Introduction

A positive integer k is given . The number k is represented by a pair of multiset ( P_+ , P_- ) satisfying the condition:

\sum_{i \in P_+}{F_i} - \sum_{j \in P_-}{F_j} = k

The size of the representation will be the sum of the sizes of multiset P_+ and P_- . We will call one representation optimal if there is no other representation of the number k with a smaller size.

First step

Intuitive observation. First of all, we can accept without losing generality that all elements in P_+ and P_- multiset (or indexes of Fibonacci numbers in the representation) are not less than 2 . Next:

Observation 1. If there is an index i in the representation of Fibonacci numbers, such that i \in P_+ and i \in P_- , this representation is not optimal.

Obviously the representation described above can be improved by removing one occurrence of the index i from both multisets.

Although the terms of the task allow the use of one Fibonacci number more than once, it seems natural (GNAQ: well, is it really natural???) that in this way no optimal representation will be obtained. An example from the content of the task (10 = 5 + 5) seems to contradict it, because we can also represent the same number differently, this time without repetition: 10 = 8 + 2 .

Observation 2.  A representation in which any Fibonacci number occurs at least three times is not optimal. What’s more, there is an optimal representation for k in which every Fibonacci number occurs at most once.

Proof. To justify the above, simple bills based on the definition of the recurrent Fibonacci sequence are sufficient:

(1)\,\, 3F_i = F_{i-2} + (F_{i-1} + F_i ) + F_i =F_{i-2} + (F_{i+1} + F_i) = F_{i-2} + F_{i+2} (2)\,\, 2F_i = F_{i-2} + (F_{i-1} + F_i) = F_{i-2} + F{i+1}

By means of operation (1) each triple occurrence of the Fibonacci number can be replaced by the appearance of only two Fibonacci numbers, which of course reduces the size of representation. Such an operation can not, therefore, be feasible in any optimal representation. However, by means of operation (2), we can gradually eliminate all double occurrences of Fibonacci numbers from the representation, without diminishing the size of the representation. However, you should be more careful here, because after performing the operation (2) , the numbers F_{i-2} and F_{i+1} can occur in the representation many times, so we could potentially get an infinite sequence of deleting double occurrences. It is worth noting, however, that each such operation reduces the sum of the Fibonacci number indices present in the representation by one. This allows you to make sure that the second type of operation will always be done only finitely times and finally each Fibonacci number will occur in the representation at most once. (For example, if after performing an operation, the number of F_2 occurs twice, we can change its occurrences to F_3 and state that the representation was not optimal. )

From the previous considerations, it appears that we can focus on searching for sets (but not multisets) of P_+ and P_-, in which we use one Fibonacci number no more than once. In the further part of the description, we will only be interested in such representations.

What’s more, it is not difficult to find out that in the optimal representation of numbers, it is not worth using the Fibonacci numbers that are significantly larger than the number k. This statement is specified in the following observation. We omit the proof of observation – it will result in proof of correctness of the standard solution.

Observation 3. If F_m \leqslant k < F_{m+1} , then there is an optimal representation of the number k , in which the indexes of Fibonacci numbers do not exceed m + 1 .

Observation 4.  Let (P_+, P_-) be a representation of the number k . If for certain i it occurs:

(a)\,\, i \in P_+ \text{ and } i+1 \in P_+ \text{ or} (b)\,\, i \in P_= \text{ and } i+1 \in P_- \text{ or} (c)\,\, i \in P_- \text{ and } i+1 \in P_+ \text{ or} (d)\,\, i \in P_- \text{ and } i+2 \in P_+

then this representation (P_+, P_-) is not optimal.

Theorem 1.F_m \leqslant k \lt F_{m+1},那么最优分解要么满足 m\in P_+,要么满足 m+1\in P_+

Proof. 如果 k \leqslant 2,命题显然成立。假设对于一个 k\geqslant 3,命题不成立。我们取出 k 的任意一种最优分解 (P_+,P_-),并且设 z=\max P_+。根据假设,我们有 z\ne m \land z\ne m+1

​ 首先,我们假设 z\leqslant m-1。根据 Observation 4 的 (a) 一条,我们可以得到的最大的 k 值是

F_{m-1}+F_{m-3}+F_{m-5}+\cdots

​ 显然地,这一串的和小于 F_m。(考虑归纳法证明。)我们又有 F_m\leqslant k,这种情况不可能。

z\leqslant m-1 的情况被排除了。那么反过来,假设 z\geqslant m+2。同样根据 Observation 4 的 (b)\, (c)\, (d) 三条,我们可以得到的最小的 k 值是

F_{m+2}-F_{m-1}-F_{m-3}-F_{m-5}-\cdots>F_{m+1}

​ 然而,k\lt F_{m+1}。所以这种情况也不成立。命题得证。

这个定理大大减少了我们要讨论的情况。但是不止如此。考虑到 F_m\leqslant k \lt F_{m+1},我们可以得出 k-Fib_mF_{m+1}-k 都不超过 F_{m-1}(因为 F_{m+1}-F_m=F_{m-1})。

情况立即被大幅减少了。这也用另一种方式得出了 Observation 3 的结论(而且比它更强)。那么我们就得到了一种 O(2^{\frac{m}{2}}) 的做法:每一步枚举从 F_{m}F_{m+1} 中选择哪一个。

Theorem 2. Assume that F_m \leqslant k < F_{m+1} . If k - F_m \leqslant F_{m+1} -k, then there is an optimal representation in which m \in P_+ .

Proof. In the proof, it is enough to limit to the case when k \geqslant 3 . Let us mark a = k - F_m , b = F_{m+1} - k. Note that if in the representation of the number k we use the component F_m , then it will leave us the number a , and if we use F_{m + 1} , it will leave us b (or -b , but this is basically the same thing). It should therefore be shown that in the case where a<b , the number of components in the optimal representation of the number a is not greater than the number of components necessary to represent the number b. Note that a + b = F{m-1} . Consider two cases:

a <F_{m-3}, then b>F_{m-2}. By Theorem 1, we should use the F_{m-1} or F_{m-2} component to try to break down the number b. In the first of these cases, we remain with the number a to decompose (using two components, which is unprofitable, because the same situation could happen in one move). If we use the F_{m-2} component, we will have to continue to represent the number b-F_{m-2}, however, note that b-F_{m-2} = F{m-1}-a-F_{m-2} = F_{m-3}-a, we would have such a move also with a. In both cases, it is not worth splitting the number of b.
a \geqslant F_{m-3} , then F_{m-3} \leqslant a \leqslant b \leqslant F_{m-2}. Based on Theorem 1, we have two options to consider: the next component of the representation (both cases where we try to further decompose a and b) can be either F_{m-3} or F_{m-2}. However, a-F_{m-3} = F_{m-2}-b and F_{m-2}-a = b-F_{m-3}. Hence, with both a and b we have the same possibilities for further decomposition.

The final conclusion is as follows: the representation of the number a will always require no more operations than the representation of b. Thus it is safe to add m to the P_+ set and optimally represent what is left.

Theorem 3. Let us assume that F_m \leqslant k < F_{m + 1}. If k - F_m> F_{m + 1} - k , then there is an optimal representation in which m + 1 \in P_+ .

Proof. Analogous to the proof of theorem 2.

The last two propositions suggest for each k the greedy movement to be made. If before this movement occurs F_m \leqslant k < F_{m + 1} (and, let’s say, m> 4) occurs, then the remaining k' after the movement does not exceed \max (k - F_m, F_{m + 1} - k ), that is:

k' \leqslant \frac{F_{m+1}-F_m}{2}=\frac{F_{m-1}}{2}=\frac{F_{m-2}+F{m-3}}{2}<\frac{2F_{m-2}}{2}=F_{m-2}

This shows that after roughly \frac{m}{3} of the movements we get a full representation of the number k. Depending on how effectively we implement single movement, we will get a solution with time complexity O(m^2) = O(\log^2k) or O(m) = O(\log k). Each of these solutions, of course, achieves the maximal point.

USACO 2007MAR Face The Right Way

Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 6005 Accepted: 2777

Description

Farmer John has arranged his N (1 ≤ N ≤ 5,000) cows in a row and many of them are facing forward, like good cows. Some of them are facing backward, though, and he needs them all to face forward to make his life perfect.

Fortunately, FJ recently bought an automatic cow turning machine. Since he purchased the discount model, it must be irrevocably preset to turn K (1 ≤ K  N) cows at once, and it can only turn cows that are all standing next to each other in line. Each time the machine is used, it reverses the facing direction of a contiguous group of K cows in the line (one cannot use it on fewer than K cows, e.g., at the either end of the line of cows). Each cow remains in the same *location* as before, but ends up facing the *opposite direction*. A cow that starts out facing forward will be turned backward by the machine and vice-versa.

Because FJ must pick a single, never-changing value of K, please help him determine the minimum value of K that minimizes the number of operations required by the machine to make all the cows face forward. Also determine M, the minimum number of machine operations required to get all the cows facing forward using that value of K.

Input

Line 1: A single integer: N 
Lines 2..N+1: Line i+1 contains a single character, F or B, indicating whether cow i is facing forward or backward.

Output

Line 1: Two space-separated integers: K and M

Sample Input

Sample Output

Hint

For K = 3, the machine must be operated three times: turn cows (1,2,3), (3,4,5), and finally (5,6,7)
呐 题意就这样
然后我们考虑枚举k做一个O(n^3)显然很简单
优化?尺取法
枚举k,从左到右对背面的牛操作
考虑能够影响当前牛的操作,是当前减去(k-1)的区间
然后统计一下这个区间有多少个操作对2取模就可以得到当前判断。
这样用一个类似前缀和的东西维护就行了 见代码
O(n^2)

#洛谷 P1095 守望者的逃离

哇,好像是到目前为止为数不多的几次独立思考并没看题解而写出的dp……

美中不足的是,最后好像忘记初始化状态了……

题目描述

恶魔猎手尤迪安野心勃勃,他背叛了暗夜精灵,率领深藏在海底的娜迦族企图叛变。守望者在与尤迪安的交锋中遭遇了围杀,被困在一个荒芜的大岛上。为了杀死守望者,尤迪安开始对这个荒岛施咒,这座岛很快就会沉下去。到那时,岛上的所有人都会遇难。守望者的跑步速度为17m/s,以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术,可在1s内移动60m,不过每次使用闪烁法术都会消耗魔法值10点。守望者的魔法值恢复的速度为4点/s,只有处在原地休息状态时才能恢复。

现在已知守望者的魔法初值M,他所在的初始位置与岛的出口之间的距离S,岛沉没的时间T。你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛,若不能逃出,则输出守望者在剩下的时间内能走的最远距离。注意:守望者跑步、闪烁或休息活动均以秒(s)为单位,且每次活动的持续时间为整数秒。距离的单位为米(m)。

输入输出格式

输入格式:

输入文件escape.in仅一行,包括空格隔开的三个非负整数M, S, T。

输出格式:

输出文件escape.out包含两行:

第1行为字符串“Yes”或“No”(区分大小写),即守望者是否能逃离荒岛。

第2行包含一个整数。第一行为“Yes”(区分大小写)时表示守望者逃离荒岛的最短时间;第一行为“No”(区分大小写)时表示守望者能走的最远距离。

我们来看一下,显然要用时间作为状态(因为路程太大而不好转移)而状态必须是二维的(考虑到法术值对决策的影响)

输出了一下sizeof(f[300010][1010])/1024/1024,发现有一个G,怎么办呢?

考虑一个贪心思想,不用白不用啊……

于是就可以设计状态了。我一开始居然想直接f[300010]转移……写着写着发现没法转移。

f[i][j]表示前i秒j个ep最远距离,顺便Notepad++万岁

 

手推一下样例,

exp1
39 200 4
180m 9ep -> 前3s
180m 13ep -> 第4s / 197m 9ep -> 第4s
died.

exp2
36 255 10
180m 6ep -> 前3s
180m 10ep -> 第4s
240m 0ep -> 第5s
257m 0ep -> 第6s

Yes-6s

试着写写方程,写到一半突然相当初始m会很大的问题……于是有了这个……

c1是计数器。

然后试着写写方程,转移一发

为什么要j<=20呢?显然j>10的时候必须直接+17,+60并耗魔法一定不会影响决策……因为不用白不用,用了一定节省时间,所以最优解一定在[0,10)区间里取,f[i][j] (j>=10)再从f[i-1][j+10]转移就没意义了,所以j上限应该是19,手癌就打了个20.

最后别忘记更新一波初始状态,还是注意j<=20

所以这里是全部的代码,注意最后出解j并不影响,所以找到一个直接return 0

但是无解j会影响,显然j<10更优,不用白不用嘛

 

[洛谷 | 1012] 拼数

20170523 update 你知不知道这个题可以用贪心!!!!(指着我自己) 

98年的NOIp提高就这么难了吗??

这个玩意回溯很费劲啊……
不过就是个单纯的全排列问题(据说某神犇小学就会打全排列代码……)

调了好久,发现是memset惹的鬼,往递归里加了个变量就OK了
代码·(对于我这种蒟蒻来说一遍AC是多么的困难……)