有些奇奇怪怪的题不能保证分析是正确的…… A 啥都不干就好了。 #include <cstdio> int main() { } 话说7秒AC的那个老哥确实离谱，这必是个大预言家（ B 需要通过诡异的手段获得系统时间，这些科技具体可以自己百度，这里提供一种（虽然我也不明白原理）： #include<bits/stdc++.h> #include <chrono> #include <ctime> using namespace std; string getCurrentSystemTime() { std::time_t sec...

大家应该普遍用的是州区划分那题的做法，毕竟这题求一个集合的贡献是很容易的，再套一个子集卷积优化递推就做完了。 这里提供一种不同的做法。假设求出来集合贡献的生成函数为 ，那么答案其实就是子集卷积意义下的 。 update： 被评论区大佬教育了，事实上这个等比数列不需要恰好求到第 项， 以上的不影响答案（并且 也不影响答案），所以可以写成 然后用求逆解决。 有一种常用的集合幂级数转化为形式幂级数的方法，也就是先用子集卷积的做法求一次FMT，设 表示做子集卷积的数组，那么对于一个 ，令 ，我们就可以对 这个形式幂级数求上面这个式子了，求出来再填回 数组内，逆变换回去就是答案。 求上面的式...

A 考虑造一张图，让每个位置 向 的所有倍数连有向边，那么 向 连了一条边的话就表示第 个杯子里的数要比第 个杯子里的数小。 然后事实上，我们只需要考虑图中最长的链就可以了，假如这条链存在合法的放数字方案，那么其他的点一定也存在合法的放数字方案，而最长的链显然是 。 所以只需要判断 是否比 大即可。 B 一个区间的愉悦值其实就是颜色段数。 考虑尺取法，因为颜色段数是有显然的单调性的，当 固定时， 增大，颜色段数一定不会减小。 预处理出 数组， 表示左端点为 时，右端点至少取到哪里，可以使区间内颜色段数不少于 ，每次询问 时，只需要判断 是否不小于 即可。 不过也可以...

考虑枚举山峰的最右边位置 ，那么 ~ 是一个不下降序列， ~ 也是个不下降序列。 考虑一个最大高度为 的不下降序列的方案数，做一下差分，那么有若干个位置不为 ，且这些位置的总和为 ，那么相当于将 分给这 个位置，由于数字都大于 ，所以第一个位置的差分值至少为 ，所以实际上是将 分给 个位置，方案数就是个插板法 。 答案就是： 后面那个部分是求杨辉三角一列的和，套公式得到： 改一下： 考虑化简里面的部分，其实里面就是在求： 这有点像一个卷积的形式，考虑生成函数，设 。 那么上面那个式子求出来的，其实就是 卷 的第 项系数，即 所以 ，代入到上面的式子，得到：，这个就是答案...

A 容易发现每一个数分一段是最优的，因为两个数或起来可能变小而绝不可能变大。 代码如下： #include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; int n; int main() { scanf("%d",&n); long long ans=0; for(int i=1;i<=n;i++){ int x; scan...

题目传送门 题目大意： 一开始箱子里有 个黑球 个白球，每次有 的概率放进去一个黑球，有 的概率放进去一个白球，放完球后再随机拿一个球，问进行 次后箱子里黑球期望个数。 题解 可以注意到每次操作后球数是保持在 不会变的。 令 表示进行 次操作后黑球的期望个数，显然有 。 有四种情况需要考虑，其中两种是放一个黑球拿一个黑球和放一个白球拿一个白球，这两种不会引起黑球数变化所以不需要考虑。 放一个黑球拿一个白球的概率为：，贡献为 ，因为多了一个黑球。 放一个白球拿一个黑球的概率为：，贡献为 ，因为少了一个黑球。 整理得到：。 令 ，那么有 ，展开得到 ，于是就可以 计算答案了。 代...

可怜的比赛又被神仙xgc秒飞了…… T1 考虑枚举断掉哪一条白线，断掉这条白线之后，要使树不联通，就要把子树里延伸出子树外的黑线都删掉，显然有两条及以上时不可能做到，一条时就把这条删掉，没有时就可以随便删一条黑线，用树上差分维护一下即可。 代码如下： #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define maxn 600010 int n,m; struct edge{int y,next;}e[maxn<<1]; int f...

题目传送门 题目大意： 给出一条线段 以及 个点，问从这 个点里面选出两个点，这两个点所在直线穿过 的方案数。 题解 考虑在 同侧的两点 ，假如 穿过 ，那么一定有 在 内或 在 内。 不妨设 在 内，那么一定满足 间一定满足 ，这个您随手画两条线段就能明白。 然后这个东西是个二维偏序问题，可以在 的时间内求出。 假如 在 异侧，那么就满足 和 。 移一下项，就是 和 ，依然是个二维偏序问题。 再说点细节，判断一个点在 哪一侧时，用两向量的叉积模长的正负性来判断（具体参考这里），求角度时，用三条边长度和余弦定理求出该角的 ，再用C++里的 函数求出其角度...

题目传送门 题目大意： 有一张 的网格图，起点为 ，终点为 ，有三种移动方式：1、 选择一个 ，移动到 ，代价为 ；2、移动到 ，代价为 ；3、移动到 ，代价为 ，问能否到达终点，能的话最小代价是多少。 题解 比较显然的是操作 至多用一次，那么看一下用和不用哪个代价更小即可。 假如只看操作 ，那么从 出发能走到 ，最后走回 。这样的路径我们称之为一个循环，那么一个循环的长度就是 ，一共有 个循环。 假如 和 在同一个循环内，那么直接一次操作 就可以了，假如不在的话，就需要用操作 来跳到同一个循环内。 但是可以发现，只用其中一个操作是最优的，不需要同时用到两个操作，因为两个操作同...

推一下柿子就好了： 令 ，代入得： 可以发现，当 时答案肯定为 ，所以只需要考虑 的情况。那么这个东西也像上面预处理出来就可以 回答询问了，代码如下： #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define maxn 1000010 #define mod 199999 int T,n; char s[maxn]; int sum[maxn],prod[maxn],inv2=(mod+1)/2; int main() { ...

A. B-Suffix Array 给出一个字符串，定义一个字符串 ~ 对应的 ~ 满足 ，如果不存在这样的 ，那么 ，现在要求将 的所有后缀按照其对应的 序列的字典序排列。 题解很神，用到一个神仙结论直接切飞，原文为（为了好看些，我自己稍微加了点 LaTeX 元素）： Let The B-Suffix Array is equivalent to the suffix array of 有了这个结论，加一点代码实现细节，就可以 这题。 这里先讲做法，再讲证明。 对于不存在这样的 的 ，我们要让他比其他 都大，设为 ，然后最后再放一个 在 的末尾，最后求出 的...