状压dp、容斥 首先我们要知道树的一个重要的特性：对于树来说，他的路径总和为: 刚开始我想换根dp。。。。还以为自己想到了一个新的方法。。。。打算先以1为根处理以每个节点为起点，到其子树中找路径能找到的路径和然后再通过找子结点和父节点的关系从而换根 但是，这里的路径，只是通过找子结点和父节点的关系我们是无法换根的！！！与整个路径的状态有关！！那么就是状压了！ 我们可以枚举我们要选的颜色一共也不过 种然后我们统计：路径中的颜色种类包含在这个状态里的数量 注意！我们这里不是统计正好颜色数就是这么多的路径数！比如我们枚举的颜色为 1 2 3那么只包含颜色 1 2 的路径也在我们的统计范围！！ ...

C:\Program Files\Microsoft SQL Server\MSSQL.2\MSSQL\DATA school.mdf

状压dp 思路很明显，但是实现起来对我来说真难。 这里我就解读一下代码 首先我们定义了一个dp数组dp[i][j][k]表示，第i个状态,再第j行，之后要放置k个国王从第一行开始遍历 我们定义状态为，如果该位为1那么这一行中，我们在这里放置了一个国王否则我们不放置国王 我们可以先跑一下，预先把所有满足条件的状态都筛选出来即，01间隔的二进制串，筛选函数pre()，判断非常简单我们将筛选过的状态存在s数组里 然后下一步，我们开始枚举状态我们从第一行开始枚举，然后枚举这一行的状态，枚举这一行之后要放置的国王 然后我们要进行状态转移了！！我们同样开始枚举所有的状态，然后判断两个状态是否冲突。判断冲突...

线段树 线段树是我的弱项我们来看这一题：要维护值得乘积对 abc如果a发生变化，那么我们要是知道b*c则只要加上a得增量就好了 基于着中国想法，我们使用了线段树。 我们一共开了7棵线段树！先开三棵a,b,c在我们的线段树所开的数组中记录的点seg[x]是，从点x到目前边界的 极差线段树维护这个极差的和而这个边界我们在不断地向后推，从而极差发生变化，用线段树维护。 同时，在维护了a,b,c每一次推边界后，以当前边界为右端点的区间的极差和后。我们可以利用刚开始的思想维护出ab,ac,bc,abc的值满足结合律，我们当然可以利用线段树！ 而，如何在将边界向后推的过程中，维护变化的极差呢？这里就要用到...

单调栈 单调栈接触挺久了，一直没有仔细研究。昨天模拟赛，一道单调栈没有看出来。现在认真学学！ 对于这道题，因为它是连续子序列所以我们可以统计每一个值的贡献即，(作为最大值的次数-作为最小值的次数)*高度 如何求作为最大值的次数？我们可以求解，向左走第一个比他大的索引，向右走第一个比他大的索引那么，在这个区间内。他就是最大值！利用单调栈可以很容易地统计出来！ 然后我们可以用同样的方法统计出最小值的次数 但是哇，我们这样有一个bug就是，这个区间内有重复的数，我们统计时可能会有区间被重复选取！那么该怎么办呢？ 学到了！我们可以在单调栈判断时，对于左边我们取等，对于右边我们不取等！真的巧妙！ #in...

本篇不适合当题解看 水位线技术 我们先利用推导dp公式，注意：这里因为dp公式的特殊性我们决定从前向后主动更新(类似dij)然后我们会注意到这个dp很是特殊，她似乎整体都上升一个相同的数。我们可以利用水位线思想：我们不要一个个地上升数，我们下降水位线不就好了吗？然后单独处理一些特殊的点。如此，复杂度直接降低了一个维度 #include<iostream> #include<algorithm> #include<map> #include<vector> using namespace std; typedef long long ll; typ...

组合数学、容斥原理 真的太毒了，今天的模拟什么都没有做出来 这一题刚开始就到想了，最后也没有想出来 首先如果没有那个n的限制的话，就是简单的隔板法，组合数学。但是有了n的限制就一下子麻烦了起来。其实当时隐隐约约的感觉到了，只不过没有方向坚定地走下去。我们在利用隔板法计算出来之后，在减去多余的。这是基本的想法。问题就在于如何计算多余的？这里利用了容斥的思想。我们可以，先从k种抽出n个然后，在对k-n个隔板后，找一个放入n个那么这就是至少有一个数超过n的可能同样我们可以算出至少又两个数超过n的可能。。。。。因为是相互包含的关系，所以容斥原理。 但是我给出了疑惑，其实我认为之前所算出来的并不是至少i...

topsort 被拓扑排序给安排了这道题让我们给边加方向让，最终的图没有环。其实没有环就意味着他是一个DAG所以他一定有一个拓扑序这点我是想到了但是，思维能力不够。我做响了错误的方向。把这道题做的极其困难。我们可以先并不关心没有方向的边。我们先处理有方向的边。将有方向的边建一个拓扑序。然后让我方向的边遵照这个拓扑序进行方向的选定就好了！！！！真的是太妙了。因为我不熟悉拓扑排序所以没有想到。虽说是套路题，但是我觉得是好题！！ #include<iostream> #include<algorithm> #include<vector> #include<...

暴力 暴力的优美！！！！！！！一针见血的解法，我们要洞悉复杂度！！！ #include<iostream> using namespace std; int main(){ int t;cin>>t; while(t--){ int a,b,c; cin>>a>>b>>c; int a1,a2,a3; int ans = 1e5; for (int i=1;i<=10000;++i) for (int j=i;...

打表找规律 对于数学题，打表找规律还是非常有用的！！！！！！ #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int max_n= 5e5+100; const ll mod = 998244353; ll POW(int a,int p){ ll base = a; ll ans=1; while (p){ if (p&1)ans = ans*base%mod; base = (...

筛法 我发现了，这种题还是挺容易卡时间的要多用筛法防止超时这题就是一个简单的质因数分解。如果当前的数有至少两个质因数的话那么就ok否则就no #include<iostream> #include<algorithm> using namespace std; typedef pair<int,int> pii; const int max_n = 5e5+100; const int max_m = 1e7+100; pii ans[max_n]; int n; int isprime[max_m]; int prime[max_m]; int main...

醉了 这题在能力范围内。 思路、方向都想对了。但是最后统计答案时的细节没想好，醉了！！！一直卡在最后统计答案上面。该说是没有手感吗？该说是生疏吗？艹！！本来能上不少分的！！艹！！ 来说思路吧！！我数论不会，所以这题在我看到gcd、lcm的时候心里一凉。并没有打算用数学的方法去解。我是达标规律做的。我打了1到300所有数，在1到300范围内的临近数们。这一打表，我就找到规律了。对于数num = a * b^2 令b最大他等价于 a所以，我们最初都可以进行数的简化又然后，在进行合并的过程中。对于一群同类数进行合并时，我们可以看到最终会变为a^k * c^2c = b1b2b3......如果k为...

不要用memset进行二维数组的初始化，会出现严重的错误！！！！！！！！！！！！！！！！！！！！！！！！！ 话说，不要用memset进行初始化了8 收获：floyd求解最小环！！！！ get! #include<iostream> #include<algorithm> #include<vector> #include<cstring> using namespace std; #define mem(a,n,val) for(int i=0;i<=n;++i)for(int j=0;j<=n;++j)a[i][j]=val; ty...

待会儿更新