Отримання знань

дистанційна підтримка освіти школярів


Уничтожение квадратов
http://acm.pku.edu.cn/JudgeOnline/problem?id=1084

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на C++:

#include "iostream" 
#include "cstring"

using namespace std;

const int MAX_SIZE = 5;
const int MAX_STK = 60;

typedef unsigned long long ULL;

class CoverInit {
private:
static int m_size;
//Number of the stick on the top of the grid [row][col].
static int m_up[MAX_SIZE][MAX_SIZE];

static void initUp() {
for (int i = 0; i < m_size; i++) {
m_up[i][0] = i * (2 * m_size + 1);
for (int j = 1; j < m_size; j++) {
m_up[i][j] = m_up[i][j - 1] + 1;
}
}
}

static void initSqr(int firstStick, int size, ULL mask, ULL* cover) {
int gap = 2 * m_size + 1;
int num = firstStick;//The upper and the lower edges.
for (int i = 0; i < size; i++) {
cover[num] |= mask;
cover[num + size * gap] |= mask;
num++;
}
num = firstStick + m_size;//The left and the right edges.
for (int i = 0; i < size; i++) {
cover[num] |= mask;
cover[num + size] |= mask;
num += gap;
}
}

public:
static void initCover(int size, ULL* cover, int stkCnt) {
m_size = size;
initUp();
memset(cover, 0, stkCnt * sizeof(ULL));
ULL mask = 1ULL;
for (int sqrSize = 1; sqrSize <= m_size; sqrSize++) {
for (int i = 0; i <= m_size - sqrSize; i++) {
for (int j = 0; j <= m_size - sqrSize; j++) {
int up = m_up[i][j];
initSqr(up, sqrSize, mask, cover);
mask <<= 1;
}
}
}
}
};

int CoverInit::m_size;
int CoverInit::m_up[MAX_SIZE][MAX_SIZE];

class Solution {
private:
ULL m_cover[MAX_STK];
bool m_stick[MAX_STK];
ULL m_universal;
int m_sqrCnt;
int m_stkCnt;
int m_minStk;
ULL m_remainCov[MAX_STK];

void dfs(char stkCnt, char lastStk, ULL cover) {
if (cover == m_universal) {
m_minStk = stkCnt;
}
else {
if (stkCnt < m_minStk
&& (m_remainCov[lastStk + 1] | cover) == m_universal
) {
for (int i = lastStk + 1; i < m_stkCnt; i++) {
if ((m_cover[i] | cover) > cover) {
dfs(stkCnt + 1, i, cover | m_cover[i]);
}
}
}
}
}

void init(int size) {
m_stkCnt = 2 * size * (size + 1);

CoverInit::initCover(size, m_cover, m_stkCnt);

int sqrCnt = 0;
for (int i = 1; i <= size; i++) {
sqrCnt += i * i;
}
m_universal = 1ULL;
for (int i = 1; i < sqrCnt; i++) {
m_universal <<= 1;
m_universal += 1ULL;
}

for (int i = 0 ; i < m_stkCnt; i++) {
m_stick[i] = true;
}
}

void modifyData() {
for (int i = 0; i < m_stkCnt; i++) {
if (!m_stick[i]) {
m_universal &= ~m_cover[i];
}
}

for (int i = 0; i < m_stkCnt; i++) {
m_cover[i] &= m_universal;
}
for (int i = 0; i < m_stkCnt; i++) {
if (m_stick[i]) {
for (int j = 0; j < m_stkCnt; j++) {
if (j != i && m_stick[j]
&& m_cover[j] == (m_cover[j] & m_cover[i])
) {
m_stick[j] = false;
}
}
}
}
int cnt = 0;
for (int i = 0; i < m_stkCnt; i++) {
if (m_stick[i]) {
m_cover[cnt] = m_cover[i];
cnt++;
}
}
m_stkCnt = cnt;

m_remainCov[m_stkCnt - 1] = m_cover[m_stkCnt - 1];
for (int i = m_stkCnt - 2; i >= 0; i--) {
m_remainCov[i] = m_remainCov[i + 1] | m_cover[i];
}
}

public:
void input() {
int size;
cin >> size;
init(size);

int rmCnt;
cin >> rmCnt;
for (int i = 0; i < rmCnt; i++) {
int rm;
cin >> rm;
m_stick[rm - 1] = false;
}
}

void search() {
modifyData();
m_minStk = m_stkCnt < 9? m_stkCnt: 9;
dfs(0, -1, 0ULL);
cout << m_minStk << endl;
}
};

int main() {
Solution solution;
int caseCnt;
cin >> caseCnt;
for (int i = 0; i < caseCnt; i++) {
solution.input();
solution.search();
}
return 0;
}

 

Попередня Зміст Наступна
В системі: гості - (1); користувачі - (0)