2022CCPC广州

E. Elevator

题意：有n个电梯， 建筑有m层。每一个电梯从小到大有一个1-n的编号和出发的时间ai。在除了第一层和第m层都有一个开关，可以使到达这里的电梯停留1ms，问你对于第i个编号的电梯，如果要让它第一个到达m层，需要按多少层的开关。(如果有电梯同时到达，算编号小的先到)

6 20
3 8 12 6 9 9
 
 
0
8
-1
4
13
14

思路：观察样例可以知道，编号为i的电梯的作为第一个到达m层的时间=ai - 在前面出发的电梯的时间aj, 且如果j < i，编号小，ans还得额外+1. 那

那么就很简单了，我们只需要去维护一个数据结构，它支持记录当前位置前面的出发的电梯的总个数和总时间即可。

那么直接用树状数组维护一下即可。c1维护前面编号小且aj小的电梯个数。c2维护前面编号小的电梯出发的时间。因为我们将出发时间从小到大排序了，所以对于编号比当前大的后缀的数，直接用总的减去前缀即可。

#include
using namespace std;
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define x first
#define y second
#define endl '\n'
#define rep(i,a,n) for (int i = a; i < n; i ++ )
#define repn(i,a,n) for (int i = a; i <= n; i ++ )
#define pb push_back
#define IOS ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
typedef long long ll;
typedef unsigned long long ull;
#define all(x) (x).begin(),(x).end()
typedef pair<int,int> PII;
 
ll lowbit(ll x) { return x & (- x); }
ll gcd(ll a,ll b) { return b ? gcd(b,a % b) : a; }
const int mod = 1e9+7;
// Binary Index Tree
// Fenwick's Tree
const int N = 500010;
template<class T>
struct BIT {
    T c[N];
    int size;
    void init(int s) {
        size = s;
        for (int i = 1; i <= s; i++) c[i] = 0;
    }
    T query(int x) { // 1 ... x
        //assert(x <= size);
        T s = 0;
        for (; x; x -= x & (-x)) {
            s += c[x];
        }
        return s;
    }
 
    void modify(int x, T s) { // a[x] += s
        assert(x != 0);
        for (; x <= size; x += x & (-x)) {
            c[x] += s;
        }
    } 
};
BIT c1, c2;
vector v;
ll ans[N];
int n, m, a[N];
int main(){
    IOS;
    cin >> n >> m;
    repn(i, 1, n) cin >> a[i], v.pb({a[i], i});
    sort(all(v));
    c1.init(n);
    c2.init(n);
    ll s = 0;//s是记录和的
    rep(i, 0, n) {
        auto [val, pos] = v[i];
        ans[pos] += c1.query(pos) * (val + 1) - c2.query(pos);//前缀的
        ans[pos] += (i - c1.query(pos)) * val - (s - c2.query(pos));
        //第一个ans[pos]是查询前缀中的差值， aj - ai(i < j) = 前面比aj小的个数 * aj - 前面的和， 因为位置问题还要加1
        //第二个ans是记录后缀中的差值， 因为插入是一步步从小到大的，比它小的一定出现了，
        //用当前的个数 - 前缀的个数就是后缀中的数字个数 * val - (后缀的总和 = s - 前缀总和) s是记录当前未插入之前的和
        s += val;
        c1.modify(pos, 1);//当前位置++, 出现了1次
        c2.modify(pos, val);//当前位置的值是val
    }
    repn(i, 1, n) {
        if(ans[i] > m - 2)  ans[i] = -1;
        cout << ans[i] << endl;
    }
    
    
    return 0;
}

 H:GameX

博弈论：其实我屁都不会
Alice和Bob玩游戏， 定义Mex(s)是s中未出现过的最小自然数
每次Alice和Bob可以向集合中放数，最后MEX(s)是偶数Alice就赢了， 反之Bob赢了。

