比赛地址:https://ac.nowcoder.com/acm/contest/5600
出题人题解:https://ac.nowcoder.com/discuss/428377
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;
}
版权属于:小影
本文链接:http://kindkidll.com/index.php/archives/152/
所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。 您可以自由的转载和修改,但请务必注明文章来源并且不可用于商业目的。