牛客小白月赛25

个人博客：http://www.kindkidll.com/index.php/archives/152

A-AOE还是单体？

知识点：贪心

显然使用技能蛮牛践踏的条件是能对不少于 $x$ 个怪造成伤害，将所有的怪按血量升序排序，存在一个最大操作次数 $cnt$ ，当使用 $cnt$ 次蛮牛践踏技能后再使用此技能的收益不如使用蛮牛冲撞。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 1e6 + 117;

int n;
LL x;
LL a[MAXN], cnt;
LL sum;
int main() {
    scanf("%d%lld", &n, &x);
    for(int i = 0; i < n; i++) scanf("%lld", &a[i]);
    sort(a, a + n);
    for(int i = 0; i < n; i++) {
        if(n - i >= x) {
            cnt = a[i];
        } else {
            sum += a[i] - cnt;
        }
    }
    printf("%lld\n", sum + cnt * x);
    return 0;
}

B-k-size字符串

知识点：组合数学

整数拆分结论：把正整数 $n$ 拆分成 $m$ 个非负整数的方案数为 $C_{n+m-1}^{m-1}$ ，详见ACM中的整数K拆分。

若 $k$ 是偶数，则序列为 $a...b$ 或 $b...a$ 的形式。先取出 $k/2$ 个 $a$ 和 $b$ 出来构成 $abababab$ 序列，剩下的 $a$ 和 $b$ 是一个整数拆分问题，把 $n-k/2$ 个 $a$ 分到 $k/2$ 个位置和 $m-k/2$ 个 $b$ 分到 $k/2$ 个位置。此时两种序列的方案数是相等的。
若 $k$ 是奇数，则序列为 $a...$ a或 $b...b$ 的形式。以前者为例，先取出 $k/2+1$ 个 $a$ 和 $k/2$ 个 $b$ 出来构成 $abababa$ 序列，把剩下 $n-k/2-1$ 个 $a$ 分到 $k/2+1$ 个位置和 $m-k/2$ 个 $b$ 分到 $k/2$ 个位置。此时两种序列的方案数是不同的。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 3e5 + 117;
const int MAXM = 1e6 + 117;

LL n, m, k;
LL inv(LL a) {
    if(a == 1) return 1;
    return inv(mod % a) * (mod - mod / a) % mod;
}
LL C(LL n, LL m) {
    LL ret = 1;
    if(n - m < m) m = n - m;
    for(int i = 1; i <= m; i++) {
        ret = ret * (n - i + 1) % mod * inv(i) % mod;
    }
    return ret;
}
LL f(LL n, LL m) {
    if(n < 0 || m <= 0) return 0;
    return C(n + m - 1, m - 1);
}
int main() {
    cin >> n >> m >> k;
    if(k & 1) cout << (f(n - k / 2 - 1, k / 2 + 1)*f(m - k / 2, k / 2) % mod + f(n - k / 2, k / 2 )*f(m - k / 2 - 1, k / 2 + 1) % mod) % mod << endl;
    else cout << f(n - k / 2, k / 2)*f(m - k / 2, k / 2) % mod * 2 % mod << endl;
    return 0;
}

C-白魔法师

知识点：树形 $dp$

设 $dp[i][0]$ 是以结点 $i$ 为根结点的子树中，在不释放魔法的情况下包含结点 $i$ 的最大白色连通块的大小， $dp[i][1]$ 是释放魔法后包含结点 $i$ 的最大白色连通块的大小。

设结点 $j$ 是结点 $i$ 的孩子， $sum=\sum_{}^{} dp[j][0]$ 。

若结点 $i$ 为黑色，则 $dp[i][0]=0,dp[i][1]=sum+1$ 。结点 $i$ 为黑色，不释放魔法无法构成连通块，对结点 $i$ 释放魔法后可以连接子树的白色连通块。
若结点 $i$ 为白色，则 $dp[i][0]=sum+1,dp[i][1]=sum+1+max(dp[j][1]-dp[j][0])$ 。结点 $i$ 为白色，无需释放魔法就可以连接子树的白色联通块。释放魔法一定是改变子树中的某个结点，任意一颗子树对答案的贡献为 $dp[j][1]-dp[j][0]$ ，只能释放一次魔法取最大值即可。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e6 + 117;
const int MAXM = 1e6 + 117;

int n;
bool vis[MAXN];
char color[MAXN];
int tot, ans, dp[MAXN][2];
int head[MAXN], to[MAXN], ne[MAXN];
void init() {
    ans = tot = 0;
    memset(head, -1, sizeof(head));
    memset(vis, false, sizeof(vis));
}
void addedge(int u, int v) {
    to[tot] = v;
    ne[tot] = head[u];
    head[u] = tot++;
}
void dfs(int id) {
    vis[id] = true;
    int sum = 0, big = 0;
    for(int i = head[id]; i != -1; i = ne[i]) {
        if(!vis[to[i]]) {
            dfs(to[i]);
            sum += dp[to[i]][0];
            big = max(big, dp[to[i]][1] - dp[to[i]][0]);
        }
    }
    if(color[id - 1] == 'W') {
        dp[id][0] = sum + 1;
        dp[id][1] = sum + 1 + big;
    } else {
        dp[id][0] = 0;
        dp[id][1] = sum + 1;
    }
    ans = max(ans, dp[id][1]);
}
int main() {
    init();
    scanf("%d", &n);
    scanf("%s", color);
    for(int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        addedge(u, v);
        addedge(v, u);
    }
    dfs(1);
    printf("%d\n", ans);
    return 0;
}
/*
4
WWWB
1 2
1 3
2 4
*/

