Little_sk

[题目链接](https://codeforces.com/contest/1966) A. Card Exchange题意给你n个牌，每个牌都有一个数字。 每次你可以选择恰好k个相同数字的牌， 然后将他们替换为任意的k-1张牌。（这k-1张牌的上的数字任意） 问在经过一些操作后，最终能剩下的牌的数量最少是多少。 思路最终剩下牌的数量 = n - 最多执行的操作次数。 所以我们很明显地发现，如果起初不存在相同的k个数，那么就无法进行操作，直接输出n即可。 给出结论，如果可以进行第一次操作，那么就可以使得最终牌的数量变为k - 1。 下面是证明： 我们设当前有n张牌 ， 在满足”存在相同的k张牌“的前提下， 有如下两种情况： 只有k张牌，且全部相同。那么再进行一次操作就可以实现最终剩下k-1张牌。 除了这k张牌之外，还有其他的牌（设他的值为num），那么我们就可以选择k-1张num来替换起初的k张相同牌，...

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

Markdown语法安装离线编辑软件TyporaTypora下载。[官网](https://typoraio.cn/)下载后去github上下载破解器https://github.com/WittonBell/typoraCracker 在线协同编辑器CodiMD在线协同编辑markdown http://120.26.48.253:3000/( 搭建在我的服务器上，所以一年后(2025/3/20)就寄了) 常用语法 中间空出一行(相当于按了两次回车)则新起一段 使用#加一个空格来表示标题 1234# 一号标题## 二号标题### ...###### 六号标题 代码块，使用反引号(在键盘左上角) 一个反引号是段内代码段内代码 ，常用作关键字标记。...

[题目链接](https://codeforces.com/contest/1946) 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...

[题目链接](https://codeforces.com/contest/1945) A. Setting up Camp题意有一些屋子，每个屋子最多容纳三个人，有三种人，**内向人**必须一个人一个屋，**外向人**必须三个人同时一个屋子，综合人随意（一个两个三个都可） 现在有a 个内向人， b 个外向人， c 个综合人。 问最少需要多少个屋子才能满足所有人的要求，如果无论如何都不能满足那么就输出-1 思路我们很容易发现， 对于内向人，不会导致输出-1.因为给他们一人一个屋子即可。 对于综合人同样不会导致输出-1. 只有当外向人在引入几个综合人之后，仍然无法成为3的倍数时，会导致出现-1的情况。 换成代码语言即为b\%3+c=sum[x] \&\& sum[n]-sum[x]>=n-x-sum[n]+sum[x] 我们直接枚举|\frac{n}{2} - i| 的值，然后推算出两个i ， 分别判断是否满足情况。 代码123456789101112131415161718192021222324def solve(): pass n = int(input())...

[ 题目链接 - Codeforces Round 933 (Div. 3)](https://codeforces.com/contest/1941) 博客中的代码仅供参考，请勿直接提交源代码，这对提升实力毫无作用!!! 题目写一半，自己不小心把编译器搞坏了，中途又重新下载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。...

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) [题目链接](https://codeforces.com/contest/1937) 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](https://codeforces.com/contest/1895) C. Torn Lucky Ticket题意给出n个**长度不大于5**的字符串s_1，s_2，...，s_n（只由数字组成）， 你需要选择其中两个串undefinedi，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] 的数字的总和 减去...