链接 这道题很容易想到要用并查集,我们只需要用逆向思维 但是,由于数据很大,对于cnt(需要的空投数)不能每次都计数,而是需要实时更新 我们不妨思考,当两个城市合并时,如果二者的根节点不同,那么我们就检查这两个城市的连通块数量,如果大于等于d,cnt就减一,合并完再加上即可 #include<bits/stdc++.h> using namespace std; #define ll long long vector<ll>tree; int n,m,x,d; int cnt=0; struct node{ ll h; int idx; bool operator&lt...

链接 嗯,不好写 这题思路与上一个帖子的思路有一点像(也许也不像?) 我们可以先计算总的价值,然后计算收集完所有的彩蛋损失的最小价值,最后一减去除以1000.0就是答案了 我们将所有的彩蛋按x的大小排个序 定义dp[l][r][0]和dp[l][r][1]表示收集完区间[l,r]且在最左端或者最右端的彩蛋损失的最小价值,接着只有两种可能 1:往左走dp[l-1][r][0] 2:忘右走dp[l][r+1][1] 中途损失的价值,就是除去[l,r]的速度乘上所花的时间,用前缀和计算 遍历每一个区间就行 记得开long long #include<bits/stdc++.h> usin...

链接 首先先定义dp[i][j] (表示前i个合并后值为j的最小翻转次数) 我们先计算每一组的差值d[i] 显然,对于每一个已经存在的dp[i][j],对于下一个i也就是dp[i+1],有两种可能 不翻转:dp[i+1][j+d[i]]=dp[i][j] 翻转:dp[i+1][j-d[i]]=dp[i][j]+1 这样相当于遍历所有可能,理论上时间复杂度会非常大,但是由于范围的限制和重叠,时间复杂度也就限制在了O(n²),可以接受 #include<bits/stdc++.h> using namespace std; const int MAXN=1005; const int ...

链接 设dp[i][j]为i-j的最小合并值,显然,它肯定等于它的所有互补的子数组的最小合并值加上这一段区间的和 也就是dp[i][j]=min(dp[i][k]+dp[k+1][j]+sum(i,j)) 由于数据量较小,三重循环也没问题 #include<iostream> #include<vector> using namespace std; int main() { int n; cin >> n; vector<int>nums(2 * n + 1, 0); vector<vector<int>>dp1(2 *...

对于这道题,先解释一下一段数组的权值 从伪代码看,就是Σ_{i=l}^{r}dis(l,i),其中dis(l,i)代表s数组按下标(从一开始)从l到i多少个不同的元素,这就是一个数组的权值计算公式 但是,我们还需要计算所有子数组的权值,因此我们需要得到所有的子数组 最终答案也就是ans=Σ_{l=1}^{n} Σ_{r=l}^{n} Σ_{i=l}^{r} dis(l,i) 但是这个用到了三重循环,非常恐怖的复杂度,因此我们必须进行优化,至少要到n log n才行,但是这个可以优化到n 先看内层的两个循环,此时l看做常数,那么dis(l,i)就只与i有关了,对于某个dis(l,i),我们不难发...

看着挺吓人的,实际上只需要掌握快速幂就可以解决了 我们先算出1/100%mod的值,可以在测试的时候算出来,这样就不用一步一步每次都算了 接着我们需要算出每个数字的概率,先处理好每个数字都需要什么二极管,然后在运算的时候处理即可(我用的是set处理) 算完每个数字的概率后,看题目有三个要求,但我们只需要看最后一个要求就行了,因为最后一个要求就包含了前两个要求 我们可以进行一个从0到c的循环,a为循环,b=c-a,接着把每个概率加起来就可以了 #include<bits/stdc++.h> using namespace std; #define ll long long const...

