C2020 2020.12.19模拟赛

信息学——模拟赛

---

T1 Piggyback

$1^o$ 分析

考虑如果没有背着走的情况。

答案显然就是$1$，$2$号点到$n$号点的最短路。

考虑最后背着走的路径，一定是某个点到$n$号点的最短路。

考虑枚举相遇的点，那么答案为

$$Ans = Min{(dis1[i] + dis2[i] + disn[i])}$$

分别求出三条最短路，取min即可。

//The code is from dawn_sdy
#include<bits/stdc++.h>
#define INF INT_MAX
#define int long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 4 * 1e4 + 5;
int b, e, p, n, m;
struct node {
    int v, nex;
}edge[maxn << 1];
int head[maxn], len;
int dist[maxn], vst[maxn], dist1[maxn], dist2[maxn], distn[maxn], ans = INF;
inline void make_map(int u, int v) {
    len++;
    edge[len].nex = head[u];
    edge[len].v = v;
    head[u] = len;
}
inline void Dijstra(int st) {
    #define pi pair<int,int> 
    #define mp make_pair
    memset(vst, 0, sizeof(vst));
    for(register int i = 1; i <= n; ++i) dist[i] = INF;
    priority_queue < pi > q;
    q.push(mp(0, st)), vst[st] = dist[st] = 0;
    while(!q.empty()) {
        int x = q.top().second; q.pop();
        if(vst[x]) continue;
        vst[x] = 1;
        for(register int i = head[x]; i; i = edge[i].nex) {
            int y = edge[i].v;
            if(dist[y] > dist[x] + 1) dist[y] = dist[x] + 1, q.push(mp(-dist[y], y));
        }
    }
    #undef pi
    #undef mp
}
signed main() {
    //freopen("piggyback.in", "r", stdin);
    //freopen("piggyback.out", "w", stdout);
    b = read(), e = read(), p = read(), n = read(), m = read();
    for(register int i = 1; i <= m; ++i) {
        int u = read(), v = read();
        make_map(u, v), make_map(v, u);
    }
    Dijstra(1); for(register int i = 1; i <= n; ++i) dist1[i] = dist[i];
    Dijstra(2); for(register int i = 1; i <= n; ++i) dist2[i] = dist[i];
    Dijstra(n); for(register int i = 1; i <= n; ++i) distn[i] = dist[i];
    for(register int i = 1; i <= n; ++i) ans = min(ans, b * dist1[i] + e * dist2[i] + p * distn[i]);
    printf("%lld", ans);
    return 0;
}

T2 Marathon

$1^o$ 分析

考虑DP。

设：$f[i][j]$表示前$i$头牛，跳过$j$个点的最短距离。

枚举点$p$，表示最后一步是从$p$跑到的$i$，则有方程：

$$f[i][j] = \min{f[p][j - (i - p - 1)] + \operatorname{Dis}(i,p)}$$
边界条件：$f[i][0] = 0$

//The code is from dawn_sdy
#include<bits/stdc++.h>
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 500 + 5;
int n, k;
struct Point {
    int x, y;
}point[maxn];
int f[maxn][maxn];
inline int Get_Dis(int x, int y) { return abs(point[x].x - point[y].x) + abs(point[x].y - point[y].y); }
int main() {
    //freopen("marathon.in", "r", stdin);
    //freopen("marathon.out", "w", stdout);
    n = read(), k = read();
    for(register int i = 1; i <= n; ++i) point[i].x = read(), point[i].y = read();  
    memset(f, 0x3f, sizeof(f)), f[1][0] = 0;
    for(register int i = 1; i <= n; ++i)
        for(register int len = 0; len <= min(i - 2, k); ++len) {
            for(register int p = i - len - 1; p < i; ++p)
                f[i][len] = min(f[i][len], f[p][len - (i - p - 1)] + Get_Dis(i, p));
            }
    printf("%d", f[n][k]);
    return 0;
}

T3 Cow Jog

$1^o$ 分析

首先将所有点按照开始位置排序。

而显然，如果有一点无法追上前面的点，则此点后面的点也始终无法追上前面的点。

这就启发我们从后往前扫，记当前段最前面的点为$now$，则我们只需要判断当前点是否能追上$now$即可。

如果可以，则$ans-1$，如果不行那么把这点设为$now$，继续操作。

//The code is from dawn_sdy
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 1e5 + 5;
int n, t;
struct node {
    int st, speed;
}a[maxn];
inline bool operator <(node x, node y) {
    return x.st < y.st;
}
signed main() {
//  freopen("cowjog.in", "r", stdin);
//  freopen("cowjog.out", "w", stdout);
    n = read(), t = read();
    for(register int i = 1; i <= n; ++i) a[i].st = read(), a[i].speed = read();
    sort(a + 1, a + n + 1);
    int ans = n, now = n;
    for(register int i = n - 1; i >= 1; --i) {
        if( (a[i].speed - a[now].speed) * t >= a[now].st - a[i].st) ans--;
        else now = i;
    }
    printf("%lld", ans);
    return 0;
}