组队排位赛15 2019 KAIST RUN Spring Contest

题解 (opens new window)

Gym 102202C *

无能为力

Gym 102202D 思维

队友过的

对于$a, b$，如果两者都为偶数，那么可以把他们同时除以2（结果不变）

基于此，如果$a$为偶数，那么执行$B+=B$操作，接下来$a,b$同时除以2

$b$为偶数时相似。

考虑$a,b$均为奇数，此时我们把小的那个数字加到大的数字上，此时$a,b$一奇一偶，按上面的方法处理即可。执行上述操作直至$a=b$。

Gym 102202E 分析 斜率Dp

见我的笔记:斜率Dp回顾

Gym 102202F 贪心 最短路转化

考虑使用网络流的方法解题，建图十分简单，但是要跑$n$次最短路（每次修改容量都要跑一遍最短路），显然超时。

---

但本题的最短路有个特点：设已选择的午餐、晚餐分别为$s[0]/s[1]$，尚未选择的午餐、晚餐分别为$ns[0]/ns[1]$，那么从$i$向$i+1$转移，只有以下三种情况：

1. $ns[0]\to s[0],ns[1]\to s[1]$
2. $s[0]\to s[1],ns[0]\to s[0], ns[0]\to s[0]$
3. $s[1]\to s[0],ns[1]\to s[1],ns[1]\to s[1]$

如上所示，转移时最多只有一个$s[0](s[1])$变成$s[1](s[0])$，下面进行证明：

假设$s[0]=\{a,b\},s[1]=\{c',d'\}, ns[0]=\{e,f,g,\dots\}, ns[1]=\{e',f',g',\dots\}$为$i=2$时的最优解

因而有

$$\forall x,y,z',w'(z',w'\not\in\{c',d'\}),cost\{x,y,z',w'\}\ge cost\{x,y,c',d'\}\tag 1$$

下面进行转移：假设$a\to a',b\to b'$，即$a/b$从午餐转化为晚餐，此时$s[0]=\empty,s[1]=\{a',b',c',d'\}$，因而必须从$s[1]$中去除一个元素，假设去除的元素为$d'$，接着，我们需要向$s[0]$中填入元素使得$\mid s[0]\mid =\mid s[1]\mid$

此时，可选的元素有$\alpha=\{d,e,f,g,\dots\}-\{d\}$，组合后总价格为$c_0=cost\{\alpha_1,\alpha_2,\alpha_3,a',b',c'\}$

根据$(1)$有$cost\{min(a',b'),c',d'\}\le cost\{a',b',c'\}$，进而$cost\{\alpha_1,\alpha_2,\alpha_3,min(a',b'),c',d'\}$

因此，若午餐/晚餐转移数大于1，那么总存在比当前解更优的解。

---

综上，每次转移时我们只需要考虑三种情况即可。

但实际写代码时，上述思路比较难写，因而可以将午餐、晚餐分开考虑，例如，对于午餐只有一下两种情况：

1. $ns[0]\to s[0]$
2. $s[1]\to s[0],ns[1]\to s[1]$

晚餐同理

于是，我们只需要维护两类优先队列

1. 已选择的午餐/晚餐
2. 未选择的午餐/晚餐

每次转移时，分别转移午餐、晚餐即可。

---

AC代码（变量名的意义清晰，应该不需要注释了吧）:

#include <bits/stdc++.h>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)

using namespace std;

const int maxn = 5e5 + 1000;
const ll inf = 0x3f3f3f3f3f3f3f3f;

struct ttuple{
    int cost, idx;
    bool operator <(const ttuple & other) const{
        return cost > other.cost;
    }
};

int type[maxn];
int meal_cost[maxn][2], n;
priority_queue<ttuple> selected[2], non_selected[2];

int pop(priority_queue<ttuple> & que){
    int ret = que.top().idx;
    que.pop();
    return ret;
}

ll add_meal(int is_diner){
    for(int i=0; i<2; i++){
        while(type[non_selected[i].top().idx] != 0) non_selected[i].pop();
    }
    ll cost1 = non_selected[is_diner].top().cost, cost2 = inf;
    if(!selected[is_diner^1].empty())
        cost2 = selected[is_diner^1].top().cost + non_selected[is_diner^1].top().cost;
    
    int idx;
    if(cost1 <= cost2){
        idx = pop(non_selected[is_diner]);
        selected[is_diner].push({meal_cost[idx][is_diner^1] - meal_cost[idx][is_diner], idx});
        type[idx] = is_diner + 1;
    }else{
        idx = pop(selected[is_diner^1]);
        selected[is_diner].push({meal_cost[idx][is_diner^1] - meal_cost[idx][is_diner], idx});
        type[idx] = is_diner + 1;
        idx = pop(non_selected[is_diner^1]);
        selected[is_diner^1].push({meal_cost[idx][is_diner] - meal_cost[idx][is_diner^1], idx});
        type[idx] = (is_diner ^ 1) + 1;
    }

    return min(cost1, cost2);
}

void solve(){
    cin >> n;
    for(int i=0; i<(n<<1); i++) {
        for(int j=0; j<2; j++) {
            cin >> meal_cost[i][j];
            non_selected[j].push({meal_cost[i][j], i});
        }
    }

    ll cost = 0;
    for(int i=0; i<n; i++){
        cost += add_meal(false);
        cost += add_meal(true);
        cout << cost << '\n';
    }
}

signed main(){
    Android;
    solve();
}

Gym 102202G 思维 LCA Dp*

Gym 102202H 二分图完美匹配(Hall's 婚配定理) 构造*

无能为力