C、Delete Edges

题目大意

你有一张个点的无向完全图，你需要删掉一些边，让这张图里面边数小于点数，输出你删除边的方案。

Solution

结论构造题

官方给的证明非常长…直接说结论了，输出全部以及的不同点对。值得注意的是在点对中我们必须保证在三元组中任选两个元素构成的二元组出现了两次。

那么我们只需要保证进行暴力即可。

vector<tuple<int, int, int>> res;

int solve() {
    n = read();
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            int k = n - i - j;
            if (k <= 0)    k += n;
            if (k > j)    res.push_back({ i,j,k });
        }
    }
    print(res.size());
    for (auto& [x, y, z] : res) {
        printf("%lld %lld %lld\n", x, y, z);
    }

    return 1;
}

F、Hamburger Steak

题目大意

你有个汉堡代煎，每个汉堡要被煎制分钟，你现在只有口锅，每个汉堡可以分两次煎制也可以一次煎完。问完成块汉堡全部的煎制最小的完成时间是多少？

Solution

考点：思维题

因为你只有口锅，并且所有汉堡需要煎制的时间也给你了，那么你就可以知道对于工作时间最长的一口锅而言，它需要工作的最长时间。

首先，我们最小的完成时间都应该是，也就是对于锅而言最小的最长时间。

但是我们可以感觉到这个最长时间不一定就是锅的工作时间，例如，那么就一定有但是很显然这个式子是错误的，所以我们选择的最长工作时间是不一定是正确的，但是我们可以解出当前模式下的最大值应该是。

那么我们知道了每口锅需要工作的最大时间，那么我们就让每口锅工作满换再换下一口就行了，因为我们已经保证一口锅的时间要大于等于任何的一个，所以口锅一定可以完成任意一个汉堡的煎制工作。

typedef tuple<int, int, int> tup;
const int N = 1e5 + 7;
struct Node {
    vector<tup> a;
}ans[N];
ll n, m;
int p[N];

int solve() {
    n = read(), m = read();
    ll sum = 0;
    for (int i = 1; i <= n; ++i)    sum += p[i] = read();
    ll maxi = *max_element(p + 1, p + 1 + n);
    maxi = max(maxi, (sum + m - 1) / m);

    int pos = 1, now = 0;

    for (int i = 1; i <= n; ++i) {
        if (now + p[i] <= maxi) {
            ans[i].a.push_back({ pos,now,now + p[i] });
            now += p[i];
        }
        else {
            ans[i].a.push_back({ pos + 1,0,p[i] - (maxi - now) });
            ans[i].a.push_back({ pos,now,maxi });
            ++pos;
            now = p[i] - (maxi - now);
        }
        if(now == maxi)    ++pos,now = 0;
    }

    for (int i = 1; i <= n; ++i) {
        cout << ans[i].a.size() << " ";
        for (auto& [id, l, r] : ans[i].a)
            cout << id << " " << l << " " << r << " ";
        cout << endl;
    }

    return 1;
}

H、Hopping Rabbit

题目大意

小兔子在一个二维的格点图中跳跃，每次它都会沿着正负方向共个方向移动个单位长度。

现在地图中有个陷阱，陷阱是以矩阵的方式存在的，问你有没有一种方法让小兔子在某个起点随意乱跳的情况下都不会掉入任何一个陷阱，你要输出这个起点，或者。

Solution

考点：线段树维护扫描线

首先由于地图本质上是无穷大的，但是对于这样的任意一个矩阵来说，由于小兔子的步长一定为，所以都一定可以离散到这样的初始矩阵中，所以我们按照覆盖关系可以将个陷阱离散到初始矩阵里面，接下来就是要去这个初始矩阵里面找是不是有那个格点它没有被任何一个矩阵覆盖，如果我们固定轴那么轴就变成了一个扫描线问题。

但是显而易见的，如果我们对于每个都暴力的的维护一个扫描线，这样时间复杂度是的会超时。