这题用dp来解决 关键思路是,对于一段完全不重叠(所有数彼此相与都为0,以后简称合法)的序列[l,i] dp[i]=dp[l-1]+dp[l]+...+dp[i-1],也就是sum[i-1]-sum[l-2] 为什么? 我们一步一步来推导 假设一段序列 a1+a2+a3+a4+a5+a6 其中a3~a6是a6往前最长的合法序列, 假设dp[0]~dp[5]已经确定好了,那么,对于a5和a6之间的符号有两种情况 1:'+',就是dp[5] 2:'|',由于'|'的优先级比较高,这势必会对之前产生影响(比如a2和a3本来可以合并,和现在不能了), 这样我们只能接着向前讨论,也就是a4和a5之间的符...

链接 直接用dfs怕是要超时,有一种巧妙的思路 设一个大小为amount的数组dp,(全部初始化为INT_MAX)对于coins的每一个值,dp[coin]都设为1, 然后,我们可以设想一下,对于某一个i,dp[k]!=INT_MAX, 那么dp[i]是不是有可能等于dp[k]+1(也有可能dp[i]本身就比较小) 既然这样,那么我们让i从1遍历到amount,就能找到最终答案了 class Solution { public: int coinChange(vector<int>& coins, int amount) { vector<int>dp(amou...

链接 文艺平衡树要求对区间进行修改,这点和线段树很像 我们可以对fhq 平衡树进行小小的变形 题目要求我们对[l,r]进行翻转,我们只需要互换两个节点的编号就行了,由于我们操作的仅仅是1-n的序列,而且编号与值是相对应的,因此我们结构体就不需要开辟出val 而且我们并不知道l对应的具体是什么值,因此split不能按val来裂开,而是根据size裂开 仿照线段树,我们就写一个reverse标记,延迟更新的标记 并用push_down函数更新 还有一个小细节,就是当某个节点发生更改的时候,需要push_down更新 #include<iostream> #include<rand...

链接 题目差不多,无非就是设两个变量(但是m怎么有1e6啊,害得我re了两次) #include<iostream> #include<random> using namespace std; const int MAXN = 2e5 + 5; #define ll long long struct node{ int l, r; ll val; int size; }fhq[MAXN]; int cnt, root; int newnode(ll val) { fhq[++cnt] = { 0,0,val,1 }; return cnt; } void update(...

链接 multiset失效了,我不得不去学习平衡树了,但是我偶然接触到了FHQ 平衡树,发现还不错,代码简单好理解 与AVL不同,FHQ实现的是分裂与合并操作,插入撤除都很方便,而且一般不会被特殊数据给卡住 重点函数是split和merge,split将要分裂的函数按val分裂为x和y两个部分(两棵树),merge则相反,将两棵树合并起来 这样插入操作就只需要将root按val拆开,在合并x和单独的val,接着全部一起合并即可 删除操作则将root按val-1,val拆成x,y,z三部分,这样我们只需要删除y的一个节点再全部合并就好了 至于获取排名,将root按val-1拆成x,y两部分,这样...

链接 又是一道和树路径有关的题目,上一次是<小红的奇数奶油球>,我用的dfs 这次用bfs(n这次也超级小的,本来还担心超时) 和那题很相似,唯一的难点在于距离如何计算 分析一下就会发现,设节点j到节点i的距离为dis[i],显然dis[j]=0 那么,只需让dis[i]=dis[k]+1即可(k为i的上一个节点) #include<iostream> #include<vector> #include<queue> #include<cstring> #include<algorithm> using namespace...

链接 这题思维难度不高,只需要找前驱后继,比一下就OK了 我想自己写平衡树实现,但是试了好几遍都错了 老实了,还是用multiset吧 #include<bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin>>t; multiset<int>num; long long count=0; for(int i=0;i<t;i++){ int x; cin>>x; if(i==0){ co...

链接 该说不愧是简化版嘛,还以为要用平衡树的,结果普通的二叉查找就可以了 至于前驱和后继,和二分法挺像的,就不解释了,代码易懂 #include<iostream> using namespace std; struct tree { int val; tree* left, * right; tree(int x):val(x),left(nullptr),right(nullptr){} }; class BST { private: tree* root; int count = 0; int rank = 0; int rank_ans = 0; tree* Insert(...