y_din-CSDN博客

原创【CF题解】Codeforces Round #738 (Div. 2) A-D2

文章目录A.Mocha and MathB.Mocha and Red and BlueC.Mocha and HikingD1.Mocha and Diana (Easy Version)D2.Mocha and Diana (Hard Version)A.Mocha and Math题意：每次操作可以选择一个区间【l,r】可以使得改区间内a[i]变成a[i]&a[r+l-i],可以进行无数次操作，问最终得到a数组的最小值思路：对于一个i来说，必然存在一个区间[l,r]可以使得该数可以和

2021-08-16 19:56:20 239 1

原创【CF题解】Codeforces Round #721 (Div. 2) A-E

A. And Then There Were K题意：给一个n，求最小的k满足n & (n−1) & (n−2) & (n−3) & … (k) = 0思路：因为是位运算，我们会发现在与的情况下，只需要出现一个0就可以消掉这一位上的数，我们会发现由于在数字不断减小的过程中，后面几位会不断地在0和1之间变换，那么最难被消除掉的位其实就是n最前面的1，然后我们会发现在某个数到形如1111的数过程中，0会不断地在出现过的位置上出现，所以，最后的答案就是小于n的最大的二进

2021-05-21 16:02:01 485

原创【树状数组优化dp】【求M元上升子序列个数】UVA12983 The Battle of Chibi

题面https://www.luogu.com.cn/problem/UVA12983题意求在一个序列中m元上升子序列的个数（不用连续）思路显然我们可以定义一个状态dp[i][j]表示以长度为i并且以j结尾的子序列个数的个数转移方程为dp[i][j]=∑k<j,a[k]<a[j]dp[i−1][k]dp[i][j]=\sum_{k<j,a[k]<a[j]}^{}dp[i-1][k] dp[i][j]=k<j,a[k]<a[j]∑dp[i−1][k]

2021-04-07 11:37:29 218

原创【线段树+双向链表】2021牛客寒假算法基础集训营3 E-买礼物

题面https://ac.nowcoder.com/acm/contest/9983/E题意两种操作把位置x上的数变成0查询【l，r】区间上有没有相同的两个数思路题意转化：可以把问题转化成对于【l，r】这个区间中是否存在一个数，使得跟该数前面最近跟它相同的数位置在【l，r】这个区间中首先我们可以预处理出每个数前面跟它相等的最近的数的位置，然后用线段树存储我们预处理的数组，我们只需要判断跟他相同的最大的位置是否在【l，r】这段区间里，就知道是否存在了那对于第一个操作，我们要如何进行更新

2021-02-08 15:16:42 127

原创【思维+线段树】牛客牛客练习赛66 E骚区间

题面https://ac.nowcoder.com/acm/contest/6112/E题意求在一个序列中有几个【L,R】满足a[l]是这个序列的次小值，a[r]是这个区间的次大值思路因为左右两边的性质相关相反，所以我们考虑把一个端点固定下来以后，找另一端的约束区间首先我们把左端点固定下来，用左端点是次小值的这个性质，把右端点的约束区间确定下来，比如说：如图这个区间，对于第二个数4而言，以4为左端点满足条件的区间只有【2，3】和【2，4】，以左端点为4的约束区间为【3，4】所以这个地

2021-01-19 19:07:31 112

原创【区间dp】洛谷P4302 字符串折叠

题面https://www.luogu.com.cn/problem/P4302思路仔细观察样例可以发现，

2021-01-19 10:10:46 132

原创【线段树】L - GTY‘s gay friends

题面http://acm.hdu.edu.cn/showproblem.php?pid=5172题意给你n个数，m次查询，每次询问一个区间【l,r】,问这个区间【l,r】是否满足【l,r】之间的数是【1,r-l+1】的一个排列思路1：题意转化+线段树对于一个区间，我们可以把它【1，r-l+1】的排列转化成满足以下两个条件：【l,r】的区间和为len*(len+1)/2,其中len=r-l+1对于【l,r】中的每个数，他的前一次出现必须在l这个位置之前对于第一个问题来说，我们可以直接用前缀和

2020-12-11 16:01:01 148

原创【树形dp】 K-The Flee Plan of Groundhog 2020牛客暑期多校训练营（第九场）

题面https://ac.nowcoder.com/acm/contest/5674/K题意给你一棵树，橘子在标号为n的这个节点，一开始一只土拨鼠以1m/s的速度从节点1出发走向n，在走了t秒以后，橘子开始追土拨鼠，橘子以2m/s的速度前进，土拨鼠的速度依然为1m/s，问最长多少时间橘子追上土拨鼠思路首先有一种情况肯定是不会出现的（红色表示橘子行动的路径，蓝色表示土拨鼠行动的路径）因为按照贪心思路，对于土拨鼠而言，他不会跟橘子相对而走，因为这样子会使得它的逃跑时间减少，最后答案会比向另一个

