去年没参加，今年抽空参加一下，因为没什么时间，六道题中就做了4题，剩下两题出来有空再更新

具体详情可以参考参赛地址

2018-6-12官方更新了解题方法，如果想验证请尝试验证地址

A 下单

题目：

美团在吃喝玩乐等很多方面都给大家提供了便利。最近又增加了一项新业务：小象生鲜。这是新零售超市，你既可以在线下超市门店选购生鲜食品，也可以在手机App上下单，最快30分钟就配送到家。新店开张免不了大优惠。我们要在小象生鲜超市里采购n个物品，每个物品价格为ai，有一些物品可以选择八折优惠（称为特价优惠）。有m种满减优惠方式，满减优惠方式只有在所有物品都不选择特价优惠时才能使用，且最多只可以选择最多一款。每种满减优惠描述为(bi,ci)，即满bi减ci（当消费>=bi时优惠ci）。求要买齐这n个物品（必须一单买齐），至少需要多少钱（保留两位小数）。

输入描述:

第一行，两个整数n,m。
接下来n行，每行一个正整数ai，以及一个0/1表示是否可以选择特价优惠（1表示可以）。
接下来m行，每行两个正整数bi,ci，描述一款满减优惠。

1 <= n,m <=10
1 <= ai <= 100
1 <= ci < bi <= 1000

输出描述:

一行一个实数，表示至少需要消耗的钱数（保留恰好两位小数）。

示例1

输入

输出

12.80

示例2

输入

输出

10.00

思路

暴力枚举….

代码

#include <iostream>
#include <vector>
#include <utility>
#include <stdio.h>
using namespace std;

double helper(vector<pair<double, double>>& nums, vector<pair<double, double>>& rule) {
    double ans = 0;
    double ret = 0;
    for (auto i : nums) {
        ans += i.first;
        ret += i.second == 1.0 ? i.first  * 0.8 : i.first;
    }
    for (auto i : rule) {
        if (i.first <= ans) {
            ret = ret > (ans - i.second) ? (ans - i.second) : ret;
        }
    }
    return ret;
}


int main() {
    int n, m;
    cin >> n >> m;
    vector<pair<double, double>> nums, rule;
    for (int i = 0; i < n; i++) {
        double a, b;
        cin >> a >> b;
        nums.push_back(make_pair(a, b));
    }
    for (int i = 0; i < m; i++) {
        double a, b;
        cin >> a >> b;
        rule.push_back(make_pair(a, b));
    }
    printf("%.2f\n", helper(nums, rule));
    return 0;
}

B 可乐

题目描述

小美和小团最近沉迷可乐。可供TA们选择的可乐共有k种，比如可口可乐、零度可乐等等，每种可乐会带给小美和小团不同的快乐程度。
TA们一共要买n瓶可乐，每种可乐可以买无限多瓶，小美会随机挑选其中的m瓶喝，剩下的n-m瓶小团喝。
请问应该如何购买可乐，使得小美和小团得到的快乐程度的和的期望值最大？
现在请求出购买可乐的方案。

输入描述:

第一行三个整数n，m，k分别表示要买的可乐数、小美喝的可乐数以及可供选择的可乐种数。接下来k行，每行两个整数a，b分别表示某种可乐分别给予小美和小团的快乐程度。
对于所有数据，1 <= n <= 10,000, 0 <= m <= n, 1 <= k <= 10,000, -10,000 <= a, b <= 10,000

输出描述:

一行k个整数，第i个整数表示购买第i种可乐的数目。
如果有多解，请输出字典序最小的那个。
对于两个序列 a1, a2, …, ak, b1, b2, …, bk，a的字典序小于b，当且仅当存在一个位置i <= k满足：ai < bi且对于所有的位置 j < i，aj = bj；

思路：

根据快乐程度的公式可以知道

$$\sum\limits_{i=1}^{n} (a_{i} w_{a} / w) n_{i} + (b_{i} w_{b} / w) n_{i} = A n_{i} + B n_{i} = (A + B) n_{i}$$

所以这是个线性关系，要求全买其中一瓶可乐哪个最大。

官方解答：

代码

