BZOJ2115 最大异或和路径

题面

给定一个 $n(n\le 50000)$ 个点 $m(m\le 10000)$ 条边的无向图,每条边上有一个权值。

请你求一条从 $1$ 到 $n$ 的路径,使得路径上的边的异或和最大。

题解

这题思想还是不错的。

可以将一条路径拆分成一条$1$到$n$的一条路径边权的异或和与一些环的异或和的异或和。

因为如果从$1$开始走到一个环的起点,将其遍历一遍之后再走回$1$就相当于获得了这个环的异或和的值。

于是我们先$dfs$一遍,然后以环的异或和为向量空间,求出线性基$\mathfrak{B}$,然后取初始答案为$dfs$后$1$到$n$的路径异或和,然后在$\mathfrak{B}$上从高位到低位贪心的取,如果当前位置异或上答案能够使答案变大就取,否则不取。
继续阅读

BZOJ1565 植物大战僵尸

题解

题目链接

我觉得这题是个不错的网络流题目,应用到了对最大权闭合图的理解。

引用一位dalao对闭合图的解释:

闭合图:定义一个有向图 $G = (V , E)$ 的闭合图,是该有向图的一个点集,且该点集的所有出边都还指向该点 集。即闭合图内的任意点的任意后继也一定在闭合图中。更形式化地说,闭合图是这样的一个点集 $V ‘ \in V$ ,满足对于 $\forall u\in V’$ 引出的 ,必有 $v \in V ‘$ 成立。按照上面的定义,闭合图是允许超过一个连通块的。
在许多实际应用中,给出的有向图常常是一个有向无环图( $DAG$ ),闭合图的性质恰好反映了事件间的必要条件的关系:一个事件的发生,它所需要的所有前提也都要发生。一个常见的例子就是制定大学的选课计划,其中一些课程需要以另一些课程为基础,这就是给出了有向无环图。若给所有课程打分,最大权闭合图对应了获益最大或效率最高的选课计划,解决了这个问题,就可以容易地选出一个最合理的选课计划。
继续阅读

BZOJ1087 互不侵犯 King

题面

在 $N\times N​$ 的棋盘里面放 $K​$ 个国王$(N\leq 9)​$,使他们互不攻击,共有多少种摆放方案。国王能攻击到它上下左右,以及左上
左下右上右下八个方向上附近的各一个格子,共 $8$ 个格子。

题解

就是个简单的状压 $DP$ 题,设状态 $f[i][s][k]$表示dp到第$i$行,这行的状态为$s$,前$i$行共放了$k$个国王的方案数。

每一行从上一行与所枚举状态不冲突的状态转移就行。
继续阅读

BZOJ1053 反素数

题面

对于任何正整数 $x$,其约数的个数记作 $g(x)$ 。例如 $g(1)=1、g(6)=4$ 。如果某个正整数 $x$ 满足:$g(x)>g(i) (0<i<x)$ ,则称 $x$ 为反质数。例如,整数 $1,2,4,6$ 等都是反质数。现在给定一个数 $N$ ,你能求出不超过 $N$ 的最大的反质数么?

题解

之前听过这是个打表,结果一直想直接打表出所有反素数,后来发现不行,还是要用数学方法解决。
继续阅读

网络流 24 题题解

网络流24题小结

我才不会告诉你这是以前写的呢。

$1.$飞行员配对方案问题

题目

英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2 名飞行员,其中1 名是英国飞行员,另1名是外籍飞行员。在众多的飞行员中,每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况,试设计一个算法找出最佳飞行员配对方案,使皇家空军一次能派出最多的飞机。

对于给定的外籍飞行员与英国飞行员的配合情况,编程找出一个最佳飞行员配对方案,使皇家空军一次能派出最多的飞机。

无解输出’No Solution!’
继续阅读

Hello World!

Hello World

sys_con 用 byethost 的免费虚拟主机搭建的博客,使用 wordpress 驱动
域名是在 freenom 上找的免费域名
网站访问可能会比较慢因为都是免费的
测试一下插件嘻嘻
$$ e^x=\sum_{n\geq 0} \frac{x^n}{n!} $$

#include <cstdio> 

int main () {
    printf("Hello World!");
    return 0;
}

使用的插件

  • markdown 编辑:WP HyperMD
  • 更改文章顺序: Post Types Order
  • 生成长文章的目录:文章内索引
    没了