D-抽卡

知识点：概率计算、模运算、逆元

求能抽到自己想要的卡的概率，则求其对立事件没有抽到一张自己想要的卡的概率。每次抽卡都是独立事件，对于第 $i$ 次抽卡没有抽到自己想要的卡的概率为 $(a_i-b_i)/a_i$ 。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n;
int a[MAXN], b[MAXN];
LL sum;
LL inv(LL a) {
    if(a == 1) return 1;
    return inv(mod % a) * (mod - mod / a) % mod;
}
int main() {
    scanf("%d", &n);
    sum = 1;
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    for(int i = 0; i < n; i++) {
        scanf("%d", &b[i]);
        sum = sum * (a[i] - b[i]) % mod;
        sum = sum * inv(a[i]) % mod;
    }
    printf("%lld\n", ((1 - sum) % mod + mod) % mod);
    return 0;
}

E-点击消除

知识点：栈

括号配对问题，依次读取字符串，若和栈顶相同则栈顶弹出，否则入栈。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 3e5 + 117;
const int MAXM = 1e6 + 117;

char s[MAXN];
stack<char> t;
int main() {
    scanf("%s", s);
    int len = strlen(s);
    for(int i = len - 1; i >= 0; i--) {
        if(t.empty()) t.push(s[i]);
        else {
            if(t.top() == s[i]) t.pop();
            else t.push(s[i]);
        }
    }
    if(t.empty()) puts("0");
    else {
        while(!t.empty()) {
            putchar(t.top());
            t.pop();
        }
    }
    return 0;
}

F-疯狂的自我检索者

知识点：贪心

最小值为隐藏全为1分，最大值为隐藏全为5分。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 1e6 + 117;

int n, m;
int a[MAXN];
LL sum;
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n - m; i++) {
        scanf("%d", &a[i]);
        sum += a[i];
    }
    printf("%.5f %.5f\n", (sum + m) * 1.0 / n, (sum + m * 5) * 1.0 / n);
    return 0;
}

G-解方程

知识点：二分

求导可知该函数是个递增函数，求解可用二分，需要注意精度的控制。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-10;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

double a, b, c;
int main() {
    cin >> a >> b >> c;
    double l = 0, r = 1e9;
    while(r - l > eps) {
        double mid = (l + r) / 2;
        double f = pow(mid, a) + b * log(mid);
        if(f > c) r = mid;
        else l = mid;
        if(abs(f - c) < eps) break;
    }
    printf("%.7f\n", r);
    return 0;
}

H-神奇的字母（二）

知识点：计数、输入

出题人说考察对输入的处理方式。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 1e6 + 117;

char s[117], t;
int main() {
    while((t = getchar()) != EOF) {
        if('a' <= t && t <= 'z') s[t]++;
    }
    char ans = 'a';
    for(int i = 'a'; i <= 'z'; i++)
        if(s[ans] < s[i]) ans = i;
    putchar(ans);
    return 0;
}

I-十字爆破

知识点：预处理

预处理出每行每列的和，则输出=行+列-顶点，对于 $n,m$ 大小未定使用一维数组代替二维即可。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n, m;
LL hang[MAXN], lie[MAXN], a[MAXN];
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            scanf("%lld", &a[i * m + j]);
            hang[i] += a[i * m + j];
            lie[j] += a[i * m + j];
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            printf("%lld ", hang[i] + lie[j] - a[i * m + j]);
        }
        putchar(10);
    }
    return 0;
}

J-异或和之和

知识点：位运算

把数按位拆分以后，亦或值为1的有1 0 0和1 1 1两种情况，分别统计对答案的贡献即可。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 3e5 + 117;
const int MAXM = 1e6 + 117;

int n;
LL a[MAXN];
LL one[77], sum;
LL fast_pow(LL a, LL n) {
    LL ret = 1;
    LL tmp = a % mod;
    while(n) {
        if(n & 1) ret = ret * tmp % mod;
        tmp = tmp * tmp % mod;
        n >>= 1;
    }
    return ret;
}
int main() {
    LL t = 1;
    LL two = fast_pow(2, mod - 2);
    LL three = fast_pow(3, mod - 2);

    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
        for(int j = 0; j < 64; j++) {
            if(a[i] & (t << j)) one[j]++;
        }
    }
    for(int j = 0; j < 64; j++) {
        LL num = (t << j) % mod;
        if(one[j]) {
            // 1 0 0组合
            LL t = one[j] * (n - one[j]) % mod;
            t = t * (n - one[j] - 1) % mod;
            t = t * two % mod;

            sum = (sum + t * num % mod) % mod;
        }
        if(one[j] >= 3) {
            // 1 1 1组合
            LL t = one[j] * (one[j] - 1) % mod;
            t = t * (one[j] - 2) % mod;
            t = t * two % mod;
            t = t * three % mod;

            sum = (sum + t * num % mod) % mod;
        }
    }
    printf("%lld\n", sum);
    return 0;
}