Little_sk

单调栈指的是一个栈，栈内的元素是单调的。 单调递增栈：从栈底到栈顶元素依次从大到小。 单调递减栈：从栈底到栈顶元素依次从小到大。 建立一个单调栈例：如果要维护一个递增单调栈（也就是栈顶的元素最小），那么元素要入栈时，如果为空栈或者栈顶元素比入栈元素大，就入栈，否则就依次将栈顶元素出栈，直到满足条件。 伪代码： 12345678910111213stack<int> s1;//一般需要在数组中添加一个结束标识符 for(遍历数组){ if(栈为空||栈顶元素大于当前元素){ 入栈; }else{ while(栈不为空&&栈顶元素小于当前元素){ 栈顶元素出栈; 更新结果; } 当前元素入栈; } } 应用1.视野总和：...

Markdown语法安装离线编辑软件TyporaTypora下载。官网下载后去github上下载破解器https://github.com/WittonBell/typoraCracker 在线协同编辑器CodiMD在线协同编辑markdown http://120.26.48.253:3000/( 搭建在我的服务器上，所以一年后(2025/3/20)就寄了) 常用语法 中间空出一行(相当于按了两次回车)则新起一段 使用#加一个空格来表示标题 1234# 一号标题## 二号标题### ...###### 六号标题 代码块，使用反引号(在键盘左上角) 一个反引号是段内代码段内代码 ，常用作关键字标记。 或者用来阻止解析公式abc 代码块:每边三个反引号(在键盘的左上角，tab的上面)，中间包裹住的行就是代码块的部分。 123这是一个代码块代码块可以偶很多行代码块还可以选择代码语言来标记高亮 在代码块(并非段内代码)的第一个三反引号的后面跟上代码语言，可以实现对应的高亮 12345#include<iostream>using namespace...

题目链接 A. Median of an Array题意给出一个数组$a$，每次操作可以让其中一个数增加一。 问最少需要几次操作能改变中位数的值。 长度为n的数组a的中位数表示为，令b是a排完序后的数组，那么$b_{\lceil \frac{n}{2}\rceil}$ 即为a的中位数。 思路假设中位数为$m$ ，那么我们就需要让最终的中位数变为$m+1$ 。做法就是对一些值为$m$ 各进行一次操作。我们假设小于等于m的数的数量为$cnt$ , 起初一定有$cnt \ge \lceil \frac{n}{2}\rceil$为了让$m+1$是中位数，就必须$cnt< \lceil \frac{n}{2}\rceil$ 。 每次操作能使得cnt减少1 。于是我们需要的操作数量就是$cnt - \lceil \frac{n}{2}\rceil + 1$ 代码123456789101112131415161718192021222324252627282930313233343536#include<bits/stdc++.h>using namespace...

题目链接 A. Setting up Camp题意有一些屋子，每个屋子最多容纳三个人，有三种人，内向人必须一个人一个屋，外向人必须三个人同时一个屋子，综合人随意（一个两个三个都可） 现在有$a$ 个内向人， $b$ 个外向人， $c$ 个综合人。 问最少需要多少个屋子才能满足所有人的要求，如果无论如何都不能满足那么就输出-1 思路我们很容易发现， 对于内向人，不会导致输出-1.因为给他们一人一个屋子即可。 对于综合人同样不会导致输出-1. 只有当外向人在引入几个综合人之后，仍然无法成为3的倍数时，会导致出现-1的情况。 换成代码语言即为$ b\%3+c<3$ 只要不是输出-1 的情况，我们的答案即为$a+ \lceil \frac{b+c}{3}\rceil$ 代码1234567891011def solve(): pass a,b,c = [int(x) for x in input().split()] if b%3 != 0 and b % 3 + c < 3 : print(-1) return ...

题目链接 - Codeforces Round 933 (Div. 3) 博客中的代码仅供参考，请勿直接提交源代码，这对提升实力毫无作用!!! 题目写一半，自己不小心把编译器搞坏了，中途又重新下载mingw呜呜呜,好在这场时间长 A. Rudolf and the Ticket题意有两个数组a和b，长度分别为n，m。即$a_1,a_2,…,a_n,b_1,b_2,..,b_m$ 。 现要求你从两个数组中各选择一个数$a_i,b_j$ 并且要求$a_i + b_j \le k$ ,问有多少种选法。 思路二分查找， 对b数组排序，然后枚举$a_i$ , 使用upperbound来在b中查找第一个大于$k - a_i$ 的下标p，那么b数组中的区间$[0,p-1]$上的数都满足和$a_i$ 相加之后小于等于$k$。 于是产生了$p$的贡献。按此理计算出总贡献即可。复杂度$O(nlogn)$ 代码12345678910111213141516171819202122232425262728293031323334#include<bits/stdc++.h>using...

