# Weekly Algorithm Contest 06.03 - 06.10
[Read Me in HackMD](https://hackmd.io/@E-5gxTGiSByBOKpvsaKa_g/rkhL8wUR4)

- [TCO 2019 India]()
https://www.topcoder.com/blog/inspiration-glory-and-butter-chicken-at-the-tco19-india-regional-topcoder-nation-ep-03/
### 1000 SubsetXor
xor 线性基。

- [TCO 2019 2B]()
- [GCJ Round 3](https://codingcompetitions.withgoogle.com/codejam/round/0000000000051707)

## Problem B. Pancake Pyramid

#### Brief Description
给定长度为 n 的序列 h[i]。
每次你可以选择一段连续子序列 [l, r]，你可以给其中某些项执行 +1 操作，使得操作后形成一个金字塔形状（先递增再递减）。
问遍历所有的子序列，总操作次数最少是多少。
#### Analysis
相同元素可能会带来重复计数，我们统一先认为相同的元素出现时，左边的更大。

考虑暴力做法。注意到我们这里 [只有 +1 操作](http://blog.watashi.ws/2067/zojmonthly1106/)，所以可以直接贪心。
每次枚举区间，设:
- M[l][r] 表示 [l, r] 区间最大的数的位置。
- L[l][r] 表示把 [l, r] 这个区间处理成递增序列的最小代价。
- R[l][r] 表示把 [l, r] 这个区间处理成递减序列的最小代价。

那么我们枚举所有的区间，统计所有 L[l][m] + R[m][r] 就是答案，可以预处理这些数组，复杂度 O(n2)，可以过小数据。

考虑大数据，其实题目里已经疯狂暗示你了要用单调栈（stack）。。。
回忆 [POJ 2559. Largest Rectangle in a Histogram](http://poj.org/problem?id=2559)。

我们发现之前是要处理出，以 h[i] 为最低点，左右两边分别可以延伸多远。
这里恰好是求，以 h[i] 为最高点，左右两边分别可以延伸多远，假设就是 Dl[i] 和 Dr[i]。
这样唯一不同的是，我们还需要一个累计代价数组 Sl[i] 和 Sr[i]，分别表示以 h[i] 为最高点，往左和往右累计的代价。
因为最后答案就是：
$$\Sigma_{i=1}^n Dl[i] * Sr[i] + Dr[i] * Sl[i]$$

我们可以在维护单调栈的过程中，顺路求 Sl 出 Sr。不放考察从左往右扫描求 Dl 的过程。
设当前扫描到位置 i，将要被弹出的栈顶元素为 sp，这个位置右边一直到 i 这个区间现在都至少需要是 h[sp] 的高度才符合要求。
记这个代价为小写的 sl，我们预处理部分和后可以 O(1) 的求出 sl。记新的栈顶元素的位置与刚才被我们弹出的栈顶元素的位置之间的距离为 sp - s.top()，
sl 需要被统计 sp - s.top() 次。最后加上这个区间本身的代价 Sl[sp]。

stack<int> s; s.push(0); REP_1(i, n) {
Sl[i] = 0;
while (h[i] > h[s.top()]) {
int sp = s.top(); s.pop();
Int sl = Int(h[sp]) * (i-sp-1) - (hh[i-1]-hh[sp]);
Sl[i] += sl * (sp - s.top()) + Sl[sp];
}
Dl[i] = i - s.top();
s.push(i);
}

- [Menci, 线性基学习笔记](https://oi.men.ci/linear-basis-notes/)

### 250 MedianFaking

#### Brief Description
给定 n 个人，每个人有 m 个测量结果。取所有人所有测量结果的中位数（偶数时下去整）为最终结果。
已知测量结果应该是 goal，问至少修改几个测量结果可以使得结果恰好为 goal，在这种情况下最少需要参与修改的人数又是多少。

#### Analysis
如果要让结果恰好为 goal，那么比 goal 小的数和比 goal 大的数都不能超过一半，显然这两边只会有一边不符合。
于是我们只要关心这一边需要修改几个数就好了，并且现在只需要考虑一边，第二问只要统计出每个人可以带来的贡献，排序贪心即可。

### 500 DivisorSequences

#### Brief Description
给定 n，我们将 n 拆分成若干个整数相加的形式：n = a1 + a2 + ... + am。
要求 a 序列严格递增且 a_i 整除 a_{i+1}，问 m 最大可以是多少。

#### Analysis
观察 15 = 1 + 2 + 4 + 8...
我们发现如果把 1 去掉的话，有 14 = 2(1 + 2 + 4)...
这样我们就发现了一个子问题！
定义 f(n) 表示将 n 分解，并且第一个数是 1 的方案数，每次减去 1 后枚举约数递归即可。那么实际的答案可能第一个数不为 1，所以开始再额外枚举一次约数就好。
复杂度虽然不太容易估计，但貌似不记忆化也能过。

### 1000 SlightlyBigger

#### Brief Description
Alice 和 Bob 报数，从 1 到 oo，目标是比对方报的数只大一点。
- 如果恰好差小于等于 maxDiff，那么大的一方获胜，并得到 ifNear 分。
- 否则，小的一方获胜，并得到 ifFar 分。

双方都采取最优策略时，问 Alice 报的数恰好为 query 的概率。
(ifNear < ifFar <= 2×ifNear)

#### Analysis
第一眼感觉这个题很神，看了一下大家后来都是高斯消元做的。但是不知道怎么列方程。后来请教了一下毕克老师，毕老师说其实这个问题跟剪刀石头布是一样的，就你想象一个剪刀石头布游戏，然后给你一个收益矩阵。
对方把自己的策略的概率分布向量已经告诉你了，在最优情况下，你发现你即便知道这个向量也并不能让你取得任何优势。
这就是传说中的 [纳什均衡](https://en.wikipedia.org/wiki/Nash_equilibrium)，于是只要设表示报 x_i 的概率，根据上面这些关系，列出线性方程组，高斯消元即可。

纳什均衡虽然提供了 n 组方程，但是 rank 似乎是 n-1 的，最后别忘了加上所有概率分布之和等于 1。
可以预计答案不会很大，可以带极限数据跑一下看看边界。

https://vjudge.net/problem/ZOJ-3645

TC 高斯消元
SRM 620 PerfectSquare.cpp
https://user.qzone.qq.com/251815992/infocenter
.cpp
SubsetXor