2018 CCPC Online Contest

oxx

一场趣味十足，大部分时间看不到榜，没有feedback的OI比赛

Problem A

Solved by dreamcloud(-2).

题意：有n天，告诉你某个货物每一天的价格，一开始你没有货物，你可以选择在第i天买进一次该货物，或者卖出一次该货物。问你最高能收获多少钱，最少的交易次数

题解：贪心，从后往前扫，维护一个买了的货物价格的优先队列和还没进行交易价格的优先队列，这时，如果新来一个货物，如果要买的话，有两种情况：其一，之前某一次买的价格比我现在买的价格要高，则将之前买的货物价格替换成当前价格，并将其归为没进行教育的队列中，交易次数不变；其二，没进行交易价格的优先队列中最大值比我当前价格要高，则买进我当前的价格，选择最大值卖出，交易次数加二。两种情况择优进行。如果两种情况都不满足，则选择将其归为未操作队列中。

Problem B

Unsolved.

题意：

题解：

Problem C

Solved by oxx1108.

题意：在环中重载加法和乘法，使得在满足$(m + n) ^ p = m ^ p + n ^ p$ $p$是素数

题解：直接重载取模意义下的加和乘就行了。证明费马小定理。

Problem D

Solved by oxx1108.

题意：给定$a$和$n$求$b$和$c$，求满足$a ^ n + b ^ n = c ^ n$ 一组$b$,$c$

题解：n一定等于1或者2，然后1的时候显然，2的时候勾股数构造一下就可以了。（$a$为2时平方无解，但是出题人友好地去掉了这个情况）

Problem E

Solved by oxx1108.

题意：求$(A+\sqrt{B})^n$二项式定理展开的奇数项的和（含根号项）$mod$ $p$

题解：答案为$((A+\sqrt{B})^n - (A+\sqrt{B})^n) / 2$，实现一下带根号的乘法然后快速幂即可。 注意不能直接求2的逆元，因为题目没有保证时素数，所以对$p * 2$取模最后再对答案除2即可。

Problem F

Unsolved.

题意：

题解：

Problem G

Upsolved by Xiejiadong(-5).

场上代码写的又臭又长，调都调不动，一对拍，问题还特别多。

题意：任意选择一个位置开始跳$m$次，每次跳的下一个都是$(i+k)%n$使得获得的价值最大。

题解：显然，所有的跳跃都是好几个循环节，先把所有的循环节抠出来，然后就是在循环节上面做最大连续子序列和，但是不能暴力的做，暴力做的复杂度是$O(n^2)$，我们用类似滑动窗口的技巧，$O(n)$的处理一下所有位置开始咋最大连续子序列和就可以了。

Problem H

Unsolved.

题意：

题解：

Problem I

Solved by oxx1108 & dreamcloud & Xiejiadong.

题意：按照一个排列的顺序依次按照最短路径访问相邻的节点会得到整个路径的和，求按照所有的全排列来遍历树的路径长度总和。

题解：用dfs求出两两点对之间的最短距离总和，模板题。其次就是所有边的总和对最终答案的贡献值，贡献是$(n-2)!*(n-1)*2$

Problem J

Solved by dreamcloud.

题意：从（0，0）出发到（1e9，1e9）,每次只能向右、向下或者右下，有若干格点，格点上有积分，只有从 (x−1,y−1) 走到该位置才能得到积分，求最高积分。

题解：先按照x坐标排序，然后可以写出dp式子，为dp[j] = max（dp[i] + val[j]）(i < j && x[i] < x[j] && y[i] < y[j])，由于x坐标已经是从大大小排序，只需要维护对应y坐标时的最大值，利用线段树维护最大值可以实现。

ECNU Foreigners

Problem A

Solved by kblack. 00:49 (+)

题意：有 $n$ 次机会以 $a_i$ 的价格买入或卖出同一类物品，求最大获益。

题解：考虑贪心，定义一个 $pair(x, y)$ 表示 当前可以以 $x$ 的价格获得一种物品，$y$ 指示这种物品是之前卖出的还是要全新买的（影响交易次数），相当于引入了一个后悔机制，每次取可以交易的最便宜的物品，更新后重新扔进堆里就好了。

Problem B

Unsolved.

Problem C

Solved by zerol. 00:50 (+)

Problem D

Solved by zerol. 00:29 (+)

Problem E

Solved by ultmaster. 02:50 (+1)

题意：求 $\displaystyle \sum_{i=1}^n [i \equiv 1 \pmod 2] \frac{a^{n-i} \sqrt{b}^i n!}{i! (n-i)!}$。

题解：简单观察，或者使用 Mathematica 化简之后就可以得到所求式是 $\displaystyle \frac{1}{2} \left( (a + \sqrt{b})^n - (a - \sqrt{b})^n \right)$。发现 $(a+\sqrt{b})^n$ 一定具有 $a + c \sqrt{b}$ 的形式，直接快速幂即可。最后要把 $\sqrt{b}$ 中的平方因子提出来，暴力搞好像会 TLE（可能是前面模多了），要预处理。

处理模数要用到经典的技巧：先模 $2p$，然后最后除以 2。

Problem F

Unsolved. (-1)

Problem G

Solved by zerol. 03:03 (+3)

Problem H

Unsolved.

Problem I

Solved by kblack. 00:26 (+1)

题意：求所有排列走法在路上距离总和。好像见到过原题。

题解：一共 $N!$ 个排列，每个排列提供 $N-1$ 条路径，显然每个路径的出现是对称的，所有每个点对一共走 $2(N-1)!$ 次，按边统计下一下就好了。

Problem J

Solved by ultmaster. 00:36 (+)

题意：有若干格点，格点上有积分，积分只有从 $(x-1,y-1)$ 走过去才能得到，求最高积分。

题解：把它想成一列一列的格子一起转移；按 $x$ 升序 $y$ 降序排，然后由于 $y$ 降序了，所以更新上面的东西并不会影响后面的。直接用一个线段树支持 set 标记和查询区间最大即可。