2020-12-09 10:53:14 123

原创【暴力约束】D - K-th K AtCoder - agc008_d

题面https://vjudge.net/problem/AtCoder-agc008_d题意给一个长度为N的序列X,X[i]表示的是i出现第i次在x[i]这个位置上，问是否能构造出这个序列思路首先x[i]这个位置上放的就是i这个数，然后就是约束前面i-1个位置来放i这个数，有一个显然的结论就是贪心地来选肯定是前面的位置先安排掉，因为对于后面的数来说，可以选择的位置更多，同样，在第一轮从前往后排的时候已经占掉前一半的数了，那么后一半的位置就倒着按照第一次的贪心思路来把后面的位置填充完代码#in

2020-12-07 16:16:03 163

原创【哈希+并查集】J - Connectivity AtCoder - arc065_b

题面添加链接描述题意有n个城市，他们之间有k条道路和l条铁路，问每个城市各有多少个城市与它既用道路可以相连又用铁路可以相连（铁路和道路之间互不相连），一个城市和它自己有道路和铁路同时相连思路题意可以转化为对于一个城市而言，在道路中有一个集合，在铁路间也有一个集合，它可以都到达的城市就是这两个集合的交集，但是直接查询的话复杂度是n2log(n)n^2log(n)n2log(n)，这个地方我们可以用哈希处理，将所有第一个集合和第二个集合相同的投影到同一个map中，在映射回来可以处理代码#inclu

2020-12-07 14:20:01 159

原创【网络流/二分图匹配】I - Magic Potion 2018icpc南京

题面https://vjudge.net/problem/Gym-101981I题意岛上有m个怪兽，n个勇士，每个勇士只能消灭特定的一些怪兽，而且每个勇士只能消灭一直怪兽，但有k瓶药水，可以让一个勇士可以多打一只怪兽，但是每个勇士只能喝一瓶，问最大能打死几只怪兽网络流思路我们只需要建一个如下图然后跑一个最大流就可以得到答案了网络流代码#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef

2020-12-02 11:56:05 160

原创【三维三分/模拟退火】D - Country Meow 2018icpc南京

题面https://vjudge.net/problem/Gym-101981A题意给n个在三维坐标上的点(x,y,z)，在空间中假设有一个点a，求每个点到点a的距离的最大值，而题目要使得这个最大值最小思路分析可得，对于每一维，另外两维固定后，另一维和答案的关系呈一个凹函数，所以可以使用三分套三分套三分的方法，使用递归来实现代码#include<bits/stdc++.h>#define INF 0x3f3f3f3f#define lowbit(x) x&(-x)#d

2020-11-30 14:36:54 234

原创【思维+双指针】I - Distance 2018ICPC焦作

题面https://vjudge.net/problem/Gym-102028I题意每一次选一个点，答案+=其他已经选的所有点到该点的距离之和，求最大能得到答案思路显然答案是要左边取一个右边取一个会最大，然后我们又发现先取那边没有关系，所以就变成了一个简单的双指针的题，主要难度在代码实现上代码#include<bits/stdc++.h>using namespace std;typedef long long ll;const double pi=acos(-1);con

2020-11-28 21:41:23 95

原创【组合数计数分类/dp】C - Insertion Sort 2018沈阳区域赛

题面：https://vjudge.net/problem/Gym-101955C题意有1-n的序列，给一个k，k可以使得n个数的排列里面的前k个数有序，问最终可以得到一个最长上升子序列的长度大于等于n-1的这个序列的排列有多少种可能题意转化前k个可以排序，也就是说我们可以把整个序列分成两段，分为【1，k】和【k-1，n】进行分类讨论思路一、分类讨论后面一段区间完全按照【k-1,n】升序来排列，前面的k个数可以随便排序式子：k!k!k!前k个不管,k!，后面有一个数可以乱序，就是

2020-11-25 13:02:06 164

原创【扫描线+计数去重】Codeforces Round #672 (Div. 2) D. Rescue Nibel!

题目链接：https://codeforces.com/contest/1420/problem/D题意：有n个灯泡，他们开关的时间分别为 l[i] 和 r[i]，在某一时刻，选择k个亮着的灯泡，求能取的方案数思路一开始的想法是用离散化来做，考虑每一个时刻有多少个灯泡是亮着的，然后利用组合数学来算但是我们会发现，这种情况会重复，如图，红线的两种情况，都需要判断一下，但是其中124这种情况会被计数两次，所以就要找一种方式使得计数的时候不重一般处理计数重复的问题有两种方法，容斥和选择取和不取

2020-09-25 19:06:34 115

原创【线段树上dp】Codeforces 750 E New Year and Old Subsequence

