BZOJ 3632 | 蒙特卡罗随机化

大概就是让你求一般图的最大团。

直接随机化。然后我们把点序当 PEO 打乱,假装第一个点在最大团里。

然后就判一下其余点的连通就好了。

 

UOJ #163 [THU2015] 新式计算机 | 如何造计算机

所以如何造计算机?

代码带一堆缩进和注释。。不过我想做这题的人水平也不会低到去抄我的破烂代码。

所以重心还是放在讲实现思路上。

#1

只要你读完题了, #1 比较显然……

#2

S[  E] 这种组合搞一下事情就好了。4 的倍数满足最后两位都是 0 ,所以每次右移+判断。

2.ans

#3

赋值的大概思路是判一下当前 (0,0) 的结尾位是什么

然后跑过去 l 和 I 一下,把一位赋给 (2,3)

然后回去 r 把下一位移下来

这里有两个高度套路的东西

S[    P] 是如果最后一位是 1 则怎么样,注意指针在里面移动都要再移回来。

SP[   P] 是末位为 0 的版本。

注意有个问题是赋完值要 v ……

代码大概是

 

 

 

 

 

 

 

 

BZOJ3456 | 有标号无向连通图计数

这玩意可以搞出生成函数然后大力卷积。。直接设 f(n) 为答案,设 g(n)n 个点有标号无向图个数

\text{ans mod 1004535809 }\gets \text{这玩意是个质数, 原根是 3 } \text{ans}=f\left( n \right) g\left( n \right) =2^{\left( \begin{array}{c} n \\ 2 \end{array} \right)} \text{枚举 1 所在的连通块大小} g\left( n \right) =\sum_{i=1}^n{f\left( i \right) \left( \begin{array}{c} n-1 \\ i-1 \end{array} \right) g\left( n-i \right)} 2^{\left( \begin{array}{c} n \\ 2 \end{array} \right)}=\sum_{i=1}^n{\frac{f\left( i \right) 2^{\left( \begin{array}{c} n-i \\ 2 \end{array} \right)}\cdot \left( n-1 \right) !}{\left( n-i \right) !\left( i-1 \right) !}} \frac{2^{\left( \begin{array}{c} n \\ 2 \end{array} \right)}}{\left( n-1 \right) !}=\sum_{i=1}^n{\frac{f\left( i \right)}{\left( i-1 \right) !}\frac{2^{\left( \begin{array}{c} n-i \\ 2 \end{array} \right)}}{\left( n-i \right) !}} \text{生成函数 }F\left( x \right) ,G\left( x \right) ,H\left( x \right) H\left( x \right) =\sum_{i=0}^{\infty}{\frac{2^{\left( \begin{array}{c} i \\ 2 \end{array} \right)}}{\left( i-1 \right) !}x^i} F\left( x \right) =\sum_{i=0}^{\infty}{\frac{f\left( i \right)}{\left( i-1 \right) !}x^i} G\left( x \right) =\sum_{i=0}^{\infty}{\frac{2^{\left( \begin{array}{c} i \\ 2 \end{array} \right)}}{i!}x^i} \therefore H\left( x \right) =F\left( x \right) \ast G\left( x \right) F\left( x \right) =H\left( x \right) G^{-1}\left( x \right) \,\,\left( \text{mod }x^{n+1} \right)

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.

毒瘤微积分(有限微积分|离散微积分)

毒瘤排版,有空再修

 

今天下午见识了毒瘤微积分,来写一下……

虽然具体数学上讲的蛮好的

以下介绍的运算都是对整数域上有定义的函数适用

( 当然,如果定义域不包含整数集,但是在关注的区间内的所有整数上都有定义,那么也可以)

(相当于微积分中的”连续”)

首先要搞清楚什么是斯特林数。后面我闲起来再写文吧,这一阵子压的文有点多,先不介绍了。各大 Wiki 上讲的应该都挺好。

然后我们就把公式先搬过来不管了:

x^n=\sum_{i=0}^n{\left\{ \begin{array}{c} n \\ i \end{array} \right\} x^{\underline{i}}}

离散意义下的所谓“微分”(求导)

感觉很扯淡吧……都离散了还怎么求导 ?

其实根本不是求导那一套(不过确实有关系)

离散意义下只要“连续”就可导,那么定义前向差分算子 \Delta(前向差分简称差分)

