AFAIK

Valar Morghulis

最近做的两道题。

感觉很囧啊,数学全忘了啊。

Google-Codejam-Round3-D

果然 GCJ 滚粗是必然的。

考虑一个事实:在 \(i\)\(j\) 这一段的一个位置 \(k\) ,如果 \(k\). ,那么 \(i\)\(k\)\(k+1\)\(j\) 是独立的,即,如果某次一个人进入摩天轮时,他遇到的第一个格子在 \(i\)\(k\) 之间,那么他最后占领的格子一定会在 \(i\)\(k\) 中而不会在 \(k+1\)\(j\) 中。

于是就倒着来思考。首先明显的在最后只剩下一个空的时候,期望是固定的,为 \(\frac{n - 1}{2}\)

所以我们枚举最后一个空的位置,然后转为序列上的问题。

序列上的问题有明显的子结构:令 \(f_{i, j}\) 表示原序列的 \(i\)\(j\) 这一段,经过若干次操作后,除位置 \(j\). 以外,其余的元素均为 X 的期望代价, \(p_{i, j}\) 表示概率。令 \(P(i, j, k)\) 表示 \(i\)\(j\) 这一段, \(j\) 一直是 . 的,最后一个转为 X. 的位置为 \(k\) ,其余的都是 . 的概率。

\[P(i, j, k) = \binom{Lk + kR}{Lk} (\frac{k+1-i}{j+1-i})^{Lk+1} (\frac{j-k}{j+1-i})^{kR} p_{i, k} p_{k+1,j}\]

其中 \(Lk\) 表示初始状态中 \([i, k - 1]\). 的个数, \(kR\) 表示 \([k+1, j-1]\). 的个数。由于最后一个转为 X.\(k\) ,所以我们要考虑到前 \(Lk + kR\)X. 的顺序,所以要乘以一个二项式。再乘以有 \(Lk + 1\) 个落在 \([i, k]\) 的概率,以及又 \(kR\) 个落在 \([k+1,j]\) 的概率,最后乘以合法的概率 \(p_{i, k} p_{k+1,j}\)

所以得到 \(f\)\(p\) 的转移如下:

\[ \begin{array}{rcl} p_{i, j} & = & \sum_{k = i}^{j - 1} P(i, j, k) \\ f_{i, j} & = & \frac{1}{P_{i, j}}\sum_{k = i}^{j - 1} P(i, j, k) (f_{L, k} + f_{k+1, R} + n - \frac{k-i}{2}) \\ \end{array} \]

注意 dp 时的 \(i\) 可能大于 \(j\) ,因为这是环状,所有计算长度的公式都需要进行一定的修正。

TopcoderOpen-Round3-Level3

