完全二叉树的权值
思路：边输入边处理，我们容易知道，每一行的最后一个数的下标都是等于(2^n)-1，比如第二行的最后一个数等于2^2-1=3,第三行的最后一个数等于2^3-1=7,用deep表示当前深度，从当前这行的第一项加到最后一项然后和最大值max_sum比较。
代码：
#include<bits/stdc++.h> using namespace std; int Ai[100005]; int main(){ int N; int deep = 1; //深度 int sum = 0; //每行的和 long long max_sum = -100000000000; //最大的和 int max_deep = 1; cin>>N; for(int i = 1; i <= N; ++i){ cin>>Ai[i]; sum += Ai[i]; if(i == pow(2, deep) - 1){ if(max_sum < sum){ //注意不要取等号，因为题目要最小的深度 max_deep = deep; max_sum = sum; } sum = 0; ++deep; } } cout<<max_deep<<endl; return 0; }
等差数列
思路
等差数列的任意两项之差为公差的倍数。(a n − a 1 = ( n − 1 ) d , n ≥ 2 a_n-a_1=(n-1)d, n\ge2a
n −a 1 =(n−1)d,n≥2)拿样例来说，2, 6, 4, 10, 20，排序之后为2, 4, 6, 10, 20，与首项的差为2, 4, 8, 18。要使得等差数列最短就要使公差尽可能的大，就是要求差的最大公约数。n个数的最大公约数为求前两个的gcd，再用求出gcd与后面的数依次求。证明？不会 等差数列需要注意公差为0的情况 用到的知识1.等差数列的通项公式，注意公差为0的情况。2.欧几里得算法又称辗转相除法。
代码
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int N = 100010; int n; int a[N]; int ans; int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); sort(a, a + n); for (int i = 1; i < n; i++) ans = gcd(ans, a[i] - a[0]); if (ans == 0) cout << n << endl; else cout << (a[n - 1] - a[0]) / ans + 1<< endl; return 0; }
后缀表达式
思路: 分4种情况，
- 减号=0，没办法只能全部加起来
- 负数数目=0，排除了第1种情况，有减号，所以一定是其他数的和-最小的数
- 全为负数，这种最容易忽略，排除上述2种情况，所以只要有减号，一定是其他所有数的绝对值-最大负数的绝对值
- 其他情况，都是所有数的绝对值的和
代码
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; ll a[200005], sum = 0, mi = 1000000009; int n, m, fu = 0; bool cmp(int a, int b) { return a > b; } int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n + m + 1; i++) { scanf("%lld", &a[i]); if (a[i] < 0) fu++; sum += a[i]; mi = min(mi, a[i]); } if (m == 0) printf("%lld\n", sum); else { if(fu == 0) printf("%lld\n", sum - mi - mi); else { if (fu == n + m + 1) //***全是负数 { sum = 0; mi = 1000000009; for (int i = 0; i < n + m + 1; ++i) { sum += abs(a[i]); mi = min(mi, abs(a[i])); } printf("%lld\n", sum - mi - mi); } else { sum = 0; for (int i = 0; i < n + m + 1; ++i) sum += abs(a[i]); printf("%lld\n", sum); } } } return 0; }
灵能传输
思路:这题题量有点大。。。简单来说就是给定一组数，我们的目标是通过两种操作使得其中的绝对值最大的数达到最小，这两种操作是：
1、如果 a[i] > 0 并且 a[i - 1] 或者 a[i+1] 小于 0，我们可以将 a[i] 借给 i-1 元素和 i+1 元素，同时 a[i] 要变成 -a[i]。
2、如果 a[i] < 0 并且 a[i - 1] 或者 a[i+1] 大于 0，我们可以将 a[i-1] 和 a[i+1] 各借 abs(a[i]) 给 i 元素，之后 i 元素的值变成 -a[i] 也就是正数（a[i] 本身是小于 0 的），同时 a[i - 1] 和 a[i + 1] 要减掉 abs(a[i])。
我们考虑几种情况：
1、所有的数字都为正数或者都为负数，即所有的数字都同号。这种情况是没法借的，因为不符合操作要求，因此这种情况求出数组中绝对值最大的数即可。
2、对于 a[i]，如果 a[i] 是正数，并且 a[i - 1] 和 a[i + 1] 至少有一个负数，那么我们的目标就是把那个绝对值最大的负数的绝对值缩小，这个时候如果另一边是正数，则需要考虑操作之后是否会产生新的绝对值更大的正数，比如现在有三个数：5 5 -6，如果我们把中间那个 5 按上面的操作 1 变换之后：10 -5 -1，绝对值最大数变成了 10，而之前是 6，显然不行。如果这三个数是这样的：1 5 -7，那么我们就可以按操作 1 变换：6 -5 -2，最大绝对值从 7 减小到了 6，是可行的。那么变换条件是什么呢？这里假设 a[i - 1] 是正数，a[i + 1] 是负数，那么条件可以写成：a[i - 1] + a[i] < abs(a[i + 1])。而如果 a[i - 1] 和 a[i + 1] 都是负数的时候，当两边的绝对值有一个大于 a[i] 时，就可以进行操作 1 变换。
3、对于 a[i] 是负数的时候，如果 a[i - 1] 是负数， a[i+1] 是正数，那么确保 a[i + 1] > abs(a[i] + a[i-1])，就可以进行操作 2 变换，如果两边都是正数则只要有一边的值大于 abs(a[i]) 时就可以进行操作 2 变换
代码
#include <cstdio> #include <cmath> #include <iostream> using namespace std; const int MAXN = 300010; int nums[MAXN]; // 判断 a 和 b 是否异号 bool judgeYi(int a, int b) { return a > 0 && b < 0 || a < 0 && b > 0; } int main() { int T, n; cin >> T; while (T--) { cin >> n; // 标志负数和正数是否出现 bool hasNe = false, hasPo = false; int res = 0; for (int i = 0; i < n; i++) { scanf("%d", &nums[i]); if (nums[i] < 0) { hasNe = true; } else if (nums[i] > 0) { hasPo = true; } } // 如果数组中同时存在正负数，则判断能否进行操作 1 和 操作 2 if (hasNe && hasPo) { bool canNext; do { canNext = false; for (int i = 1; i < n - 1; i++) { // nums[i] 和 nums[i-1] 或 nums[i+1] 异号 if (judgeYi(nums[i], nums[i-1]) || judgeYi(nums[i], nums[i+1])) { if (nums[i] > 0) { // nums[i-1] 和 nums[i+1] 异号， // 这里的 if 和 else 可以合并，为了逻辑清晰，这里分开写 if (judgeYi(nums[i-1], nums[i+1])) { if ((nums[i-1] > 0 && abs(nums[i+1]) > nums[i-1] + nums[i]) || (nums[i+1] > 0 && abs(nums[i-1]) > nums[i+1] + nums[i])) { nums[i+1] += nums[i]; nums[i-1] += nums[i]; nums[i] = -nums[i]; canNext = true; } } else { // nums[i-1] 和 nums[i+1] 同号，都 < 0 if (abs(nums[i-1]) > nums[i] || abs(nums[i+1]) > nums[i]) { nums[i+1] += nums[i]; nums[i-1] += nums[i]; nums[i] = -nums[i]; canNext = true; } } } else if (nums[i] < 0) { // nums[i-1] 和 nums[i+1] 异号 if (judgeYi(nums[i-1], nums[i+1])) { if ((nums[i-1] > 0 && nums[i-1] > abs(nums[i+1] + nums[i])) || (nums[i+1] > 0 && nums[i+1] > abs(nums[i-1] + nums[i]))) { nums[i+1] += nums[i]; nums[i-1] += nums[i]; nums[i] = -nums[i]; canNext = true; } } else { // nums[i-1] 和 nums[i+1] 同号，都 > 0 if (nums[i-1] > abs(nums[i]) || nums[i+1] > abs(nums[i])) { nums[i+1] += nums[i]; nums[i-1] += nums[i]; nums[i] = -nums[i]; canNext = true; } } } } } } while (canNext); } int t; // 求绝对值最大的值 for (int i = 0; i < n; i++) { res = max(res, abs(nums[i])); } cout << res << endl; } return 0; }
