problem1
设行数为$n$列数为$m$
对于任意的两行$r_{1},r_{2}$以及任意的两列$c_{1},c_{2}$所确定的四个格子，只要知道其中的三个就能确定第四个，且必须要三个。
这样的话，可以看作$n+m$个节点，如果$(i,j)$为‘Y’那么将第$i$行表示的节点和第$j$列表示的节点连一条边。这样的话，每个联通块都代表了一个子矩阵。
假设有$k$个联通块，那么答案为$k-1$。
因为需要将$k$个联通块连接起来。
problem2
首先，如果$A \le \frac{B}{2}$,那么令$A=\frac{B}{2}+1$。因为$[A,\frac{B}{2}]$内的数字的2倍一定在$[\frac{B}{2}+1,B]$中。 $C$作类似处理。
现在$[C,D]$中的数字一定需要全部保留下来。$[A,B]$中那些有倍数在$[C,D]$中可以不要。
（1）如果$B \le 10^{5}$，那么只需要挨个枚举$[A,B]$中的每个数字即可。
（2）如果$B > 10^{5}$，枚举因子$k,k>1$，那么$[\left \lceil \frac{C}{k} \right \rceil,\left \lfloor \frac{D}{k} \right \rfloor]$与$[A,B]$的交集内的数字都可以不要。
由于$D \le 10^{10},A > 5*10^{4}$，所以$k$最大枚举到$2*10^{5}$即可。
problem3
首先，可以计算出以下两种情况：
（1）和是0。那么只需要枚举将第$i$个数字变成0，然后剩余数字的和是0即可；
（2）最多有一个数字的绝对值不是1，剩余都是。那么可以枚举这个数字，然后剩下的数字应该正好有一半的-1一半的1，且-1的个数是偶数。
那么现在只需要处理和不是0且至少有两个数字的绝对值大于1的情况。
可以发现，这种情况，最后的和（也就是乘积）的绝对值不会大于100.
比如等于102，那么可能是$2*51*1^{t}$，由于最多50个数字，那么 $t$最大为48，此时2+51+1*48=101<102。可以发现，越比100大，越不可能得到。
因此，可以进行动态规划。设f[i][j][k]表示考虑了前$i$个数字，和是$j$乘积是$k$的最小代价。
这里有一个优化，就是对于一个状态$(i,j,k)$，还剩下$[i+1,n]$个数字未考虑,即$t=n-(i+1)+1=n-i$个数字。那么当$|k|-|j|>t$时，后面$t$个数字无论是什么组合都不会使得最后的和与乘积相等。（由于python跑的太慢，加上这个优化后才能跑过）
code for problem1
class RectangleArea: f = [] def getRoot(self, x): if self.f[x] != x: self.f[x] = self.getRoot(self.f[x]) return self.f[x] def minimumQueries(self, known): n = len(known) m = len(known[0]) for i in range(0, n + m): self.f.append(i) for i in range(0, n): for j in range(0, m): if known[i][j] == 'Y': ri = self.getRoot(i) rj = self.getRoot(n + j) self.f[ri] = rj ans = -1 for i in range(0, n + m): if self.getRoot(i) == i: ans += 1 return ans
code for problem2
class SetMultiples: def smallestSubset(self, A, B, C, D): if A <= B / 2: A = B / 2 + 1 if C <= D / 2: C = D / 2 + 1 ans = D - C + 1 + B - A + 1 if B <= 100000: for x in range(A, B + 1): t = (C + x - 1) / x if t * x <= D: ans -= 1 else: for x in range(200000, 1, -1): left = (C + x - 1) / x right = D / x if left < A: left = A if right > B: right = B; if left <= right: ans -= right - left + 1 A = right + 1 return ans
code for problem3
class PerfectSequences2: def calculate1(self, seq): n = len(seq) result = 1 << 40 for i in range(n): sum = 0 for j in range(n): if i != j: sum += seq[j] result = min(result, abs(sum) + abs(seq[i])) return result def calculate2(self, seq): n = len(seq) result = 1 << 40 if n % 4 != 1: return result for i in range(n): f = [] for j in range(n): if i != j: f.append(seq[j]) f.sort() tmp = 0 for j in range(n/2): tmp += abs(f[j] - (-1)) tmp += abs(f[n - 2 - j] - 1) result = min(result, tmp) return result def minimumMoves(self, seq): n = len(seq) if n == 1: return 0 result = min(self.calculate1(seq), self.calculate2(seq)) N = 201 M = 100 inf = 1 << 40 f = [0] * (n + 1) for i in range(n + 1): f[i] = [0] * N for j in range(N): f[i][j] = [inf] * N f[0][M][M + 1] = 0 for i in range(n): val = seq[i] for x in range(N): for y in range(N): t = f[i][x][y] if t == inf: continue xx = x - M yy = y - M if abs(yy) - abs(xx) > n - i: continue limit = M / abs(yy) if abs(yy) > 1: limit = min(limit, (n - i - 1 + abs(xx)) / (abs(yy) - 1)) for j in range(1, limit + 1): if abs(xx + j) <= M: rx = xx + j + M ry = yy * j + M f[i + 1][rx][ry] = min(f[i + 1][rx][ry], abs(val - j) + t) if abs(xx - j) <= M: rx = xx + (-j) + M ry = yy * (-j) + M f[i + 1][rx][ry] = min(f[i + 1][rx][ry], abs(val - (-j)) + t) for i in range(N): result = min(result, f[n][i][i]) return result