题意 求一棵最小生成树。 分析 就只是单纯的求一个最小生成树。 代码 #include<bits/stdc++.h> using namespace std; const int N = 510*510; #define LL long long const int inf = 0x3f3f3f3f; int read() { int x = 0,f = 0;char ch = getchar(); while(!isdigit(ch)) {if(ch=='-')f=1;ch = getchar();} while(isdigit(ch)) {x = x *...

题意 从 个位置中选出两两不相邻而且元素尽可能多的方案数。 分析 我们可以考虑递归有序列 这个时候如果我们在末尾添加了新的元素，那么我们就可以在第 或者第 个选择一个。那么我们就有递推式 。在 时。特判一下就好了。最后输出 因为我们对于最后一个元素可以选择 也可以选择 。 代码 #include<bits/stdc++.h> using namespace std; const int N = 201; #define LL long long const int inf = 0x3f3f3f3f; int read() { int x = 0,f = 0...

分析 我们可以对于每一天考虑，如果有一天改了道，那么贪心的选择也应该是最短路，而不是其它的路径。这个还是比较显然的。那么现在考虑一个线性 。令 表示考虑 从第 天的最小代价和。那么转移为 。这里引入了一个 的数组。这里表示从第 天到第 天的合法的最短路。那么我们可以先预处理 总的复杂度为 。最后 的复杂度为 。 代码 #include<bits/stdc++.h> using namespace std; const int N = 201; #define LL long long const int inf = 0x3f3f3f3f; int read(...

分析 很套路的一道题，但是初始值初始时有点搞心态。主要是考虑到 ，很自然的想到用状压去维护。定义 为当前节点在 ，已经过了的节点状态为 。那么我们的转移也比较简单 。那么我们只需要预处理 即可。 代码 #include<bits/stdc++.h> using namespace std; #define LL long long const LL N = 2e5 + 1000,M = 3e5 + 10,inf = 1e18; LL read() { LL x=0,f=0;char ch=getchar(); while(!isdigit(ch)) {...

题意 给你 两个整数，要求求出约瑟夫问题中最后一个人是谁。 分析 总所周知，约瑟夫问题有模拟 ，线性 。这里解释一种 的解决方法。考虑到我们每次走 个删一个，那么在一圈以内我们可以删掉 个。我们可以模拟这个过程递归求解。由于每次递归问题规模变为 。通过归纳验证时间复杂度大概是 代码 #include<bits/stdc++.h> using namespace std; int read(){ int x=0,f=0;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar()...

分析 我们对于每个子树的答案是可以预先知道的 ，那么如果 那么一定无解。之后我们可以直接遍历整个树得到 的节点。那么当这样的节点个数超过 的时候，这个树就是合法的，输出两个非树根的节点就可以了。那么总的复杂度为 。 代码 #include<bits/stdc++.h> using namespace std; int read() {int x=0,f=0;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();} while(isdigit(ch)){x=x*10+ch-'0'...

关于多项式的操作，我会慢慢补充的。 多项式求ln 前置公式， 和 。 前置知识，多项式点值表示，多项式求逆。 给你一个多项式 ，要求求出一个多项式满足 。考虑积分和求导。我们考虑 是 和 复合。那么 那么 ，左右同时积分 。那么就做完了。 代码 #include<bits/stdc++.h> using namespace std; const int N = 4e6 + 100,P = 998244353; int limit,r[N],L; int ksm(int a,int b) {int x=1;for(;b;b>>=1,a=1LL*...

分析 我们主要考虑如何处理 的操作又重新做一次，这个我们考虑区间加，定义 为第 次操作要执行的次数。那么这个我们可以通过差分做到。最后处理区间加。这个一样可以用差分来做，那么最后的复杂度为 。 差分，我们定义数组 ，如果原值为 。那么满足 。那么给 全部 等同于 。这样我们对于区间加就可以直接修改两个点来操作了。 代码 #include<bits/stdc++.h> using namespace std; int read() { int x=0,f=0;char ch=getchar(); while(!isdigit(ch)) {if...

rp++，保我过初赛

必要公式 首先我们知道 根据第二类斯特林数和贝尔数的定义很容易证明。 第二类斯特林数的通项公式，可以根据容斥定理枚举空的盒子得到。 我们知道 这个是 在 处的展开。而 ，因此 得证。 这个是最简单的二项式展开了。不多说明。 推导 那么现在 。是不是很神奇，神奇就点个赞再走吧。

分析 我们可以考虑一个合法答案 ，那么 ，则 也是一个合法答案。那么这个满足单调性，我们可以考虑二分，如何判断 是否是一个合法解。我们考虑贪心，从左向右考虑，每次考虑最靠左而且没有被现在的区间覆盖的点。对于这个点也可以二分，好像直接做也没有问题。那么最后判断是否 就可以了。 代码中所有二分的地方，我都换成了倍增。感觉还是非常快的。 代码 #include<bits/stdc++.h> using namespace std; const int N = 5e4 + 10000,inf = 0x3f3f3f3f; int a[N],n,K,Log[N]; int rea...