topcoder srm 505 div1

problem1 link

设行数为$n$列数为$m$

对于任意的两行$r_{1},r_{2}$以及任意的两列$c_{1},c_{2}$所确定的四个格子，只要知道其中的三个就能确定第四个，且必须要三个。

这样的话，可以看作$n+m$个节点，如果$(i,j)$为‘Y’那么将第$i$行表示的节点和第$j$列表示的节点连一条边。这样的话，每个联通块都代表了一个子矩阵。

假设有$k$个联通块，那么答案为$k-1$。

因为需要将$k$个联通块连接起来。

problem2 link

首先，如果$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 link

首先，可以计算出以下两种情况：

（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

巴特西

topcoder srm 505 div1

最新文章

热门文章