BZOJ4318 OSU!

题意

给定一个序列,每个位置为 $\texttt{o}$ 的几率为 $p_i$ ,为 $\texttt{x}$ 的几率为 $1 – p_i$ 。对于一个 $\texttt{ox}$ 序列,连续 $x$ 长度的 $\texttt{o}$ 会得到 $x^3$ 的收益,问最终得到的 $\texttt{ox}$ 序列的期望收益是多少?

题解

这题和20181106的考试题很像( $x^2$ 变成了$x^3$),属于升级版,和BZOJ3450有一定联系。
可以将题目转化一下,变成以每个点为右端点的区间长度的期望的立方的和。
设 $g[i]$ 为以 $i$ 位置为右端点的的期望的立方的和。
继续阅读

BZOJ3668 起床困难综合症

题解

题目链接

是非常简单的一道题 然鹅我太弱了还WA了两次 ,只要明白二进制和基本的贪心就行了。

首先对于某个位 $i$ ,先预处理出这一位原来在攻击力中取 $0/1$ 时经过 $n$ 扇门后分别变成 $0/1$ ,记作 $trans[i][0/1]$

我们知道对于某一位 $j$ 肯定有 $(1 << j) > \sum_{k=0}^{j – 1} (1 << k)$ ,那么就可以考虑用贪心取最优解。

从大到小位的贪心,如果当前确定的初始攻击力与 $M$ 的差能够使第 $i$ 位填上 $1$ 并且该位填上 $1$ 比填 $0$ 严格优秀,那么就贪心的填 $1$ 并将初始攻击力更新,否则直接填 $0$,根据所选的数字用 $trans[i][0/1]$ 更新答案。
继续阅读

BZOJ2844 albus 就是要第一个出场

题意

给定 $n(n \le 10000)$个数 $a_1, a_2, \ldots, a_n$ 以及一个数 $Q$。将 $a_1, a_2, \ldots, a_n$ 的所有子集(可以为空)的异或值从小到大排序得到序列 $B$,请问 $Q$ 在 $B$ 中第一次出现的下标是多少?保证 $Q$ 在 $B$ 中出现。

题解

这题也是我学习线性基时在Sengxian的博客上看到的例题。

由于Sengxian讲的已经非常好了,我就将重点部分贴上他的话吧。

这题要求某个数第一次出现的下标,也就相当于求它在线性基$\mathfrak{B}$中可以被张成的所有元素的排名,但是实际上应该求的是它在向量空间$V$中可以被张成的所有元素的排名。
继续阅读

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
  • 生成长文章的目录:文章内索引
    没了