出题人关于 F 题的一点说明

F 题内测初期，由于其表述并不好的题意，加上这题本身题面就不简洁，导致没什么人愿意去写。同时，这题一眼给人的感觉就是模拟题，内测期间唯一的选手使用分数类模板+优先队列模拟的写法，很难写，后面貌似是直接弃了。我提出 std 做法很简洁，可以验验 std 做法，但是没有回应。最后就一直搁置到比赛了。后面题意改成现在这个基本没什么问题的版本的时候，估计大家已经被题目风评劝退了，其次是本身 F 题就不严格需要很多人都做，最后的结果这题几乎没有有效验题。最后的结果大家都知道， std 赛后有被 hack。

不过，出题人认为这个 hack 是 std 一个小细节写错了，稍微改一下就行，大方向做法没有问题。

如果还有问题，欢迎联系出题人 hack。

下面是原题解：

F

考虑各边之间独立。

所以把所有 $\sum(k-1)$ 次线路上的行车离线下来，按进入线路的时间升序处理。

扫描这 $\sum(k-1)$ 条线路，对于当前这条线路，当前车是否追尾只和当前这条边上已开过的，未产生追尾的车中最晚的一趟有关（证明下面写），所以每条边只记录最晚的一趟车。所以只要判断两车是否会追尾。

令时间为 $x$ 轴，路程为 $y$ 轴，速度即为斜率。

假设这两趟车 $u$ 出发时间为 $t_1,t_2$ ，到达 $v$ 时间为 $t_3,t_4$ ，则追尾当且仅当 $(t_1-t_2)\times(t_3-t_4)\le 0$ 。

时间直接算实数会有精度误差，因为速度是定值，时间等于路程除以速度，所以累计一下路程，把上述式子展开计算即可。

若当前车产生追尾，则标记它，在后续过程中忽略。

对于特殊情况，其实只要 “把所有 $\sum(k-1)$ 次线路上的行车离线下来，按进入线路的时间升序处理。” 时，对于时间相同的车，按编号为第二关键字降序即可。

时间复杂度： $O(n\log n)$ 。

证明：

对于当前线路中，若干未产生追尾的车，显然要追尾首先追的是在最后面的。如果时间不是最晚的，那它不会是最后的。

一种可能会想复杂的特殊情况：若 $A$ 车进入 $(u,v)$ 后会追尾 $B$ ，但是在追尾 $B$ 之前，被后面更晚出发的 $C$ 追上了怎么办（如果我们直接判断 $A$ 产生追尾就把它忽略掉的话，就判断不了 $A,C$ 追尾）？实际上，若出现这种情况，那么本身 $C$ 还是会追尾 $B$ 的，因为题目只要判断车是否存在追尾，所以等价的。

原 std 的问题是，有一种情况是，对于若干相同时间出发的列车，std 按时间顺序判断时，可能会出现编号最大的那一辆与当前最晚的车产生了追尾，那么 std 就把它去掉了，这是不合理的。所以应该先用编号大的去标记同时出发的其它列车，再去和当前最晚的车进行判断即可。

下面是修改后的 std：

#include<bits/stdc++.h>
#define For(i,a,b) for(i=a;i<=b;i++)
using namespace std;
typedef long long i64;
const int N = 1e6 + 10;
struct train {
    int x, v, k;
    vector<int> a;
} a[N];
struct edge {
    int u, v, w;
} p[N];
struct line {
    i64 s, v;
    int id1, id2;
    bool operator <(const line &a) const {
        if (s * a.v == a.s * v) return id2 > a.id2;
        return s * a.v < a.s * v;
    }
    bool operator==(const line &a) const {
        return s * a.v == a.s * v;
    }
};
line Q[N];
bool st[N];
bool inter(line x, line y, int len) {
    i64 res1, res2;
    res1 = (x.s * y.v - y.s * x.v);
    if (res1) res1 = res1 / abs(res1);
    x.s += len, y.s += len;
    res2 = (x.s * y.v - y.s * x.v);
    if (res2) res2 = res2 / abs(res2);
    return res1 * res2 <= 0;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    int i;
    For(i, 1, m) {
        cin >> a[i].x >> a[i].v >> a[i].k;
        a[i].a.resize(a[i].k + 1);
        int j;
        For(j, 1, a[i].k) cin >> a[i].a[j];
    }
    int M;
    cin >> M;
    map<pair<int, int>, int> mp;
    For(i, 1, M) {
        int u, v, w;
        cin >> u >> v >> w;
        mp[ {u, v}] = i;
        p[i] = {u, v, w};
    }
    vector<line> q;
    For(i, 1, m) {
        int j;
        i64 s = a[i].x * a[i].v;
        For(j, 1, a[i].k - 1) {
            int id = mp[ {a[i].a[j], a[i].a[j + 1]}];
            q.push_back({s, a[i].v, id, i});
            s += p[id].w;
        }
    }
    sort(q.begin(), q.end());
    vector<bool> vis(m + 1);
    for (unsigned i = 0; i < q.size(); i++) {
        if (vis[q[i].id2]) continue;
	    /* 唯一的修改
        for (unsigned j = i + 1; j < q.size(); j++) {
            if (q[j] == q[i]) {
                vis[q[j].id2] = 1;
            }
            else break;
        }*/
        if (!st[q[i].id1]) {
            Q[q[i].id1] = q[i];
            st[q[i].id1] = 1;
            continue;
        }
        auto now = Q[q[i].id1];
        if (inter(now, q[i], p[q[i].id1].w)) vis[q[i].id2] = 1;
        else Q[q[i].id1] = q[i];
    }
    For(i, 1, m) if (vis[i]) cout << "YES\n"; else cout << "NO\n";
    return 0;
}

全部评论

推荐最新楼层

LargeRice16pro

楼主

成都工业学院 C++

这场比赛，总体质量确实有很多槽点，从各方面，也确实应该是可以预料到的。只能说是多方妥协的结果。这套题基本上讲只有半个月到一个月之间的准备周期。最早是 9 月初投的第一版，国庆期间对初审意见做了修改，就直接过审了，我原本以为这套题会至少在 12 月中旬才能排到，结果 10 月 14 日被告知原本的队列里的题要么是出题人鸽了，要么是升到练习赛，我就被抬上来了。原本的 E 题我觉得是一个比较有 edu 意义的典题，但是赛前三天被告知原了（出题人坚持认为给出原题链接才是原）于是紧急造了现在的 E，实际上是一天之内我造了三个版本的题，但是前两个都严重偏难，都是可以放到相对容易的 F 的题，赛前一天才修改成现在这个版本。被诟病的 fg 的强行复合，在原本的版本中虽然也有一点点牵强，但是确实是有用的（与现在的版本相比而言）。

点赞回复分享

发布于 10-30 12:48 浙江

LargeRice16pro

楼主

成都工业学院 C++

至于 GPT 速通的事情，出题人完全没有考虑到，也是始料不及的。对于那些因为这场比赛带来了不好参赛体验的选手，出题人在这里深表歉意。如果，之后还有出题，出题人一定吸取教训，尽量为选手们带来更好的体验。

点赞回复分享

发布于 10-30 12:50 浙江

LargeRice16pro

楼主

成都工业学院 C++

至于出题风格，题目类型上的事情，比如 B 放模拟题，题目比较“典”，出题人认为是不同选手对题目看法问题，没有谁对谁错，仁者见仁智者见智吧。