724119-opt

more than OIers and algorithm learners

最新文章

[WC2011]最大XOR和路径 题解

[WC2011]最大XOR和路径 题解

题目地址:洛谷:【P4151】[WC2011]最大XOR和路径 – 洛谷、BZOJ:Problem 2115. — [Wc2011] Xor

题目描述

WC2011xor

题意简述

给你一个n点m边的无向图,求一条1到n的路径使边权异或和最大。

输入输出格式

输入格式:
第一行包含两个整数 N 和 M, 表示该无向图中点的数目与边的数目。
接下来 M 行描述 M 条边,每行三个整数Si,Ti,Di,表示 Si 与 Ti 之间存在一条权值为 Di 的无向边。
图中可能有重边或自环。

输出格式:
仅包含一个整数,表示最大的XOR和(十进制结果),注意输出后加换行回车。

输入输出样例

输入样例#1:

5 7
1 2 2
1 3 2
2 4 1
2 5 1
4 5 3
5 3 4
4 3 2 

输出样例#1:

6

说明

WC2011xor

题解

首先,我们考虑异或和最大的路径应该是怎么样的。我们考虑图中的环,显然我们可以从任意一个节点走到环上,绕环一圈,再走回来,这样只有这个环的权值异或和就被异或了进去。那么我们可以DFS处理一遍环的权值异或和来得到一个集合。
具体来说,DFS如果遇到一条边两端的点都已经访问过,那么就可以将dis[u]^dis[v]^边权记作环的权值异或和,这是由于dis[u]^dis[v]会将不在环上的边通过一次异或消去。
我们发现,我们只需要用一条1到n的路径再组合上这个集合的某一些权值使得异或和最大就行了。对于这个集合的处理,我们可以求线性基,这样就可以代表所有可能的情况的异或值。我们只需要任选一条1到n的路径并且使用线性基计算最大值就可以了。
任选一条路径为什么是正确的?我们考虑1到n的路径假如有2条,那么这两条路径会构成环,任选其中一条,再异或上这个环,实际上得到了另一条路径的异或和,而环的情况刚刚已经处理过,我们可以保证答案最优。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>

#include <algorithm>
#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 50005;

int n, m;

struct Edge {
    int to;
    LL w;
};

std::vector<Edge> gra[MAXN];

bool vis[MAXN];
LL dis[MAXN];
std::vector<LL> cir;

inline void dfs(int u) {
    vis[u] = true;
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i].to;
        if(vis[v]) {
            cir.push_back(dis[v] ^ dis[u] ^ gra[u][i].w);
        } else {
            dis[v] = dis[u] ^ gra[u][i].w;
            dfs(v);
        }
    }
}

LL mat[65];

int main() {
    n = readint(); m = readint();
    int u, v; LL w;
    for(int i = 1; i <= m; i++) {
        u = readint(); v = readint(); w = readint();
        gra[u].push_back(Edge {v, w});
        gra[v].push_back(Edge {u, w});
    }
    dfs(1);
    for(int i = 0; i < cir.size(); i++) {
        for(int j = 63; j >= 0; j--) {
            if(cir[i] & (1ll << j)) { // 这里不是1ll会爆int
                if(!mat[j]) {
                    mat[j] = cir[i];
                    break;
                } else {
                    cir[i] ^= mat[j];
                }
            }
        }
    }
    LL ans = dis[n];
    for(int i = 63; i >= 0; i--) {
        ans = std::max(ans, ans ^ mat[i]);
    }
    printf("%lld", ans);
    return 0;
}
[NOI2010]航空管制 题解

[NOI2010]航空管制 题解

题目地址:洛谷:【P1954】[NOI2010]航空管制 – 洛谷、BZOJ:Problem 2535. — [Noi2010]Plane 航空管制2

题目描述

世博期间,上海的航空客运量大大超过了平时,随之而来的航空管制也频频发生。最近,小X就因为航空管制,连续两次在机场被延误超过了两小时。对此,小X表示很不满意。
在这次来烟台的路上,小X不幸又一次碰上了航空管制。于是小X开始思考关于航空管制的问题。
假设目前被延误航班共有n个,编号为1至n。机场只有一条起飞跑道,所有的航班需按某个顺序依次起飞(称这个顺序为起飞序列)。定义一个航班的起飞序号为该航班在起飞序列中的位置,即是第几个起飞的航班。
起飞序列还存在两类限制条件:

  • 第一类(最晚起飞时间限制):编号为i的航班起飞序号不得超过ki;
  • 第二类(相对起飞顺序限制):存在一些相对起飞顺序限制(a, b),表示航班a的起飞时间必须早于航班b,即航班a的起飞序号必须小于航班b的起飞序号。

