topcoder srm 600 div1

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

problem1 link

首先，如果一个数字的某一位是1但是$goal$的这一位不是1,那么这个数字是不用管它的。那么对于剩下的数字，只需要统计在$goal$为1的位上，这些数字对应位上也是1的数字个数。所有这样的位取最小值即可。这些数字就是要都被删除的。

problem2 link

首先暴力枚举哪些行是最后回文的行。然后对于列来说，将其对称折叠成$\frac{m}{2}$列，每一列可以选择0、1、2个，最后选出$columnCount$列。这个可以动态规划。

problem3 link

考虑一条线一条线添加进去。

每次添加一条线所增加的区域等于1加上这条线与已有的线交点的个数。如果多个线交于一点那么这个点只能算一次。

对于一条线$y=ax+b$,只需要考虑以下这些直线：$y=a^{'}x+b^{'},0\leq a^{'}<a,0\leq b^{'}<B$

交点为横坐标为$x=\frac{b^{'}-b}{a-a^{'}}=\frac{p}{q},-b\leq p<B-b,1\leq q\leq a$

可以将$p$分为三段:$-b\leq p<0,p=0,0<p<B-b$

如果当前直线与之前的两条线相交于一点，那么有$\frac{p_{1}}{q_{1}}=\frac{p_{2}}{q_{2}}$，那么只需要考虑$p_{i},q_{i}$互质的那一组即可。由于$q$的连续性，必有一组是互质的。

令$f[a][b]=\sum_{i=1}^{a}\sum_{j=1}^{b}[Gcd(i,j)=1]$

所以答案为$f[a][b]+1+f[a][B-b-1]$表示上面分成的三段。

code for problem1

#include <algorithm>
#include <vector>class ORSolitaire {
public:
int getMinimum(const std::vector<int> &numbers, int goal) {
std::vector<int> b(30);
for (auto x : numbers) {
if ((goal & x) == x) {
for (int i = 0; i < 30; ++i) {
if ((x & (1 << i)) != 0) {
++b[i];
}
}
}
}
int result = -1;
for (int i = 0; i < 30; ++i) {
if ((goal & (1 << i)) != 0) {
if (result == -1 || result > b[i]) {
result = b[i];
}
}
}
return result;
}
};

code for problem2

#include <string>
#include <vector>class PalindromeMatrix {
public:
int minChange(const std::vector<std::string> &A, int rowCount,
int columnCount) {
int n = static_cast<int>(A.size());
int m = static_cast<int>(A[0].size());
int result = n * m; for (int mask = 0; mask < (1 << n); ++mask) {
std::vector<int> rows;
for (int i = 0; i < n; ++i) {
if ((mask & (1 << i)) != 0) {
rows.push_back(i);
}
}
if (static_cast<int>(rows.size()) == rowCount) {
result = std::min(result, Compute(rows, A, columnCount, n, m));
}
}
return result;
} private:
int Compute(const std::vector<int> &rows, const std::vector<std::string> &A,
int column, int n, int m) {
auto Cost = [&](int c1, int c2, int tag) {
std::vector<int> visited(n);
std::vector<int> row_hash(n);
for (auto r : rows) {
row_hash[r] = 1;
}
int result = 0;
for (auto r : rows) {
if (visited[r] == 1) {
continue;
}
int c[2] = {0, 0};
visited[r] = 1;
++c[A[r][c1] - '0'];
++c[A[r][c2] - '0'];
if (tag == 1) {
++c[A[n - 1 - r][c1] - '0'];
visited[n - 1 - r] = 1;
if (row_hash[n - 1 - r] == 1) {
++c[A[n - 1 - r][c2] - '0'];
}
} else if (tag == 2) {
++c[A[n - 1 - r][c2] - '0'];
visited[n - 1 - r] = 1;
if (row_hash[n - 1 - r] == 1) {
++c[A[n - 1 - r][c1] - '0'];
}
} else if (tag == 3) {
++c[A[n - 1 - r][c2] - '0'];
++c[A[n - 1 - r][c1] - '0'];
visited[n - 1 - r] = 1;
}
result += std::min(c[0], c[1]);
} for (int i = 0; i < n / 2; ++i) {
if (visited[i] == 0) {
if ((tag & 1) == 1 && A[i][c1] != A[n - 1 - i][c1]) {
++result;
}
if ((tag & 2) == 2 && A[i][c2] != A[n - 1 - i][c2]) {
++result;
}
}
}
return result;
};
std::vector<std::vector<int>> f(m >> 1, std::vector<int>(column + 1, -1));
auto Update = [&](int i, int j, int cost) {
if (j <= column && (f[i][j] == -1 || f[i][j] > cost)) {
f[i][j] = cost;
}
};
Update(0, 0, Cost(0, m - 1, 0));
Update(0, 1, std::min(Cost(0, m - 1, 1), Cost(0, m - 1, 2)));
Update(0, 2, Cost(0, m - 1, 3)); for (int i = 1; i < (m >> 1); ++i) {
for (int j = 0; j <= column; ++j) {
if (f[i - 1][j] == -1) {
continue;
}
Update(i, j, f[i - 1][j] + Cost(i, m - 1 - i, 0));
Update(i, j + 1, f[i - 1][j] + std::min(Cost(i, m - 1 - i, 1),
Cost(i, m - 1 - i, 2)));
Update(i, j + 2, f[i - 1][j] + Cost(i, m - 1 - i, 3));
}
}
return f[m / 2 - 1][column];
}
};

code for problem3

constexpr int kMax = 1200;
int table[kMax][kMax];class LotsOfLines {
public:
long long countDivisions(int A, int B) {
Initialize(A, B);
long long result = B + 1;
for (int a = 1; a < A; ++a) {
for (int b = 0; b < B; ++b) {
result += 2 + table[a][b] + table[a][B - 1 - b];
}
}
return result;
} private:
void Initialize(int A, int B) {
for (int i = 1; i < A; ++i) {
for (int j = 1; j < B; ++j) {
int t = Gcd(i, j) == 1 ? 1 : 0;
table[i][j] =
table[i - 1][j] + table[i][j - 1] - table[i - 1][j - 1] + t;
}
}
} int Gcd(int x, int y) { return y == 0 ? x : Gcd(y, x % y); }
};