牛客小白25
[toc] 通过数量 9/10 C和J题值得思考 比赛链接
A
牛可乐准备和 n 个怪物厮杀. 已知第 i 个怪物的血量为 a_i . 牛可乐有两个技能: 第一个技能是蛮牛冲撞, 消耗 1 mp , 可以对任意单体怪物造成 1 点伤害. 第二个技能是蛮牛践踏, 消耗 x mp , 可以对全体怪物造成 1 点伤害. 牛可乐想知道, 将这些怪物全部击杀, 消耗 mp 的最小值的多少?
题解: 当x < n的时候, 都是划算的, 否则就单体击杀(x==n是都一样) 所以我们对怪物的血量进行排序, 找到第x大的怪物, 比他大的怪物, 都要一个一个消灭. 所以可以计算出需要几次aoe, 几次平a, 算出答案即可.
B
这个需要补, 不太会
C
这个题很棒, 答案挺出乎意料.
题意:
你是一个白魔法师. 现在你拿到了一棵树, 树上有 n 个点, 每个点被染成了黑色或白色. 你可以释放一次魔法, 将某个点染成白色.(该点不一定是黑色点, 也可以是白色点) 现在释放魔法后要保证最大的白色点连通块尽可能大. 请求出最大白色连通块的大小. 注: 所谓白色连通块, 指这颗树的某个连通子图, 上面的点全部是白色.
n<=1e5 题解: 这个题解我一开始没想到.
其实树有个很好的性质, 就是一个点最多与周围三个点发生联系. 也就是其父亲+左右儿子. 以为只能染白一个, 所以就枚举是哪个黑节点被染白就可以了. 对于每个黑节点, 其如果被染白, 无非就是让父亲和儿子节点发生联通. 那么如何加快联通呢? 答案就是首先用并查集预处理这棵树, 将白连通块都缩成一个点(也不是真的缩点, 就是任意一个白节点都知道自己所在的连通块的大小(此时可以先更新一下最大值, 也就是染色之前的最大值)). 然后对于每个被枚举的黑节点, 他有可能让父亲儿子, 或者儿子儿子之间的连通块合并成更大的, 所以就查询一下父亲和儿子(如果是白节点的话)所在的连通块大小, 然后将其合并, 更新最大值即可.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
// contest5600C
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define maxn 100000 + 100
vector<int> v[maxn];
int f[maxn];
int value[maxn];
int Find(int x) {
if (x != f[x]) {
f[x] = Find(f[x]);
}
return f[x];
}
void Mix(int x, int y) {
int fx = Find(x);
int fy = Find(y);
if (fx != fy) {
f[fx] = fy;
value[fy] += value[fx];
value[fx] = 0;
}
}
int main() {
int n;
cin >> n;
for (int i = 0; i <= n; ++i) {
f[i] = i;
}
string s;
cin >> s;
for (int i = 0; i < n - 1; ++i) {
int x, y;
cin >> x >> y;
--x, --y;
v[x].push_back(y);
v[y].push_back(x);
}
for (int i = 0; i < n; ++i) {
if (s[i] == 'W') {
value[i] = 1;
} else {
value[i] = 0;
}
}
for (int i = 0; i < n; ++i) {
if (s[i] == 'W') {
for (auto j : v[i]) {
if (s[j] == 'W') {
Mix(i, j);
}
}
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == 'W') {
ans = max(ans, value[Find(i)]);
}
}
for (int i = 0; i < n; ++i) {
if (s[i] == 'B') {
int res = 1;
for (auto j : v[i]) {
res += value[Find(j)];
}
ans = max(ans, res);
}
}
cout << ans << endl;
return 0;
}
D
题意: 王子连接的国服终于上线啦~ 已知王子连接的抽卡系统如下: 共有 n 个卡池, 第 i个卡池共有 a_i 种卡, 每张卡的出货率都是相等的(也就是说该卡池单次抽卡, 每种卡出货率是 1/a_i). 第 i 个卡池中, 你有 b_i 种卡是自己很想要的. 现在的问题是, 如果每个卡池里都单抽一次, 能抽到自己想要的卡的概率是多少? 可以证明, 这个概率一定可以写成 形式的分数. 最后输出该分数在模 10^9+7意义下的值就可以了. 即输出满足 b*x%1000000007=a 的最小非负整数 .
不难看出, 最后的答案就是
\(1- \prod_{0}^{n-1}\left(\frac{a_i-b_i}{a_i}\right)\mod (1e9+7)\) 然后将分数化成整数, 使用一下乘法逆元即可.
E
题目:
牛牛拿到了一个字符串. 他每次”点击”, 可以把字符串中相邻两个相同字母消除, 例如, 字符串”abbc”点击后可以生成”ac”. 但相同而不相邻、不相同的相邻字母都是不可以被消除的. 牛牛想把字符串变得尽可能短. 他想知道, 当他点击了足够多次之后, 字符串的最终形态是什么? 字符串长度<=3e5
思路: 做过类似的, 用栈的思想即可, 如果字符串当前的字符和栈顶的字符一样, 那么就弹出栈顶, 丢弃当前字符. 否则(也包括栈为空的情况)就将当前字符压栈.
F
牛妹作为偶像乐队的主唱, 对自己的知名度很关心. 她平时最爱做的事就是去搜索引擎搜自己的名字, 看看别人对自己的评价怎么样. 这天, 她打开了一个”偶像评分系统”, 上面有很多人给她打分. “偶像评分系统”的分数有1分、2分、3分、4分和5分. 给牛妹评分的人有 n 个. 但其中有 m 个人把分数隐藏了, 牛妹并不能看到这些人给她打的分数. 牛妹想知道, 已知这些信息的情况下, 自己得到的平均分数的最大可能和最小可能分别是多少? m, n<=2e5
思路: 假设m个人都打5分或者1分, 算出平均分即可.
G
牛能作为一个学霸, 非常擅长解方程. 有一天, 他拿到了一个方程: x^a+blnx=c 牛能当然一下子就解出了这个方程. 但他想考考聪明的你, 这个方程的解的多少?
1< a< 3 b, c < 1e9
思路: 其实很简单, 我们观察 x^a+blnx-c , 发现x->0的时候, 这个式子小于0, 发现x->1e9的时候, 这个式子一定大于0
我们直接二分一下就好了.
H
输出字符串中出现次数最多的字母即可
I
题目: 牛牛在玩一个游戏: 一共有n行m列共nm个方格, 每个方格中有一个整数. 牛牛选择一个方格, 可以得到和这个方格同行、同列的所有数之和的得分. 例如: 对于一个22的方格: 1 2 3 4 牛牛选择每个方格的得分如下: 6 7 8 9 因为1+2+3=6, 1+2+4=7, 1+3+4=8, 2+3+4=9. 现在牛牛想知道下一步选择每个格子的得分情况, 你可以帮帮他吗?
思路: 预处理每一行和每一列的和, 然后枚举所有的点位, 将对应的行列值加起来, 统计最大值即可
J
给一个数组, 数组内有 个正整数. 求这些数任取3个数异或运算后求和的值. 也就是说, 取一共$C_{n}^{3}$ 个三元组, 计算这些三元组内部异或, 之后求和.(具体操作可以见样例描述) 由于该值可能过大, 输出其对 1e9+7 取模的值.
3< n <2e5 a_i<1e18
思路:
题目的意思是枚举所有的三元组求和, 实际上直接枚举的话很困难. 我们考虑算贡献.
对于两个数的异或, 其实可以看成逐位异或之后加权求和, 那对于所有的数也可以如此拆分. 我们把每一个数都拆成64位, 然后我们就得到了对于每一位, 有多少个数字这一位上是1, 有多少是0
对于每一位, 都是从n中挑3个数异或, 也就是说, 从n个数中抽取是三个数, 对于当前的这个位, 会有四种情况: 111 110 100 000. 其异或的结果分别是 1 0 1 0 . 所以我们只需要记录111和100这两种情况的贡献就行.
如果对于第j位, 有x个数此位为1, 有n-x个数此位为0. 那么, 111 的情况总共有 x*(x-1)*(x-2)/6 种, 100的情况总共有 x*(n-x)*(n-x-1) 种. 然后我们按照每个位的贡献加权一下, 就得到了最后的答案.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll a[200000 + 100];
ll bit[100];
int mod = 1000000007;
ll cal(ll x, ll y) {
ll ans = 0;
// 1 1 1
ans = (ans + (x * max(0ll, x - 1) * max(0ll, x - 2) / 6) % mod) % mod;
// 1 0 0
ans = (ans + x * y * max(0ll, y - 1) / 2 % mod) % mod;
// 1 1 0
// 0 0 0
return ans;
}
ll qpow(ll a, ll b) {
ll res = 1ll;
while (b) {
if (b & 1)
res = (res * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return res;
}
int main() {
int n;
cin >> n;
ll res = 0;
for (int i = 0; i < n; ++i) {
cin >> a[i];
for (int j = 0; j < 64; ++j) {
if ((a[i] & (1ll << j)) != 0) {
++bit[j];
}
}
}
for (int j = 0; j < 64; ++j) {
res = (res + cal(bit[j], n - bit[j]) * qpow(2, j)) % mod;
}
cout << res << endl;
return 0;
}
