2020百度之星初赛二 Car（状压DP+二分）

本文主要是介绍2020百度之星初赛二 Car（状压DP+二分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem Description
W 市最近面临了严重的交通拥堵问题，现在决定要在工作日（周一到周五）限号。
每天可以限制若干尾号的车辆，譬如说周一限尾号为 0 的车，周二限尾号为 1,2 的车。

每个尾号在五天当中最多只能被限一次，一天也可以什么牌照都不限。

我们要设置一个容量上限 m，使得至少存在一种方案，每一天不被限号的车的总数都小于等于 m。

请求出最小的 m。

Input
第一行一个整数 test(1≤test≤10) 表示数据组数。

对于每组数据，第一行一个正整数 n(1≤n≤10000) 表示这个城市里有多少辆车。

接下来 n 行，每行一个字符串表示车牌。车牌由 5 位字符构成，每位都是’0’-'9’的数字。两辆车的车牌可能相同。

Output
对于每组数据，一行一个整数表示答案。

Sample Input
2
1
00000
10
00000
00001
00002
00003
00004
00005
00006
00007
00008
00009

Sample Output
1
8

Source
2020 年百度之星·程序设计大赛 - 初赛二

思路：
10的范围一眼状压，然后这个结果肯定有单调性，限制越大越容易满足，所以状压dp+二分就好了。只不过状压肯定不能两层for枚举状态，可以枚举超集，复杂度为3^n，这个之前也遇到了很多次了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include <map>
#include <string>
#include <cmath>using namespace std;
typedef long long ll;typedef long long ll;
const int maxn = 1e5 + 7;
const int mod = 1e9 + 7;int a[maxn]; //每个车牌号的数量int n;
int f[11][1 << 11];
int sta[1 << 11];void init() {for(int i = 0;i < (1 << 10);i++) {sta[i] = 0;for(int j = 0;j < n;j++) {if(i & (1 << j)) {sta[i] += a[j];}}}
}bool check(int mid) {memset(f,0x3f,sizeof(f));for(int i = 0;i < (1 << 10);i++) {f[1][i] = n - sta[i];}int cnt = 0;for(int i = 2;i <= 5;i++) { //第几天for(int j = 0;j < (1 << 10);j++) { //前一天状态if(f[i - 1][j] > mid) continue;for(int k = j; k < (1 << 10); k = (k + 1) | j) { //今天状态int num = n - sta[k ^ j];if(num > mid) {continue;}f[i][k] = min(f[i][k],num);}}int flag = 1;for(int j = 0;j < (1 << 10);j++) {if(f[i][j] <= mid) {flag = 0;break;}}if(flag) return false;}for(int i = 0;i < (1 << 10);i++) {if(f[5][i] <= mid) return true;}return false;
}int main() {int T;scanf("%d",&T);while(T--) {scanf("%d",&n);memset(a,0,sizeof(a));for(int i = 1;i <= n;i++) {int x;scanf("%d",&x);x %= 10;a[x]++;}init();int l = 0,r = n;int ans = n;while(l <= r) {int mid = (l + r) >> 1;if(check(mid)) {r = mid - 1;ans = mid;} else {l = mid + 1;}}printf("%d\n",ans);}return 0;
}