\(\newcommand{\stirone}[2]{\left\{ { #1 } \atop { #2} \right\} }\) \(\newcommand{\stirtwo}[2]{\left[ { #1} \atop { #2} \right] }\) jzp 的神题,我表示被吓傻了……

我还是直接上 传送门 吧……我就写写我的感觉 →_→

主要思想

感觉非常牛逼啊。

  1. 用容斥写出答案的表达式
  2. 观察这个表达式和 \(\Delta^n f(x)\) 很像,于是用 \((-1)^n \Delta^n f(x)\) 来求答案
  3. 具体化 \(f(x)\) 。如何求 \(\Delta^n f(0)\) ?考虑写成 \[f(x) = \sum a_i x^i = \sum b_i \binom{x}{i}\]
  4. 可以得到 \[\Delta^n f(0) = b_n\] 所以求 \(b_n\) 就好了……

一些细节

考虑如何求 \(b_n\) ?利用 \[x^n = \sum_{k=0}^n k!\stirone{n}{k} \binom{x}{k}\] 可以得到 \[b_n = n! \sum_{k = n} \stirone{k}{n} a_k\]

于是我们只要求 \(a\) 就好了。利用 \[\binom{n}{k} = \sum_k \stirtwo{n}{k} (-1)^{n-k} x^k\] 可以拆开一个 \(n\) 中含有未知数的二项式。

如何求两类 stirling 数?题目中说了 \(m - n \leq 10^3\) ,于是我们要在 \(m - n\) 相关的的时间内求出所有涉及到的 stirling 数。假如我们要求 \(\stirone{n}{m}\) ,当 \(n - m\) 特别小时,考虑 \(\stirone{n}{m}\) 的实际意义,表示将 \(n\) 个数分成 \(m\) 个环的方案数,至多有 \(n - m\) 个环的大小不为 1 ,这些环的大小之和至多是 \(2(n - m)\) ,于是考虑 \(f(i, j)\) 表示 \(j\) 个大小大于 2 的环的总大小为 \(i\) 的方案数,可以得到一个和 stirling 数类似的递推。

从 xiaodao 空间上看到的……

感觉蛮好玩的于是就试了试。xiaodao 最后的那个连乘真的没有想到,我只会暴力积分……

Problem

\(d\) 维单位球体中随机选 \(n\) 个点,到球心 \(k\) 远点距离球心的期望是多少?

Solution

\(n\) 个点,随机选一个为 \(k\) 远点,再选 \(k - 1\) 个点为前 \(k - 1\) 远点,方案数为 \(\binom{n}{1, k - 1}\)

维基百科\(d\) 维单位球体的体积是 \[V_d(R) = \frac{\pi^{\frac{d}{2}}R^d}{\Gamma(\frac{d}{2}+1)} = C_d R^d\] 其中 \(C_d\) 为与 \(d\) 相关的常数。

根据“维”的定义,我们有距离为 \(r\) 的点的密度为 \[\rho(r) = \frac{V'_d(r)}{V_d(1)} = d r^{d - 1}\]

于是 \(k\) 远点的期望是: \[\begin{array}{rl} & \binom{n}{1, k - 1} \int_0^1 r \rho(r) (r^d)^{k-1} (1 - r^d)^{n-k} \mathrm{d} r \\ = & d \binom{n}{1, k - 1} \int_0^1 r^{kd} (1 - r^d)^{n-k} \mathrm{d} r \\ = & nd \binom{n - 1}{k - 1} \int_0^1 r^{kd} \sum_{i=0}^{n-k} \binom{n-k}{i} (-r^d)^i \mathrm{d} r \\ = & nd \binom{n - 1}{k - 1} \sum_{i=0}^{n-k} \binom{n-k}{i} (-1)^i \int_0^1 r^{kd+id} \mathrm{d} r \\ = & nd \binom{n - 1}{k - 1} \sum_{i=0}^{n-k} \frac{\binom{n-k}{i} (-1)^i}{kd+id+1} \\ \end{array} \]

这样做的值应该是没错的,但是精度误差特别大 >__<

于是我们还需要继续化简……

我对如何操作二项式已经忘得差不多了,于是无意间拿起 CM 居然看到了这货:

对于函数 \(f(x)\) ,定义 \(\Delta^{(0)} f(x) = f(x)\) 。然后可以定义 \(\Delta^{(n)} f(x) = \Delta^{(n - 1)} f(x + 1) - \Delta^{(n - 1)} f(x)\) ,然后可以得到: \[\Delta^{(n)} f(x) = \sum_{k} \binom{n}{k} (-1)^{n-k} f(x+k)\]

注意到 \(\Delta^{(n)}f(x)\) 的表达式与要化简的那个式子中的比较像,考虑令 \(f(x) = \frac{1}{x}\) , 用 \((-1)^{n-k} \Delta^{(n - k)} f(x)\) 来代替 \(\sum\)

\[\begin{array}{rl} & nd \binom{n - 1}{k - 1} \sum_{i=0}^{n-k} \frac{\binom{n-k}{i} (-1)^i}{kd+id+1} \\ = & n \binom{n - 1}{k - 1} (-1)^{n-k} \sum_{i=0}^{n-k} \frac{\binom{n-k}{i} (-1)^{n-k-i}}{k+i+\frac{1}{d}} \\ = & n \binom{n - 1}{k - 1} \Delta^{(n - k)} f(k+\frac{1}{d}) (-1)^{n-k} \\ \end{array}\]

由于 \(f(x) = \frac{1}{x}\) ,我们又有: \[\begin{array}{rcl} \Delta^{(1)} f(x) & = & \frac{-1}{x^{\bar{2}}} \\ \Delta^{(2)} f(x) & = & \frac{2}{x^{\bar{3}}} \\ \Delta^{(3)} f(x) & = & \frac{-6}{x^{\bar{4}}} \\ \end{array}\]

其中 \(x^{\bar{k}} = \prod_{i = 0}^{k - 1} (x+i)\)

可以找出规律(然后归纳法)\[\Delta^{(n)} f(x) = \frac{(-1)^n n!}{x^{\bar{n+1}}}\]

继续代入: \[\begin{array}{rl} & n \binom{n - 1}{k - 1} \Delta^{(n - k)} f(k+\frac{1}{d}) (-1)^{n-k} \\ = & n \binom{n - 1}{k - 1} \frac{(-1)^{n-k} (n-k)!}{(k+\frac{1}{d})^{\bar{n-k+1}}} (-1)^{n-k} \\ = & \frac{n!}{(k-1)! (k+\frac{1}{d})^{\bar{n-k+1}}} \\ = & \frac{n!}{(k-1)! \prod_{i=0}^{n-k} (k+i+\frac{1}{d})} \\ = & \frac{\prod_{i=0}^{n-k}(n-i)}{\prod_{i=0}^{n-k} (k+i+\frac{1}{d})} \\ = & \prod_{i=0}^{n-k} \frac{(n-i)}{k+i+\frac{1}{d}} \\ = & \prod_{i=k}^{n} \frac{i}{i+\frac{1}{d}} \\ = & \prod_{i=k}^{n} \frac{di}{di+1} \\ \end{array}\]

这样化简的结果和 xiaodao 的方法是一样的……真是太开心了 @_@ ……

Epilogue

这推导真是恶心死我了……

学的东西都忘光了怎么破……

写的公式太多了感觉会跪? @dyh 求查错……

Markdown 里的替换

大概是为了防止 TeX 里面的 _^ 被转义而写的。由于要改多次……还是先记下来吧。

\([^\]\)^ -> \1\^
\([^\]\)_ -> \1\_

好久没做题了,前一段时间旅游了一小会儿然后趁着 **USC 的机会溜回家开始了长达七天的暑假生活。

闲着无聊做了一下 PE-432 ……

Problem

\[S(n, m) = \sum_{i=1}^{m} \phi(n \times i)\]\(S(510510, 10^{11})\)

Solution

\(n = pq\) ,且 \(p\) 为质数,有 \[ S(n, m) = (p - 1) S(q, m) + S(n, \lfloor \frac{m}{p} \rfloor)\]

于是我们只要计算 \[S(1, m) = \sum_{i = 1}^m \phi(i)\] 即可。

线性筛法可以去死了。我们可以采用 @dyh 的理性愉悦 \(O(n^{\frac{2}{3}})\) 的方法:

\(S_f\) 表示函数 \(f\) 的前缀和函数,即 \[S_f(n) = \sum_{i = 1}^n f(i)\] 。我们要求 \(S_{\phi} (n)\)

\(g_n = \sum_{d|n} f_n\) 于是有 \[S_g(n) = \sum_{i = 1}^n \sum_{d|i} f(d) = \sum_{i=1}^n S_f(\lfloor \frac{n}{i} \rfloor)\] 这个等式只要注意到每个 \(f(i)\) 被加的次数都是 \(\lfloor\frac{n}{i}\rfloor\) 就好了。

如果我们能够快速计算 \(S_g(n)\) ,就可以利用 \[S_f(n) = S_g(n) - \sum_{i = 2}^n S_f(\lfloor \frac{n}{i} \rfloor)\] 来计算 \(S_f(n)\) 了。

\(f(n) = \phi(n)\) 时, \(g(n) = \sum_{d|n} f_n = n\)\(S_g(n) = \frac{1}{2} n(n+1)\) 。我们用筛法算出 \(i \leq n^{\frac{2}{3}}\) 时的 \(S_f(i)\) ,其余的暴力记忆化递归做下去,复杂度是 \(O(n^{\frac{2}{3}})\)

我一开始把 \(m\) 看成了 \(10^{14}\) 跑了 20min 才跑出来, \(m = 10^{11}\) 时只要 3s 就可以了……

这几天都忙着高考送考(以及考后狂欢)去了。一年毕业季,一年别离时。

(祝在高考这天生日的同学年年有今日,岁岁有今朝 23333)

IPSC 2013

IPSC 的题感觉蛮好玩的,但是非常难……

我一开始还没组队,然后 dyh 拉我组了一队,然后我就把 xlk 拉了进去。事实证明把 xlk 拉进去是个非常正确的决定。

practice

P

easy:不说了 - -

hard:看了 solution 才发现坑爹啊……居然连 l33t 语都出现了……我还是不吐槽了 >__<

Q

easy: 显然很水 - -

然后我就不会 hard 了 - -

hard:显然平均数是可以被忽略的。我们要构造的是方差,也就是找到一组 \(a_{1, \dots, n}\) 使得 \(\sum a_i = 0\)\(\sum a^2_i = nv\)

考虑如下构造:序列长度为 \(2n\) ,且 \(a_{2k - 1} = -a_{2k}\) ,那么第一个限制显然就满足了,第二个限制直接贪心就好。

R

easy 也不难,(a-z)*25+a 就可以了。

然后 YY 了好久的 hard 没想法。于是我把很小的 n 的解的长度打出来放到 OEIS 上搜,发现了 这个序列 。OEIS 上还顺便提了一下某种较优解的构造方法,然后就没有然后了。

题解也是用的这种构造……

formal contest

完全不会啊亲……

所以你是来看题解的话是找不到任何东西的哈哈哈哈。

待我先去研究一番题解……

A

其实我没看题 2333

B

看了一眼后发现……这不是某个经典结论吗亲……

这个题我曾经 YY 过一个证明方法:令一个数 \(n\) 的势能 \(\phi(n) = \frac{n^2}{2}\) 。那么将 \(n\) 分成 \(x + y = n\) 两份时,释放的能量为 \(\phi(n) - \phi(x) - \phi(y) = xy\) ,这表示将 \(n\) 分成若干个数,释放的能量与具体分法是无关的。那么将 \(n\) 分成若干个 1 ,无论怎么分,释放的能量总为 \(\phi(n) - n \phi(1) = \frac{n(n - 1)}{2}\)

我以前一位同学 YY 出另外一个证法:考虑图 \(K_n\) ,把 \(n\) 分成 \(x+y = n\) 对应着图上选择两个点集,大小分别为 \(x, y\) ,并将这两个点集之间的 \(xy\) 条边的删掉。那么初始的时候有 \(\frac{n(n-1)}{2}\) 条边,结束的时候没有边( \(n\) 个孤立的点),所以一共删了 \(\frac{n(n - 1)}{2}\) 条边。

C

easy :你把函数 t 的值打出来,可以发现 \(t(n) = \phi(n) + 1\)\(\phi\) 为欧拉函数。

然后就可以直接跑了。这样会输出一个指令,然后照着这个指令依次做下去就好了。

为啥我和 dyh 都跑不出指令,就 xlk 可以?

hard :可以得到当 \(b > 500\) 时, \(g(b)\) 一定是 1 。然后每次求 \(g\) 就可以 \(O(1)\) 求,然后会输出一堆点的坐标。然后就不会了……

题解如是说:把这些点的坐标全部画出来,然后可以得到一个二维码,用手机扫描可以得到一句话:88767->7123398 ,然后就是 easy 的节奏了。

D

easy: 就是昨天 R 的 checker 。首先我们想怎样检验一个排列是否出现过?肯定是每次选择最近的一个下一个字母。所以这样就可以 dp 了。 \(f_S\) 表示集合 \(S\) 中的所有元素按照一定顺序全部出现,所有的顺序中,最后一个字母出现的位置最靠后的一个位置是什么。转移的话枚举下一个字母就好了。

我写的比较渣,跑了 10min 才跑出来 >__<

hard:如果继续按照这个思路去做的话, \(f_{S, t}\) 表示集合 \(S\) 的排列中,最后一个元素出现的位置是 \(t\) 的方案数,内存会受不了 >__< 然后我也不会了...

E

居然没人出。。。

F

首先注意到,每次查询有 50+% 的正确率。

easy:三分。我们将序列分成 LMR 三段,每次查询 25 次 L 和 M 的关系,25 次 M 和 R 的关系,然后就可以确定在 \(L, R, M\) 中的哪一个,4 次就可以找到了。

hard:不会……

题解:我的理解是每次随机比较任意 83 枚与 83 枚,最后枚举那个是答案,用概率最大的? @dyh 你怎么看……我都不好说什么了。

G

参见 Keshavarz-Kohjerdi, Fatemeh, Alireza Bagheri, and Asghar Asgharian-Sardroud. ”A linear-time algorithm for the longest path problem in rectangular grid graphs.” Discrete Applied Mathematics 160.3 (2012): 210-217.

呵呵呵呵呵呵

H

看了半天的 pdf 没找到答案啊……

easy:看网页源代码去 - -

hard:看 response header. 随便设置个包含 chocolate 的 cookie 发送过去,然后就会有一个问题,然后再发送一个 request ,修改 request header 使之包含答案,然后 response 里面就有答案了。

I

。。。

J

easy:xlk 如是说:由于 NAND gate 是 unversal unary gates ,J1。。随便取两个变量 与非 或者是 或非 ,然后就有六种了。然后看xy一不一样,如果一样返回xz的与非,否则随便返回一个。

hard:我想了一下,似乎可以直接爆搜所有函数?想起来都觉得好麻烦啊 >__<

题解如是说:不满足以下五个条件中的任意一个的函数就是 universal 的:

  1. 如果输入全是 1 那么输出 1
  2. 如果输入全是 0 那么输出 0
  3. 如果把某个输入的 0 改为 1 ,则输出的结果不会由 1 变为 0
  4. 如果把所有输入取反,那么结果也会取反
  5. 每个输入要么总与输出相关,要么总与输出无关

K

easy:分开计算,直接乘起来。

hard:直接考虑下来的一步,如果这一步有 1 个格子,则上去有 1 种方案;有两个格子,则上去有 2 种方案;etc。然后还是递推一下就好。

L

easy:手玩吧哈哈哈哈

hard:不会……

我居然没去看看 hard 的形状,罪过罪过。

这就是个 3-SAT 问题啊……然后自己写个程序爆搜或者直接找第三方程序吧。

我以前一直很喜欢玩这种东西的啊,居然没发现 >__<

M

不会

problem 在此

根据 \(E(\sum X_i) = \sum E(X_i)\) 可以知道答案就是每个格子为白色格子的期望和。

对于第 \(1 \leq i \leq n\) 个格子,我们知道某次被翻转的几率是 \[p = \frac{2 i (n + 1 - i) - 1}{n^2}\]

\(f_k\) 表示 \(k\) 次翻转后仍然是白色的概率,可以得到 \[f_0 = 0, f_{k+1} = (1 - p) f_k + p (1- f_k)\] 可以化出 \[f_{k+1}- \frac{1}{2} = (1 - 2p) (f_k - \frac{1}{2})\] 于是有 \[f_k = \frac{1}{2}(1 + (1 - 2p)^k)\]

如果暴力做的复杂度是 \(O(10^{10} \log 4000)\) 。然后一个很小的优化是如果 \(1 - 2p \leq 0.99\) ,那么 \((1 - 2p)^k \leq 10^{-18}\) ,直接忽略不计了……

然后要跑 3min 才跑得出来。

如果有更好的做法求告诉我 >__<

(版面不够了于是只好用 display equation 来充版面么 LOL)

说好的 AFK 呢,还是忍不住参加了。

Solution

250 pts

慢慢码代码。不多说。

500 pts

考虑一条边 Ai-Bj 对答案的贡献。显然它一定会在一个环上,而且环的形状一定是 Ai --- At - Bs --- Bj ,可以得到 |Ai --- At| + |Bs --- Bj| = K - 2

然后枚举 \(i\) ,枚举 \(j\) ,统计所有到 \(i\) 距离为 \(a\) 的点数目为 \(cnt1_a\) ,统计所有到 j 距离为 b 的点数目为 \(cnt2_b\) 。那么 Ai - bj 对答案的贡献为 \(\sum_{a+b = K-2} cnt1_a cnt2_b\)

注意到一个环被算两次,除个 2 就好。

900 pts

由于每一列至多只能进行一种操作,所以我们 \(2^m\) 枚举每一列只允许哪一种操作。

假如我们知道了第一行的每个操作,那么我们可以依次推出剩下的每个格子的操作,因为第二行的操作要满足第一行的结果为 B ,所以第一行的操作也确定了,依次递推下去,可以知道后面每行的操作。我们只需要验证最后一行是否仍然满足要求即可。

所以在 \(2^m\) 枚举每一列允许哪种操作后,再枚举第一行每个操作。如果这里再 \(O(2^m)\) 枚举显然会 T 。考虑到这些操作应该是同一种操作,所以进行操作的若干个格子一定是进行同一种操作的若干个格子,我们只需要枚举两个集合的子集就好了。

总时间复杂度为 \(O(nm 3^m)\)

nonsense

一进来看到一个 ID 为 just.for.fun 。一看是 NFLS 的,但是不知道是谁。看命名风格有点像 blue.boy ,最后发现果然是 JZP 。亚历山大 >_<

最后 room #2, #1 显然是 just.for.fun

Division #33 涨了 rating 。这真是极好的。

GCJ 应该是可以骗到一件衣服的 - -

POJ 的奖品居然没骗到 >__< 做到一半机房断网了于是 #11 真是不能更爽

Google Codejam Round 2

A

一开始看错题了……

显然最后每个人的路线是不相交的,允许包含。于是上车点与下车点构成了括号序列。

然后用栈处理一下就好。

B

假设第一步是二分吧(感觉有不用二分的方法),那么我们的问题就是判定一个人最好/最坏排名是多少。

共有 \(T\) 个人,令 \(f(x, T)\) 表示能力排名为 \(0 \leq x < T\) 的人最差排名是多少。考虑 \(x = 0\) 的情况,易得 \(f(x, T) = T - 1\) 。否则,最差情况下, \(x\) 会被打败,而且下一轮中 \(x\) 的能力值排名是所有可能的值中最大的。 \(x\) 之前有 \(x\) 个人比他强,进入败者组的人至多有 \(\lfloor\frac{x - 1}{2}\rfloor\) 个人,所以有 \(f(x, T) = \frac{T}{2} + f(\lfloor\frac{x - 1}{2}\rfloor, \frac{T}{2})\)

最好情况类似,令 \(g(x, T)\) 表示 \(x\) 最好可以打败多少人,可以得到当 \(x = T - 1\) 时有 \(g(x, T) = 0\) ,否则有 \(g(x, T) = \frac{T}{2} + g(\lfloor\frac{x + 1}{2}\rfloor, \frac{T}{2})\)

python 真是极好的。

C

根据 LIS 和 LDS 序列可以构出一个拓扑图,一条有向边 \(s \to t\) 表示 \(x_s < x_t\) 。我们要求这个拓扑图的一个拓扑序列,满足 1 出现的位置尽量靠前,在此基础上, 2 出现的位置尽量靠前 etc 。

直接上伪代码吧 = =||

def dfs(x) : # 要使得 x 尽量先出来
    if x 已经在拓扑序中 :
        return
    ys <- 所有要使得 x 出来必须出来但是还未出来的点
    sort ys increasingly
    for y in ys :
        dfs(y)
    Q += [x]

Q = []
for i from 1 to n :
    dfs(i)
# 然后 Q 就是要求的拓扑序

这样做显然是 \(O(n^2)\) 的。

其实有个更好写的 \(O(n \log n)\) 的方法。反向建图,每次选择标号最大的点出来,相当于求出逆拓扑序。

D

计算几何,哈哈哈哈。

POJ Challenge Beta 1

有中文题面,这真是极好的。

A

\(a(a + b) = c^2\) 可得 \(a = \frac{\sqrt{b^2 + 4c^2} - b}{2}\) ,可以发现只要 \(\sqrt{b^2 + 4c^2}\) 为整数即可,奇偶性可以保证。

\(b^2 + 4c^2 = d^2\)\(b^2 = (d - 2c)(d + 2c)\) 。易知 \(d - 2c \leq 4\) ,所以枚举 \(d - 2c\) ,看看是否存在整数 \(c\) ,如果存在 \(c\) 就可以直接求 \(d\) 然后求 \(a\) 了。

为啥 \(d - 2c \leq 4\) ?当 \(b\) 为奇数时显然 \(d - 2c = 1\) ,当 \(b\) 为偶数时 \(d - 2c = 2, d + 2c = \frac{b^2}{2}\)\(d - 2c = 4, d + 2c = \frac{b^2}{4}\) 中至少有一组可行解。(其实继续分析下去可以直接找到规律,只不过这样已经很好写了于是就直接写了。)

B

一个 \(O(n^3)\) 的 dp 是显然的, \(f_{i, j}\) 表示区间 \([i, j]\) 的最优解,枚举根进行转移。

然后我就不会了 = =

不过我是怎么在 20min 过的呢……因为我看到有人(wkn ?)在 15min 过了,于是觉得这个题应该是可做的,于是猜了个结论: \(f_{i, j}\) 的根只可能是 \(i\)\(j\) 。随机生成了几组极限数据试试发现是对的……然后就没有然后了……

感觉如果按照 dp 的一般优化思路去想的话应该也是可做的。

C

如果一个数同时出现在两组限制中,那么这两组限制必定是连续的,也就是最后的限制就是若干条链,每条链分别搞搞就好了。

感觉好多细节啊不想写啊。你要牛逼就写 PQ 树去吧哈哈哈哈。

D

std 的想法大概是 dp 吧, \(f_{i, j}\) 表示最后一条线段是 \(i \to j\) ,转移的话利用极角序优化一下就好了。

我写的另外一种方法,但是 WA 了。

考虑枚举最低点。两边点到这个点的斜率递增,求出斜率后直接 LIS 。为啥我会错……难道老了连 LIS 都不会了么 T_T

E

果的数据结构题。

依次 dfs 每个点。对于 \((a, b)\) ,我们要求所有的 \((c, d)\) 数目使得 \((c, d)\) 能够覆盖 \((a, b)\) ,我们在 dfs c 的时候在 d 点放个标记,那么在 dfs a 的时候就相当于查询 b 到根的路径上有多少个标记。显然 dfs 序 + 树状数组。

F

显然是原题。

半平面交是 \(O(n^2 \log n)\) 的吧。似乎我估错复杂度以为是 \(O(n^3 \log n)\) 的就没写了 →_→

模拟退火 balabala 不知道怎么样。你要牛逼就写 Voronoi 图去吧哈哈哈哈。

似乎这几天刷水刷的比较多 >_<

似乎最近卖萌比较多 >__<

Problem

在一个单位圆上随机取点,期望要取几个点,才能使这若干个点的凸包包含圆心?

Read more »

一来就发现 roosaphu #1 。

然后 cp12321 #2 。

然后 kAc #5 。

其中必有引擎。我就呵呵不说话。

(这场 CF 真心是给国人做的)

(我不知道我对 unrated 是该高兴还是该悲伤)

Solution

B

原题可以抽象出这么个模型:给定 \(m\) 个数,要求分成 \(p\) 组,最后每个元素对答案的贡献为它所在组的最大值,求答案的最小值。

排序是显然的。然后序列上 dp : \(f_{i, j}\) 表示前 \(i\) 个数分成 \(j\) 组,最小的总贡献是多少。转移考虑转入,枚举第 \(j\) 组的元素个数。

\[f_{i, j} = \min_{k < i} (f_{k, j - 1} + (i - k) x_i) = i x_i + \min_{k < i} (f_{k, j - 1} - k x_i)\]

然后就可以斜率优化了。考虑两个决策 \(p < q < i\)\(q\)\(p\) 优的充要条件是 \(f_{p, j - 1} - p x_i > f_{q, j - 1} - q x_i\) 也就是 \[x_i > \frac{f_{q, j - 1} - f_{p, j - 1}}{q - p}\]

我相信只要你看了 杨哲 《凸完全单调性的一个加强与应用》,你就一定会做这个题。

C

我相信只要你看了 周奕超 《墨墨的等式》 出题报告,你就一定会做这个题。

一眼题不多说。

D

问题主要就出在那个啥三次方上吧。

你有没有感到很奇怪,为啥会给一个奇怪的数 95542721,还特意说明这是个素数?

其中必有隐情。

疑心重重, \(\phi(95542721) = 95542720\) ,这个数与 3 是互质的。

于是我们试着在 \(\mod{95542720}\) 的意义下求 3 的幂。

于是乎,你会发现 \(3^{48} \equiv 1 \mod{95542720}\)

剩下的就不用我多说了。用线段树维护 0 到 47 次立方后的结果。

E

我相信只要你做了 Topcoder SRM 558 Div1 1000pts SurroudingBoard ,或者听懂了 曹钦翔 《线性规划与网络流》 ,你就一定会做这个题。

首先那个啥 friend 是用来搞笑的。

每个变量可以取 0 或 1 ,有些取 0 需要代价,有些取 1 需要代价。有种网络流的既视感……

剩下的就是那个特殊的获利的方法:当若干个变量全 0 或全 1 的时候,可以获得一定利润。

如果你突然有了 IDEA ,可以直接构出图:先把利润全部加入答案,然后对于每种获利方式建立一个节点。考虑啥时候需要这利润从答案里扣除。不妨设此时的限制为某些变量全 1 就得到利润吧,那么必定是这些变量中的一些为 0 那么就得扣除利润。某些变量为 0 的话,网络流中的表示为与 T 连通,我们直接把 S 连向利润这个点,容量为利润,再把利润这个点连向与其相关的那些变量,容量无穷大。这样的话一旦有个变量为 0 (图上对应的就是与 T 连通),那么利润这个点必定与 T 连通(无穷大的边你割不去),所以必定要割掉 S 与利润这个点的连边,相当于减去了利润。这就是个最小割模型。

当然你要是牛逼,直接上 cqx 的线性规划也是可以的。我试了一下,发现 SurroudingGame 和这个题都可以用线性规划建模的方法通杀,无比炫酷。

nonsense

节操掉尽,请勿再念。

@xiaodao 关于 #183 D 的 solution …… 我只能说 what the heck 当初觉得很明显的一步我居然不会证 →_→ 于是剩下的就坑了。

首先要证明数的大小一定是 \(\frac{1}{n+1}\) ,然后就好证明了。(这一步怎么证明……我只能说 wiki 上有一句原话)

对于 \(kx = \frac{k}{n+1} = b^p x - q\) ,我们有 \(k = b^p - q(n+1)\) ,在 \(\mod{n+1}\) 意义下有 \(k=b^p \mod{n+1}\) 。由于对于每个 \(k\) 都存在这么一个 \(p\) ,所以容易知道 \(n+1\) 一定为质数,且 \(b\)\(n+1\) 的一个原根。

这次 CF 被拉过去当 Tester ,就写了 BCDE 的没写 A ,结果 A 的 checker 就挂了,真是不能更逗。不得不说他们几个(@lyd, @wqs, @zgx)还是很认真的

近期做的两道题。

Problem

ProjetEuler-429

定义 \(d\)\(n\) 的单位因子,当且仅当 \(gcd(d, \frac{n}{d}) = 1\)

\(f(n)\) 表示 \(n\) 的所有单位因子的平方和。例如 \(f(24) = 1^2 + 3^2 + 8^2 + 24^2 = 650\)

\(f(10^8 !)\)

湖大 ACM 区域赛 A

\(\lceil (a + \sqrt{b})^n \rceil \mod{m}\)

\(b, n \leq 2^{30}, a, m \leq 2^{15}\)

保证 \((a - 1)^2 < b < a^2\)

Read more »
0%