当前位置：首页 > news >正文

#题解#牛客：小心火烛的歪#枚举组合#位运算#dfs#

news 2026/5/12 18:22:26

传送门

分析

1.这是一个枚举组合求最优的问题：集合大小q为7，可以用位运算来进行组合枚举

2.若点火方案f[i][j]==g[i][j]=1则，该方案一定不能用

3.令 g[i][j]+=f[i][j]，若该方案可用且在枚举子集内，最终g中没有0则该子集符合条件

代码实现

#include<bits/stdc++.h>
using namespace std;
int n, m, q;
int  g[10][10], f[10][10][10], book[10];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int kk = 0;cin >> n >> m >> q;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++){char c;cin >> c;g[i][j] = c - '0';kk += g[i][j];}int no = 0;for (int k = 0; k < q; k++)for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++){char c;cin >> c;f[k][i][j] = c - '0';if (f[k][i][j] == g[i][j] and g[i][j] == 1){if (!book[k])no++;book[k] = 1;}}if (kk == n * m)//g本身已经符合无0条件{cout << 0;return 0;}if (no == q)//所有方案都不能用{cout << -1;return 0;}bool check = 0;//记录是否有解int ans = q;//记录最小方案数int N = (1 << q);int method = N - 1;//记录方案集for (int x = 0; x < N; x++)//枚举方案集{int tmp[10][10];memcpy(tmp, g, sizeof(tmp));for (int k = 0; k < q; k++)if (!book[k] and x >> k & 1 )//k可用且在方案集x中for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)tmp[i][j] += f[k][i][j];bool flag = 1;//记录x是否符合无0条件for (int i = 1; i <= n; i++){if (!flag) break;for (int j = 1; j <= m; j++)if (tmp[i][j] == 0){flag = 0;//有0则x不符合无0条件break;}}if (flag)//x是个解{check = 1;//有解int y = x;int cnt = 0;for (; y; y -= y & -y)//求x在二进制下有多少1，即这个集合的大小，即方案数cnt++;if (ans > cnt)//更新{ans = cnt;method = x;}}}if (check)//有解则输出{cout << ans << "\n";for (int k = 0; k < q; k++)if ( method >> k & 1 )cout << k + 1 << " ";}else//无解cout << -1;return 0;
}