\Delta f(x) \xlongequal{\mathrm{def}} f(x+1) - f(x)

或者更广泛的说

\Delta_{h} f(x) \xlongequal{\mathrm{def}} f(x+h) - f(x)

以前傻子的我一直以为差分就是序列上扫一遍减一减……

离散意义下的“积分”

在这边我们先说和“定积分”相像的部分。

无限微积分里面有个算子 D 是用来求导的,那么他的逆算子(积分算子) 是 \int  。

相似地,差分算子的逆是 \sum

离散意义下也有类似的基本定理:

g(x)=\Delta f(x) \Leftrightarrow \sum{g(x) \delta x } = f(x) + C

这里 \sum{g(x) \delta x } g(x) 的不定和式,是差分等于 g(x) 的一个函数类。而 C 是满足 p(x+1) = p(x) 的一个任意函数 p(x) 。这样差分的时候 C 就没了。

然后定积分就变成和式了:

\sum_{a}^{b}{g(x) \delta x } = f(x) \mid_{a}^{b} = f(b) - f(a)

这里注意他是区间 [a,b) 上的求和( \sum_{a\leqslant i < b}{g(i)} ,右半边是开的。


离散意义下的差分公式

这类玩意是最有用的,类似求导公式。

比如说我给你个 x^k 。现在我们知道他的导数显然是 kx^{k-1}

但是这不适用于有限微分。不过我们有下降幂这个东西:

\Delta(x^{\underline{k}}) = kx^{\underline{k-1}}

唔,具体推导大概是

\Delta(x^{\underline{k}}) = (x+1)^{\underline{k}} - x^{\underline{k}} = (x+1-(x-k+1))x^{\underline{k-1}} = kx^{\underline{k-1}}

幂级数怎么搞?还记得开头的公式么?

x^n=\sum_{i=0}^n{\left\{ \begin{array}{c} n \\ i \end{array} \right\} x^{\underline{i}}}

然后包括指数函数

\Delta k^x = k^{x+1} - k^x = (k-1) k^x

这公式非常简单,轻松易懂…

别的类的也都可以类似地推出来

有意思的是 \Delta 2^x = 2^x ,而 2 = \lfloor e \rfloor ……


离散意义下的求导法则

看,基本都是成立的:

\Delta \left( f\left( x \right) +g\left( x \right) \right) =f\left( x+1 \right) +g\left( x+1 \right) -f\left( x \right) -g\left( x \right) =\Delta \left( f\left( x \right) \right) -\Delta \left( g\left( x \right) \right)

如果预先定义一个位移算子 E 使得满足 Ef\left( x \right) =f\left( x+1 \right) 的话

\Delta \left( f\left( x \right) g\left( x \right) \right) =f\left( x+1 \right) g\left( x+1 \right) -f\left( x \right) g\left( x \right) =\left( f\left( x+1 \right) -f\left( x \right) \right) g\left( x+1 \right) +\left( g\left( x+1 \right) -g\left( x \right) \right) f\left( x \right) =\Delta f\left( x \right) Eg\left( x \right) +\Delta g\left( x \right) f\left( x \right)

 

 

 

 

 

 

 

 

 

 

CQOI2005 三角形面积并

计算几何 × 扫描线入门题

首先把线段都搞出来,然后求所有线段交点的横坐标(包括三角形顶点)并且去重。

也就是求出所有线段交点的 x 轴垂线。

然后把数据排序,枚举相邻的一对垂线,这个时候差不多是这样的

沃日,这图太大了。。 iPad Mini 2 的 Retina 屏真带劲。。

然后你会发现枚举的垂线中间夹着的是若干梯形。假设枚举的是 x_1,x_2 ,那么我用 \frac{(x_1+x_2)}{2}=0 这个“中间的直线”去切割这截出来的一大堆梯形。

显然同一个三角形在 x_1,x_2 之间的部分会被这个直线穿两次,如果我们把下面那次看做一个 ( ,上面的看做 ) ,这就是求所有 至少被一对括号包括起来 的部分的长度。然后用这个长度乘以 x_2-x_1 就是这部分的答案。

还有一点细节是比如像绿色那货,它有条直线是和 x 垂直的,因为特判难写难调,精度要求不高,那条直线直接给他加上一个 OFFSET 带走。比如变成斜率 k=10^{-5} 什么的。

代码。注意精度问题。