蓝桥杯，ACM算法学习【文档】【视频】大放送【点击此进入】
 
 
2019年第十届蓝桥杯【C++省赛B组】【题目汇总】
 
 
第一题：组队
 
 
第二题：年号字串
 
 
第三题：数列求值
 
 
第四题：数的分解
 
 
第五题：迷宫
 
 
第六题：特别数的和
 
 
第七题：完全二叉树的权值
 
 
第八题：等差数列
 
 
第九题：后缀表达式
 
 
第十题：灵能传输
 
 
2018年第九届蓝桥杯【C++省赛B组】【题目汇总】
 
 
第一题：第几天
 
 
第二题：明码
 
 
第三题：乘积尾零
 
 
第四题：测试次数
 
 
第五题：快速排序
 
 
第六题：递增三元数组
 
 
第七题：螺旋折线
 
 
第八题：日志统计
 
 
第九题：全球变暖
 
 
第十题：最大乘积
 
 
蓝桥杯，ACM算法进阶资料大放送
 
 
2016年第七届蓝桥杯C/C++程序设计本科B组省赛题目汇总
 
 
1、煤球数目
 
 
2、生日蜡烛
 
 
3、凑算式
 
 
4、快速排序
 
 
5、抽签
 
 
6、方格填数
 
 
7、剪邮票
 
 
8、四平方定理
 
 
9、交换瓶子
 
蓝桥杯，ACM算法进阶资料大放送

题目提交点
 
点我进入官方提交点
 
题目
 
 
思路
 
分析题目， 发现限制条件
 
这个题目是从n个数中选k个数使得乘积最大， 结果需要取余。
 后面的注意说明就是告诉你取余之后数可以是负数，恰好我们计算机取余的都是负数，所以直接取余即可。
 
关键词有n,k,取最大值，数据范围为$10^5$,数据有点大，排除DP写法， 所以尝试使用贪心思想去解这一题。
 
贪心思路
 
因为k的取值是不确定的， 所以我们对k进行分类讨论：
 
① 当 k == n 时， 无需考虑，直接将所有结果相乘即可。
 ②当 k < n时， 需要考虑其奇偶性，因为偶数个负数的乘积一定是偶数。
 当 k 为 偶数时， 最佳策略是我们选的时候选择偶数个负数，偶数个正数。一定可以选择到的，假如我们的负数有奇数个，那么我们可以直接将一个最小的数纳入绝对不会选择数中，k < n,必然会存在选不上的数， 那么剩下来的就都是偶数个奇数了。
 当k 为奇数时， 如果n个数全为负数，结果是直接选大的k位数。如果n个数中存在正数，那么就把最大的数提前选出来，就转化为了k为偶数的情况了。
 
AC 代码
 
#include<bits/stdc++.h>
using namespace std;

#define _for(i, a, b) for (int i = (a); i < (b); ++i)
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define For(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(a) cout << #a << " = " << a << endl;
#define mod(x) (x) % MOD
#define ENDL "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 100000 + 10, MOD = 1e9 + 9;
ll a[N];  

int main()
{
#ifdef LOCAL
    freopen("data.in", "r", stdin);
#endif
    ios::sync_with_stdio(false); // 取消cin与stdin 的同步
    cout.tie(0), cin.tie(0);

    int n, k;
    cin >> n >> k;
    _for(i, 0, n) cin >> a[i];
    sort(a, a + n);

    ll ans = 1;
    int sign = 1, i = 0, j = n - 1; 
    if (k % 2) {
        ans = a[j--];
        k--;
        if (ans < 0) sign = -1;
    }

    while (k) {
        ll x = a[i] * a[i + 1], y = a[j] * a[j - 1];
        if (x * sign > y * sign) {
            ans = mod(mod(x) * ans);
            i += 2;
        }
        else {
            ans = mod(mod(y) * ans);
            j -= 2;
        }
        k -= 2;
    }

    cout << ans << ENDL;
    return 0;
}