模式字符串 今天考了一道类似点分治的模板题，结果没做出来。 正解就是对每一个分治中心处理出前后缀的个数，统计的时候拼接一下就行了。 #include<iostream> #include<cstdio> #define ULL unsigned long long using namespace std; int T, n, m, tot, x, y, num, root; long long ans; const int N = 1000010, zhi = 13121; int head[N], siz[N], mx[N], vis[N], f[N], g[N],...

T1 \(n \le 20 ,m \le n!\) 这道题可以证明一定有解，我们每次找出 比我们要凑成的数小且是n!的约数 里最大的数就可以了。跑得飞快~ #include<iostream> #include<cstring> #include<cstdio> #define LL long long using namespace std; LL n, m, jc, tot, js; const LL N = 3700010, inf = 0x3f3f3f3f3f3f3f3f; LL w[N], cnt[N], ans[N]; inline int r...

T1 \(n \le 5 \times 10^5 , a_i \le 10^8\) 今天就临时测了这么一道题。 考场上用单调栈水了70分，结果那30分还是因为少取模（捂脸） 正解是分治，先计算左半部分，再计算右半部分，跨区间的：在左区间用一个指针从右向左枚举，右边用一个j,k, 表示能在左区间取到最大值和最小值的最大的区间右端点，再大力讨论维护一大堆数组就OK了。 挂一下sunny_r的链接 单调站\(O(n*玄学)\) #include<iostream> #include<cstdio> #define LL long long using namespace s...

T1 01分数规划 很明显我们需要的区间最大值和最小值在区间两端，因为有L的限制，所以我们可以先做一遍长度为L的滑动窗口。 问题判定的转化,设我们二分的值是v： \(\displaystyle \frac{A[r]-A[l]}{r-l+k} > v\) \(\displaystyle (A[r]-rv)-(A[l]-lv) > kv\) 再用一个单调队列维护一下就好了。 #include <iostream> #include <cstdio> #define LL long long #define DB double using namespace s...

吉爷爷可真是一位神仙... 看到题目毫无思路，发现题目限制和条件较多，让我们先坐下来数一数条件，推一推结论。 机器人行走要求： 1.机器人只能向右或向下。 2.机器人走到边界后会回到行/列坐标为1的地方。 3.要求机器人走过每一个点且仅走一次。 4.是先规定好了机器人的每一种行走路线，再放的障碍物。 1.从左下到右上直线上机器人的行走方向相同。 这是最基本的一条结论，我们观察一下对于 \((i+1,j)\) 和 \((i,j+1)\) 这两个点，倘若在这两个点走的方向不一样，那么 \((i+1,j+1)\) 这个点要么走不到，要么会走两遍，都不符合题意。 2.机器人行动的...

恭贺 treAKer 在 毒瘤之神的考验 一题中取得 rank1 的好成绩，成为新一届 毒瘤之神 ! ...... 结果今天就考了 treAKer 的毒瘤题... T1 考场上看到1e6就想O(n)的做法，结果失败了... 正解思路很神奇，就是先对物品按照a来排序，询问按照m来排序，用双指针一起扫，同时维护\(f_i\) 当物品的和为i时 在所有的方案中，最小的b最大 的方案中的 b值。判一下\(f_i\)和m+s的大小关系即可。 #include<algorithm> #include<cstring> #include<iostream> #incl...

T1 数据范围很合适.. 第一档就是暴力枚举 第二档就是数位DP 第三档就是矩阵乘法 丢一下学长的博客 #include<iostream> #include<cstring> #include<cstdio> #define LL long long using namespace std; LL n; const int mod = 1e9 + 7; struct ju { LL c[4][4]; friend ju operator *(const ju &a, const ju &b) { ...

1.正序删边可以离线反向操作，变成加边。 2.有相同的变量尽量挪到一边。 \(\displaystyle \sum_{i=1}^md_i=2m-2\) \(\displaystyle \sum{(d_i-2)}=-2\) 3.恰好变为至少，然后容斥原理。 4.看到问题想一想能不能二分答案。 5.倘若题目告诉你“随机”数据的生成方式，它就不是真随机了。

设\(d(x)\)为\(x\)的约数个数\(\displaystyle d(ij)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]\) 设\(\sigma_1(i)\)表示i的约数和，那么\(\displaystyle \sigma_1(ij)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]\frac{xj}{y}\) 简单多面体的顶点数 \(V\) 、面数 \(F\) 及棱数 \(E\) 间的关系:\(F-E+V=2\) 将二维平面看作平面图时，注意到平面图包含无限面。 \(\displaystyle \left \lf...

T1圆圈游戏 暴力DP有60分，设包含圆i的最小的圆是fa[i]，那没最终会的得到一棵树，对于一棵子树，选了根节点就不能选子树内其它点，f[i]=max(w[i],\(\sum f[son]\)). 瓶颈就在怎么建图，因为圆不相交相切，所以扫描线的时候相对位置不会发生改变，用set维护一下就好啦。 #include<algorithm> #include<iostream> #include<cmath> #include<queue> #include<cstdio> #include<set> using names...

持续更新中 生成函数 二项式系数(组合数) \(\displaystyle C_n^m=\frac{n!}{m!(n-m)!}\) \(n \in R,m \in N\)时广义二项式定理系数 \(\displaystyle C_n^m=\frac{n(n-1)...(n-m+1)}{m!}\) 广义二项式定理(a 不一定是整数) \(\displaystyle (1+x)^a=\sum_{i=0}^{\infty}C_a^ix^i\) 关于二项式的恒等式 \(C_n^m=C_n^{n-m}\) 多项式求导 \(\displaystyle (x^a)'=ax^{a-1}\)...

T1摆棋子 看到这么多的限制，第一直觉就是网络流，最小费用最大流不能做，因为把棋子代价看成1后最大流的条件并不好满足。 注意到每一行每一列都有一个最小限制，对应到网络流上就是流的下界，整体跑一个有下界的最小流就可以了。 #include<iostream> #include<cstring> #include<cstdio> #include<queue> #define LL long long #define DB double using namespace std; int n, m, k, x, y, tot = 1, S, T, S...

\(NTT\) 神仙题，强烈建议先自己推一推式子再看题解,顺便orz memset0。 题面没看太懂，大概意思就是求有n个不同的小球，放进 \(1\)、\(2\)、$……n $ 个不同的盒子，不可空的情况下，期望用了几个盒子。 按照套路，我们应该分别求出总的方案数\(g_i\)和总共用的盒子数 \(f_i\) ,答案就是 \(f_i\times g_i^{-1}\)。 我们先来求总的方案数，设 \(S\) 是第二类斯特林数，则 \(\displaystyle g_n=\sum_{i=1}^nS[n][i]\times i!\) 就是我们枚举用了几个盒子，在乘上 \(i!\) 将盒子看...

又是一道神仙题orz 我们先化一化式子。 \(\displaystyle Ans[n]=\sum_{i=0}^n\sum_{j=0}^iS(i,j)\times 2^j\times (j!)\) 看着\(\displaystyle \sum_{j=0}^i\)很不爽，因为当\(j>i\)时，\(S(i,j)=0\),所以 \(\displaystyle Ans[n]=\sum_{i=0}^n\sum_{j=0}^nS(i,j)\times 2^j\times (j!)\) 看着\(S(i,j)\)很不爽，我们先把它单独拎出来。 $\displaystyle Ans[n]=\s...