题目链接 https://codeforces.com/contest/1443/problem/B 解题思路 也算是dp吧。转移（抽象讲解）：对于每个连通块（特指为1），无非是选择单独引爆，或者选择与前面的连通块相连通。dp[i]表示引爆前i个连通块的最小花费，那对于第i个连通块而言，选择单独引爆时dp[i]=dp[i-1]+a；选择与前面的连通块连通引爆时，由于dp[i-1]表示的就是前i-1个引爆的最小花费，所以其实对于第i个连通块来说，只需要与前面的连通块相连，不需要再加上引爆的费用了，而连通的费用就是第i个连通块前面相邻的0的个数*b。 AC代码 #include<bits/s...

题目链接 https://codeforces.com/contest/1443/problem/B 解题思路 对数组a进行升序排列，如果让前i个快递员送，那么快递员所花费时间为a[i]，剩下的由自己拿。用前缀和存储自己拿的时间。 AC代码 #include<bits/stdc++.h> #define ll long long #define x first #define y second const int N=2e5+100; const int inf=0x3f3f3f3f; using namespace std; pair<ll,ll> p[N]; int...

题目链接 https://codeforces.com/problemset/problem/351/B 题目大意 给你一个1到n的排列a[i]。Jeff和Furik轮流操作，Jeff先手。Jeff每次会交换a[i]>a[i+1]的两个数。Furik每次有1/2的概率交换a[i]<a[i+1]的两个数，有1/2的概率交换a[i]>a[i+1]的两个数。当这个排列变成升序时，游戏停止。问你操作数的期望。 解题思路 假设原序列中有t个逆序对。那么将这个序列变成升序，就是将这t个逆序对一个个消除。  Jeff每次会减少一个逆序对。Furik每次有1/2概率增加一个逆序对，有1/2概...

题目链接 https://codeforces.com/problemset/problem/351/A 题目大意 给你一个2×n长的序列，进行n次操作，每次操作是选取两个从未选过的数，一个取上整，一个取下整，问你最后能得到最接近原来和的序列是多少。 解题思路 大佬题解写的***简单，我理解了好一会儿。对于每个非整数，可以选择向下取整，也可以选择向上取整；假设数i的小数部分为x，比如i=1.234，则x=0.234，如果i向下取整，我们规定向下取整丢失的小数部分要加到答案上，即ans+=x；如果i向上取整，ans-=1-x，还是上面的例子，若i=1.234向上取整，导致多加了1-0.234，因...

题目链接 https://vjudge.net/problem/HihoCoder-1483 解题思路 二分第k小的值，假设为m，统计区间价值小于等于m的区间数量（这个统计的方法真是绝了），若数量比k大说明二分的区间右端点大了；反之，说明二分的区间左端点小了。 AC代码 #include<bits/stdc++.h> #define ll long long using namespace std; const int N=2e5+100; ll k,a[N],b[N],n,vis[N]; int T; bool check(ll x){//统计区间价值小于等于x的区间数量，太牛逼...

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=5696 解题思路 大致思路：找到区间[l,r]的最小值的位置p，确定了区间[l,r]的最小值为a[p]，那么区间[l,r]内包含p点的任意子区间都要通过a[p]去乘以某个此子区间的最大值得到此子区间价值吧。很显然，value[p,i]=max(value[p,j],a[p]*a[j+1])，解释一下，假设p<j，那么由于所有区间的最小值都是a[p]，那么区间价值只取决于最大值的大小，而位于p同侧的大区间的价值比小区间的价值大，要么相等；（你想想是不是）更新完以区间[l,r]中最小值为分界点的a...

题目（来自PTA，没有测试平台） 给定一个全部由小写英文字母组成的字符串，允许你至多删掉其中 3 个字符，结果可能有多少种不同的字符串？ 输入格式：输入在一行中给出全部由小写英文字母组成的、长度在区间 [4, 10^6] 内的字符串。 输出格式：在一行中输出至多删掉其中 3 个字符后不同字符串的个数。 输入样例：ababcc输出样例：25提示： 删掉 0 个字符得到 "ababcc"。 删掉 1 个字符得到 "babcc", "aabcc", "abbcc", "abacc" 和 "a...

小G有一个大树 解题思路 大佬题解 AC代码 #include<bits/stdc++.h> using namespace std; const int inf=0x3f3f3f3f; const int N=1e6+10; int sum=inf,node,n,w[N]; vector<int> tree[N]; void dfs(int x,int fa) { int maxx=0; w[x]=1; for(int i=0;i<tree[x].size();i++) { int tx=tree[x][i]; ...

