牛客周赛 Round 60

题目链接

A

4个相等的数异或为0，直接输出0

B

设正数数量为 a，负数数量为 b。当 a = b，res = a + b

当 a != b，那么相当于将多的放在最前面和最后面，res = 2 * min(a, b) + 1;

C

求同行和同列的最大极差

#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
vector<int> row[N], col[N];
int n, m;

int main()
{
    cin >> n >> m;  
    while (m--)
    {
        int x, y; cin >> x >> y;
        row[x].push_back(y), col[y].push_back(x);
    }
    
    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        if (row[i].size() < 2) continue;
        int mx = -1, mi = 1e6;
        for (auto& e : row[i])
            mx = max(mx, e), mi = min(mi, e);
        res = max(res, mx - mi);
    }
    for (int i = 1; i <= n; i++)
    {
        if (col[i].size() < 2) continue;
        int mx = -1, mi = 1e6;
        for (auto& e : col[i])
            mx = max(mx, e), mi = min(mi, e);
        res = max(res, mx - mi);
    }
    cout << res << endl;
}

D

维护一个集合（sum），表示当前可以组成的数的上界。先将数组排序，比较当前数 a[i] 和上界的大小：

• a[i] > sum + 1，表示 sum + 1 无法被构造出来
• a[i] <= sum + 1，当前可以构成的上界为：sum + a[i]

using LL = long long;
const int N = 1e5 + 10;
int a[N], n;

void slove()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    LL sum = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] <= sum + 1) {
            sum += a[i];
        }
    }
    
    if (sum >= n) cout << "Cool!" << endl;
    else cout << sum + 1 << endl;
}  

E

一个组合数，中间长度为 n - 2，能推 m - 1 次，问有多少种推法？

C(n - 2, m - 1)

#include<iostream>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
const int Mod = 1e9 + 7;
int fact[N], infact[N];
int n, m;
int qmi(int a, int k, int p)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = (ll) res * a % p;
        a = (ll) a * a % p;
        k >>= 1;
    }
    return res;
}

void init()
{
    infact[0] = fact[0] = 1;
    for(int i = 1; i < N; i++)
        fact[i] = (ll) fact[i - 1] * i % Mod;
    for(int i = 1; i < N; i++)
        infact[i] = (ll) infact[i - 1] * qmi(i, Mod - 2, Mod) % Mod;
}

int main()
{
    int t; cin >> t;
    init();
    while(t--)
    {
        cin >> n >> m;
        int a = n - 2, b = m - 1;
        cout << (ll) fact[a] * infact[b] % Mod * infact[a - b] % Mod << endl;
    }
    return 0;
}