Алгоритмы C++
.pdf
if (mask & my_mask)
calc (x, y+1, mask, next_mask);
else
{
calc (x, y+1, mask, next_mask | my_mask);
if (y+1 < m && ! (mask & my_mask) && ! (mask &
(my_mask << 1)))
calc (x, y+2, mask, next_mask);
}
}
}
int main()
{
cin >> n >> m;
d.resize (n+1, vector<long long> (1<<m)); d[0][0] = 1;
for (int x=0; x<n; ++x)
for (int mask=0; mask<(1<<m); ++mask) calc (x, 0, mask, 0);
cout << d[n][0];
}
Нахождение наибольшей нулевой подматрицы за O (N M)
Дана матрица A размером N x M, состоящая только из нулей и единиц. Требуется найти в ней наибольшую (по площади) подматрицу, состоящую только из нулей.
Здесь будет описано решение, работающее за линейное относительно размера матрицы время: O (N M).
Описание
Пусть дана матрица A, имеющая N строк и M столбцов.
Будем последовательно двигаться по строчкам этой матрицы; пусть текущая строка - i. Посчитаем для всех элементов текущей строки величину D[1..M], где D[j] равно наибольшему номеру строки <= i, в которой в j-ом столбце стоит единица; если такой строки нет, то полагаем D[j] равным -1. Иными словами, D[j] указывает для элемента A[i] [j] ближайшую сверху единицу. (В частности, когда A[i][j] = 1, то D[j] = i)
Такую динамику легко посчитать для каждой строчки, если знать её значение для предыдущей строки. Например, вот код, вычисляющий значения этой динамики для всех элементов матрицы:
vector<int> d (m, -1); for (int i=0; i<n; ++i) {
for (int j=0; j<m; ++j) if (a[i][j] == 1)
d[j] = i;
// вычислили для i-ой строки, можем использовать эти значения
}
Значения D[j] позволят нам определить верхнюю границу для нулевой подматрицы, если мы будем ставить её так, чтобы её нижняя граница находилась в строке i.
Уже сейчас мы можем решить задачу за O (N M2) - просто перебирать в текущей строке левую и правую границы, и с помощью динамики D[j] вычислять за O (1) верхнюю границу нулевой подматрицы. Однако можно пойти дальше и значительно улучшить асимптотику.
Ясно, что наибольшая нулевая подматрица ограничена сверху как минимум одной единицей в некотором столбце,
также она ограничена единицами слева и справа (можно считать, что за пределами матрицы A стоят одни
единицы). Поэтому мы не пропустим наилучший ответ, если будем действовать следующим образом: в текущей строке i будем перебирать столбец j; верхней границей нулевой подматрицы будем считать D[j]; для текущего j
найдём ближайшую слева позицию k1 такую, что D[k1] > D[j] (т.е. левая граница нулевой подматрицы), а также позицию k2 такую, что D[k2] > D[j] (правую границу). Тогда величиной текущей нулевой подматрицы будет (i - D[j]) * (D[k2] - D[k1] - 1). И из всех таких матриц надо будет выбрать наибольшую по площади, она и будет ответом.
Осталось научиться эффективно вычислять позиции k1 и k2 для текущего j, а именно, вычислять за O (1). Для этого посчитаем две соответствующие динамики D1 и D2.
Заведём стек St. Будем двигаться в текущей строке по столбцам j от 1 до M. Будем поддерживать инвариант, что в стеке St находятся номера столбцов, в которых величина D меньше D[j]. Очевидно, что при переходе от одного элемента
к следующему мы должны просто удалить с вершины стека все столбцы, величина D в которых >= D[j], затем присвоить D1[j] = St.top, и затем положить в стек j. Аналогично построим и вторую динамику D2, просто двигаться будем
справа налево: j от M до 1. Ясно, что на вычисление каждой динамики потребуется O (M) времени.
Итак, схема алгоритма такова: перебираем строку i, для каждой строки последовательно считаем динамики D, D1, D2, и проходом по всем столбцам j строим нулевые подматрицы, из которых выбираем наибольшую.
Реализация
Реализация алгоритма, которая считываем матрицу и выводит размер наибольшей нулевой подматрицы. Ясно, что добиться вывода самих координат подматрицы несложно.
int n, m;
cin >> n >> m;
vector < vector<char> > a (n, vector<char> (m)); for (int i=0; i<n; ++i)
for (int j=0; j<m; ++j) cin >> a[i][j];
int ans = 0; vector<int> d (m, -1);
vector<int> dl (m), dr (m); stack<int> st;
for (int i=0; i<n; ++i) {
for (int j=0; j<m; ++j)
if (a[i][j] == 1) d[j] = i;
while (!st.empty()) st.pop(); for (int j=0; j<m; ++j) {
while (!st.empty() && d[st.top()] <= d[j]) st.pop(); dl[j] = st.empty() ? -1 : st.top();
st.push (j);
}
while (!st.empty()) st.pop(); for (int j=m-1; j>=0; --j) {
while (!st.empty() && d[st.top()] <= d[j]) st.pop(); dr[j] = st.empty() ? m : st.top();
st.push (j);
}
for (int j=0; j<m; ++j)
ans = max (ans, (i - d[j]) * (dr[j] - dl[j] - 1));
}
cout << ans;
static BigInteger det (BigDecimal a [][], int n)
{
try {
for (int i=0; i<n; i++)
{
boolean nonzero = false; for (int j=0; j<n; j++)
if (a[i][j].compareTo (new BigDecimal
(BigInteger.ZERO)) > 0)
nonzero = true;
if (!nonzero)
return BigInteger.ZERO;
}
BigDecimal scaling [] = new BigDecimal [n]; for (int i=0; i<n; i++)
{
BigDecimal big = new BigDecimal (BigInteger.ZERO); for (int j=0; j<n; j++)
if (a[i][j].abs().compareTo (big) > 0) big = a[i][j].abs();
scaling[i] = (new BigDecimal (BigInteger.ONE)) .divide (big, 100, BigDecimal.ROUND_HALF_EVEN);
}
int sign = 1;
for (int j=0; j<n; j++)
{
for (int i=0; i<j; i++)
{
BigDecimal sum = a[i][j]; for (int k=0; k<i; k++)
sum = sum.subtract (a[i][k].multiply (a[k][j])); a[i][j] = sum;
}
BigDecimal big = new BigDecimal (BigInteger.ZERO); int imax = -1;
for (int i=j; i<n; i++)
{
BigDecimal sum = a[i][j]; for (int k=0; k<j; k++)
sum = sum.subtract (a[i][k].multiply (a[k][j])); a[i][j] = sum;
BigDecimal cur = sum.abs();
cur = cur.multiply (scaling[i]); if (cur.compareTo (big) >= 0)
{
big = cur; imax = i;
}
}
if (j != imax)
{
for (int k=0; k<n; k++)
{
BigDecimal t = a[j][k]; a[j][k] = a[imax][k]; a[imax][k] = t;
}
BigDecimal t = scaling[imax]; scaling[imax] = scaling[j]; scaling[j] = t;
sign = -sign;
}
if (j != n-1)
for (int i=j+1; i<n; i++)
a[i][j] = a[i][j].divide (a[j][j], 100,
BigDecimal.ROUND_HALF_EVEN);
}
BigDecimal result = new BigDecimal (1); if (sign == -1)
result = result.negate(); for (int i=0; i<n; i++)
result = result.multiply (a[i][i]);
return result.divide
(BigDecimal.valueOf(1), 0, BigDecimal. ROUND_HALF_EVEN).toBigInteger();
}
catch (Exception e)
{
return BigInteger.ZERO;
}
}
Метод Гаусса решения системы линейных уравнений
Дана система из N линейных уравнений с N неизвестными. Известно, что система имеет единственное решение (т. е. определитель её отличен от нуля). Требуется найти это решение.
Описание метода
Дана система:
a11 x1 + a12 x2 + ... + a1n xn = b1 a21 x1 + a22 x2 + ... + a2n xn = b2
...
an1 x1 + an2 x2 + ... + ann xn = bn
Выполним следующий алгоритм.
На первом шаге найдём в первом столбце наибольший по модулю элемент, поставим уравнение с этим элементом на первую строчку (обменяв две соответствующие строки матрицы A и два соответствующих элемента вектора B), а затем будем отнимать это уравнение от всех остальных, чтобы в первом столбце все элементы (кроме
первого) обратились в ноль. Например, при прибавлении ко второй строке будем домножать первую строку на -a21/a11, при добавлении к третьей - на -a31/a11, и т.д.
На втором шаге найдём во втором столбце, начиная со второго элемента, наибольший по модулю элемент, поставим уравнение с этим элементом на вторую строчку, и будем отнимать это уравнение от всех остальных (в том числе и от первого), чтобы во втором столбце все элементы (кроме второго) обратились в ноль. Понятно, что эта операция никак не изменит первый столбец - ведь от каждой строки мы будем отнимать вторую строку, домноженную на некоторый коэффициент, а во второй строке в первом столбце стоит ноль.
Т.е. на i-ом шаге найдём в i-ом столбце, начиная с i-го элемента, наибольший по модулю элемент, поставим уравнение с этим элементом на i-ю строчку, и будем отнимать это уравнение от всех остальных. Понятно, что это никак не повлияет на все предыдущие столбцы (с первого по (i-1)-ый).
В конце концов, мы приведём систему к так называемому диагональному виду:
c11 x1 = d1 c22 x2 = d2
...
cnn xn = dn
Т.е. мы нашли решение системы.
Замечание 1. На каждой итерации найдётся хотя бы один ненулевой элемент, иначе система бы имела нулевой определитель, что противоречит условию.
Замечание 2. Требование, что на каждом шаге мы выбираем наибольший по модулю элемент, очень важно в смысле численной устойчивости метода. Если выбирать произвольный ненулевой элемент, то это может привести к гигантской погрешности, когда получившееся решение будет отличаться в разы от правильного.
Реализация
Для упрощения реализации матрица коэффициентов A и столбец свободных коэффициентов B будем хранить в одном векторе a.
const double EPS = 1E-9; int n;
vector < vector<double> > a (n, vector<double> (n+1));
... чтение n и a ...
for (int i=0; i<n; ++i) { int k = i;
for (int j=i+1; j<n; ++j)
if (abs (a[j][i]) > abs (a[k][i])) k = j;
swap (a[i], a[k]);
for (int j=i+1; j<=n; ++j) a[i][j] /= a[i][i];
for (int j=0; j<n; ++j) if (j != i)
for (int k=i+1; k<=n; ++k)
a[j][k] -= a[i][k] * a[j][i];
}