题目链接：https://codeforces.com/contest/750/problem/E题意给一个1~n的数字串，每次询问在区间【l,r】之间至少要删除几个字符使得剩下的的数中有2017但是没有2016思路我们会发现，这个问题由两个子问题构成：对于一个串，我们要如何来计算需要删除几个字符如何将这个问题转化成一个区间查询的问题问题1解决显然这个问题要用dp来解决，但是怎么解决呢这个地方用到了矩阵和floyd最短路的转移假设说这个问题求的是1~n的字符串的转移，那么代码如下

2020-08-07 20:25:48 141

原创【字符串构造】hdu第一场1004Distinct Sub-palindromes

题目链接http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=879思路以及推导过程一开始是想到写了几个字符串aaaa，abcd，abbc，发现它的回文子串个数都是4，然后用了快速幂发现错了然后开始思考，我们可以把这个问题变成一个动态的增加字符的过程假设S为原串，那我们来考虑增加一个字符，会发生什么，首先，显然增加一个字符有可能会使得回文子串增加，也有可能不增加，然后我们来寻找增加的情况发现当且仅当一下三

2020-07-22 17:02:16 119

原创【二分+思维】排位赛1-D Meetings

题面：思路：这里有两个结论：两头牛相遇，速度交换，由于速度只有1和-1两个状态，所以

2020-07-11 21:23:10 117

原创【基础算法】前缀和和差分数组详解

文章目录一、前缀和概念作用例题二、差分数组概念差分数组与前缀和的关系差分数组的应用一、前缀和概念前缀和就是前面i个数之和即：sum[i]=num[1]+num[2]+……+num[i]例(如图)：sum[1]=num[1]sum[2]=num[1]+num[2]sum[3]=num[1]+num[2]+num[3]sum[4]=num[1]+num[2]+num[3]+num[4]作用在理解了前缀和是什么以后，那么前缀和有什么作用呢？前缀和最大的用处就是可以对区间和进行o(1)

2020-07-04 15:00:15 1507

原创【思维】C港口（差分数组）第十五届中北大学算法与程序设计竞赛

题目链接：https://ac.nowcoder.com/acm/problem/205919题目描述：港口有n堆货物，他们的重量分别为w1,w2,…wn，每堆货物的重量不一定相同。吊车师傅每次操作可以使任意第i堆到第j堆的货物都增加一个重量或者减少一个重量。请问吊车师傅最少需要执行几次操作可以使n堆货物重量都相同。这个题是从差分数组的角度思考的。从差分数组的角度来看，每次对于区间[l,r]进行加操作就是对于差分数组cf[l]++,对cf[r+1]–;那么反过来思考，如果对原数组进行了区间[l,r

2020-06-30 20:05:42 1052

qq_46129590的博客

原创【SQL练习】练习总结

转载【动态规划】最长上升子序列LIS

原创【CF题解】Codeforces Round #738 (Div. 2) A-D2

原创【CF题解】Codeforces Round #721 (Div. 2) A-E

原创【树状数组优化dp】【求M元上升子序列个数】UVA12983 The Battle of Chibi

原创【线段树+双向链表】2021牛客寒假算法基础集训营3 E-买礼物

原创【思维+线段树】牛客牛客练习赛66 E骚区间

原创【区间dp】洛谷P4302 字符串折叠

原创【线段树】L - GTY‘s gay friends

原创【树形dp】 K-The Flee Plan of Groundhog 2020牛客暑期多校训练营（第九场）

原创【暴力约束】D - K-th K AtCoder - agc008_d

原创【哈希+并查集】J - Connectivity AtCoder - arc065_b

原创【网络流/二分图匹配】I - Magic Potion 2018icpc南京

原创【三维三分/模拟退火】D - Country Meow 2018icpc南京

原创【思维+双指针】I - Distance 2018ICPC焦作

原创【组合数计数分类/dp】C - Insertion Sort 2018沈阳区域赛

原创【扫描线+计数去重】Codeforces Round #672 (Div. 2) D. Rescue Nibel!

原创【线段树上dp】Codeforces 750 E New Year and Old Subsequence

原创【字符串构造】hdu第一场1004Distinct Sub-palindromes

原创【二分+思维】排位赛1-D Meetings

原创【基础算法】前缀和和差分数组详解

原创【思维】C港口（差分数组）第十五届中北大学算法与程序设计竞赛

原创【思维】糖糖别胡说，我真的不是签到题目

原创【树】树、二叉树、森林的转化与遍历

原创【二叉树的非递归遍历】用堆栈实现中序遍历

原创【循环队列】循环队列使用过程中的问题及解决方案

原创【堆栈】中缀表达式转化为后缀表达式以及后缀表达式的计算

原创【线性表】线性表的随机存取和顺序存储？

原创【线性表】在矩阵的多重链表表示中，第i行的head和第i列的head实际上是同一个结点？

原创【图论之最短路问题】简单易懂入门篇：Bellman-Ford、Dijkstra和Floyd算法

原创【c++基础】STL常用总结

原创素数筛（埃氏筛和欧拉筛）

空空如也

空空如也