归雨の算法小窝

单调队列思想与方法总结总结 单调队列：队列指的是双端队列，而单调指的是队列具有单调性。 单调队列和单调栈非常相像，但是侧重点不同，一种的强调大小，在弹出的时候计算结果(盖棺定论)或者计算贡献，在弹出的时候终结贡献。而单调队列，侧重点则在于值中。我们通过维持一定范围内的最大值与最小值，来进行接下来项目的计算，直到计算出答案。单调队列的重点，就在于一定范围的维持，和怎么与动态规划如何结合,同时，为了范围计算的方便，我们往往在队列中存储下标。 最基础板子P1886 滑动窗口 /【模板】单调队列 计算范围为 $ k $ 的最小值和最大值，最基础的模板，单调队列的运作，就像是打ACMer一样。 如果最强的选手到了退役的年纪，那么就该退役了(弹出头部)。 如果出现了一个又强又新的新人，他就可以把比他弱的老人给顶替掉(弹出尾部)。 (有时候，因为我们的计算问题，我们最好手动添加节点，方便之后的计算) 我们根据这个逻辑，去写出最小值，接下来将值取成负数再求一次即可。 1234567891011121314151617181920 int n ; cin...

单调栈 单调栈的精粹感觉不仅是单调的处理，更是栈里面大小的处理。很多的时候，题目里面都有大小的反馈，我们一般是维护单调栈，根据其中的规律，去进行大小的处理。而后得出答案。 单调栈最基本的运用 我们通过单调栈，去维持一个递增或者递减的情况。当然我们最重要的不是求其中递增递减的情况，反而是我们前面的情况，因为我们并不会直接对本点进行处理，反而是对之前的点进行处理。 123456789101112131415 stack<pair<int,int>>stk ; int n ; cin >> n ; vector<int>ans(n+1) ; for(int i =1 ; i<= n ; i++){ int x; cin >> x ; while(!stk.empty() && stk.top().x < x){ ans[stk.top().y] = i ; stk.pop() ; } ...

2025.8.20 Codeforces Round 1013 (Div. 3)总结 感觉自己图论还是不太行，下一周还是要以加训图论专题为主了，不过终归还是有点进步的qwq， 一次第一次把div3补完，希望以后有一天能进前一千名 题目部分A. Olympiad Date题意 我们有 $ n $ 个数字，我们要凑出来 $ 01.03.2025 $ 问最早什么时候能凑出来，凑不出来就输出$ -1 $ 思路 要哈希或数组存一下数字的数量, 如果到 $ 0 $ 的时候存一下，最后判断一下是否全部数字 $ <=0 $ 即可，这样如果凑的出来，我们肯定能得到最早的数字。 代码 123456789101112131415161718vector<int>a(11 , 0 ) ;a[0] = 3 ; a[1] = 1 ;a[2] = 2 ; a[3] = 1 ;a[5] = 1 ; int n ; cin >> n ;int flag = 0 ; for(int i = 1; i<= n ; i++){ int x ;...

2025.8.20 Codeforces Round 1016 (Div. 3)总结 最近跑去参加了贵阳的代码源集训营，回去又摸鱼了好久，最近大补了一下图论，感觉还好。准备接下来继续补图。 昨天vp了一下，个人感觉其实自己分治的思维不太行，(关于F做的出来D反而不会这档事),等图论练完可以尝试训练一下，以及有空可以补一下字典树。 ok，唠嗑完了，开局 题目部分A. Ideal Generator题意 我们有一个长度为 $ k $ 的数组 $ a $ ,如果这个数组和对任意 $ n(n>=k) $ ，并且有回文的特性，我们就称他为理性生成器，否则输出No 思路 我们手玩一下，可以注意到对于任意奇数$k$,我们都可以通过使除中间数以外的数字都为1，中间数为$n-x+1$来满足条件，对任意偶数，我们都可以构造$ n=k+1 $来卡掉。 代码 123int k ; cin >> k ;if(k&1)cout << "Yes\n" ; else cout <<...

2025.7.21 divEducational Codeforces Round 180 (Rated for Div. 2)总结 今日VP,状态不太好ac1,最近还是给vp+补题+图论的组合,准备花两周先入一下图论基础,目标是能轻易做出以树和图为基础的铜牌题,补足短板. 题目部分A Race 需要注意到,题目的数据范围为 $ t(1≤t≤1000), a，x， y(1≤a,x,y≤100) $ 这昭示的我们可以使用暴力去解,固直接枚举即可. 时间复杂度$O(n)$ ; 代码 12345678910111213int a , n , m ; cin >> a >> n >> m ;bool ok = 0 ; int st1 =abs(a-n) , st2 = abs(a - m ) ;for(int i = 0 ; i<= 200 ; i++){ if(i == a )continue ; if(abs(n - i) < st1 && abs(m - i) < st2...

参考代码1234567891011121314151617181920int partition(int a[] , int l , int r){ int povit = a[l] , i = l , j = r ; while(i<j){ while(i<j && a[j] >= povit)j-- ; swap(a[i],a[j]); while(i<j && a[i] <= povit)i++ ; swap(a[i],a[j]); } a[i] = povit ; return i ; }void Quicksort(int a[] , int l , int r ){ if(l<r){ int mid = partition(a,l,r) ; Quicksort(a , l , mid-1); ...