Codeforces Round 964 (Div. 4)](https://codeforces.com/contest/1999)

B.如何优雅的暴力？

题意：总共四张牌，每个人分两张牌，进行两轮游戏。每轮游戏双方各出一张牌，谁大谁win。在所有可能的抽卡结果和出牌顺序中，alice能win的数量。win定义为两场全胜

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int f(int x, int y) {
    if (x > y)
        return 1;
    else if (x == y)
        return 0;
    else
        return -1;
}
void solve() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int ans = 0;
    if (f(a, c) + f(b, d) > 0)
        ans++;
    if (f(a, d) + f(b, c) > 0)
        ans++;
    if (f(b, c) + f(a, d) > 0)
        ans++;
    if (f(b, d) + f(a, c) > 0)
        ans++;
    cout << ans << endl;
}

E.给出一个操作，每次选两个集合里的数x,y。x−>x/3,y−>3yx->x/3,y->3y.多次区间询问[l,r]作为这个初始集合的时候，需要多少次操作才能让集合变为全部变为0.

Sol：考虑应该先让最小的元素变成0，这样他就能一直作为y，从而使次数不增加。考虑多次区间询问，我们预处理前缀和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int n, m;
int a[N];
int pre[N];
void init() {//在main函数调用
    for (int i = 1; i <= N - 10; i++) {
        int tmp = i;
        int cnt = 0;
        while (tmp) {
            cnt++;
            tmp /= 3;
        }
        pre[i] = cnt;
        pre[i] += pre[i - 1];
    }
}
void solve() {
    int l, r;
    cin >> l >> r;
    int ans = pre[r] - pre[l - 1];
    int mn = pre[l] - pre[l - 1];
    cout << ans + mn << endl;
}

F：给定一个0,1序列。求长度为k的子序列所有中位数之和。

Sol:kk输入保证是奇数。中位数就是a[(k+1)/2]a[(k+1)/2].希望它能贡献，就需要它0的个数少于（k+1)/2（k+1)/2.设0的总数数量为c0c_{0}，1的数量的为c1c_{1}。枚举0的数量为x，则答案为∑x=0(k+1)/2−1Cc0xCc1n−x\sum_{x=0}^{(k+1)/2-1}C_{c_{0}}^{x}C_{c_{1}}^{n-x}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void solve() {
    int k;
    cin >> n>>k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int c0=0,c1=0;
    for(int i=1;i<=n;i++)if(a[i]==0)c0++;else c1++;
    int ans=0;
    for(int x=0;x<=(k-1)/2;x++){
        int y=k-x;
        ans=(ans+C(c0,x)*C(c1,y)%mod)%mod;
 
    }
    cout<<ans<<endl;
}