Day1
C Wandering
题意：每一步等概率走到以当前位置为圆心，$R_i$为半径的圆的任意一点，$n\le 1000000$。问最终与原点期望的平方。
解：首先观察样例可以发现可能答案就是每个$R_i$的平方和除以2，所以我们就做完了。（误）
下面给出证明：
最终要求的答案是
$$
E[(\sum^{n}_{i=1}x_i)^2+(\sum^{n}_{i=1}y_i)^2]
$$
而这显然等于
$$
\sum ^{n} _{i=1} \sum ^{n} _{j=1} E[(x_i\cdot x_j)+(y_i\cdot y_j)]
$$
考虑到$x_i与x_j$互相独立，则
$$
\sum ^{n} _{i=1} \sum ^{n} _{j=1} E(x_i \cdot x_j)= \sum ^{n} _{i=1}E(x_i \cdot \sum _{j!=i}x_j)+E({x_i}^2)= \sum ^{n} _{i=1}E(x_i \cdot \sum _{j!=i}E(x_j))+E({x_i}^2)
$$
显然$E(x_j)$是0。对$y$同理。因此所求答案等于
$$
\sum^{n}_{i=1}E[{x_i}^2+{y_i}^2]
$$
几何意义就是圆内随机撒点与原点的期望距离的平方，可以很方便利用积分进行求解。
E Minimum Spanning Tree
需要水平长进一点之后再看看
https://official.contest.yandex.com/icpc-camp-21/contest/24597/problems/E/
可以发现任意环内的mst边必定比没加进去的小。因此可以找环然后处理出所有边之间的大小关系。然后状压dp即可。
Day2
M Discrete Logarithm is a Joke
原来题目就说了这是个Joke…
题意：已知$a_0=960002411612632915$，$g=42$，$M=10^{18}+31$，$g$是$M$的原根。每次操作求离散对数$\log _{g}a_i$。问$a_n$，其中$n\le 1000000$。
解：不看最后一组样例不能做。最后一组样例$n=1000000,a_n=300$。反着即可。
G Remove the Prime
https://official.contest.yandex.com/icpc-camp-21/contest/24598/problems/G/
题意：给一个$n\le 1000$的数列$a_n\le 10^{18}$，两人博弈，每个操作可以选取一段区间和一个质数并将所有该区间内的数除该质数直到不能除尽(区间内每个数必须是该质数的倍数)。不能操作即输。问谁赢。
解：可以发现，将某个数用$10^6$以内的质数试除后，发现不能除尽的一定至多只有两个质因子。用miller-rabin可以检验该数究竟是质数还是含有两个质因子的合数。对于相邻的数可以利用gcd求出他们的共同质因子。然后就可以转化成nim游戏进行判断（这步我还不太会…大概博弈论也要好好搞搞）。
J Increasing or Decreasing
思维题，没什么好说的…读题要读清楚
I Trade
题意：有$n\le 100000$个商品，每个商品有$p_i$和$c_i$属性。已经买了$k$个物品，并准备买序号为$i$的物品时，需要花$c_i+k\times p_i$来购买。现在有$S\le 10^9$块钱，问最多能买几件。保证$p_i$为正整数，各不相同。$c_i$也为正整数。
解：假设已经确定哪些物品需要选择，则必定先买$p_i$大的。反过来，如果物品已经按照$p_i$排好序，则可以比较方便研究哪些需要选择。先将物品降序排序。设$f[i][j]$表示处理了前$i$个物品，其中选取$j$个物品时的最小花费。转移方程比较显然。这样我们就得到了一个$O(n^2)$的做法。但没法过。观察发现（这有点脑筋急转弯的感觉啊）由于$p_i$各不相同，选取时由于$S$的限制是有上限的。所以第二维只要做到三四千，这个题目就ac了。