D - Minimax Problem
题意: 一个 n 行 m 列的矩阵, 找一对可能相同的 i,j, 使得这两行中, 设 bk 为每列对应元素 aik,ajk 的最大值, 使得 b 序列的的最小值最大.
题解: 二分这个值, 然后转化成验证其是否成立.
为了减少 check 的次数, 先进行一次离散化, 大概可以减少 10 次 check(应该), 优化了 1/3 常数. 应该还可以找每行的最小值的最大值作为二分的 L.
check 里面, 对每行计算一个可行向量, 当两行的可行向量的或为全 1 时, 则这两行为题目所要的解.
注意若一直 check 失败最后要补 check 一次 L 来真正更新答案, 这里被 hack 了. 因为这种二分是必定有解的所以忽略了最后 check(L) 的步骤, 可能这种对低级题目的掌控全局的自满导致了我的 FST 吧, 还好不是区域赛不然就惊喜 30 分钟了. 以后二分到达边界之后把两个值都 check 一遍, 确定一定会有解的话就把这种自满加在 assert 里面吧.
- int a[300005][8];
- int vis[1 <<8];
- int b[2400005], btop;
- int ansi, ansj;
- int n, m;
- bool check(int mid) {
- memset(vis, 0, sizeof(vis));
- for(int i = 1; i <= n; ++i) {
- int cur = 0;
- for(int j = 0; j < m; ++j)
- cur = (cur << 1) | (a[i][j]>= mid);
- vis[cur] = i;
- }
- int all1 = (1 <<m) - 1;
- for(int i = all1; i; --i) {
- if(!vis[i])
- continue;
- for(int j = 0; j < m; ++j) {
- if((i>> j) & 1)
- vis[i ^ (1 <<j)] = vis[i];
- }
- }
- for(int i = 0; i < (1 << m); ++i) {
- if(!vis[i])
- continue;
- int w = all1 ^ i;
- if(vis[w]) {
- ansi = vis[i];
- ansj = vis[w];
- return true;
- }
- }
- return false;
- }
- void bs() {
- int L = 1, R = btop;
- while(true) {
- int mid = (L + R)>> 1;
- if(mid == L) {
- if(check(R))
- return;
- else {
- assert(check(L));
- return;
- }
- }
- if(check(mid))
- L = mid;
- else
- R = mid - 1;
- }
- }
- void test_case() {
- scanf("%d%d", &n, &m);
- for(int i = 1; i <= n; ++i) {
- for(int j = 0; j < m; ++j) {
- read(a[i][j]);
- b[++btop] = a[i][j];
- }
- }
- sort(b + 1, b + 1 + btop);
- btop = unique(b + 1, b + 1 + btop) - (b + 1);
- for(int i = 1; i <= n; ++i) {
- for(int j = 0; j < m; ++j)
- a[i][j] = lower_bound(b + 1, b + 1 + btop, a[i][j]) - b;
- }
- bs();
- printf("%d %d\n", ansi, ansj);
- }
来源: http://www.bubuko.com/infodetail-3382597.html