10.4模拟赛 —— Violet I

2022秋

Contest_Summray

期望得分

实际得分：

• T1因为数据有行末空格挂掉 $10$ 分
• T2其实考场上正确性并没有完全想清楚，但还是过了
• T3想到了可以转换参考系，但是没想到转换后会是两组平行线段，加之计算几何不熟练，没有实现出来。

T1 Maze

Description

给你一个 $n\times m$ 的地图，上下行走需要花费 $v$ 时间，左右行走需要花费 $1$ 时间。求出最大的 $v$，使得从起点到终点的最短时间小于等于 $l$。保留 $5$ 位小数。

$1\leq n,m\leq 100,0\leq v<10$。

Solution

签到题。

答案显然单调。

二分 $v$，最短路算出时间，与 $l$ 比较即可。

Code

//The Code Is From Dawn
#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 = 205, INF = 1e9 + 7;
const double eps = 1e-7;
int T;
double X, Dist[maxn][maxn];
int n, m;
int a[maxn][maxn], sx, sy, ex, ey;
int go[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}, Vst[maxn][maxn];
inline double Dijstra(double V) {
    priority_queue < pair<double, pair<int, int> > > Q;
    Q.push(make_pair(0.0, make_pair(sx, sy))), Dist[sx][sy] = 0.0;
    while(!Q.empty()) {
        int x = Q.top().second.first, y = Q.top().second.second;
        Q.pop();
        if(Vst[x][y]) continue;
        Vst[x][y] = 1;
        if(x == ex && y == ey) { return Dist[x][y]; }
        for(register int i = 0; i < 4; ++i) {
            int nx = x + go[i][0], ny = y + go[i][1];
            if(nx < 1 || ny < 1 || nx > n || ny > m || Vst[nx][ny] || !a[nx][ny]) continue;
            if(Dist[nx][ny] > Dist[x][y] + (i < 2 ? V : 1)) {
                Dist[nx][ny] = Dist[x][y] + (i < 2 ? V : 1);
                Q.push(make_pair(-Dist[nx][ny], make_pair(nx, ny)));
            }
        }
    }
    return INF;
}
inline bool Check(double V) {
    for(register int i = 1; i <= n; ++i)
        for(register int j = 1; j <= m; ++j) Vst[i][j] = 0, Dist[i][j] = INF;
    return Dijstra(V) <= X; 
}
inline void Erfen() {
    double L = 0.0, R = 10.0;
    while(L + eps < R) {
        double mid = (L + R) / 2.0;
        if(Check(mid)) L = mid;
        else R = mid;
    }
    printf("%0.5lf\n", L);
    return ; 
}
int main() {
//  freopen("maze.in", "r", stdin);
//  freopen("maze.out", "w", stdout);
    scanf("%d", &T);
    while(T--) {
        scanf("%lf%d%d", &X, &n, &m);
        memset(a, 0, sizeof(a));
        string c;
        getline(cin, c);
        for(register int i = 1; i <= n; ++i) {
            getline(cin, c);
            for(register int j = 1; j <= m; ++j) {
                if(c[j - 1] == 'S') sx = i, sy = j;
                if(c[j - 1] == 'E') ex = i, ey = j;
                if(c[j - 1] == '#') a[i][j] = 0;
                else a[i][j] = 1;
            }
        }
        Erfen();
    }
    return 0;
}

T2 Puppet

Description

给你一个长为 $n$ 的数组 $a$，和一个完全相同的数组 $b$。

你需要从数组 $a$ 中选出一个数 $x$，若 $b$ 数组中存在元素 $v$，使得 $|v-x|\leq 1$，则扔掉 $x$ 和 $v$，否则只扔掉 $x$，得分加 $1$。

输出得分最大可能是多少。

$1\leq n\leq 50,1\leq a_i\leq 100$。

Solution

先手玩一下，考虑如果想要一段东西丢掉 $k$ 个可以怎么构造方案。

将两个序列错开 $k$ 位，即第 $i$ 位与 $i + k$ 位匹配。

那么只要保证：1.重合的位可以匹配，2.不重合的位不能匹配。

这样就可以判断一个序列是否可以丢掉 $k$ 个。

所以单独算一个序列的答案只要枚举 $k$ 然后 $check$ 即可。

但是考虑整个问题时，整个序列可以被分为很多个段，每个段单独匹配。

所以就变成了一个经典的分段 $DP$

用上述方式预处理 $g(i, j)$ 即可。

另：考场上没考虑到的一个正确性有关的问题，那就是段与段之间，错开的那部分有没有可能互相匹配。

实际上是有可能的，但有处理方法，只要把上下两排交换，也就是每次是交错的把他错开，那就不会有这样的问题，而实际上这个的答案是与不交换等价的。

Code

//The Code Is From Dawn
#include<bits/stdc++.h>
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) {
        if(c == EOF) return -1;
        f |= (c == '-'), c = getchar();
    }
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 55;
int n, a[maxn], f[maxn], g[maxn][maxn];
int main() {
//  freopen("puppet.in", "r", stdin);
//  freopen("puppet.out", "w", stdout);
    while(~(n = read())) {
        for(register int i = 1; i <= n; ++i) a[i] = read();
        sort(a + 1, a + n + 1);
        memset(g, 0, sizeof(g));
        memset(f, 0, sizeof(f));
        for(register int i = 1; i <= n; ++i)
            for(register int j = i; j <= n; ++j) {
                for(register int k = 1; i + k - 1 <= j; ++k) {
                    int flag = 1;
                    for(register int p = 0; i + p + k <= j; ++p)
                        if(a[i + k + p] - a[i + p] > 1) { flag = 0; break; }
                    if(abs(a[j - k + 1] - a[i + k - 1]) <= 1) flag = 0;
                    if(!flag) break;
                    g[i][j] = k;
                }
            }
        for(register int i = 1; i <= n; ++i)
            for(register int j = 0; j < i; ++j) f[i] = max(f[i], f[j] + g[j + 1][i]);
        printf("%d\n", f[n]); 
    }
    return 0;
}

