C. Guessing the Greatest（交互题）

题意

一个数组有$n$个不同的数，你每次可以询问一个区间，可以得到这个区间里第二大的数的位置。

问你是否能在$20$次以内，找到最大的数。$2 <= n <= 1e5 $。

思路

首先看范围 $20$次正好大于$1e5$，所以答案肯定是$logN$的复杂度，大概可以确定是二分。

先询问整个区间，找到整个区间第二大的位置$x$，这就是解题的关键。
随便选一个点与$x$进行询问，如果返回结果是$x$，那么表示最大值在这个区间里，如果不是$x$，则最大值不在这个区间。
我们用这点进行二分。

得到$x$后，要确定最大值在$x$左边还是右边，所以找两个端点（任意一个）和$x$做询问。
判断出最大值在那边，然后就是模板二分了。

需要注意的几个点：
1.区间询问一定要大于1，也就是l,r不能相等，所以要在n=2的时候做一个特判。
2.要注意$x$如果为边界点（1 or n）的时候，直接二分另外一边就行。
3.二分时要把点x去掉，原因还有点没想通。。

代码

#include<bits/stdc++.h>

using namespace std;

#define x first
#define y second

typedef long long LL;
typedef pair<int,int> PII;

const int N = 2010;

int n;
int a[N], b[N];

int check(int l, int r)
{
    cout << "? " << l << ' ' << r << endl;
    cout.flush();
    int t;
    cin >> t;
    return t;
}

void solve()
{
    cin >> n;
    int x = check(1, n), t;
    if(n == 2)
    {
        if(x == 1) cout << "! " << 2 <<endl;
        else cout << "! " << 1 <<endl;
        return;
    }
    if(x != 1 && x != n) t = check(1, x);
   if(t == x || x == n) // 在左边
    {
        int l = 1, r = x - 1;
        while(l < r)
        {
            int mid = l + r + 1>> 1;
            if(check(mid, x) == x) l = mid;
            else r = mid - 1;
        }
        cout << "! " <<l<<endl;
    }
    else
    {
        int l = x + 1, r = n;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(check(x, mid) == x) r = mid;
            else l = mid + 1;
        }
        cout << "! " << l << endl;
    }

}

int main()
{

    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
   /*int t;
    cin >> t;
    while(t --)*/
        solve();
    return 0;
}

D. Max Median

题意

给一个长度为n的数组，找到一个长度不小于k的子数组（连续），且中位数最大。

思路

找一个区间内的中位数，可以用前缀和来写，设中位数为$x$。

将比x小的数设为-1，大于等于的设为1，对这个求前缀和sum。

如果存在sum[r] > sum[l]，则在[l, r]上可以找到这个中位数。

所以可以通过二分枚举中位数，上述条件作为check，

代码

#include<bits/stdc++.h>

using namespace std;

#define x first
#define y second

typedef long long LL;
typedef pair<int,int> PII;

const int N = 200010;

int n, k;
int a[N], sum[N], w[N];

int check(int x)
{
    int lower = 0;
    for(int i = 1; i <= n; i ++)
    {
        if(a[i] >= x) w[i] = 1;
        else w[i] = -1;
        sum[i] = w[i] + sum[i - 1];
        if(i >= k && sum[i] > lower) return true;
        if(i >= k) lower = min(lower, sum[i - k + 1]);
    }
    return false;
}

void solve()
{
    cin >> n >> k;

    for(int i = 1; i <= n; i ++) cin >> a[i];
    int l = 1, r = n;
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << r << endl;
}

int main()
{

    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
   /*int t;
    cin >> t;
    while(t --)*/
        solve();
    return 0;
}

很多地方学习的 @滑稽_ωﾉ 大佬