牛客编程巅峰赛S2第4场 - 钻石&王者

A 牛牛摆玩偶

需要放置个 物品，每个物品都必须放在合法区间内，每个位置只能放一个物品。有 个互不相交的区间，题目希望相邻物品之间的距离的最小值越大越好，请输出这个值。

思路

二分答案，或者来。

我的做法貌似麻烦了一点，问题不大，欢迎提出你的做法。

因为区间两两不相交，但是我又不确定区间是否有序，所以我把区间左右端点全部用一个set保存起来，并记录一下是左端点还是右端点。

然后记录一下上一个玩偶放置的位置，用找到下一个可以放的位置：

• 如果是左端点，这一个就放在这里
• 如果是右端点，这一个就放在

看是否放置了个玩偶。

#define fi first
#define se second
#define mk make_pair
#define o2(x) (x) * (x)
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset((a), (b), sizeof((a)))
#define GKD std::ios::sync_with_stdio(false);cin.tie(0)
#define rep(i, s, t) for(int i = (s), LIM=(t); i < LIM; ++i)
#define per(i, s, t) for(int i = (s), LIM=(t); i >= LIM; --i)
#define my_unique(x) sort(all(x)), x.erase(unique(all(x)), x.end())
typedef long long LL;
typedef long long int64;
typedef unsigned long long uint64;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;// 998244353
const int MXN = 2e5 + 5;
const int maxn = 2e5 + 7;

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param n int整型 玩偶数
     * @param m int整型 区间数
     * @param intervals Interval类vector 表示区间
     * @return int整型
     */
    int doll(int n, int m, vector<Interval>& intervals) {
        // write code here
        LL L = 1, R = 1e10, mid, ans = 0;
        set<pii> mp;
        for(Interval x: intervals) {
            mp.insert(mk(x.start, 1));
            mp.insert(mk(x.end, 2));
        }
        auto check = [&](int mid) {
            LL L = -1e11;
            int cnt = 0;
            while(cnt < n) {
                auto p = mp.lower_bound(mk(L + mid, 0));
                if(p == mp.end()) return false;
                if((*p).se == 1) {
                    ++ cnt;
                    L = (*p).fi;
                }else if((*p).se == 2) ++ cnt, L = L + mid;
            }
            return cnt == n;
        };
        while(L <= R) {
            mid = (L + R) >> 1;
            if(check(mid)) ans = mid, L = mid + 1;
            else R = mid - 1;
        }
        return (int)ans;
    }
};

B 交叉乘

给你个数，多次询问，每次询问给你，输出的值模1000000007。

思路

算贡献经典老题。

将答案补全为：。

预处理出。

再预处理。

然后就可以回答答案了。

#define fi first
#define se second
#define mk make_pair
#define o2(x) (x) * (x)
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset((a), (b), sizeof((a)))
#define GKD std::ios::sync_with_stdio(false);cin.tie(0)
#define rep(i, s, t) for(int i = (s), LIM=(t); i < LIM; ++i)
#define per(i, s, t) for(int i = (s), LIM=(t); i >= LIM; --i)
#define my_unique(x) sort(all(x)), x.erase(unique(all(x)), x.end())
typedef long long LL;
typedef long long int64;
typedef unsigned long long uint64;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;// 998244353
const int MXN = 2e5 + 5;
const int maxn = 2e5 + 7;

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 多次求交叉乘
     * @param a int整型vector a1,a2,...,an
     * @param query int整型vector l1,r1,l2,r2,...,lq,rq
     * @return int整型vector
     */
    vector<int> getSum(vector<int>& a, vector<int>& query) {
        // write code here
        int n = a.si***t)query.size() / 2;
        vector<LL> suf(n + 1, 0), pre(n, 0), pre2(n, 0);
        per(i, n - 1, 0) {
            suf[i] = suf[i + 1] + a[i], suf[i] %= mod;
            if(i != n - 1) pre[i] = a[i] * suf[i + 1] % mod;
        }
        rep(i, 1, n) pre[i] = (pre[i] + pre[i - 1]) % mod;
        pre2[0] = a[0];
        rep(i, 1, n) pre2[i] = (pre2[i - 1] + a[i]) % mod;
        vector<int> ans, q(query);
        while(m --) {
            int R = q.back() - 1; q.pop_back();
            int L = q.back() - 1; q.pop_back();
            LL res = pre[R] - (L == 0? 0: pre[L - 1]);
            res %= mod;
            LL res2 = pre2[R] - (L == 0? 0: pre2[L - 1]);
            res2 %= mod;
            LL hou = 0;
            if(R != n - 1) hou = suf[R + 1];
            res = (res - res2 * hou % mod) % mod;
            res = (res + mod) % mod;
            ans.push_back((int)res);
        }
        reverse(all(ans));
        return ans;
    }
};

C 回家

二维矩阵内，每个格子住了一个人，初始矩阵为空，给出个人回家顺序，每个人可以从矩阵边缘的任意一点出发，4联通方式走回家，一个人完全回家后另一个人才能出发。回家的时候尽量不经过有人的格子，经过一次有人的格子他的沮丧值加，我希望所有人沮丧值之和最小，输出这个值。