menu ZigZagK的博客

正在努力加载中QAQ

[倍增+线性基]BZOJ4568(Scoi2016)【幸运数字】题解
题目概述给出一棵树,求从 $x$ 到 $y$ ,经过的每个点都可以决定异或还是不异或,求能够得到的最大异或值。解题报告倍增+线性基就好啦,复杂度为 $O(60^2nlog_2n)$ ,这是假的完...
apps BZOJ
local_offer 查看标签
comment 0 条评论
remove_red_eye 28 次访问
阅读全文
[倍增+并查集+贪心]Codeforces1059E【Split the Tree】题解
题目概述把一棵有权值的树分成若干条儿子到祖先的路径,每条路径节点个数不能超过 $L$ ,节点权值和不能超过 $S$ ,问最少分成多少路径。解题报告一个不知道正确性的解法,大佬可以来证明或者证伪一...
apps Codeforces
local_offer 查看标签
comment 0 条评论
remove_red_eye 30 次访问
阅读全文
[贪心+ST表]BZOJ4444(Scoi2015)【国旗计划】题解
题目概述在一个长为 $m$ 的环上有 $n$ 个线段 $(s_i,t_i)$ ,问第 $i$ 个线段必选时至少需要多少线段能够覆盖这个环。解题报告和BZOJ5397差不多,唯一要注意的就是在BZ...
apps BZOJ
local_offer 查看标签
comment 0 条评论
remove_red_eye 49 次访问
阅读全文
[贪心+ST表]BZOJ5397(湖南省队集训2018 Day3)【circular】题解
题目概述在一个长为 $m$ 的环上有 $n$ 个线段 $(s_i,t_i)$ ,在线段不交的情况下最多选择多少个线段?解题报告思路还停留在以前的斯波解法上……然后gg……没环的话可以有三种做法:...
apps BZOJ
local_offer 查看标签
comment 0 条评论
remove_red_eye 49 次访问
阅读全文
[倍增]Codeforces1008E【Guess two numbers】题解
题目概述交互题,让你猜两个 $[1,n]$ 的数 $a,b$ ,每次会回复四种情况之一,如果多条满足随机回复一条合法的:$x=a,y=b$ 。$x<a$ 。$y<b$ 。$x>...
apps Codeforces
local_offer 查看标签
comment 0 条评论
remove_red_eye 40 次访问
阅读全文
[Kruskal重构树+ST表]LOJ2718(NOI2018)【归程】题解
题目概述给出 $n$ 个点 $m$ 条无向边的连通图,每条边有距离和高度,如果高度 $\le$ 水的高度这条边就会被淹没,令 $dis_i$ 表示到达 $1$ 号点的最短路,问从 $x$ 点出发...
apps LOJ
local_offer 查看标签
comment 0 条评论
remove_red_eye 49 次访问
阅读全文
[二分+后缀树+ST表+DFS序+主席树]LOJ2059(TJOI / HEOI2016)【字符串】题解
题目概述给出一个字符串 $S$ ,求 $max\{LCP(S_{[i,j]},S_{[c,d]})|a\le i\le j\le b\}$ 。解题报告先二分答案 $len$ ,然后只需要验证 $...
[ST表]Codeforces1011F【Mars rover】题解
题目概述给出一个逻辑运算树,每个节点有一个逻辑运算或输入框( $0$ 或 $1$ )以及 $0/1/2$ 个儿子(根据符号定)。问每次只把所有输入框中的一个改成相反的( $0\to 1,1\to...
apps Codeforces
local_offer 查看标签
comment 0 条评论
remove_red_eye 58 次访问
阅读全文
[二分+后缀树+ST表]BZOJ5405【platform】题解
题目概述给出一个长度为 $n$ 的字符串和一个长度为 $n$ 的序列 $\{a_n\}$,问有多少个子串 $s_{[L,R]}$ 满足 $Rank(s_{[L,R]})=\sum_{i=L}^{...
apps BZOJ
local_offer 查看标签
comment 0 条评论
remove_red_eye 86 次访问
阅读全文
keyboard_arrow_up