ビット演算+列挙
ビット演算http://c.biancheng.net/cpp/html/101.html
多くの場合(例えば駒をひっくり返す)は検索時に大量の列挙に関連してタイムアウトを招くことが多く、ビット演算はこの問題をよく解決し、便利で速い.
HDU 1882 Strange Billboard
http://acm.hdu.edu.cn/showproblem.php?pid=1882
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 813 Accepted Submission(s): 348
Problem Description
The marketing and public-relations department of the Czech Technical University has designed a new reconfigurable mechanical Flip-Flop Bill-Board (FFBB). The billboard is a regular two-dimensional grid of R ×C square tiles made of plastic. Each plastic tile is white on one side and black on the other. The idea of the billboard is that you can create various pictures by flipping individual tiles over. Such billboards will hang above all entrances to the university and will be used to display simple pictures and advertise upcoming academic events.
To change pictures, each billboard is equipped with a ”reconfiguration device”. The device is just an ordinary long wooden stick that is used to tap the tiles. if you tap a tile, it flips over to the other side, i.e., it changes from white to black or vice versa. Do you agree this idea is very clever?
Unfortunately, the billboard makers did not realize one thing. The tiles are very close to each other and their sides touch. Whenever a tile is tapped, it takes all neighboring tiles with it and all of them flip over together. Therefore, if you want to change the color of a tile, all neighboring tiles change their color too. Neighboring tiles are those that touch each other with the whole side. All inner tiles have 4 neighbors, which means 5 tiles are flipped over when tapped. Border tiles have less neighbors, of course.
For example, if you have the billboard configuration shown in the left picture above and tap the tile marked with the cross, you will get the picture on the right. As you can see, the billboard reconfiguration is not so easy under these conditions. Your task is to find the fastest way to ”clear” the billboard, i.e., to flip all tiles to their white side.
Input
The input consists of several billboard descriptions. Each description begins with a line containing two integer numbers R and C (1 ≤ R, C ≤ 16) specifying the billboard size. Then there are R lines, each containing C characters. The characters can be either an uppercase letter “X” (black) or a dot “.” (white). There is one empty line after each map.
The input is terminated by two zeros in place of the board size.
Output
For each billboard, print one line containing the sentence “You have to tap T tiles.”, where T is the minimal possible number of taps needed to make all squares white. if the situation cannot be solved, output the string “Damaged billboard.” instead.
Sample Input
その後,このような書き込み時間の複雑さはnm 2^nであり,最大テストデータは15であるがタイムアウトは避けられないことが分かった.
最終的に長い間ビット演算に葛藤し、コード最適化を加えてやっと過ぎた.
acコードは以下の通りである
同じビット演算が多くの場所で適用され、不意の効果が得られます
swust oj 781牛が水を飲む
牛が水を飲む
Time limit(ms): 1000
Memory limit(kb): 65535
Submission: 4
Accepted: 4
Accepted
The cows have a line of 20 water bowls from which they drink. The bowls can be either right-side-up (properly oriented to serve refreshing cool water) or upside-down (a position which holds no water). They want all 20 water bowls to be right-side-up and thus use their wide snouts to flip bowls. Their snouts, though, are so wide that they flip not only one bowl but also the bowls on either side of that bowl (a total of three or -- in the case of either end bowl -- two bowls). Given the initial state of the bowls (1=undrinkable, 0=drinkable -- it even looks like a bowl), what is the minimum number of bowl flips necessary to turn all the bowls right-side-up?
Description
Line 1: A single line with 20 space-separated integers
Input
Line 1: The minimum number of bowl flips necessary to flip all the bowls right-side-up (i.e., to 0). For the inputs given, it will always be possible to find some combination of flips that will manipulate the bowls to 20 0's.
Output
1
0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0
Sample Input
1
3
Sample Output
Explanation of the sample: Flip bowls 4, 9, and 11 to make them all drinkable: 0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 [initial state] 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 [after flipping bowl 4] 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 [after flipping bowl 9] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 [after flipping bowl 11]
1匹の牛がボウルをひっくり返すことができて、(口が大きすぎるため^^)同时に彼の左右のボウルをすべてひっくり返すことができて、1はひっくり返す必要があるボウルを代表して、少なくとも何回ボウルをすべてひっくり返すことができます(0は表します)
この問題は、dfsでもできるし、以前はdfs aが落としていたので、今日はビット演算をして考えてみました.これは1つの行為1で、20のビット演算ではないでしょうか.
先にdfsのコード100 msを上げる(どうせ100を下回らない)
ビット演算で0 ms秒を列挙しよう~~~
多くの場合(例えば駒をひっくり返す)は検索時に大量の列挙に関連してタイムアウトを招くことが多く、ビット演算はこの問題をよく解決し、便利で速い.
HDU 1882 Strange Billboard
http://acm.hdu.edu.cn/showproblem.php?pid=1882
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 813 Accepted Submission(s): 348
Problem Description
The marketing and public-relations department of the Czech Technical University has designed a new reconfigurable mechanical Flip-Flop Bill-Board (FFBB). The billboard is a regular two-dimensional grid of R ×C square tiles made of plastic. Each plastic tile is white on one side and black on the other. The idea of the billboard is that you can create various pictures by flipping individual tiles over. Such billboards will hang above all entrances to the university and will be used to display simple pictures and advertise upcoming academic events.
To change pictures, each billboard is equipped with a ”reconfiguration device”. The device is just an ordinary long wooden stick that is used to tap the tiles. if you tap a tile, it flips over to the other side, i.e., it changes from white to black or vice versa. Do you agree this idea is very clever?
Unfortunately, the billboard makers did not realize one thing. The tiles are very close to each other and their sides touch. Whenever a tile is tapped, it takes all neighboring tiles with it and all of them flip over together. Therefore, if you want to change the color of a tile, all neighboring tiles change their color too. Neighboring tiles are those that touch each other with the whole side. All inner tiles have 4 neighbors, which means 5 tiles are flipped over when tapped. Border tiles have less neighbors, of course.
For example, if you have the billboard configuration shown in the left picture above and tap the tile marked with the cross, you will get the picture on the right. As you can see, the billboard reconfiguration is not so easy under these conditions. Your task is to find the fastest way to ”clear” the billboard, i.e., to flip all tiles to their white side.
Input
The input consists of several billboard descriptions. Each description begins with a line containing two integer numbers R and C (1 ≤ R, C ≤ 16) specifying the billboard size. Then there are R lines, each containing C characters. The characters can be either an uppercase letter “X” (black) or a dot “.” (white). There is one empty line after each map.
The input is terminated by two zeros in place of the board size.
Output
For each billboard, print one line containing the sentence “You have to tap T tiles.”, where T is the minimal possible number of taps needed to make all squares white. if the situation cannot be solved, output the string “Damaged billboard.” instead.
Sample Input
5 5 XX.XX X.X.X .XXX. X.X.X XX.XX 5 5 .XX.X ..... ..XXX ..X.X ..X.. 1 5 ...XX 5 5 ...X. ...XX .XX.. ..X.. ..... 8 9 ..XXXXX.. .X.....X. X..X.X..X X.......X X.X...X.X X..XXX..X .X.....X. ..XXXXX.. 0 0
Sample Output
You have to tap 5 tiles. Damaged billboard. You have to tap 1 tiles. You have to tap 2 tiles. You have to tap 25 tiles.
这题刚开始按照一般枚举写 很高兴的 TML了 (ノへ￣、) 代码如下
#include
#include
using namespace std;
int dir[][2] = { -1, 0, 0, -1, 0, 0, 0, 1, 1, 0 };
int n, m, map[16][16], flip[16][16];//flip
//int opt[16][16];
void init(){
char x;
memset(map, 0, sizeof(map));
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
cin >> x;
if (x == 'X')
map[i][j] = 1;
}
}
} //
int get_colour(int x, int y){
int a = map[x][y], i;
for (i = 0; i < 5; i++){
int x2 = x + dir[i][0], y2 = y + dir[i][1];
if (x2 >= 0 && x2 < n&&y2 >= 0 && y2 < m){
a += flip[x2][y2];
}
}
return a % 2;
}
int calc(){
int i, j, cnt = 0;
for (i = 1; i < n; i++){
for (j = 0; j < m; j++){
if (get_colour(i - 1, j))
flip[i][j] = 1;
}
}
for (i = 0; i < m; i++){
if (get_colour(n - 1, i))
return -1;
}
for (i = 0; i < n; i++){
for (j = 0; j < m; j++){
cnt += flip[i][j];
}
}
return cnt;
}
int main(){
while (cin >> n >> m, n || m){
int cnt = -1, i, j, num;
init();
for (i = 0; i < 1 << m; i++){
memset(flip, 0, sizeof(flip));
for (j = 0; j < m; j++){
flip[0][m - j - 1] = i >> j & 1;
}
num = calc();
if (num >= 0 && (cnt<0 || cnt>num)){
cnt = num;
//memcpy(opt, flip, sizeof(flip));
}
}
if (cnt < 0)
cout << "Damaged billboard.
";
else{
cout << "You have to tap " << cnt << " tiles.
";
//for (i = 0; i < n; i++){
//for (j = 0; j < m; j++){
//cout << opt[i][j] << ' ';
//}
//cout << "\r
";
//}
}
}
return 0;
}
その後,このような書き込み時間の複雑さはnm 2^nであり,最大テストデータは15であるがタイムアウトは避けられないことが分かった.
最終的に長い間ビット演算に葛藤し、コード最適化を加えてやっと過ぎた.
acコードは以下の通りである
/******************************************************
& ( )
| ( )
^ ( )
~
<<
>>
S|1<
#include
using namespace std;
#define inf 0x7fffffff
#define min(a,b) a= m){
for (i = 0; i < n; i++){
cin >> map[i];
for (j = 0; j < m; j++){
if (map[i][j] == 'X')
mpt[i] |= 1 << j;
//cout << mpt[i] << endl;
// X,
}
}
}
else{ // ,
for (i = 0; i < n; i++){
cin >> map[i];
for (j = 0; j < m; j++){
if (map[i][j] == 'X')
mpt[j] |= 1 << i;
}
}
n ^= m ^= n ^= m;
}
}
int find_set(){
int minn = inf, tmp[17], sign[17], i, j, k, cnt;
for (i = 0; i < 1 << m; i++){
for (j = 0; j < n; j++)
tmp[j] = mpt[j];
for (j = 0; j < n; j++){
// ,
sign[j] = j == 0 ? i : tmp[j - 1];
tmp[j] ^= sign[j];
tmp[j] ^= sign[j] << 1 & ((1 << m) - 1);
tmp[j] ^= sign[j] >> 1;
tmp[j + 1] ^= sign[j];
// , ( !!!!!)
}
if (!tmp[n - 1]){
cnt = 0;
for (j = 0; j < n; j++){
for (k = sign[j]; k>0; k >>= 1){
if (k & 1)
cnt++;
}
}
minn = min(minn, cnt);
}
}
return minn;
}
int main(){
while (cin >> n >> m, m || n){
init();
int minn = find_set();
if (minn == inf)
cout << "Damaged billboard.
";
else
cout << "You have to tap " << minn << " tiles.
";
}
return 0;
} 同じビット演算が多くの場所で適用され、不意の効果が得られます
swust oj 781牛が水を飲む
牛が水を飲む
Time limit(ms): 1000
Memory limit(kb): 65535
Submission: 4
Accepted: 4
Accepted
The cows have a line of 20 water bowls from which they drink. The bowls can be either right-side-up (properly oriented to serve refreshing cool water) or upside-down (a position which holds no water). They want all 20 water bowls to be right-side-up and thus use their wide snouts to flip bowls. Their snouts, though, are so wide that they flip not only one bowl but also the bowls on either side of that bowl (a total of three or -- in the case of either end bowl -- two bowls). Given the initial state of the bowls (1=undrinkable, 0=drinkable -- it even looks like a bowl), what is the minimum number of bowl flips necessary to turn all the bowls right-side-up?
Description
Line 1: A single line with 20 space-separated integers
Input
Line 1: The minimum number of bowl flips necessary to flip all the bowls right-side-up (i.e., to 0). For the inputs given, it will always be possible to find some combination of flips that will manipulate the bowls to 20 0's.
Output
1
0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0
Sample Input
1
3
Sample Output
Explanation of the sample: Flip bowls 4, 9, and 11 to make them all drinkable: 0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 [initial state] 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 [after flipping bowl 4] 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 [after flipping bowl 9] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 [after flipping bowl 11]
1匹の牛がボウルをひっくり返すことができて、(口が大きすぎるため^^)同时に彼の左右のボウルをすべてひっくり返すことができて、1はひっくり返す必要があるボウルを代表して、少なくとも何回ボウルをすべてひっくり返すことができます(0は表します)
この問題は、dfsでもできるし、以前はdfs aが落としていたので、今日はビット演算をして考えてみました.これは1つの行為1で、20のビット演算ではないでしょうか.
先にdfsのコード100 msを上げる(どうせ100を下回らない)
#include
using namespace std;
int bowl[21], step, flag;
int range()
{
int i;
for (i = 0; i<20; i++)
if (bowl[i] == 1)
return 0;
return 1;
}
void turn(int i)
{
bowl[i] = !bowl[i];
if (i>0)
bowl[i - 1] = !bowl[i - 1];
if (i<19)bowl[i + 1] = !bowl[i + 1];
}
void DFS(int i, int dp)
{
if (step == dp)
{
flag = range();
return;
}
if (i >= 20 || flag) return;
turn(i);
DFS(i + 1, dp + 1);
turn(i);
DFS(i + 1, dp);
}
int main()
{
int i;
for (i = 0; i < 20; i++)
cin >> bowl[i];
for (step = 0; step<20; step++)
{
flag = 0;
DFS(0, 0);
if (flag) break;
}
cout << step << endl;
return 0;
} ビット演算で0 ms秒を列挙しよう~~~
#include
#include
using namespace std;
#define inf 0x7fffffff
#define min(a,b) a> x;
if (x)
mpt[j] |= 1 << 0;
} // 1， 20
for (i = 0; i < 1 << 1; i++){
for (j = 0; j < 20; j++)
tmp[j] = mpt[j];
for (j = 0; j < 20; j++){
sign[j] = j == 0 ? i : tmp[j - 1];
tmp[j] ^= sign[j];
tmp[j + 1] ^= sign[j];
}
if (!tmp[19]){
cnt = 0;
for (j = 0; j < 20; j++)
if (sign[j] & 1)
cnt++;
}
minn = min(minn, cnt);
}
cout << minn << endl;
return 0;
}