Codeforces Round #703 (Div. 2)補題

前言

一題自閉，掉大分，

題目

A

注意只能后移不能前移即可，

B

之前學長講過一維推廣到二維的情況，賽時也回想到了，但是沒想到曼哈頓距離也能推廣，算是個結論吧，

一維：奇數取中位數，偶數取兩個中位數之間的任何位置都可以，

AC代碼：

/*
 * @Author: hesorchen
 * @Date: 2020-11-26 09:12:46
 * @LastEditTime: 2021-02-19 15:31:36
 * @Description: 栽種絕處的花
 */
#include <bits/stdc++.h>
using namespace std;

int x[1010];
int y[1010];

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> x[i] >> y[i];
        sort(x + 1, x + 1 + n);
        sort(y + 1, y + 1 + n);
        if (n & 1)
            cout << 1 << endl;
        else
            cout << 1ll * (abs(x[n / 2] - x[n / 2 + 1]) + 1) * (abs(y[n / 2] - y[n / 2 + 1]) + 1) << endl;
    }

    return 0;
}

C2

互動題限制次數，1e5 20次，顯然二分，

賽時炸了腦子不夠清醒，在那碼了刪，刪了碼也不知道碼了些啥，比賽一結束理了一下思路就知道正解了，

先查詢一次[1,n]，得到position

• position==1，那么最大值肯定在[2,n]，對這個區間進行二分，每次查詢[1,mid]，如果結果不為1，那么說明最大值在[mid+1,n]，否則最大值在[2,mid]
• position==n，那么最大值肯定在[1,n-1]，對這個區間進行二分，每次查詢[mid,n]，如果結果不為n，那么說明最大值在[1,mid-1]，否則最大值在[mid,n-1]
• position在[2,n-1]，我們再查詢一次[1,position]，如果結果還是position，那么最大值在區間[1,position]，我們把position看做n，按照情況二處理即可，否則把position看做1，按照情況一處理，

AC代碼：

/*
 * @Author: hesorchen
 * @Date: 2020-11-26 09:12:46
 * @LastEditTime: 2021-02-19 15:39:29
 * @Description: 栽種絕處的花
 */
#include <bits/stdc++.h>
using namespace std;

int main()
{
    long long n;
    cin >> n;
    int pre = n, ans, flag = 1, res;
    cout << "? " << 1 << ' ' << n << endl;
    cout.flush();
    cin >> pre;
    if (n == 2)
    {
        int l = 1, r = 2;
        cout << "? " << l << ' ' << r << endl;
        cout.flush();
        cin >> pre;
        if (pre == l)
            return cout << "! " << r << endl, 0;
        else
            return cout << "! " << l << endl, 0;
    }
    if (pre == 1) //情況1
    {
        int l = 2, r = n;
        ans = n;
        while (l <= r)
        {
            int mid = l + r >> 1;
            cout << "? " << pre << ' ' << mid << endl;
            cout.flush();
            int temp;
            cin >> temp;
            if (temp != pre)
                l = mid + 1;
            else
            {
                r = mid - 1;
                ans = mid;
            }
        }
    }
    else if (pre == n) //情況2
    {
        int l = 1, r = n - 1;
        ans = 1;
        while (l <= r)
        {
            int mid = l + r >> 1;
            cout << "? " << mid << ' ' << pre << endl;
            cout.flush();
            int temp;
            cin >> temp;
            if (temp != pre)
                r = mid - 1;
            else
            {
                l = mid + 1;
                ans = mid;
            }
        }
    }
    else //情況3
    {
        int l = 1, r = n;
        int re1, re2;
        cout << "? " << 1 << ' ' << pre << endl;
        cout.flush();
        cin >> re1;

        if (re1 == pre) //類比情況2
        {
            int l = 1, r = pre - 1;
            ans = 1;
            while (l <= r)
            {
                int mid = l + r >> 1;
                cout << "? " << mid << ' ' << pre << endl;
                cout.flush();
                int temp;
                cin >> temp;
                if (temp != pre)
                    r = mid - 1;
                else
                {
                    l = mid + 1;
                    ans = mid;
                }
            }
        }
        else //類比情況1
        {
            int l = pre + 1, r = n;
            ans = r;
            while (l <= r)
            {
                int mid = l + r >> 1;
                cout << "? " << pre << ' ' << mid << endl;
                cout.flush();
                int temp;
                cin >> temp;
                if (temp != pre)
                    l = mid + 1;
                else
                {
                    r = mid - 1;
                    ans = mid;
                }
            }
        }
    }
    cout << "! " << ans << endl;
    return 0;
}

打比賽時頭腦還是不夠清醒，得改掉這個壞習慣，