题目链接 https://ac.nowcoder.com/acm/contest/7606/D 解题思路 刚拿到以为是树状数组的题，心想完了，一个数据也过不去了。结果仔细一看，原来不是树状数组的题目，舒服多了，还是一个数据没过。 不知道大家有没有做过一道蓝桥的题（可能是），题目找不到了，大致意思是n堆馒头，每堆数量不一样，每天能将n-1个馒头分到n-1个堆里，问最少几天每堆变得一样。就这意思，正着想的话，选出最多的一堆不分，其他每堆一个，模拟下去；反向操作一下，每天都让最多的一堆减一个，直到所有堆的馒头数都相等，这和选n-1个加一个的效果一样吧。 对应到本题来说，除素数和乘素数都一样，算出的最...

题目链接 https://ac.nowcoder.com/acm/contest/7606/C 解题思路 开始看到这个题，感觉好难啊，到底怎么贪心啊，变的这么多。结果发现居然做出来了，就是少了个细节少了10分。对于每年的加薪，我们有两种选择，可以一群人加薪，另一群不加，下一年再给上一次加薪的继续加薪，给不加薪的继续不加，让他们淘汰，这样最后第m年（m>2）肯定就没有这些被淘汰的人对答案的贡献了；另外，若对去年没加薪的加薪，对去年加薪的不加薪，把人留住了，这样最后第m年（m>2）所有人（不一定是所有人都能留下）都对答案有贡献了。到底哪个更好？首先，我们很容易能想到的是肯定要对本来薪水...

题目链接 https://ac.nowcoder.com/acm/contest/7606/B 解题思路 每个人的回合要淘汰尽可能多的人，所以肯定优先淘汰手牌少的。谁的手牌少？那些抽得的手牌数比被抽走的手牌数少的人吧。我们根据抽取数量的多少从小到大将他们排序，顺序遍历，因为我们要先淘汰容易淘汰的吧，也就是获取手牌数量少的；若此人可获取的手牌数量比在场剩下的人（不包括他自己）的数量都少，说明他的手牌数量在减少，每轮都减少，肯定最终被淘汰；将每个人都遍历一遍，最后剩下的就是无法被淘汰的人数。 AC代码 #include<bits/stdc++.h> using namespace st...

前言 1.算法学习，三分靠别人题解，七分靠自己理解。2.前一阵有同学问过我，我也做过KMP的题，但是当时只是会板子，理解的并不是很深，所以直接把大佬题解给那个同学了。这次数据结构，理解比较好了，才敢自己写讲解。 最朴素的暴力时间复杂度O(n*m) 文本串 s 的长度为 n ，模式串 p 的长度为 m ，通过i指针访问 s 串每个位置的字符，通过 j 指针访问 p 串每个位置的字符。最朴素的暴力就是，若 i 指向的字符与 j 指向的字符一样，那 i，j 一起后移；若不相等，i 回溯到开始与j相同的下一个位置，j 回溯到 p 串的开头。i 指针遍历一遍 s 串，对于每一个不同的 i ，最差情况 j...

题目链接 https://ac.nowcoder.com/acm/contest/7604/D 解题思路 参考先看看大佬的大致思路，再看我的代码讲解。 代码讲解 先扫一眼代码，再看讲解。 构建最大值/最小值区间： 大佬写的代码比较难理解，但是时间复杂度应该比这样低点。抽丝剥茧，分离出本质，就是找第i个位置之后第一个比a[i]大的位置，将其保存在ka[i]中。所以说，区间[i,ka[i]-1]的最大值为a[i]。同理，找到第i个位置之后第一个比a[i]小的位置，将其保存在ki[i]中。区间[i,ki[i]-1]的最小值为a[i]。 接下来的循环 ans[i]表示区间长度为i的最终和与区间长度为...

题目链接 https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/ 解题思路 先确定大思路：移动右端点直到区间内有重复字符；再移动左端点直到区间内无重复字符。也就是说右端点的移动条件是区间内不存在重复字符，移动右端点是为了尽可能扩大区间，找到最大解；而左端点移动条件是区间内存在重复字符，移动左端点是为了缩小区间，保证区间满足要求。 AC代码 class Solution { public: int lengthOfLongestSubstring(string s) { ...