2020, XIII Samara Regional Intercollegiate Programming Contest

题目比较简单，找几个比较难的题讲一下。

B. Bonuses on a Line

题意：

给你一些在x轴上的坐标，每个坐标都有一些食物，给你一个时间t，你每秒钟可以一个单位，刚开始你在原点（0）问在t秒之后你最多可以获得多少食物？

题解：

A: 这题是枚举状态吧？

B：是的！难点就是你要如何找到所有状态。

A: 如何找到所有状态呢？

B: 因为刚开始在0的位置，所以先枚举在x轴左边，最后一次到的点，剩下的时间走右边，

同理，在枚举x轴的右边最后一次走的点剩下时间走左边。

A: 那暴力查找会超时呀。

B：这里可以用二分取优化，查第一个大于就行了。

代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 200000 + 7;

ll n, t, a[N];
vector<ll>positive, negative;

int main(){    
    ll ans = 0;
    scanf("%lld %lld", &n, &t);
    for(int i = 1; i <= n; i++){
        scanf("%lld", &a[i]);
        if(a[i] == 0){
            ans++;
        }else if(a[i] > 0){
            positive.push_back(a[i]);
        }else{
            negative.push_back(-a[i]);
        }
    }
    sort(negative.begin(), negative.end());
    positive.push_back(100000000000000);
    negative.push_back(100000000000000);
   
    // positive
    ll cnt = t;
    ll res = 0;
    ll maxn = 0;
    for(int i = 0; i < positive.size() - 1; i++){
        if(cnt >= positive[i]){
            res++;
            ll cn =cnt - positive[i];
            if(cn >= positive[i]){
                ll cat =cn - positive[i];
                int p = upper_bound(negative.begin(), negative.end(), cat) - negative.begin();
                maxn = max(ans + res + p, maxn);

            }
        }else{
            break;
        }
    }
    maxn = max(maxn, res + ans);

    // negative
    res = 0;
    cnt = t;
    for(int i = 0; i < negative.size() - 1; i++){
        if(cnt >= negative[i]){
            ll cn =cnt - negative[i];
            res++;
            if(cn >= negative[i]){
                ll cat = cn - negative[i];
                int p = upper_bound(positive.begin(), positive.end(), cat) - positive.begin();
                maxn = max(ans + res + p, maxn);
            }
        }else{
            break;
        }
    }
    maxn = max(ans + res, maxn);
    printf("%lld
", maxn);


}

D. Lexicographically Minimal Shortest Path

题意：

给你一张图边权是字符，问找一个最多路径，如果有多个输出经过的边的字符字典序最小的那个。

题解：

A：这题咋想的？

B: 先求出最短路然后，找出所有最短路径，枚举一个字典序最小的。

A: 就是找出所有的最短路径然后再枚举？不会超时吗？

B: 不能直接找出所有的最短路径枚举，那样肯定会超时！，我们可以先求出来到 n的所有点的最短路，

如果有一条边比如(u， v) dist[u] == dist[v] - 1, 那么(u, v) 这条边就可以做最短路的一条边，找出所有可能的边，

然后从源点（1）开始贪心枚举，要是当前边有一个最小的就走这个，要是有多个最小的，就全部都走，然后第二层继续枚举，之前的走的点，要是有多个最小的也是全部都走，有一个就走一个，这样的话时间复杂度最多也就是 o（m）.

A：没听懂！！!

B: 我想你看我代码模拟一边会更好。

A: 好的。

#include<bits/stdc++.h>

using namespace std;
const int N = 200007;

vector<pair<int, char> > g[N];

int n, m, dist[N];

queue<pair<int, int> > q;

void bfs(){
    q.push({n, 0});
    memset(dist, -1, sizeof(dist));
    while (q.size()){
        auto cd = q.front();
        q.pop();
        if (dist[cd.first] != -1) continue;
        dist[cd.first] = cd.second;
        for (auto it: g[cd.first]) {
            int to = it.first;
            q.push({to, cd.second + 1});
        }
    }
}

int vis[N];
vector<int>Q;
vector<int> ans;
int fa[N];

void path(int x){
    if(x == 0) return;
    path(fa[x]);
    printf("%d ", x);
}

int main(){
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        char w;
        scanf("%d %d %c", &u, &v, &w);
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    bfs();
    Q.push_back(1);
    for (int i = 1; i <= dist[1]; i++) {
        int minn = 1000;
        vector<int> v;
        for(int cd: Q) {
            for (auto it: g[cd]){
                int to = it.first;
                int cost = (int)it.second;
                if (dist[to] + 1 == dist[cd])
                    minn = min(minn, cost);
            }
        }
        for(int cd: Q){
            for (auto it: g[cd]){
                int to = it.first;
                int cost = (int)it.second;
                if (dist[to] + 1 == dist[cd]) {
                    if (cost == minn && vis[to] == 0) {
                        v.push_back(to);
                        fa[to] = cd;
                        vis[to] = 1;
                    }
                }
            }
        }

        ans.push_back(minn);
        Q.clear();
        for(int j: v){
            Q.push_back(j);
        }

    }

    printf("%d
", (int)ans.size());
    path(n);
    puts("");
    for(int i: ans){
        printf("%c", (char)i);
    }
    puts("");
    
}