「CF1423M」Milutin's Plums

发表于 | 更新于 | 分类于 | 阅读次数：

题意简述

交互题。
矩阵 $n\times m$，有性质：
对于任意子矩阵（即任意行的子集和列的子集的交），设子矩阵中第 $i$ 行最小值最先出现的位置是 $L(i)$，则 $L(i)$ 单调不降。

通过不超过 $4(n + m)$ 次单点询问确定该矩阵的最小值。

主要思路

转化问题为对每行 $i$ 求 $ans_i$ 使得 $(i, ans_i)$ 为该行最小最前的位置。

那么根据给定的性质，一个自然的想法是：

假如现在需要求答案的行集合为 $S$（按大小排序），已求出 $T = \{S_{2i}\}$ 的答案。
则此时 $S$ 中未被求出答案的所有元素 $x$ 的答案都被限定在上下两元素的答案范围内，可以暴力询问求解。
边界情况显然为 $|S| = 1$，此时使用 $m$ 次询问暴力求出答案即可。

那么对于集合 $S$，记其最多需要的询问次数为 $f(|S|) = f(\frac{|S|}{2}) + |S| + m$。
则总共需要 $2n + m\log n$ 次。

尽管 $n$ 的系数足够小，但 $m$ 的系数太大。

设可能的列的集合为 $T$，如果 $|T|>|S|$，我们尝试将先减小 $T$ 的大小。

考虑两个元素 $a(x, l), a(x, r)$。
如果 $a(x, l)\le a(x, r)$，则显然对于任意 $i\le x$，$L(i)\ne r$；
如果 $a(x, l)> a(x, r)$，则同理对于任意 $i\ge x$，$L(i)\ne l$。

由此我们可以在 $|S| + |T|$ 步内将 $T$ 的大小缩小为 $|S|$。

此时对于集合 $S$，最多需要的询问次数即为 $f(|S|) = f(\frac{|S|}{2}) + 2|S| + 2|T|$，即最多需要 $4(n + m)$ 次。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a), ed_##i = (b); i <= ed_##i; ++i)
#define ROF(i, a, b) for (int i = (a), ed_##i = (b); i >= ed_##i; --i)
#define MP make_pair
#define pb push_back
typedef pair<int, int> PII;
typedef vector<int> VI;
#define SZ(x) ((int)(x).size())
#define Templ(T) template <typename T>
inline int read() {
    int ans = 0;
    char c = getchar();
    while (!isdigit(c)) c = getchar();
    for (; isdigit(c); c = getchar())
        ans = ans * 10 + c - '0';
    return ans;
}
Templ(_Tp) inline int chkmin(_Tp &x, _Tp y) { return x > y ? x = y, 1 : 0; }
Templ(_Tp) inline int chkmax(_Tp &x, _Tp y) { return x < y ? x = y, 1 : 0; }

#ifdef LOCAL
#define N 1010
int qry[N][N];
int qry_cnt;
#endif

map<PII, int> mem;

inline int ask(int x, int y){
    if(mem.count(MP(x, y))) return mem[MP(x, y)];
    printf("? %d %d\n", x, y), fflush(stdout);
    #ifdef LOCAL
    return ++qry_cnt, qry[x][y];
    #endif
    return mem[MP(x, y)] = read();
}

//由于列太多，需要去除一些不可能在 ans 里的列
inline VI Reduce(VI rows, VI cols){
    VI ans;
    const int n = SZ(rows);

    int i = 0, r;
    for(int c: cols){
        if(ans.empty()){
            ans.pb(c);
            continue;
        }
        r = rows[i];
        int y = ans.back();
        while(ask(r, y) > ask(r, c)){
            ans.pop_back();
            --i;
            if(ans.empty()) break;
            r = rows[i];
            y = ans.back();
        }
        if(SZ(ans) == n) continue;
        else{
            ans.pb(c);
            ++i;
        }
    }
    //注意这里仅仅是简单地去掉了一些多余的列
    //并不具有正确性
    return ans;
}

//(rows[i], ans[i]) 为该行最小且最前的
VI Solve(VI rows, VI cols){
    if(SZ(rows) < SZ(cols)){
        cols = Reduce(rows, cols);
    }

    const int n = SZ(rows), m = SZ(cols);

    VI nrows;
    for(int i = 1; i < n; i += 2){
        nrows.pb(rows[i]);
    }

    VI nans;
    if(!nrows.empty()){
        nans = Solve(nrows, cols);
    }
    //先做奇数行

    VI ans;
    int lc = 0, rc;
    int x, y;
    FOR(i, 0, n - 1){
        if(i & 1){
            //对于奇数行，已经做过了
            ans.pb(nans[i >> 1]);
            continue;
        }
        rc = m - 1;
        if(i + 1 < n){
            rc = lc;
            while(cols[rc] < nans[i >> 1]){
                ++rc;
            }
        }else{
            rc = m - 1;
        }
        //根据题目性质，偶数行的答案应该在上下两行之间
        x = rows[i];
        y = cols[lc];
        // printf(": %d %d\n", x, y);
        int mn = ask(x, y);
        FOR(j, lc, rc){
            // printf(": %d %d\n", x, cols[j]);
            if(chkmin(mn, ask(x, cols[j]))){
                y = cols[j];
            }
        }
        //暴力找出来即可
        ans.pb(y);
        lc = rc;
    }
    return ans;
}

int main() {
    int n = read(), m = read();

    #ifdef LOCAL
    FOR(i, 1, n) FOR(j, 1, m) qry[i][j] = read();
    #endif

    VI rows, cols;
    FOR(i, 1, n) rows.pb(i);
    FOR(i, 1, m) cols.pb(i);
    VI ans = Solve(rows, cols);

    int mn = 0x3f3f3f3f;
    FOR(i, 0, n - 1){
        chkmin(mn, ask(rows[i], ans[i]));
    }

    printf("! %d\n", mn), fflush(stdout);

    #ifdef LOCAL
    printf("ask times: %d\n", qry_cnt);
    int rmn = 0x3f3f3f3f;
    FOR(i, 1, n) FOR(j, 1, m) chkmin(rmn, qry[i][j]);
    printf("real min: %d\n", rmn);
    puts(mn == rmn ? (qry_cnt <= 4 * (n + m) ? 
        "AC" : "AC but too many times") : "WA");
    #endif

    return 0;
}