2023.8.15 nfls集训Day7 考试总结

2023暑nfls

前言：不知道为什么没做出 $H$

Result

Progress

经典憋气干，开题。

$F$：环上 DP 或 贪心
$G$：暴力可以费用流，那不是直接线段树优化建图！
$H$：不知道什么题

$G$ 又是码量题，那就先想 $F$

倍长一下，考虑链上问题，链上问题有平凡的贪心做法。

注意到这个贪心策略，是选择能覆盖当前点的最右边的区间。

是不是和昨天的 $H$ 很像！和那题一样直接倍增合并区间就好了。

成功拿到 $F$ 一血。

开 $G$，先写个暴力建图费用流，为啥是 WA 不是 T 啊？？？

写网络流建图又是从 $0$ 开始的，调了半小时。

套线段树优化建图，调一调就过了。

还有一个多小时，为啥没人做 $H$ 啊，写个暴力吧，为啥 WA 0 啊。

然后忘记想了些什么，然后就下班了。

F 覆盖环

倍长，做链上问题，有平凡的贪心做法。

注意到这个贪心是一个区间合并的形式。

我们采用昨天 $H$ 的方式，倍增做区间合并。

G 游戏得分

暴力费用流很好建，一个二分图就好了。

发现左部点 $i$ 连向右部点 $[A_i, B_i - 1]$ 区间

显以线段树优化建图，具体的，将区间拆成 $\log$ 个，叶子连原来到 $T$ 的边。

线段树结点之间连 INF

H 冲撞的牛

“操作流程很长，操作形式是一个整体，可以拆成各个单位考虑”

如果要维护从一轮到下一轮的改变，十分的困难。

应该以每头牛的视角，单独考虑。

会发现这样问题就简单很多，原因是每头牛每一次都会先将相邻的下一头牛撞飞。

我们可以拿这个过程当做 “一步” 操作，维护每一步的改变。

那么我们只需要维护出，每头牛想要撞飞下一头牛需要多少时间。

每次取出所需时间最少的撞飞，并且更新这个时间。

链表加 set 可以很好的处理，维护难度不大，

#include<bits/stdc++.h>
#define Pre first
#define Nex second
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, INF = 1e9 + 7;
int n, m, Answer;
struct node {
    int x, v;
    int Id;
}Point[maxn];
int Dis[maxn], Vst[maxn];
pair <int, int> Link[maxn];
set < pair<int, int> > S;
inline int Get_Dis(int i, int j) {
    if(i == j) return INF;
    int d = ((Point[j].x - Point[i].x + m) % m + Point[j].v * (j < i)) % m;
    if(d <= Point[i].v) return 1;
    if(Point[i].v <= Point[j].v) return INF;
    return (d - Point[j].v - 1) / (Point[i].v - Point[j].v) + 1;
}
int main() {
//    freopen("H.in", "r", stdin);
//    freopen("H.out", "w", stdout);
    n = read(), m = read();
    for(register int i = 1; i <= n; ++i) Point[i].x = read() - 1, Point[i].v = read(), Point[i].Id = i;
    sort(Point + 1, Point + n + 1, [](node x, node y){ return x.x < y.x; });
    for(register int i = 1; i <= n; ++i) {
        Link[Point[i].Id].Pre = Point[i - 1].Id;
        Link[Point[i].Id].Nex = Point[i + 1].Id;
    }
    Link[Point[n].Id].Nex = Point[1].Id;
    Link[Point[1].Id].Pre = Point[n].Id;
    sort(Point + 1, Point + n + 1, [](node x, node y){ return x.Id < y.Id; });
    for(register int i = 1; i <= n; ++i) {
        Dis[i] = Get_Dis(i, Link[i].Nex);
        S.emplace(make_pair(Dis[i], i));
    }
    while(!S.empty()) {
        set< pair<int, int> >::iterator It = S.begin();
        int d = It -> first, i = It -> second;
        if(d == INF) break;
        S.erase(It), S.erase(make_pair(Dis[Link[i].Pre], Link[i].Pre)), S.erase(make_pair(Dis[Link[i].Nex], Link[i].Nex));
        Point[i].x = Point[i].x + d, Point[i].v--, Vst[Link[i].Nex] = 1;
        Link[i].Nex = Link[Link[i].Nex].Nex, Link[Link[i].Nex].Pre = i;
        Dis[Link[i].Pre] = Get_Dis(Link[i].Pre, i), Dis[i] = Get_Dis(i, Link[i].Nex);
        S.emplace(make_pair(Dis[Link[i].Pre], Link[i].Pre)), S.emplace(make_pair(Dis[i], i));
    }
    for(register int i = 1; i <= n; ++i)
        if(!Vst[i]) Answer++;
    printf("%d\n", Answer);
    for(register int i = 1; i <= n; ++i)
        if(!Vst[i]) printf("%d ", i);
    return 0;
}