menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[Min-Max容斥+树上高斯消元]LOJ2542(PKUWC2018)【随机游走】题解
题目概述有一棵树,刚开始你在 $X​$ ,每次随机走到相邻的点。有 $q​$ 个询问,每次询问给出一些点,求把这些点至少经过一次的期望时间。解题报告不难想到Min-Max容斥,令 $min(S)...
[贪心]NOIP2018Day2【旅行】题解
解题报告树的情况直接贪心做,基环树枚举环上的边断开然后贪心做。乱优化代码害人不浅,少 $20$ 分送我爆炸。测评鸭上面有 $O(n)$ 加强版,大佬们可以去切啊QAQ。示例程序#include&...
apps LOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[扫描线+线段树]LOJ6276【果树】题解
题目概述一棵 $n$ 个节点的树,每个节点有颜色,求路径上没有相同颜色的路径个数,每种颜色出现次数不超过 $20$ 。解题报告填联赛前的坑,模拟考的时候我疯狂想容斥,我都想到用正解做链了却没想到...
apps LOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[LCT+泰勒展开]LOJ2289(THUWC 2017)【在美妙的数学王国中畅游】题解
题目概述有 $n$ 个点,每个点是一个函数:$sin(ax+b),e^{ax+b},ax+b$ 。有 $4$ 种操作:1.连接 $x,y$ 。2.断开 $x,y$ 。3.修改 $x$ 点函数。4...
apps LOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[线段树+复杂度分析]LOJ6507(雅礼集训 2018 Day7)【A】题解
题目概述区间与,区间或,区间最小值。解题报告完了我连吉利线段树裸题都不会做。这种题一般都是考虑差分数组来分析复杂度,如果 $[L,R]$ 与(或)上 $x$ ,那么 $x$ 为 $0(1)$ 的...
[树形DP]LOJ2485(CEOI2017)【Chase】题解
题目概述有 $n$ 个点的树,每个点上有 $p_i$ 只咕咕咕。从任意点出发开始走,有 $k$ 次放面包的机会,放下面包后相邻点的咕咕咕就会凑到该点,问先走一遍之后再走一遍遇到的咕咕咕个数之差最...
apps LOJ
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$ ,然后只需要验证 $...
[非互质CRT]LOJ2721(NOI2018)【屠龙勇士】题解
题目概述求方程组 $atk_ix\equiv a_i\ (mod\ m_i)$ 最小的解。示例程序如果把系数去掉就是裸的非互质CRT,根据同余方程的同除性,我们可以同除 $r=(atk_i,m_...
apps LOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[霍尔定理+线段树]LOJ6062(2017 山东一轮集训 Day2)【Pair】题解
题目概述两个数 $x,y​$ 可以匹配定义为 $x+y\ge H​$ 。现在给出 $\{a_n\}​$ 和 $\{b_m\}​$ ,问 $\{a_n\}​$ 有多少个连续子序列满足:存在一种方法...
apps LOJ
local_offer 查看标签
comment 0 条评论
阅读全文
keyboard_arrow_up