Miku 还是莫队板子 啥叫互不相同？区间内不同的元素的数量==区间元素数 #include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<cmath> using namespace s…

Miku 仍然是要优化的，但是输出方案是非常恶心的 一维爆炸，以下为二进制优化做法 关键是如果最后到着找方案的话，就比如说样例 5的最少方法就是一个5，但是因为dp的顺序是逆序。会把10指向5，然后5指向0 、？？，但是只有一个啊。所以不能倒序 #include<iostream> #include<cstdio> #inc…

Miku [理论]（https://www.cnblogs.com/WAMonster/p/10118934.html） 感谢这位神仙帮助我深刻理解了莫队 #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #…

Miku 简单版就是个单纯的模板 ac自动机是啥，就是一个加了类似于kmp的next数组的tire树 #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #inclu…

Miku 字典树部分非常好解决，只要把最后每个单词结尾处记录下翻译成了啥 但是输出很麻烦，要处理空格，回车，换行和标点符号 不过有string在，还行 #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #…

Miku 字典树模板题级别 字典树是啥，就是一颗从根走到底就找到了一个单词的树 非常好理解 #include #include #include #include #include using namespace std; int n; string s; struct t{ int ne[28]; int cnt; }tr[400001]; in…

Miku 多重背包板子 纯多重背包好想>$dp[i]=max{dp[i-kw[j]]+kv[j]}$ 但是要优化。这里采用二进制优化。 二进制优化是啥呢，假如i物品有13个 13可以拆成1+2+4+6，然后用这四个，就可以表示除1-13所有可能了 这样就把多重背包优化成了01背包 #include<iostream> #inclu…

Miku 规律：假如只有一个栈，那么如果原序列存在三个数x<y<Z&&$V_y>V_x>V_z$ 那么就不可能排序成功，但是这里有两个栈，那么就应该把原序列分成两部分 两部分？二分图。 把不能在一起的点连边，进行二分图染色。 如果成功，就意味着存在&&两个栈的成员搞定了 反之不存在 #incl…

Miku 显然思路是倒着扫，倒着染。 然而这样有一个问题，这样做，那么对于已经染色的区间是不需要重新染色的， 但是遍历的时候可以找到已染色区间的一个端点，另一个在哪？ 用并查集解决 fa[x]为x右边第一个没染色的端点 然后就O（N）解决了 提示：n+1个点也要初始化，因为只要n点被染色，那么一定指向n+1，如果不初始化 fa[n+1]=0，那么就…

Miku 莫名其妙每一天 如果一天满足和前面的连续一些天可能不下降，那么它的最大气温一定不小于之前序列的每一天的最小气温 然后这东西用单调队列维护 再开一个队列维护这一段序列的堆头 就Ac了 #include<iostream> #include<cstdio> #include<algorithm> #incl…