可以将题目转化一下,变成以每个点为右端点的区间长度的期望的立方的和.
 是非常简单的一道题 然鹅我太弱了还WA了两次 ,只要明白二进制和基本的贪心就行了.
 从大到小位的贪心,如果当前确定的初始攻击力与 $M$ 的差能够使第 $i$ 位填上 $1$ 并且该位填上 $1$ 比填 $0$ 严格优秀,那么就贪心的填 $1$ 并将初始攻击力更新,否则直接填 $0$,根据所选的数字用 $trans[i][0/1]$ 更新答案.
 这题也是我学习线性基时在Sengxian的博客上看到的例题.
 由于Sengxian讲的已经非常好了,我就将重点部分贴上他的话吧.
 这题要求某个数第一次出现的下标,也就相当于求它在线性基$\mathfrak{B}$中可以被张成的所有元素的排名,但是实际上应该求的是它在向量空间$V$中可以被张成的所有元素的排名.
 继续阅读
 BZOJ2115 最大异或和路径
 一月 26, 2019 二月 8, 2019 sys_con 评论
 题面
 给定一个 $n(n\le 50000)$ 个点 $m(m\le 10000)$ 条边的无向图,每条边上有一个权值.
 请你求一条从 $1$ 到 $n$ 的路径,使得路径上的边的异或和最大.
 题解
 这题思想还是不错的.
 可以将一条路径拆分成一条$1$到$n$的一条路径边权的异或和与一些环的异或和的异或和.
 因为如果从$1$开始走到一个环的起点,将其遍历一遍之后再走回$1$就相当于获得了这个环的异或和的值.
 于是我们先$dfs$一遍,然后以环的异或和为向量空间,求出线性基$\mathfrak{B}$,然后取初始答案为$dfs$后$1$到$n$的路径异或和,然后在$\mathfrak{B}$上从高位到低位贪心的取,如果当前位置异或上答案能够使答案变大就取,否则不取.
 继续阅读
 BZOJ1565 植物大战僵尸
 一月 26, 2019 二月 8, 2019 sys_con 评论
 题解
 题目链接
 我觉得这题是个不错的网络流题目,应用到了对最大权闭合图的理解.
 引用一位dalao对闭合图的解释:
 闭合图:定义一个有向图 $G = (V , E)$ 的闭合图,是该有向图的一个点集,且该点集的所有出边都还指向该点 集.即闭合图内的任意点的任意后继也一定在闭合图中.更形式化地说,闭合图是这样的一个点集 $V ' \in V$ ,满足对于 $\forall u\in V'$ 引出的 ,必有 $v \in V '$ 成立.按照上面的定义,闭合图是允许超过一个连通块的.
 在许多实际应用中,给出的有向图常常是一个有向无环图( $DAG$ ),闭合图的性质恰好反映了事件间的必要条件的关系:一个事件的发生,它所需要的所有前提也都要发生.一个常见的例子就是制定大学的选课计划,其中一些课程需要以另一些课程为基础,这就是给出了有向无环图.若给所有课程打分,最大权闭合图对应了获益最大或效率最高的选课计划,解决了这个问题,就可以容易地选出一个最合理的选课计划.
 继续阅读
 BZOJ1087 互不侵犯 King
 一月 26, 2019 二月 8, 2019 sys_con 评论
 题面
 在 $N\times N$ 的棋盘里面放 $K$ 个国王$(N\leq 9)$,使他们互不攻击,共有多少种摆放方案.国王能攻击到它上下左右,以及左上
 左下右上右下八个方向上附近的各一个格子,共 $8$ 个格子.
 题解
 就是个简单的状压 $DP$ 题,设状态 $f[i][s][k]$表示dp到第$i$行,这行的状态为$s$,前$i$行共放了$k$个国王的方案数.
 每一行从上一行与所枚举状态不冲突的状态转移就行.
 继续阅读
 BZOJ1053 反素数
 一月 26, 2019 二月 8, 2019 sys_con 评论
 题面
 对于任何正整数 $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 题题解
 一月 25, 2019 二月 8, 2019 sys_con 2 条评论
 网络流24题小结
 我才不会告诉你这是以前写的呢.
 $1.$飞行员配对方案问题
 题目
 英国皇家空军从沦陷国征募了大量外籍飞行员.由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2 名飞行员,其中1 名是英国飞行员,另1名是外籍飞行员.在众多的飞行员中,每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合.如何选择配对飞行的飞行员才能使一次派出最多的飞机.对于给定的外籍飞行员与英国飞行员的配合情况,试设计一个算法找出最佳飞行员配对方案,使皇家空军一次能派出最多的飞机.
 对于给定的外籍飞行员与英国飞行员的配合情况,编程找出一个最佳飞行员配对方案,使皇家空军一次能派出最多的飞机.
 无解输出'No Solution!'