小X思考的第一个问题是,若给定以上两类限制条件,是否可以计算出一个可行的起飞序列。第二个问题则是,在考虑两类限制条件的情况下,如何求出每个航班在所有可行的起飞序列中的最小起飞序号。

输入输出格式

输入格式:
输入文件plane.in第一行包含两个正整数n和m,n表示航班数目,m表示第二类限制条件(相对起飞顺序限制)的数目。
第二行包含n个正整数k1, k2, …, kn。
接下来m行,每行两个正整数a和b,表示一对相对起飞顺序限制(a, b),其中1≤a,b≤n, 表示航班a必须先于航班b起飞。

输出格式:
输出文件plane.out由两行组成。
第一行包含n个整数,表示一个可行的起飞序列,相邻两个整数用空格分隔。输入数据保证至少存在一个可行的起飞序列。如果存在多个可行的方案,输出任意一个即可。
第二行包含n个整数t1, t2, …, tn,其中ti表示航班i可能的最小起飞序号,相邻两个整数用空格分隔。

输入输出样例

输入样例#1:

5 5
4 5 2 5 4
1 2
3 2
5 1
3 4
3 1

输出样例#1:

3 5 1 4 2
3 4 1 2 1

输入样例#2:

5 0
3 3 3 5 5

输出样例#2:

3 2 1 5 4
1 1 1 4 4

说明

【样例说明】
在样例1 中:
起飞序列3 5 1 4 2满足了所有的限制条件,所有满足条件的起飞序列有:
3 4 5 1 2 3 5 1 2 4 3 5 1 4 2 3 5 4 1 2
5 3 1 2 4 5 3 1 4 2 5 3 4 1 2
由于存在(5, 1)和(3, 1)两个限制,航班1只能安排在航班5和3之后,故最早起飞时间为3,其他航班类似。
在样例2 中:
虽然航班4、5没有相对起飞顺序限制,但是由于航班1、2、3都必须安排在前3个起飞,所以4、5最早只能安排在第4个起飞。
【数据范围】
对于30%数据:n≤10;
对于60%数据:n≤500;
对于100%数据:n≤2,000,m≤10,000。

题解

第一问,考虑把限制条件建个图,一定是一个DAG,直接进行拓扑排序,只不过拓扑的队列要改成优先队列,优先级按最晚时间限制从小到大排序,这样出来的顺序就是正确的了。
但是考虑第二问的时候,发现就算建反图DFS还可能出现其他需要满足的条件,例如样例2中前三个飞机必须在前三飞。此时我们考虑倒着找,建反图按限制从大到小的顺序拓扑,我们枚举每个飞机u,每次都拓扑一遍,遇到u的时候直接把它设置为不可以被加入队列中,这样就可以无视掉u的前置,直到条件不能被满足位置。倒着拓扑的意义,实质上是在求满足了u以后剩下最多的点。用n减去这个数字就得到了我们想要的答案。
这个做法的复杂度是O(n^2 \log n)的,在洛谷得开O2才能跑过。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <queue>
#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 20005;

std::vector<int> gra[MAXN];
int deg[MAXN];

inline void addedge(int u, int v) {
    gra[u].push_back(v); deg[v]++;
}

int n, m, lim[MAXN];

struct Node {
    int u, lim;
    inline bool operator<(const Node &rhs) const {
        return lim < rhs.lim;
    }
};

int now[MAXN];
int ans[MAXN];

inline void toposort() {
    std::priority_queue<Node> pq;
    memcpy(now, deg, sizeof(deg));
    for(int i = 1; i <= n; i++) {
        if(!now[i]) pq.push(Node {i, lim[i]});
    }
    int cnt = n;
    while(!pq.empty()) {
        int u = pq.top().u; pq.pop();
        ans[cnt--] = u;
        for(int i = 0; i < gra[u].size(); i++) {
            int v = gra[u][i];
            if(!--now[v]) {
                pq.push(Node {v, lim[v]});
            }
        }
    }
}