A. Entertainment in MAC题意有一个字符串$s$和偶数$n$， 你可以对这个字符串进行$n$次操作（不能多不能少） 操作一：将$s$的反向字符串拼接到s的后面，比如对字符串abc进行操作会变成 abccba 操作二：将当前的字符串反转 问进行完这n次操作后，最终的字符串的字典序最小的可能是什么样子的。 思路可以发现，如果这个字符串翻转后更大（比如abc ，进行翻转后是cba 比原先更大了）,那么我们就可以进行n次翻转，这样最终的字符串就是原先的字符串，也就实现最小了。 如果这个字符串s在反转后更小了，那么我们就必须执行奇数次翻转，才能保证这个s最终是较小的。但题目中说n是偶数，所以就意味着我们必须进行至少一次拼接操作， 那么显而易见，拼接操作进行的越少越好， 因此需要翻转$n-1$次，然后拼接一次。 （比如bca， 如果进行偶数次翻转，那么最终的字符串前三个字符是bca ，而进行奇数次翻转时最终的字符串的前三个字符是acb...

线段树123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121struct Info{ LL sum = 0;}; struct Tag{ LL add = 0;}; Info operator+(const Info &a, const Info &b){ return {a.sum + b.sum};} void apply(Info &x, Tag &a, Tag f){ if...

Codeforces Round 930 (Div. 2) 题目链接 A. Shuffle Party题意给出一个数组$a_1,a_2,…,a_n$ 起初$a_i = i$ ，之后定义$swap(k)$ 操作为 : 找到最大的，不等于$k$的因子$d$ ，交换$a_d$和 $a_k$ 。 下面令$i = 2,3,…,n$ ，依次进行$swap(i)$ ，问最终数值$1$会在哪个位置。 思路数值1会随着不断运行swap来移动位置，我们可以观察1的移动轨迹。 于是我们模拟一下操作会发现， i = 2时， $swap(2)=swap(a_1,a_2)$ 此时1移动到了位置2 。接下来若想要让位置2发生交换，那么就必须找到一个最小的k，使得这个k所对应的d恰好是2 。 并且k尽可能地小。 于是我们想到了2的2倍4 。 下一步数值1便从位置2 移动到了位置4。接下来就是4的2倍即8， 数值1又从位置4移动到了位置8 。 这样循环往复，直到数值1移动到了$2^j$ , 并且满足$2^j \le n < 2^{j+1}$...

Dashboard - Educational Codeforces Round 157 (Rated for Div. 2) - Codeforces C. Torn Lucky Ticket题意给出n个长度不大于5的字符串$s_1，s_2，…，s_n$（只由数字组成）， 你需要选择其中两个串$(i，j)$ （$i$ 和$j$可以相等，并且 $(i,j)$与 $(j,i)$视为两个不同的选择）, 令$s = s_i + s_j$。 问有多少种选择，使得： s的长度为偶数 s的前一半的数字的总和等于后一半的数字总和 $1\le n \le 2*10^5$ 思路我们使用string类型的一维数组dat存储原始数据。 使用二维的vector数组vec（算上vector一共三维）存储处理后的数据。 $vec[i][j]$ 中存储的元素表示长度为 i的字符串， 他的后缀s[j,i-1] 的数字的总和 减去 前缀s[0,j-1]的数字总和。 我们对所有的vector类型进行排序。以便于我们使用lower_bound和upper_bound...

题目链接-牛客周赛 Round 35 A - 小红的字符串切割题意给出一个长度为偶数的字符串，分别输出前一半和后一半 思路&代码按题意输出即可 12345678910111213141516171819202122#include<bits/stdc++.h>using namespace std;#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define int long long#define rep(i,l,r) for(int i = l;i<=r;i++)#define per(i,r,l) for(int i = r;i>=l;i--)const int INF = 0x3f3f3f3f3f3f3f3f;typedef pair<int,int> PII;void solve(){ string str; cin>>str; ...