A.bubble冒泡排序
考虑k次冒泡中的每一次，会把最大的数移到最右边
而只有最大数在变吗?
以1 4 3 5 2为例
5的右边相对顺序是不变的，而5的左边是要变的
发现在不断地把小的往前面移，且每一个较小的数都会往前最多移动k个
但我们不好算每个i往前移k个的数
考虑反向处理：算有哪些点可以被移到i
很显然在i的位置是1~k+i中的某一个数
找规律：第一个位置一定是1~ k+1中最小的，第二个是1~k+2中第二小的……
那么i的数就是1~k+i中第i小的
用优先队列实现
B.digit打字计划
暴力复杂度是，也超时得不多，然而空间有很小
考虑如何优化？
很显然可以被“用空间换时间”的折半搜索优化
先搜前5个，再搜后5个
也可以先把特殊的处理了，在直接搜
C.lake湖泊建造
要让石头圈的水最多，很显然是要使石头排成一个三角形
（由于我们不好控制水，可以换过来思考控制石头)
如果有奇数个石头，那么可以构成底为1的三角形，偶数个石头底为2
奇数个:
0 . . . . . 0
0 . . . 0
0 . 0
0
偶数个:
0 . . . . . . 0
0 . . . . 0
0 . . 0
0 0
那么就可以用数学公式计算（注意容易爆ll，有平方的先除再乘，用ull）
（注意unsigned long long的输出是%llu）
给出水就可以用二分求石头个数
也可以直接用类似倍增的方法求，这样更优
for(ull step=1ull<<30;step>0;step>>=1ull)
if(gets(n+step)<m) n+=step;
n+=1ull;//和LCA一样都会停在前一个位置，所以要加一
总结：
1.这次模拟赛时间的分配做得不好，在第一题上死磕太久，导致第三题没有时间了
2.在遇到正向做不动的时候，可以考虑换个角度分析:
比如T1中不好算每个点会移到哪里，可以反向考虑ans中第i个是原数组的哪一个点移过来的；
T3中不好算控制水需要的石头数，可以反向考虑n个石头控制的水的数量
————————————————
版权声明：本文为CSDN博主「hewanying0622」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/hwy0622/article/details/129221848