admin管理员组

文章数量:1559094

icpc 2017 japan domestic --making lunch boxes(位运算枚举）

题目描述
taro has been hooked on making lunch boxes recently. taro has obtained a new lunch box recipe book today, and wants to try as many of the recipes listed in the book as possible. 
enough of the ingredients for all the recipes are at hand, but they all are in vacuum packs of two. if only one of them is used leaving the other, the leftover will be rotten easily, but making two of the same recipe is not interesting. thus he decided to make a set of lunch boxes, each with different recipe, that wouldn't leave any unused ingredients. 
note that the book may include recipes for different lunch boxes made of the same set of ingredients. 
how many lunch box recipes can taro try today at most following his dogma? 
 

 

输入
the input consists of at most 50 datasets, each in the following format. 
n m
b1,1...b1,m 
 ... 
bn,1...bn,m 
the first line contains n, which is the number of recipes listed in the book, and m, which is the number of ingredients. both n and m are positive integers and satisfy 1 ≤ n ≤ 500, 1 ≤ m ≤ 500 and 1 ≤ n × m ≤ 500. the following n lines contain the information for each recipe with the string of length m consisting of 0 or 1. bi,j implies whether the i-th recipe needs the j-th ingredient. 1 means the ingredient is needed for the recipe and 0 means not. each line contains at least one 1. 
the end of the input is indicated by a line containing two zeros. 
 

 

输出
for each dataset, output the maximum number of recipes taro can try. 

 

样例输入
4 3
110
101
011
110
7 1
1
1
1
1
1
1
1
4 5
10000
01000
00100
00010
6 6
111111
011000
100000
000010
100001
100100
0 0

 

样例输出
3
6
0
6


ｎ×ｍ小于500，n较小时枚举n，m较小时枚举m，界限为根号500=22.3=22；
#include "bits/stdc  .h"
using namespace std;
const int inf = 0x3f3f3f3f;
int mp[600][600];
int dp[2][1 << 22];
int bit[560];
int n, m;
void slove_n() {
    int ans = 0;
    int to = 1 << n;
    for (int i = 0; i < to; i  ) {
        int cnt = 0;
        for (int j = 0; j <= m; j  ) bit[j] = 0;
        for (int j = 0; j < n; j  ) {
            if (i & (1 << j)) {
                for (int k = 0; k < m; k  )
                    bit[k] ^= mp[j][k];
                cnt  ;
            }
        }
        int flag = 0;
        for (int j = 0; j < m; j  ) flag |= bit[j];
        if (!flag) ans = max(ans, cnt);
    }
    cout << ans << endl;
}
void slove_m() {
    int to = 1 << m;
    for (int i = 0; i < n; i  ) {
        bit[i] = 0;
        for (int j = 0; j < m; j  ) {
            bit[i] |= (mp[i][j] << j);
        }
    }
    for (int i = 0; i < to; i  ) {
        dp[0][i] = -inf;
        dp[1][i] = -inf;
    }
    dp[0][0] = 0;
    for (int i = 0; i < n; i  ) {
        for (int j = 0; j < to; j  ) {
            dp[(i   1) % 2][j ^ bit[i]] = max(dp[(i   1) % 2][j ^ bit[i]], dp[i % 2][j]   1);
            dp[(i   1) % 2][j] = max(dp[(i   1) % 2][j], dp[i % 2][j]);
        }
    }
    cout << dp[n % 2][0] << endl;
}
int main() {
    freopen("input.txt", "r", stdin);
    char ch;
    while (cin >> n >> m) {
        if (n == 0 && m == 0) break;
        for (int i = 0; i < n; i  ) {
            for (int j = 0; j < m; j  ) {
                cin >> ch;
                mp[i][j] = ch - '0';
            }
        }
        if (n <= 22)
            slove_n();
        else
            slove_m();
    }
    return 0;
}

 

posted @ 2018-10-24 20:45 albert_liu 阅读( ...) 评论( ...) 编辑 收藏

本文标签： japandomestic

j9九游会老哥俱乐部交流区的版权声明：本文标题：icpc 2017 japan domestic --making lunch boxes(位运算枚举） 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.elefans.com/xitong/1727371409a1111215.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。