题目链接 https://codeforces.com/problemset/problem/616/D 解题思路 做过两遍了吧。类似尺取法，不过尺子是不同数字的个数。双指针。右指针每到一个数字让cnt统计当前遍历到的区间中此数的个数++，左指针每到一个数字让cnt--。若右指针向右移动时添加了区间内没有的数，则区间不同数字个数++，若左指针向右移动时删去了区间内唯一的一个此数值的数字，则区间不同数字个数--。当l~r的区间内不同数字个数大于k时开始移动左指针，否则移动右指针，满足k时，更新最优解。 代码 #include<bits/stdc++.h> using namespac...

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=4608 解题思路 思路一：与CodeForces - 1409D Decrease the Sum of Digits 有异曲同工之妙。看当前数位之和与最小10倍数差多少，若此数加上这个差不发生最低位的进位，则直接修改最低位为原最低位+差即可；若发生进位，那么我们就通过“大数加”，让进位加到次最低位，最低位先变成0，统计“大数加”完成后的数位和。再计算此时的数位和与最小10的倍数的差，将最低位修改为差即可。代码部分可以不分情况，因为同一代码两者适用。 思路二：若不发生进位，则直接修改最低位；反之，从...

题目链接 https://codeforces.com/problemset/problem/76/E 解题思路 数学题，降维应该都能想到 由题意可知： 答案= (x1-x2)^2+(y1-y2)^2 (x1-x3)^2+(y1-y3)^2 (x2-x3)^2+(y2-y3)^2 (x1-x4)^2+(y1-y4)^2 (x2-x4)^2+(y2-y4)^2 (x3-x4)^2+(y3-y4)^2 ....... ....... (x1-xn)^2+(y1-yn)^2 (x2-...

题目链接 https://codeforces.com/problemset/problem/1419/C 解题思路 总共三种情况0，1，2分情况讨论一下。1.全都是x时，02.存在x或全部之和为n*x时，13.其他情况，2 代码 // 废物代码 #include<bits/stdc++.h> using namespace std; const int N = 1e3+10; int T, a[N], f, sum, n, x, ff; int main() { cin>>T; while(T--) { f = 0; ...

题目链接 https://codeforces.com/problemset/problem/1409/D 解题思路 卧槽，前天刚去青岛理工参加的青岛市ACM，其中一个题就是把这个题翻译成中文了，当时就听赛场上有人喊原题，***原题啊！ 位数太多，不按位存会爆ll。整体思路：从低位开始修改，且每次修改都是不断加1直至当前位变成0，即发生进位，因为只有发生进位才能使所有位数之和减小。且低位进位完毕后若仍无法使和满足条件，则需要让高位向更高位进位。每次发生进位都需要修改原数（按位保存在数组中，即修改数组），同时保存对当前这位的修改次数，最后输出每位的操作次数即可。（可能有同学不明白为什么可以直接保...

题目链接 https://codeforces.com/problemset/problem/1515/D 解题思路 第一步：先将左右脚袜子个数经转换变成一样的；第二步：变色。也就是说先变类型至左右脚相等，再变色得到完全匹配。 先说第二步，假设经过一定的算法后左右脚袜子个数相等了。设dif[i]表示l[i] - r[i]，即同种颜色左脚袜子数减去右脚袜子数。答案为 如何将袜子数变换成一致的：假设初始右袜子个数大于左袜子个数，则若dif[i] <= -2，则将此颜色的一根右袜子变成左袜子；待全部颜色的袜子都按此方式循环完后，仍无法使左右袜子数一致，则再次循环。若dif[i] == -1，...

题目连接 https://codeforces.com/contest/1183/problem/F 解题思路 大致思路： 1.选一个数，必然选最大的数；2.选两个数，最大的数+不为其约数的最大的数（下注证明）；3.选三个数，要么是最大的数+不为其约数的最大的数+不为前面俩数约数的最大的数，要么是最大数/2+最大数/3+最大数/5。 证明1： 就很显然，选一个数，肯定选最大的； 证明2： 如果选的两个数中一个为最大的数，那么另一个一定不为其约数，所以要选不为其约数的最大的数；反之如果不选最大的数，那么两个数一定都要为其约数（你不选其约数的话为啥不把最大的选上呢？假如这两个数其中一个是约数一个不...