#include <iostream>
#include <vector>
#include <utility>
using namespace std;
void helper(vector<pair<double, double>>& nums, int n, int m) {
    double ret = -10E9;
    int index = -1;
    int len = nums.size();
    for (int i = 0; i < len; i++) {
        auto temp = nums[i];
        double ans = temp.first * m / n + temp.second * (n - m) / n;
        if (ret <= ans) {
            ret = ans;
            index = i;
        }
    }
    if (nums.empty()) return;
    if (index == 0) cout << n;
    else cout << "0";
    for (int i = 1; i < len; i++) {
        if (i == index) {
            cout << " " << n;
        }
        else cout << " 0";
    }
    cout << endl;
}

int main () {
    int n, m, k;
    cin >> n >> m >> k;
    vector<pair<double, double>> nums;
    for (int i = 0; i < k; i++) {
        double a, b;
        cin >> a >> b;
        nums.push_back(make_pair(a, b));
    }
    helper(nums, n, m);
    return 0;
}

C 世界杯

题意：给16支球队互相胜利的概率，问每支球队获胜的概率。

题目描述

世界杯就要开始啦！真真正正的战斗从淘汰赛开始，现在我们给出球队之间的胜负概率，来预测每支球队夺冠的可能性。
在接下来的篇幅中，我们将简单介绍淘汰赛阶段的规则。
淘汰赛阶段的90分钟常规时间内（含补时阶段）进球多的球队取胜，如果参赛双方在90分钟内（含补时阶段）无法决出胜负，将进行上下半场各15分钟的加时赛。加时赛阶段，如果两队仍未分出胜负，则通过点球大战决出胜者。也就是说，每场比赛，有且仅有一个队能够晋级到下一轮。
淘汰赛共有16支球队参加（小组赛阶段共分8个小组，每组前两名晋级），对阵安排如下。
1/8决赛
A组第一对阵B组第二=胜者1
B组第一对阵A组第二=胜者2
C组第一对阵D组第二=胜者3
D组第一对阵C组第二=胜者4
E组第一对阵F组第二=胜者5
F组第一对阵E组第二=胜者6
G组第一对阵H组第二=胜者7
H组第一对阵G组第二=胜者8
获胜的8个队进入1/4决赛，即所谓“8强”
1/4决赛
胜者1对阵胜者3=胜者A
胜者2对阵胜者4=胜者B
胜者5对阵胜者7=胜者C
胜者6对阵胜者8=胜者D
1/4决赛的4个获胜队进入“4强”
半决赛
胜者A对阵胜者C
胜者B对阵胜者D
半决赛获胜两队进入决赛，失利的两队争夺三名
决赛获胜的队伍就是最后的冠军！

输入描述:

球队会被以1..16进行标号，其分别表示：
1 A组第一；
2 B组第二；
3 C组第一；
4 D组第二；
5 E组第一；
6 F组第二；
7 G组第一；
8 H组第二；
9 B组第一；
10 A组第二；
11 D组第一；
12 C组第二；
13 F组第一；
14 E组第二；
15 H组第一；
16 G组第二。

数据共有16行，每行16个浮点数，第i行第j列的数Fi,j表示i和j进行比赛时i获胜（包括常规时间获胜、加时赛获胜以及点球大战获胜）的概率。
对于1 <= i, j <= 16 且 i != j, 满足0 <= Fi,j <= 1, Fi,j + Fj,i = 1；
对于1 <= i <= 16, 满足 Fi,i = 0。

输出描述:

输出一行16个浮点数，用空格隔开，分别表示每只球队获得世界杯的概率，结尾无空格。
绝对误差或相对误差在1e-5之内的解会被判为正确。

输入