Summary

主要还是通过手玩发现单独把一个段匹配的算法，再去设计DP就显得比较简单。

T3 Chaser

Description

给你一条射线 $(x_{w1},y_{w1})\rightarrow(x_{w2},y_{w2})$ 和一条线段 $(x_{t1},y_{t1})-(x_{t2},y_{t2})$，点 $a$ 从射线端点沿着射线以速度 $v_w$ 运动，点 $b$ 从点 $t1$ 开始，以速度 $v_t$ 在线段上往返运动。

令点 $a$ 和 $b$ 的最短距离为 $d$，若 $d<d_l$，输出 Dangerous，若 $d>d_u$，则输出 Miss，否则输出 Perfect。

$-2\times 10^9\leq x,y\leq 2\times 10^9,1\leq v\leq 2\times 10^4$

$0\leq d_l,d_l+10^{-5}<d_u\leq 2\times 10^6,1\leq T\leq 5\times 10^3$

Solution

考虑将其中一个点固定，例如可以将往返运动的点固定不动。

也就是更换参考系，重新计算另一个点的路线。

考试的时候傻掉了，实际上可以先把两个点的速度向量 $Vw$，$Vt$ 分别求出

那么新的路线显然是折线，然后用向量运算把这个折线的速度向量算出来：$Vw - Vt$，$Vt - Vw$，从而算出直线的向量表示。

然后可以发现这些周期性折线的两段会分别平行。

也就是可以将其划分为两组平行的周期性线段，然后求点到这两组线段的最小距离。

单看一组，点到这组线段的距离显然具有单峰性，考虑三分，然后套个点到线段的距离求法就行了。

另：点到线段的距离求法：

与两端点求叉积，得到平四面积，除掉线段的长度，得到点到该直线的距离。

用点积判断垂足是否落在线段上，若不在则与两端点求距离。

Code

//The Code Is From Dawn
#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 INF = 1e18;
struct node {
    double x, y;
}W1, W2, T1, T2, Vw, Vt, P, Q, Cnt;
double vw, vt, dl, dr, Answer, Time;
inline node operator + (node A, node B) { return (node){A.x + B.x, A.y + B.y}; }
inline node operator - (node A, node B) { return (node){A.x - B.x, A.y - B.y}; }
inline node operator * (node B, double A) { return (node){A * B.x, A * B.y}; }
inline node operator / (node B, double A) { return (node){B.x / A, B.y / A}; }
inline double operator * (node A, node B) { return A.x * B.y - A.y * B.x; }
inline double operator ^ (node A, node B) { return A.x * B.x + A.y * B.y; }
inline double Len(node A) { return sqrt(A.x * A.x + A.y * A.y); }
inline double Dis(node A, node B) { return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y)); }
inline double Segment_Dist(node A, node L, node R) {
//  printf("%lf\n", Len(L -R));
    if(((A - L) ^ (R - L)) < 0.0 || ((A - R) ^ (L - R)) < 0.0) return min(Len(A - L), Len(A - R));
    else return fabs((A - L) * (A - R)) / Len(L - R);
}   
inline void Work1() {
    int l = 0, r = 2e9;
    while(r - l > 12) {
        int mid1 = l + (r - l) / 3, mid2 = r - (r - l) / 3;
        if(Segment_Dist(T1, W1 + Cnt * mid1, P + Cnt * mid1) >= Segment_Dist(T1, W1 + Cnt * mid2, P + Cnt * mid2)) l = mid1;
        else r = mid2;
    }
    for(register int i = l; i <= r; ++i) Answer = min(Answer, Segment_Dist(T1, W1 + Cnt * i, P + Cnt * i));
}
inline void Work2() {
    int l = 0, r = 2e9;
    while(r - l > 12) {
        int mid1 = l + (r - l) / 3, mid2 = r - (r - l) / 3;
        if(Segment_Dist(T1, P + Cnt * mid1, Q + Cnt * mid1) >= Segment_Dist(T1, P + Cnt * mid2, Q + Cnt * mid2)) l = mid1;
        else r = mid2;
    }
    for(register int i = l; i <= r; ++i) Answer = min(Answer, Segment_Dist(T1, P + Cnt * i, Q + Cnt * i));  
}
signed main() {
//  freopen("chaser.in", "r", stdin);
//  freopen("chaser.out", "w", stdout);
    while(~scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf", &W1.x, &W1.y, &W2.x, &W2.y, &vw, &T1.x, &T1.y, &T2.x, &T2.y, &vt, &dl, &dr)) {
        Vw = (W2 - W1), Vw = Vw / Len(Vw) * vw, Vt = (T2 - T1), Vt = Vt / Len(Vt) * vt;
        Time = Len(T2 - T1) / vt, Answer = INF;
        P = W1 + (Vw - Vt) * Time, Q = P + (Vw + Vt) * Time, Cnt = Vw * (2.0 * Time);
        Work1(), Work2();
        if(Answer <= dl) printf("Dangerous\n");
        else if(Answer <= dr) printf("Perfect\n");
        else printf("Miss\n");
    }
    return 0;
}

Summary

求两个动点间的动态距离，可以考虑更换参考系，使其只有一个动点，从而转化为定点与定线的问题。

转换参考系时，另一个点路径的改变就是做速度向量运算。

许多周期性折线，线段到点距离似乎都具有单峰或单调性，适合三分或二分。