源代码:https://github.com/abmcar/ACM/tree/master/OpenjudgeNow/Codeforces/Codeforces%20Round%20%23763%20(Div.%202)
cf合集:https://github.com/abmcar/ACM/tree/master/OpenjudgeNow/Codeforces

A. Robot Cleaner

在这里插入图片描述

题目大意:给你一个n*m的网格，给你一个扫地机器人的坐标和垃圾坐标，扫地机器人每次可以清理和他同行和同列的的垃圾，每次机器人会向右下移动，遇到墙会反弹，问它移多少次可以清扫到垃圾
思路：分别在x、y轴判断机器人到达同行或者同列的时间，只需要判断是否会反弹回来即可

代码：

void work()
{
    cin >> n >> m;
    cin >> rb >> cb >> rd >> cd;
    int ans = 1e9;
    if (rb > rd)
        ans = 2 * n - rb - rd;
    else
        ans = rd - rb;
    if (cb > cd)
        ans = min(ans, 2 * m - cb - cd);
    else
        ans = min(ans, cd - cb);
    cout << ans << endl;
}

B. Game on Ranges

在这里插入图片描述

题目大意：给你一个数组，你可以选择一个区间[L,R]并选择一个K使其分裂为[L,K-1]和[K+1,R]，现在给你数组的长度和每次选择的区间，求每次选择的K
思路：
记录下每个区间的L,R，对区间的大小排序，因为每次分裂选择一个数，所以我们从小到大即可保证分裂的子区间已经计算过
我们用一个数组num来记录是否这个位置的已经被分裂过
对于长度为1的区间，K既是它本身，此时num[k] += k
对于长度不为1的区间,因为之前的区间已经处理过，此时我们知道k = 原区间和-num的区间和，得到k后继续num[k] += k
至于这个求和和修改操作，我们可以用树状数组解决
代码：

template <typename T>
class Fenwick
{
public:
    vector<T> fenw;
    int n;
    Fenwick(int _n) : n(_n)
    {
        fenw.resize(n + 1);
    }
    void modifty(int x, int val)
    {
        while (x <= n)
        {
            fenw[x] += val;
            x |= (x + 1);
        }
    }

    T get(int x)
    {
        T cnt{};
        while (x >= 0)
        {
            cnt += fenw[x];
            x = (x & (x + 1)) - 1;
        }
        return cnt;
    }
};

int t, n;
struct Edge
{
    int from, to;
    int size;
    bool operator<(Edge b) const
    {
        return size < b.size;
    }
} edges[Maxn];
void work()
{
    cin >> n;
    unordered_map<int, int> M[Maxn];
    vector<int> r(n + 1);
    vector<int> tx, ty;
    vector<int> g[Maxn];
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        int t1, t2;
        cin >> t1 >> t2;
        tx.push_back(t1);
        ty.push_back(t2);
        M[t1][t2] = ++cnt;
        edges[cnt].from = t1;
        edges[cnt].to = t2;
        edges[cnt].size = t2 - t1 + 1;
    }
    Fenwick<int> fen(n);
    sort(edges + 1, edges + 1 + cnt);
    for (int i = 1; i <= cnt; i++)
    {
        int l = edges[i].from;
        int r = edges[i].to;
        int nowAns = fen.get(r) - fen.get(l - 1);
        nowAns = edges[i].size * (l + r) / 2 - nowAns;
        fen.modifty(nowAns, nowAns);
        cout << l << " " << r << " " << nowAns << endl;
    }
    cout << endl;
}

树状数组板子：https://blog.csdn.net/qq_23323539/article/details/122277303

C. Balanced Stone Heaps

在这里插入图片描述
题目大意:给你n堆石子的数量h1,h2--hn,你可以从第3堆到第n堆对这些石子进行一些操作,你可以选择一个d,0 <= 3d <= hi,把第i堆的d个石子给第i-1堆,把2d个石子给第i-2堆,问操作后最小的石子堆中的最大石子数使多少
思路:最小找最大,是很常见的二分,如果没有顺序限制,这就是一个二分答案板子题,从n到3判断时候大于mid,是则移动n-mid个石子给前面,但实际上,这道题虽然要求了顺序,但我们发现并不影响二分答案的正确性,只需要给每次移动的石子一个限制,即每次移动的石子是<hi的即可

代码:

bool check(int x)
{
    vector<int> nowH(n + 1);
    nowH = h;
    for (int i = n; i >= 1; i--)
    {
        if (nowH[i] < x)
            return false;
        if (i < 3)
            continue;
        int nowMore = nowH[i] - x;
        int nowD = nowMore / 3;
        int oriMax = h[i]/3;
        nowD = min(oriMax,nowD);
        nowH[i] = nowH[i] - 3*nowD;
        nowH[i - 1] += nowD;
        nowH[i - 2] += 2 * nowD;
    }
    // for (int i = 1; i <= n; i++)
    //     cout << nowH[i] << " ";
    // cout << endl;
    return true;
}

void work()
{
    cin >> n;
    h.resize(n+1);
    for (int i = 1; i <= n; i++)
        cin >> h[i];
    int l = 0;
    int r = h[n];
    int ans;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (check(mid))
        {
            l = mid + 1;
            ans = mid;
        }
        else
            r = mid - 1;
    }
    cout << ans << endl;
}