Baka's Blog

国王奇遇记加强版之再加强版 本题有$O(m^2)$做法，网上很多，这里只有$O(m)$。 题意：求 $$\sum_{i=1}^n i^m m^i$$ 令$F_m(n)$等于这个式子。经过大胆打表看题解，可以知道 $$F_m(n) = m^n P_m(n) - P_m(0)$$ 其中$P_m$是$m$

重返现世 就在这里系统复习一下这类内容好了。 下面式子都是Min求Max，因为貌似用Min求Max比较多，反过来也行。 Min Max容斥： $$\min(S) = \sum_{T \subseteq S} (-1)^{T - 1} \max(T) $$ 广义Min Max容斥： $${\rm

[Jsoi2010]游戏 考场rush 50分，挂成10分了5555 给一个数列，判断是否合法。 注意到只需要二进制后$3$位，$5^k$在$\mod 8$意义下，$1 \rightarrow 5 \rightarrow 1 \rightarrow 5 …$。注意到$1$和$5$的后两位都是$01$

[SCOI2014]舌尖上的方伯伯 本题需要计算几何，把蔬菜看作点处理。 题目中有一个很强的限制：点必须被更近的井灌溉。考虑一种合法的方案，把两组点用一条线划分成两部分。可以发现，因为题目中的限制，一定可以通过一条直线来分割点。 如果可以画出一条分割线，它一个点也没有过，那么可以通过移动与旋转这条线

[HEOI2016/TJOI2016]排序 今日见高一要学线段树分裂，发现自己没写过，大惊，来补了一下这个题。。。 其实这题很水的，只不过线段树分裂当板子用，专门记一下。。。 维护权值线段树，把一段区间都塞进权值线段树当作排好了。 那么用set维护线段树的根，操作一段区间的时候，把涉及到的一段取出来

Number of Components 神仙题。。。 观察可以发现，如果图分成了两个联通块，一定存在$i$，使得$\min_{ j \leq i } A_j > \max_{j > i} A_j$ 我们称这个位置为分界点。那么只需找出有多少分界点。 考虑分界点$A_i = x$，令$ > x $的

烷基计数 加强版 加强版 因为我太菜没有约，只能去学高中数学/化学（ 题意就是求无标号，有根，儿子不超过$3$个的树的数量。 做法还是很神奇的。 做一个简单DP：令$f_x$表示$x$个点的答案： $$f_x = \sum_{i+j+k+1 = x} f_i f_j f_k$$ $\uparrow$

Day -1 什么都不会，还病了，凉了 嗓子疼的厉害，面试要凉 然而热动分析了一下我肯定进不了面试 蛤蛤蛤 Day0 咕 Day1 生病考场难受摸鱼睡觉 正解头疼想不到 暴力不会打凉了 Day2 凉了 yy到的神奇idea能出一个新题，然而就是不能切这些题，凉了 Day3 凉了 本来就菜，状

[APIO2016]划艇 考虑一个大暴力：令$f_{i,j}$表示前$i$个，强制选$i$，选的数是$j$的答案 $$f_{i,j} = \sum_{a < i, b < j} f_{a,b}$$ 值域很大，离散化。为了方便表示，把区间表示为$[l,r)$的形式。 那么定义$f_{i,j}$表示前$

Minimax 之前写过题解，在这里 很好想，不过代码有点难写… Slay the Spire 看错输入啦OAO。以为强化牌可以有小数w。 强化牌$ > 1$，并且都是整数的情况下，出强化一定比出攻击优秀。 分类讨论，有两种情况： 选的强化牌$\geq k - 1$，那么出$k-1$次，然后攻击一