0.000 0.133 0.210 0.292 0.670 0.270 0.953 0.353 0.328 0.128 0.873 0.082 0.771 0.300 0.405 0.455
0.867 0.000 0.621 0.384 0.934 0.847 0.328 0.488 0.785 0.308 0.158 0.774 0.923 0.261 0.872 0.924
0.790 0.379 0.000 0.335 0.389 0.856 0.344 0.998 0.747 0.895 0.967 0.383 0.576 0.943 0.836 0.537
0.708 0.616 0.665 0.000 0.146 0.362 0.757 0.942 0.596 0.903 0.381 0.281 0.294 0.788 0.804 0.655
0.330 0.066 0.611 0.854 0.000 0.687 0.983 0.217 0.565 0.293 0.256 0.938 0.851 0.487 0.190 0.680
0.730 0.153 0.144 0.638 0.313 0.000 0.832 0.526 0.429 0.707 0.414 0.617 0.925 0.638 0.526 0.545
0.047 0.672 0.656 0.243 0.017 0.168 0.000 0.357 0.125 0.307 0.879 0.551 0.641 0.959 0.981 0.465
0.647 0.512 0.002 0.058 0.783 0.474 0.643 0.000 0.325 0.494 0.893 0.064 0.563 0.429 0.501 0.872
0.672 0.215 0.253 0.404 0.435 0.571 0.875 0.675 0.000 0.940 0.053 0.329 0.232 0.280 0.359 0.474
0.872 0.692 0.105 0.097 0.707 0.293 0.693 0.506 0.060 0.000 0.040 0.776 0.589 0.704 0.018 0.968
0.127 0.842 0.033 0.619 0.744 0.586 0.121 0.107 0.947 0.960 0.000 0.486 0.266 0.662 0.374 0.698
0.918 0.226 0.617 0.719 0.062 0.383 0.449 0.936 0.671 0.224 0.514 0.000 0.821 0.027 0.415 0.227
0.229 0.077 0.424 0.706 0.149 0.075 0.359 0.437 0.768 0.411 0.734 0.179 0.000 0.841 0.409 0.158
0.700 0.739 0.057 0.212 0.513 0.362 0.041 0.571 0.720 0.296 0.338 0.973 0.159 0.000 0.935 0.765
0.595 0.128 0.164 0.196 0.810 0.474 0.019 0.499 0.641 0.982 0.626 0.585 0.591 0.065 0.000 0.761
0.545 0.076 0.463 0.345 0.320 0.455 0.535 0.128 0.526 0.032 0.302 0.773 0.842 0.235 0.239 0.000

输出

0.0080193239 0.1871963989 0.0797523190 0.1233859685 0.0836167329 0.0438390981 0.0079035829 0.0604644891 0.0237087902 0.0050549016 0.1149551151 0.0679247259 0.0511307364 0.0395744604 0.0800843771 0.0233889799

思路

16支球队组成一颗4层的二叉树，求每支球队到达根的概率。

官方思路

代码

#include <iostream>
#include <cstring>
using namespace std;

double nums[17][17];
double dp[37][17];

void helper(int n) {
    if (n >= 16) {
        dp[n][n - 16] = 1.0;
    }
    else {
        helper(n << 1);
        helper(n << 1 | 1);
        for (int i = 0; i < 16; i++) {
            for (int j = 0; j < 16; j++) {
                dp[n][i] += nums[i][j] * dp[n << 1][i] * dp[n << 1 | 1][j];
                dp[n][j] += nums[j][i] * dp[n << 1][i] * dp[n << 1 | 1][j];
            }
        }
    }
}


int main() {
    memset(dp, 0.0, sizeof(dp));
    for (int i = 0; i < 16; i++) {
        for (int j = 0; j < 16; j++) {
            cin >> nums[i][j];
        }
    }
    helper(1);
    cout << dp[1][0];
    for (int i = 0; i < 16; i++) {
        cout << " " << dp[1][i];
    }
    cout << endl;
    return 0;
}

D 出线

题目描述

小胖参加了人生中最重要的比赛——MedoC 资格赛。MedoC 的资格赛由 m 轮构成，使用常见的 “加权标准分” 的规则。每位选手需要参加所有的 m 轮的比赛。在一轮中，能取得的分数为自己的成绩除掉最高分的成绩。每个选手的总分为每一轮获得的分数乘上这一轮比赛占得比重。如果在某一轮比赛中所有人获得了零分，那么所有选手在这一轮获得的分数都为 0 分。
比如说，资格赛一共 3 轮，三轮的权重分别为 30%, 30%, 40%。在第一轮中，小胖获得了 300 分，最高分也为 300 分。在第二轮中，小胖获得了 0 分，最高分也为 0 分。在第三轮中，小胖获得了 150 分，最高分为 300 分，那么小胖的总分为 (300/300)30%+030%+(150/300)*40%=0.5。
一共有 n 位选手参加了比赛，其中成绩最高的 k 位选手能够晋级到初赛。如果有多人在分数线上同分，那么系统会随机在这些同分的人中选取，选满 k 个晋级为止。
小胖现在知道了每个选手每场比赛的成绩，但是由于他的疏忽，其中的某个人某场比赛的成绩消失了。所以更多人出线的情况变得未知起来。现在只知道成绩一定是 0 到 C 之间的一个整数（包含 0 和 C）。
小胖想知道对于每个人的出线情况是怎么样的，也就是一定能出线，一定不能出线还是有可能出线。

