menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[指数型生成函数+倍增+NTT]BZOJ5381【or】题解
题目概述求多少序列 $\{A_n\},A_i\in[1,2^K)$ 满足 $B_1=A_1,B_i=B_{i-1}\ or\ A_i$ 的序列 $\{B_n\}$ 严格递增。解题报告不难转化成这...
[第一类斯特林数+倍增+NTT]Codeforces960G【Bandit Blues】题解
题目概述求有多少 $n$ 的排列满足从左边会更新 $A$ 次最大值,从右边会更新 $B$ 次最大值。解题报告第一类斯特林数:$s(n,k)$ 表示把 $n$ 个数分成 $k$ 个圆排列的方案数。...
[倍增+线性基]BZOJ4568(Scoi2016)【幸运数字】题解
题目概述给出一棵树,求从 $x$ 到 $y$ ,经过的每个点都可以决定异或还是不异或,求能够得到的最大异或值。解题报告倍增+线性基就好啦,复杂度为 $O(60^2nlog_2n)$ ,这是假的完...
apps BZOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[倍增+并查集+贪心]Codeforces1059E【Split the Tree】题解
题目概述把一棵有权值的树分成若干条儿子到祖先的路径,每条路径节点个数不能超过 $L$ ,节点权值和不能超过 $S$ ,问最少分成多少路径。解题报告一个不知道正确性的解法,大佬可以来证明或者证伪一...
apps Codeforces
local_offer 查看标签
comment 0 条评论
阅读全文
[贪心+ST表]BZOJ4444(Scoi2015)【国旗计划】题解
题目概述在一个长为 $m$ 的环上有 $n$ 个线段 $(s_i,t_i)$ ,问第 $i$ 个线段必选时至少需要多少线段能够覆盖这个环。解题报告和BZOJ5397差不多,唯一要注意的就是在BZ...
apps BZOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[贪心+ST表]BZOJ5397(湖南省队集训2018 Day3)【circular】题解
题目概述在一个长为 $m$ 的环上有 $n$ 个线段 $(s_i,t_i)$ ,在线段不交的情况下最多选择多少个线段?解题报告思路还停留在以前的斯波解法上……然后gg……没环的话可以有三种做法:...
apps BZOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[倍增]Codeforces1008E【Guess two numbers】题解
题目概述交互题,让你猜两个 $[1,n]$ 的数 $a,b$ ,每次会回复四种情况之一,如果多条满足随机回复一条合法的:$x=a,y=b$ 。$x<a$ 。$y<b$ 。$x>...
apps Codeforces
local_offer 查看标签
comment 0 条评论
阅读全文
[Kruskal重构树+ST表]LOJ2718(NOI2018)【归程】题解
题目概述给出 $n$ 个点 $m$ 条无向边的连通图,每条边有距离和高度,如果高度 $\le$ 水的高度这条边就会被淹没,令 $dis_i$ 表示到达 $1$ 号点的最短路,问从 $x$ 点出发...
apps LOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[二分+后缀树+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 条评论
阅读全文
keyboard_arrow_up