题目连接 https://codeforces.com/contest/822/problem/C 解题思路 存两个数组中，一个按左端点从小到大排序，一个按右端点从小到大排序，遍历每一个，找到其对应的满足l<r的全部区间，保存区间长度对应的最小花费，对于遍历到的每一段区间，我们找到满足与其之和为x的另一段区间，维护最小花费即可。这样可以保证，每一段区间的花费被存在了cost[区间长度]中，同时每次去维护答案的所有cost是满足区间不相交的最小花费。（需要自己理解一下） AC代码 #include<bits/stdc++.h> #define INF 2147483647 #d...

题目链接 https://vjudge.net/contest/413174#problem/C 解题思路 思维吧。是不是有人没看懂题QWQ，看我题解，会讲解一个样例大致思路：从后往前找到第一个不符合自己位置的数现在所在的位置。对于每一次实验，若输入的数比记录的位置小，是否改成有序，都无所谓，因为要想整个序列变得有序，必须要把无序的部分一次性改完才行；否则，这次实验可以把序列变得有序，为了方便解释，我们拿题目给的第三个样例讲解一下，很显然，这个序列前三个的顺序错了，所以小于3的改不改无所谓，我们完全可以忽略（2，0.4）这组实验，进行第一次实验（4，0.9），修改成功的概论为0.9，所以ans...

题目链接 https://vjudge.net/contest/413174#problem/B 解题思路 dp。dp[i][j]表示以点(i,j)为树顶的树的个数，最后求一下所有位置的点为树顶能构成的树的个数之和，即为答案。转移方程：开始所有为 * 的位置全部初始化为1，dp[i][j]+=min{dp[i+1][j-1],dp[i+1][j],dp[i+1][j+1]}注意：1.边界；2.因为给出的是n * m的范围，所以我们要用一维数组存储二维信息，不细说了，一维数组的下标整除m表示行坐标，取余m表示列坐标，行列坐标均从0开始。dp数组要设置成一维的。3.一个一个输入字符的时候，也要注意...

题目链接 https://www.luogu.com.cn/problem/CF666A 解题思路 居然是dp。提醒：twice in a row译为 连续两次dp[i][2]=1表示(i,i+1)满足条件，=0表示不满足；dp[i][3]=1表示(i,i+1,i+2)满足条件，=0表示不满足。转移方程： 如果(i,i+1)==(i+2,i+3)，dp[i][2]=dp[i+2][3] //含义为如果连续两个长度为2的子字符串相等，那么要能选起始地址小的长度为2的子字符串，就只能由与之相连的长度为3的子字符串转移过来，只有这个长度为3的子字符串满足，接下来的这个子串才能被选。 如果(i,i+1...

题目链接 https://ac.nowcoder.com/acm/contest/9752/B 解题思路 abc不一定要连续，但是a与a必须连续，对于b，c同理。二分；先把a，b，c选出来，二分题目中的n，check函数先看能不能找到n个a，再看能不能找到n个b，再找n个c，如果任意一个不行，则返回false，否则返回true。 AC代码 int n; string ss; bool check(int x) { int len=3*x,i=1,cnta=0,cntb=0,cntc=0; while(i<=n) { if(ss[i]=='a') c...

题目链接 https://ac.nowcoder.com/acm/contest/9667/I 解题思路 二分+技巧技巧1：异或运算的性质，x^a^a=x，利用这个性质，可以通过类似前缀和与的方式，在O(1)的时间复杂度中求出某段区间的异或和；技巧2：因为要求最小长度，自然要二分长度，之所以能二分长度是因为，对于本题而言，区间的异或和随长度的增加而增加。为什么这么说，很显然可以举出反例，区间长的异或和小，区间短的异或和大，这明显不是单调的？但是对于本题而言，对于一个x，如果长的区间小于x，短的区间大于x，那肯定选小的区间，如果小的区间大于x，那么长的区间肯定也大于x，还是选短者，所以如果长的区...

题目链接 https://ac.nowcoder.com/acm/contest/9667/B 解题思路 线段树，特征过于明显类似于线段树维护区间最大值，这里多了个对最大值个数的维护，最大值个数的维护只要在PushOn函数中同最大值的维护一起进行即可。PushDown是用大区间更新小区间，一般用在有lazy的时候；PushOn是小区间更新大区间，为了维护某些值进行的。比较板子，难点在于容易敲错，bug还难de……注意：1.因为要输出最大值和个数，但是通过return返回只能返回一个值，因此我们这里采用引用的方式进行返回。2.对于最大值的维护比较板子，对于个数的维护需要判断一下左右子树的最大值是...