我们就要想要一个更优秀的方式去维护轴的扫描线，对于区间问题，常用的工具就是线段树了。

我们在树上开出一个懒惰标记，很显然这个懒惰标记一定只有和等于的两种情况，那么当某个区间懒惰标记很显然这个区间的合法长度应该是，那么当懒惰标记退为了怎么办呢？当这个区间是叶子的时候我们就把区间长度赋值成就行，如果不是叶子的话，我们应该保留之前它左右孩子的区间长度之和。因为这个大区间被剔除，小区间可能还是存在一定长度的。例如已经被删除，但是还在扫描线里面，甚至都在扫描线里面。所以我们还是需要等于之前那个区间长度。

接下来就看区间的区间长度是否等于即可判断是不是存在空点了，时间复杂度。特殊的输出答案我们用树上二分的思想，找到那个长度不满足的叶子节点就行了。

const int N = 1e5 + 7;

struct Node {
#define mid (l + r >> 1)
#define ls rt << 1
#define rs rt << 1 | 1
#define lson ls,l,mid
#define rson rs,mid+1,r

    ll len[N << 2], cnt[N << 2];
    void push_up(int rt, int l, int r) {
        if (cnt[rt])    len[rt] = r - l + 1;
        else if (l == r)    len[rt] = 0;
        else len[rt] = len[ls] + len[rs];
    }

    void update(int rt, int l, int r, int L, int R, ll v) {
        if (L <= l && r <= R) {
            cnt[rt] += v;
            push_up(rt, l, r);
            return;
        }
        if (L <= mid)    update(lson, L, R, v);
        if (R > mid)    update(rson, L, R, v);
        push_up(rt, l, r);
    }
    ll query(int rt, int l, int r) {
        if (l == r)    return l;
        if (len[ls] < mid - l + 1)    return query(lson);
        else return query(rson);
    }
#undef mid
#undef ls
#undef rs
#undef lson
#undef rson
}A;

vector<tup> G[N];
vector<pai> add[N], del[N];
int n, d;

void push(int x1, int x2, vector<pai>& seg) {
    if (x2 - x1 >= d) {
        seg.push_back({ 0,d - 1 });
    }
    else if (x1 % d <= (x2 - 1) % d) {
        seg.push_back({ x1 % d ,(x2 - 1) % d });
    }
    else {
        seg.push_back({ 0, (x2 - 1) % d });
        seg.push_back({ x1 % d, d - 1 });
    }

}



int solve() {
    n = read(), d = read();
    const int P = (1 << 30) / d * d; // 坐标偏移
    for (int i = 1; i <= n; ++i) {
        int X1 = read() + P, Y1 = read() + P, X2 = read() + P, Y2 = read() + P;
        vector<pai> seg1, seg2;
        push(X1, X2, seg1);
        push(Y1, Y2, seg2);
        for (auto& [l, r] : seg1) {
            for (auto& seg : seg2) {
                add[l].push_back(seg);
                del[r + 1].push_back(seg);
            }
        }
    }
    for (int i = 0; i < d; ++i) {
        for (auto& [l, r] : add[i])
            A.update(1, 0, d - 1, l, r, 1);
        for (auto& [l, r] : del[i])
            A.update(1, 0, d - 1, l, r, -1);
        if (A.len[1] < d) {
            puts("YES");
            cout << i << " " << A.query(1, 0, d - 1) << endl;
            return 1;
        }
    }
    puts("NO");

    return 1;
}

I、Intervals on the Ring

题目大意

给出不相交的条圆上线段，圆的编号为，现在你要构造一个长度为的新线段集合，保证你构造的线段区间交等于之前的条线段的区间并。

Solution

比较轻松的可以想到用相邻两条线段的左右端点构造新的线段即可。

我们按照的方式进行排序后，输出不包含的那条线段就行了，这样条线段交集之后就会把原先不存在的空格剔除。