输入描述:

第一行四个正整数 n,m,k,C (m <= 6, k <= n <= 500, C <= 500)。
接下来一行 m 个整数 w1, w2, …, wm，表示每场比赛的权重，第 i 场比赛的权重为 wi/(w1+w2+…+wm)，保证 wi >= 0 且 1 <= w1 + w2 + … + wm <= 1000。
接下来 n 行每行 m 个整数，第 i 个整数表示这个选手在第 i 场比赛中获得的成绩。如果这个数字为 - 1 表示这个数据丢失，保证恰好有一个 - 1。

输出描述:

n 行每行输出一个 1 到 3 之间的整数。1 表示一定出线，2 表示一定不出线，3 表示可能出线。

思路

这题如果看清楚题意与数据范围真的不难, 因为 - 1 只有一个, 从 0~C 枚举即可

代码

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

void helper(vector<vector<long long>>& nums, vector<long long> w, const int n, const int m, const int k, vector<vector<int>>& ret) {
    vector<long long> score(n, 0);
    vector<long long> mark(n, 0);
    vector<long long> max_score(m, 0);
    vector<long long> ans(m, 1);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            max_score[i] = max_score[i] < nums[j][i] ? nums[j][i] : max_score[i];
        }
        if (max_score[i] == 0) {
            max_score[i] = 1;
        }
    }
    // 直接将所有max_score连称会溢出
    for (int i = 0; i < m; i++) {
        ans[i] = w[i];
        for (int j = 0; j < m; j++) {
            if (j != i)
                ans[i] *= max_score[j];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            score[i] += nums[i][j] * ans[j];
        }
        mark[i] = score[i];
    }
    sort(mark.begin(), mark.end(), greater<long long>());
    for (int i = 0; i < n; i++) {
        if (mark[k-1] <= score[i]) ret[0][i] ++; // 胜利的局数
        if (k != n && mark[k] >= score[i]) ret[1][i] ++; // 失败的局数
    }
}

int main() {
    int n, m, k, C;
    cin >> n >> m >> k >> C;
    vector<long long> w(m, 0);
    for (int i = 0; i < m; i++) {
        cin >> w[i];
    }
    int x, y;
    vector<vector<long long>> nums(n, vector<long long>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> nums[i][j];
            if (nums[i][j] == -1) x = i, y = j;
        }
    }
    vector<vector<int>> ret(2, vector<int>(n, 0));
    for (int i = 0; i <= C; i++) {
        nums[x][y] = i;
        helper(nums, w, n, m, k, ret);
    }
    for (int i = 0; i < n; i++) {
        if (ret[1][i] == 0) cout << 1 << endl;
        else if (ret[0][i] == 0) cout << 2 << endl;
        else cout << 3 << endl;
    }
   return 0;
}

E 你的城市

题目描述

2018年第一季度，美团旅行的酒店业务以5770万的订单总量，成为行业第一名。
与此同时，美团旅行也提供机票、火车票、船票等各种服务，不断开辟新的目的旅游城市。最近新开的目的地，就包括对小A有特殊意义的偏僻小城C。
“我来到你的城市熟悉的那一条街。”小A哼着歌，从北京出发，要去C城。这对他非常重要，必须当天到达，虽然交通并不是非常方便。
但是，错过火车并不是一个小概率事件。为了保险起见，小A决定选择一个即使错过火车也存在补救措施的交通方案。（即假使未赶上原方案中的任何一班火车，依然可以改乘其他的车次能够在当天到达C城，但同时小A是一个乐观主义者，所以他认为改乘以后的所有车次都不会延误。）当然了，在满足上述条件的情况下，小A希望花费的钱越少越好（只考虑计划中的，不考虑发生意外时换乘带来的代价）。
城市及交通网可以看做一张n个点m条边的有向图。每个点代表一个城市（1号点代表北京，n号点代表C城）。每条边由一个五元组<x, y, c, ts, td>组成，表示存在一个车次，由ts时刻从城市x出发，在td时刻到达城市y，且花费为c元。
为了简化问题，ts，td均为以半小时为基本单位（具体格式见样例及Hint）。并假设每次中转最少需要花费半个小时，且中转只能发生在同一城市（即到达一个城市距离再次从这个城市出发至少需要间隔半个小时），注意，小 A 如果因为没赶上车次需要改乘，也需要半个小时的时间。
问小A到达C城最少需要花费多少钱（行程必须在这一天内完成，可以在0:00上车，也可以在24:00到达）。

