• 时间:
  • 分类: OI
摘要： 文章讨论了SSL-OI夏日合宿2020.08.17 A组的三道题目。T1题要求根据边权求点权，解法涉及基环树和环上的k元一次方程组求解。T2题要求将数组分为两个上升子序列，使差值最小，解法涉及二分图染色和DP。T3题涉及序列操作，支持修改和查询，解法提出了树剖和树套树两种方法。文章还提到了出题人胡睿和博客更新情况。

今天是他的生日,让我们祝他生日快乐!

这套题是北大爷不知道从哪里找来的, 只知道出题人署名是 HRupd:刚刚北大爷悄悄透露了, 大佬叫$胡睿$, 裸考被屏蔽强的一批QwQ.

今天也是卑微爆0, 下次一定(?)认真打简单题&暴力.

博客好久没更了, 主要是因为腐太多了? 还是要好好打一打题解的, 不然真的啥都没留下就退役了.

今天的代码估计要咕, 还是先打完博客梳理一下思路吧.

后续如果能改出来的话, 会更新在Github.

T1 图

题意

给一个n个点n条边的图, 边权表示所连的两点的权值和. 给出边权, 求点权.

正解

显然这是一棵基环树, 图中的环是一个$k$元一次方程组, 可以求解. 环上的点权解出后, 对于每棵树上的点权直接求出.

有关x元一次方程组的求解, 可以用高斯消元, 但在这道题中有更加简单的解法: 考虑到每个方程组只有两个非${0}$系数且系数都为${1}$, 可以用钦定一个点$x$作为起点, 从它的一条出边开始遍历环, 将环上的$k$条边都表示成含$x$的式子. 显然, 当我们回到点$x$时,这条边上的方程只有变量$x$且系数为${2}$.

#define MXN (100020)

#include <math.h>
#include <stdio.h>
#include <string.h>

#include <vector>

int n;

struct Edge {
    int v, w;
} cer[MXN];
std::vector<Edge> edge[MXN];
int cnt;

int nc;
bool vis[MXN], in;
void dfs1(int x, int f) {
    if (vis[x]) {
        nc = x;
    } else {
        vis[x] = true;
        for (int i = edge[x].size() - 1; !nc && i >= 0; --i) {
            if (edge[x][i].v != f) {
                dfs1(edge[x][i].v, x);
                if (in) cer[++cnt] = edge[x][i];
            }
        }
        vis[x] = false;
    }
    if (x == nc) in = !in;
}

double ans[MXN];

void dfs2(int x) {
    vis[x] = true;
    for (int i = edge[x].size() - 1; i >= 0; --i)
        if (!vis[edge[x][i].v])
            ans[edge[x][i].v] = edge[x][i].w - ans[x], dfs2(edge[x][i].v);
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("A.in", "r", stdin);
#endif

    scanf("%d", &n);

    for (int i = 0, x, y, w; i < n; ++i)
        scanf("%d%d%d", &x, &y, &w), edge[x].push_back(Edge{y, w}), edge[y].push_back(Edge{x, w});

    dfs1(1, 0);

    for (int i = 1, p = -1; i <= cnt; ++i)
        ans[cer[1].v] += (p *= -1) * cer[i].w;
    ans[cer[1].v] /= 2.0;

    dfs2(cer[1].v);

    for (int i = 1; i <= n; ++i)
        printf("%g\n", ans[i]);

    return 0;
}

T2 上升子序列

题意

给出一个数组, 要求将其分为两个上升子序列, 求两个子序列的差最小.(无解输出${-1}$)

正解

考虑到每一个值都必须在某个上升子序列中, 那么对于每个逆序对, 都必在两个不同的上升子序列中. 若每个逆序对连一条边跑二分图染色, 若染色成功会留下若干个连通块. 若染色不成功, 则序列不合法.

证明 每个连通块的值域没有交集: 若值域有交集, 前面一个区间的最大值和后面一个区间的最小值是一个逆序对, 必有连边.

所以我们只用枚举一个分界点. $i,i+1$是两个连通块的分界点, 当且仅当$max[1,i]<min(i,N]$.

然后对于每个连通块区间, 判断是否合法. 想起一道经典题<导弹拦截>: 最小划分上升子序列数等于最长降, 所以只要存在一个长度为$3$的下降序列, 这个区间就不合法.

对于每个连通块, 最多只有一种划分方法. 所以只要求出一个最长上升子序列, 其中必包含每个逆序对的其中一个. 用区间长度减去最长升长度, 得到每个连通块的差值. 要使总差值最小, 只要DP每个区间取${+}$或取${-}$.

T3 大冰隙2

题意

给出一个序列, 每个元素$i$包含两个值: 种类 ${b_i\in\{0,1\}}$ , 数值 ${c_i<2^{30}}$.

支持两个操作:

修改: 单点修改某个元素的数值.

查询: 相邻两个种类为的元素会被消去(不计入答案), 某一段消去后其左右两边视为相邻. 求一段区间中没被消去的元素的最大数值. (无剩余输出${0}$)

思路 (故事)

暴力的日子就要用暴力的解法.很显然这题是一个区间查询问题, 那么我们用莫队; 这题有修改, 那么我们用带修莫队; 这题合并不可逆, 那么我们用回滚莫队. 另外还要维护一棵平衡树(multiset)支持插入删除求最大.

综上: 这题可以用带修回滚莫${N\sqrt{N}\log_2{N}}$的复杂度获得$?$分的好成绩. (正常都是因为没打出来而爆0吧?)

正解1 树剖

我们发现有顺序的${01}$抵消很像出入栈顺序, 我们把一段${01}$序列视作某棵树的dfs序的一部分, ${0}$表示向下遍历, ${1}$表示向上回溯.
注意: 若有"多余"的${1}$则新建一个点作为新的根, 将旧的根作为其儿子.

如此建树后, 每棵棵子树内的所有点都没有贡献, 区间查询问题变成了树上两点间的路径最大值查询, 我们用树链剖分即可.
注意: 由于边权有向的, 设$x<y$有: 链 ${x}$ -> ${LCA_{x,y}}$应取向上边权, 链 ${LCA_{x,y}}$ -> ${y}$应取向下边权. 我们开两棵线段树分别处理向上/向下边权即可.

正解2 树套树

显然对于某段区间, 充分合并后只剩余若干个${1}$和若干个${0}$, 形如${111100}$.

我们维护一个线段树, 对于每个区间维护${1}$的数量和${0}$的数量, 再用线段树分别对于${1}$和${0}$处理出区间最大值.

合并时两个区间中间同时消去$min(0_{Left},1_{Right})$, 再将剩下区间的线段树合并.

标签: none

添加新评论