inline int toposort1(int uu) {
    std::priority_queue<Node> pq;
    memcpy(now, deg, sizeof(deg));
    now[uu] = n;
    for(int i = 1; i <= n; i++) {
        if(!now[i]) pq.push(Node {i, lim[i]});
    }
    for(int i = n; i; i--) {
        if(pq.empty() || pq.top().lim < i) return i;
        int u = pq.top().u; pq.pop();
        for(int i = 0; i < gra[u].size(); i++) {
            int v = gra[u][i];
            if(!--now[v]) pq.push(Node {v, lim[v]});
        }
    }
}

int main() {
    n = readint(); m = readint();
    for(int i = 1; i <= n; i++) {
        lim[i] = readint();
    }
    for(int i = 1, u, v; i <= m; i++) {
        u = readint(); v = readint();
        addedge(v, u);
    }
    toposort();
    for(int i = 1; i <= n; i++) {
        printf("%d ", ans[i]);
    }
    printf("\n");
    for(int i = 1; i <= n; i++) {
        printf("%d ", toposort1(i));
    }
    return 0;
}
线性基原理及应用

线性基原理及应用

概述

线性基是一类用于方便解决数字的异或问题的方法,可以实现O(n \log(max))维护基集合、O(n)进行其他一些查询操作的复杂度。下面是对线性基及其相关知识的介绍。

线性代数前置知识

向量空间(Vector space)

定义

给定域F,F上的向量空间V是一个集合,其上定义了两种二元运算:

  • 向量加法 + : V × V → V,把V中的两个元素 uv 映射到V中另一个元素,记作 u + v
  • 标量乘法 · : F × V → V,把F中的一个元素 a 和 V 中的一个元素 u 变为V中的另一个元素,记作 a · u

V中的元素称为向量,相对地,F中的元素称为标量。
而集合V公理才构成一个向量空间(对F中的任意元素a、b以及V中的任意元素uvw都成立):

公理说明
向量加法的结合律u + (v + w) = (u + v) + w
向量加法的交换律u + v = v + u
向量加法的单位元存在一个叫做零向量的元素0 ∈ V,使得对任意u ∈ V都满足u + 0 = u
向量加法的逆元素对任意v ∈ V都存在其逆元素−v ∈ V使得v + (−v) = 0
标量乘法与标量的域乘法相容a(bv) = (ab)v
标量乘法的单位元域F存在乘法单位元1满足1v = v
标量乘法对向量加法的分配律a(u + v) = au + av
标量乘法对域加法的分配律(a + b)v = av + bv

前四个公理说明装备了向量加法的V是交换群,余下的四个公理应用于标量乘法。需要注意的是向量之间的加法“+”和标量之间的加法“+”是不一样的,标量与向量之间的标量乘法·和两个标量之间的乘法(域F中自带的乘法)也是不一样的。
简而言之,向量空间是一个F−模。

性质

以下是一些可以从向量空间的公理直接推出的性质:

  • 零向量0是唯一的;
  • 对任意a ∈ F,a · 0 = 0
  • 对任意u ∈ V,0 · u = 0(0是F的加法单位元)。
  • 如果a · u = 0,则要么a = 0,要么u = 0
  • 向量加法的逆向量v是唯一的,记作−vu + (−v)也可以写成uv,两者都是标准的。
  • 对任意u ∈ V,−1 · u = −u.
  • 对任意a ∈ F以及u ∈ V, (−a) · u = −(a · u) = a · (−u).

线性组合(Linear combination)

即形如w = a_1v_1 + a_2v_2 + a_3v_3 + \dots + a_nv_n的w,其中所有a为标量,而v可以为任意类型的项,如向量或标量。

线性无关(Linear independence)

向量空间的一组元素中,若没有向量可用有限个其他向量的线性组合所表示,则称为线性无关,反之称为线性相关。

基(Basis)

定义