输入描述:

第一行，两个正整数n, m。n表示城市数量，m表示当天不同班次的火车数量。
接下来m行，每行3个整数x, y, c加两个字符串ts, td，均以空格作为分隔，表示当天的某一班火车。其中x, y, c, ts, td的含义如前描述。
所有的车次都是当天的，没有隔夜的票。
2 <= n <= 500, m <= 15000, c <= 1000, ts < td，所有数均为正整数。
车次保证不过夜，时间范围0:00, 0:30, 1:00, … , 23:00, 23:30, 24:00，可能存在重复车次。

输出描述:

一个整数，表示存在补救措施的前提下，小A到达C城的最小花费。如果不存在这样的路径，则输出-1。

示例1

输入

3 5
1 3 800 18:00 21:00
1 2 650 13:30 14:00
2 3 100 14:00 18:00
2 3 300 14:30 19:00
2 3 200 15:00 19:30

输出

说明
选择第二个和第四个车次。
第三个车次由于中转时间太短无法选择。第五个车次由于没有可改乘的航班无法选择。
如果错过第二个车次，可以改乘第一个车次。如果错过第四个车次，可以改乘第五个车次。

示例2

输入

3 5
1 2 1000 0:00 12:00
1 2 100 0:30 14:00
1 2 100 0:30 15:00
2 3 300 16:00 24:00
2 3 200 16:30 24:00

输出

说明
选择第一个和第四个车次。
不能选择第二个车次是因为，如果错过了0:30的车次2，那么同样在0:30出发的车次3也是来不及改乘的。

示例3

输入

3 4
1 2 100 0:30 14:00
1 2 200 0:30 15:00
2 3 300 16:00 24:00
2 3 200 16:30 24:00

输出

-1

说明
和样例二类似，但是缺少了原先的车次一，所以没有换乘方案。

示例4

输入

3 4
1 2 100 0:30 14:00
1 2 200 1:00 16:00
2 3 300 16:00 24:00
2 3 200 16:30 24:00

输出

说明
选择第一个和第三个车次。

示例5

输入

3 4
1 2 100 0:30 14:00
1 2 200 1:00 16:30
2 3 300 16:00 24:00
2 3 200 16:30 24:00

输出

-1

说明
和样例四类似，但假如错过了第一个车次，改乘车次二在16:30到达城市2是不足以赶上16:30出发的车次四的。

D 匹配

##题目描述
美团外卖日订单已经超过2000万，背后有一个非常复杂的智能调度系统。
我们考虑一个简化的情形，有n个外卖小哥要去 n 家商店取货，第 i 个外卖小哥到达商店 j 需要时间 e[i][j] 。现在有 m 对外卖小哥和商店的合作关系。假定每个外卖小哥只能取到一个货物，每个商店只需要一位外卖小哥取货。
询问最少多少时间，能有 k 位外卖小哥到达 k 个商店取到货物？对于每个 k ，都输出一个数表示最少使用时间，如果无解输出 -1。

输入描述:

第一行输入两个整数 n , m （1 <= n <= 1000 , 1 <= m <= 100000）。
接下来 m 行，每行输入 3 个整数 i , j , e[i][j] (1 <= i, j <= n , 0 <= e[i][j] <= 10^9)，定义如题所述。
注：本题测试用例较多，请耐心等待判题结果，也可以去排行榜刷新查看自己的提交结果。

输出描述:

输出一行n个整数，第 i 个整数，表示当 k=i 时，需要的最少时间，如果无解输出-1，结尾无空格。

示例1

输入

输出

0 2 5