pair<int, int> p[N];

int solve() {
    n = read(), m = read();
    for (int i = 1; i <= m; ++i) {
        p[i] = { read() , read() };
    }
    sort(p + 1, p + 1 + m);
    p[m + 1] = p[1];
    print(m);
    for (int i = 1; i <= m; ++i) {
        printf("%d %d\n", p[i].first, p[i + 1].second);
    }

    return 1;
}

J、Defend Your Country

题目大意

你有一张个点条边的无向联通图，现在对于图中的连通分量产生的价值做出如下定义。

如果一个联通分量里面点的个数是偶数那么它的价值就是里面每个点权的和。

如果一个连通分量里面点的个数是奇数那么他的价值就是里面每个点权的和的相反数。

保证每个点的点权。

你现在可以选择一个点把它删去，并且它连的边也一并删去，问进行删除任意多个点之后整张图的权值和最大是多少？

Solution

考点：求割点

首先可以知道，当是偶数的时候，我们不需要进行删点，直接输出就行了。

当是奇数的时候，结论是只需要删掉最多一个点，接下来我们稍微验证一下这个结论。

首先我们去找不是割点的点，这些点是可以随意删除的，删掉它不会带来其他点的损失，那么我们把所有非割点定为可删的点。

那么还有一大类就是对于割点而言，那么如果从号点开始我们会跑出一个类似树的结构。

我们又知道了一定是奇数，那么对于任意个一个割点而言，如果存在一棵子数它的节点总数是奇数，那么一定存在一个对应的子数节点数也是奇数，因为去掉这个割点之后其余点数之和应该为偶数了，所以我们对于存在奇数子树节点的割点，我们就不能删掉，否则如果它下面全部的子树都是偶数，那么对应的它头顶上剩下的子树节点数也是偶数个，对于这样的割点删掉带来的负反馈也是一个节点的值，这样的割点我也认为它可删去。

接下来就去找全部可删去的点里面权值的最小值，用就是答案了。

const int N = 1e6 + 7;
const int M = 1e6 + 7;

struct Map {
    struct Node {
        int v, nxt;
    };
    int head[N], tot;
    Node edge[M << 1];
    void init(int n) { fill(head,head+n+1,-1), tot = 0; }
    void add(int u, int v) {
        edge[++tot].v = v;
        edge[tot].nxt = head[u];
        head[u] = tot;
    }
}G1;

int a[N];
bool cut[N], ok[N];
int rt, low[N], dfn[N], tot, sz[N];

void tarjan(int u) {
    dfn[u] = low[u] = ++tot;
    sz[u] = 1;
    int son = 0;
    for (int i = G1.head[u]; ~i; i = G1.edge[i].nxt) {
        int v = G1.edge[i].v;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
            sz[u] += sz[v];
            if (low[v] >= dfn[u]) {
                ++son;
                if (u != rt or son > 1)    cut[u] = 1;
                if (sz[v] & 1)    ok[u] = 0;
            }
        }
        else low[u] = min(low[u], dfn[v]);
    }
}

int solve() {
    int n = read(), m = read();
    G1.init(n);
    for (int i = 1; i <= n; ++i) {
        cut[i] = 0;
        ok[i] = 1;
        low[i] = dfn[i] = sz[i] = 0;
    }
    int sum = 0;
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
        sum += a[i];
    }
    for (int i = 1; i <= m; ++i) {
        int u = read(), v = read();
        G1.add(u, v);
        G1.add(v, u);
    }
    if (n & 1) {
        rt = 1;
        tarjan(1);
        int mini = INT_MAX;
        for (int i = 1; i <= n; ++i) {
            if (cut[i] == 0 || (cut[i] == 1 && ok[i] == 1)) {
                mini = min(mini, a[i]);
            }
        }
        print(sum - 2 * mini);
    }
    else {
        print(sum);
    }

    return 1;
}