给定一个向量空间V,V的一组基\mathfrak{B}是指V里面的可线性生成的V的一个线性无关子集。
\mathfrak{B} = \{ \mathbf{e}_1, \mathbf{e}_2, \dots, \mathbf{e}_n \}是在系数域\mathbb{F}上的向量空间V的有限子集。如果\mathfrak{B}满足以下条件:

  1. 对任意 (\lambda_1, \lambda_2, \dots, \lambda_n) \in \mathbb{F}^n ,如果 \lambda_1\mathbf{e}_1 + \lambda_2\mathbf{e}_2 + \dots + \lambda_n\mathbf{e}_n = 0 ,则必然 \displaystyle \sum_{i=1}^n \lambda_i = 0
  2. 对任意v \in \mathrm{V},可以选择 (\lambda_1, \lambda_2, \dots, \lambda_n) \in \mathbb{F}^n ,使得 v = \lambda_1\mathbf{e}_1 + \lambda_2\mathbf{e}_2 + \dots + \lambda_n\mathbf{e}_n

就说\mathfrak{B}是向量空间V的一组基。

性质

\mathfrak{B}是向量空间V的子集。则\mathfrak{B}是基,当且仅当满足了下列任一条件:

  1. V是\mathfrak{B}的极小生成集,就是说只有\mathfrak{B}能生成V,而它的任何真子集都不能生成全部的向量空间。
  2. \mathfrak{B}是V中线性无关向量的集大集合,就是说\mathfrak{B}在V中是线性无关集合,而且V中没有其他线性无关集合包含它作为真子集。
  3. V中所有向量都可以按唯一的方式表达为\mathfrak{B}中向量的线性组合。如果基是有序的,则在这个线性组合中的系数提供了这个向量关于这个基的坐标。

“线性基”算法

异或意义下的向量空间与基

如果我们定义一个向量空间V,其中F = \{0, 1\},给定一个集合\mathfrak{B}作为基,此时向量实际上是一个01组成的向量,可以看做一个整数的二进制表示,将加法定义为这些对应的整数的异或,数乘不变。我们来研究这样的向量空间的性质。
首先异或运算是满足上述公理的,这个向量空间的V显然是这些基能异或表示出的所有整数。这样,如果我们有一个集合,想求这个集合内的数字异或能表示哪些数字,实际上只需要把这个基\mathfrak{B}求出来就可以了,利用向量空间的性质,我们可以处理一些对异或的询问。

维护基集合

我们考虑使用类似高斯消元的方法,维护一个右上三角矩阵,对于集合中的每个数,插入该三角阵时,首先枚举二进制的每一位,若遇到该位为1且三角阵该行对角线上也为1,则应该用三角阵该行异或该数,反之令三角阵该行为该数(的二进制表示向量),且对上下元素进行一次消元。
C++代码实现如下(默认数据为64位有符号整数):

for(int i = 1; i <= n; i++) {
    for(int j = 63; j >= 0; j--) {
        if(a[i] & (1 << j)) {
            if(mat[j]) {
                a[i] ^= mat[j];
            } else {
                mat[j] = a[i];
                for(int k = j - 1; k >= 0; k--) {
                    if(mat[k] && (mat[j] & (1 << k))) mat[j] ^= mat[k];
                }
                for(int k = j + 1; k <= 63; k++) {
                    if(mat[k] & (1 << j)) mat[k] ^= mat[j];
                }
                break;
            }
        }
    }
}

各种查询操作的实现

是否能异或出某个数

类似插入的思路,用三角阵检验每一位异或掉后是否能将该数消至0。

能表示出的异或最大值

从高位向低位枚举每一位,如果异或上该位的基会使答案更大,则将其异或进答案中。

能表示出的异或最小值

最低位上的基。

能表示出的异或k小值

考虑k的二进制表示,对于为1的位,异或上该位的基即可。

例题:[BJWC2011]元素

参考资料

APIO2018游记

APIO2018游记

谨以此文献&#324 […]


广告

KS的OI模板库开始维护啦~

KS的OI模板库开始维护啦~

最近是省选复习阶段,就想边打板子边整理板子,于是就在GayHub上建了个仓库放模板,也分享给大家~
地址:KSkun/OI-Templates: My templates used in OI. All C++.
不保证这里面的模板常数最佳,只是自己的一种写法罢了。其实很多也是参考了其他人的写法233。
另外可以在这里:知识 | KSkun’s Blog找到很多已经放在博客上的模板哦w


Scroll Up