A-牛牛玩平板
题目描述
https://ac.nowcoder.com/acm/contest/93583/A
思路
仔细读下题目，直接猜排序后就是最佳方案，一写，诶，还真是。
咳咳，不玩玄学，下面才是题解。
题目给出了加和乘两种操作，让我们选一个顺序使最后的结果最大话。既然这样，那就应该分析一下这两种操作最后贡献的价值。在正整数的情况下，普遍是乘法的贡献比加法高，那么是否可以按照类似于田忌赛马的策略进行安排呢？这个例子不行啊，乘法运算的结果可是爆发式的增长。
那么这样，就可以直接让小的数主要贡献加法，一直相加，使最后相乘时的结果最大化。换句话说就是所有小的数都放在前面处理，大的数全部放在后面处理。
代码
#include <stdio.h>
// const int N = 100 + 10; 牛客编译器又抽风了...
#define N 110
int a[N];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
// 冒泡排序
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (a[i] > a[j]) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
}
// 按照题目的要求从小到大计算结果
int ans = 0;
for (int i = 1; i < n; i++) {
ans += a[i - 1] * a[i];
a[i] += a[i - 1];
}
printf("%d\n", ans);
return 0;
}
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
for i in range(1, n):
ans += a[i] * a[i - 1]
a[i] = a[i] + a[i - 1]
print(ans)
B-[NOIP2015]金币
题目描述
https://ac.nowcoder.com/acm/contest/93583/B
思路
额，题目要你一起跟着他的思路进行模拟，好像是恶心人的傻B题。
那就直接按照他的方式来吧，首先需要一个变量来记录今天需要发多少枚金币，然后还需要一个变量来统计这种发金币的方法已经用过几次了，如果发完了（也就是这两个变量相等的时候）就发下一种。别忘了清空统计次数的变量哦。
代码
#include
int main() {
int n;
scanf("%d", &n);
int ans = 0;
int coin = 1; // 统计现在该发几枚金币
int cnt = 0; // 统计这种方法用了几次
for (int i = 1; i <= n; i++) {
ans += coin;
cnt += 1;
// 如果发完了的话 就该发下一种了
if (coin == cnt) {
coin += 1;
cnt = 0;
}
}
printf("%d\n", ans);
return 0;
}
n = int(input())
ans = 0
coin = 1 # 统计该发几枚金币
cnt = 0 # 统计这种硬币已经发了几次
for i in range(1, n + 1):
ans += coin
cnt += 1
# 如果发完了的话 就该发下一种了
if cnt == coin:
coin += 1
cnt = 0
print(ans)
C-等式
题目描述
https://ac.nowcoder.com/acm/contest/93583/C
思路
不会写，去找我们这的大佬问，结果大佬给出了两页纸的解题过程……听完后还是蒙。
代码
D-脸盆大哥的木桶
题目描述
https://ac.nowcoder.com/acm/contest/93583/D
思路
木桶效应，一个桶能够承载的容量取决于最短的那块木板。
既然这样，同时又需要最大化容量，那么就应该尽量拼出短板最长的桶，如果木板有多就应该直接抛弃最短的那部分。直接从大到小枚举木板长度即可。
代码
#include <stdio.h>
#define N 1010
int a[N];
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n, k, s;
scanf("%d%d%d", &n, &k, &s);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (a[i] < a[j]) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
}
int cnt = 0;
int ans = 0;
int minn = 1e9;
for (int i = 1; i <= n; i++) {
if (minn > a[i]) minn = a[i];
cnt++;
if (cnt == k) {
ans += s * minn;
cnt = 0;
}
}
printf("%d\n", ans);
}
return 0;
}
t = int(input())
while t:
t -= 1
n, k, s = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
ans = 0
minn = int(1e9)
cnt = 0
for i in range(n):
minn = min(minn, a[i])
cnt += 1
if cnt == k:
cnt = 0
ans += s * minn
print(ans)
E-Mountain
题目描述
https://ac.nowcoder.com/acm/contest/93583/E
思路
根据题意画出图形：
因为不会用电脑画图，所以直接用Excel生成了一个图，不要在意这些细节
其中绿色表示滑索，红色表示海拔的变化。红色部分的总和就是 $1+2+2+1+2+2=10$。
你应该可以发现什么吧，没有发现？再看下一个例子：
因为题目中也说明了可以不通过中间海拔比较低的山，那么$4$和$5$也就可以直接跳过了，最后红色部分的总和是 $1+2+2+4+1=10$。
咳咳，剩下的部分就不需要我说明了吧……
还是没看出来？再仔细分析一下我们上面得到的图形，将得到的红色部分平移一下，让同一边的线全部拼在一起，那么就可以得到下面的图形：
那么也就是变成了求最左右这两边的红线的长度，红色部分的长度是多少应该很容易想得到了吧，也就是最高的那座山的高度（毕竟红线要完全覆盖嘛，总不能在半山腰打个洞钻过去吧）。
那么就可以得出，这道题的答案就是最高的那座山的高度乘以2。
代码
#include <stdio.h>
const int N = 1000 + 10;
int a[N];
int main() {
int n;
scanf("%d", &n);
int maxn = 0;// 记录最大值
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
if (maxn < a[i]) maxn = a[i];
}
printf("%d\n", maxn * 2);
return 0;
}
n = int(input())
a = list(map(int, input().split()))
print(max(a) * 2)F-最小生成树
题目描述
https://ac.nowcoder.com/acm/contest/93583/F
思路
最小生成树算法？这么经典？立马掏出板子（代码模板）来看一眼，不对劲，很不对劲，图上有 $10^5$ 个点，还是完全图，这光是连边就炸掉了啊。（大概有 $5 \times 10^9$条边）
在仔细看看，权值都是落于点上的，这意味着什么呢。不懂，画个图看看
假设1,2,3,4号点的权值对应的就是1,2,3,4那么要怎样才能使最后得到的边权最小呢，题目中说一条边 $(u,v)$ 的权值就是 $a_u + a_v$ ，那么最小的方法应该就是使最后的 $ans = (a_{u_1}+a_{v_1}) + \dots + (a_{u_{n-1}}+a_{v_{n-1}})$ 最小。因为最后生成的图是“最小生成树”，也就是说图上所有点都是相连的，那么每个点都至少会被加一次，如果把这个必须会被加上的数看成终点的话，那么我们的目的也就是变成了要如何求权值最小的起点。
是不是有点头绪了，那么这个最小的起点该怎么找呢，因为题目中给出的是完全图，也就是说图中任取一个点，这个点都可以抵达图中其他任意一点，直接把权值最小的那个点设置为起点，那么最后得到的边权也就是最小的。上图的最终结果也就是 $ans = (a_{min} + a_{v_1}) + \dots + (a_{min} + a{v_n}) - 2 \times a_{min}$ ，最后为什么要减去 $2 \times a_{min}$ 呢，因为最后得到的图只有 $n - 1$ 条边，但是计算了 $n$ 条边的情况，需要从中减去 $a_{min}$ 以自己为起点同时以自己为终点的情况。
代码
#include <stdio.h>
#define N 100010
long long a[N];
int main() {
int n;
scanf("%d", &n);
int minn = 1e9;// 记录出现的最小值
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
if (minn > a[i]) minn = a[i];
}
long long ans = 0;
for (int i = 1; i <= n; i++) {
ans += minn + a[i];// 把每个点都作为终点加一遍
}
printf("%lld\n", ans - 2 * minn);
return 0;
}
n = int(input())
a = list(map(int, input().split()))
minn = min(a)
ans = 0
for i in a:
ans += i + minn
print(ans - minn * 2)
写在最后
这些题目都还是有点难度的，主要还是面向已经学完了编程语言的基础语法的同学，没有写出来也不要灰心，毕竟还是有点难度的（比如这个C题）。因为看到群里很多人都会python，所以提供了python的代码，以后可能会统一使用 C++作为题解的标准语言（当然，可能也会有一些python的奇技淫巧），不过编程语言这方面并不用当心，语言只是解题的工具，正真重要的还是自己解题的思维。
写题解的时候发现了一些bug，有的时候数学公式可能并没有正确的加载，如果看见了奇怪的$符号刷新一下页面就可以了。
例子：
$$
\nabla \cdot \mathbf{B} = 0
$$
$$
\oint_{\partial V} \mathbf{B} \cdot d\mathbf{A} = 0
$$
Comments NOTHING