思路：因为要找最小的没出现过的数，要使一个数成为最终的判定数，小于他的数必须都出现过，
所以我们无论怎么放，都等价于从最小的数开始逐个往大放，我们从0开始遍历。A的最优策略就是放偶数，B的最优策略就是放奇数，我们从0开始遍历每个没在集合中的数，然后让AB进行他们所有的K个回合后，再重新遍历，看哪个数第一个没有出现。模拟

#include
using namespace std;
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define x first
#define y second
#define endl '\n'
#define rep(i,a,n) for (int i = a; i < n; i ++ )
#define repn(i,a,n) for (int i = a; i <= n; i ++ )
#define pb push_back
#define IOS ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
typedef long long ll;
typedef unsigned long long ull;
#define all(x) (x).begin(),(x).end()
typedef pair<int,int> PII;
 
ll lowbit(ll x) { return x & (- x); }
ll gcd(ll a,ll b) { return b ? gcd(b,a % b) : a; }
const int mod = 1e9+7;
const int N = 200010;
 
void solve() {
    int n, k; cin >> n >> k;
    map<int, int> mp;
    for (int i = 1; i <= n; i ++ ) {
        int x; cin >> x;
        mp[x] ++;
    }
    int now = 0;
    int opa = k, opb = k;
    while(opa || opb) {
        while(mp[now])  now ++;//找出不在集合中的第一个元素
        if(opb != 0 && now & 1) {
            opb --;
            mp[now] ++;
        }
        else if(opa != 0 && now % 2 == 0) {
            opa --;
            mp[now] ++;
        }
        now ++;
    }
    now = 0;
    while(mp[now])  now ++;//找出第一个不在集合中的元素
    if(now & 1) puts("Bob");
    else    puts("Alice");
}
 
int main(){
 
    IOS;
    int t;
    cin >> t;
    while(t -- ){
        solve();
    }
    
    return 0;
}

 L. Station of Fate

有n个人，m个车站，问你有多少种分配方式，保证每个车站必须有人。

思路：他妈的插板法。要把n个人分成m组，因为有n-1个空挡，我们只需要在n-1个空档中插入m-1个板子就行了， 又因为题目规定不同的排列算不同，所以再×排列的个数n!，这就是答案了。

记得算组合数Cn-1(m-1)时用一下费马小定理，将÷改成×。

#include
using namespace std;
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define x first
#define y second
#define endl '\n'
#define rep(i,a,n) for (int i = a; i < n; i ++ )
#define repn(i,a,n) for (int i = a; i <= n; i ++ )
#define pb push_back
#define IOS ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
typedef long long ll;
typedef unsigned long long ull;
#define all(x) (x).begin(),(x).end()
typedef pair<int,int> PII;
#define int long long 
 
ll lowbit(ll x) { return x & (- x); }
ll gcd(ll a,ll b) { return b ? gcd(b,a % b) : a; }
const int mod = 998244353;
const int N = 200010;
int f[N];
int qpow(int x) {
    int res = 1, b = mod - 2;
    while (b) {
        if (b & 1)
            res = res * x % mod;
        x = x * x % mod;
        b >>= 1;
    }
    return res;
}
 
void init() {
    f[0] = 1;
    for (int i = 1; i <= N; i ++ )  f[i] = (f[i - 1] * i) % mod;
}
 
int C(int a, int b) {
    if(b == 0)  return 1;
    return 1ll * f[a] * qpow(f[b]) % mod * qpow(f[a - b]) % mod;//费马小定理
}
 
 
void solve() {
    int n, m; cin >> n >> m;
    cout << f[n] * C(n - 1, m - 1) % mod << endl;
}
 
signed main(){
 
    IOS;
    init();
    int t;
    cin >> t;
    while(t -- ){
        solve();
    }
    
    return 0;
}
 
/*
where to find:
就是考虑n个人， 然后分成m组， 且n个人的顺序是可以不一样的
那么我们考虑一下插板法
n个人有n-1个空挡， 只需要插入m-1块板子， 就可以分成m组， 然后因为n个人的顺序不一样，所以×n!
*/