本文迁移自洛谷原文。
这里是官方题解
考虑到在所有的排序操作之后，之前的所有操作都会没有用。
所以我们只需要找到最后的一个排序操作后处理即可。
对于翻转，我们只需要设定一个变量$x$。
如果是正序，$x=0$，反之，$x=1$
如果翻转了，$x=1-x$
如果交换了：
当 $x=0$ 时 $swap(a[l],a[r])$
当 $x=1$ 时 $swap(a[n-l+1],a[n-r+1])$
最后输出即可。
Code:
1 | #include<iostream> |
本文迁移自洛谷原文。
我们不难发现毒瘤们想让我们写状压dp，所以我们考虑如何不写状压dp。
由于这题的数据范围很小，所以我们可以考虑随机。
假设当前随机到的数为tmp，则分为3种情况：
1.将所有的点设置为”选择”（因为我们可能在一开始有一个不好的开头）
2.随机删除一条边
3.随机补回一条边
由于要使得最终结果最小，所以2的概率要大点
测试得到1为$\frac{1}{1024}$，2为$\frac{3}{4}$，3为$\frac{1}{4}$时可以过。
上代码：
1 | #include<bits/stdc++.h> |
本文迁移自洛谷原文。
来个python题解
由于只是要求A是B的子串，而没有限制长度最短（如果限制的话就比这难得多了），所以我们可以贪心的让B为A+A的反串。
代码如下：
1 | s=input() |
本文迁移自洛谷原文。
结论+dp
我们可以先观察样例。当 $n=4$ 时，整个序列的最大值为8。在merge后的序列中8后面的数在原序列中一定跟在8后面。同理得，在7后面8前面的所有数都一定跟在7后面。
于是原序列被分成了很多小段。现在要做的事就是将这些小段重新组合，得到两个长度为 $n$ 的原序列。由于你已经分好了，所以你不需要知道小段内的内容，只要知道它们的长度，然后01背包即可。
Code:
1 | #include<bits/stdc++.h> |
本文迁移自洛谷原文。
做为出题人来一发（
首先，我们可以想到，敌人有很多是重复的，所以每一个位置上只留一个敌人即可。
然后，我们可以贪心的想：走到一个位置以后，等着别人来送死。
如何求出这个位置？
将这棵树，以任意一个节点为根，遍历一遍。
然后我们需要截取出“有用”的一块。（定义“有用”的一块为会被至少一个人走过的路径）
于是，我们可以让自己的初始位置为根，遍历一边这棵老树。
从所有有用的点出发，往上遍历，途中所有的点都变成有用的点。
然后删掉所有没有用的点即可。
然后，在这棵新的树上，找到最长链。
这个“最优点”一定就是这条最长链的中点了。（它到所有的叶子的距离的最大值最小。）
然后二分答案即可。
对于每一个二分到的值，循环所有有人站着的点，判断它的mid被祖先与你的初始位置的mid辈祖先之间的距离是否$\le k$。
这个距离也可以用LCA求出:deep[x]+deep[y]-deep[LCA(x,y)]*2
复杂度：$O(n \times (log n)^2)$
优化：对于最后一步，每一次二分只需要枚举3个点(自己，最长链的两端)即可。
并且将二分去掉，直接暴力即可。（删了那个预处理的$nlogn$）
复杂度：$O(n)$
为什么这个贪心是正确的？
你要走的话，必定向着敌人走。而且是最远的，不然没有意义。
首先，我们可以选出两个敌人($x$和$y$)，使得他们和自己组成一个三人组，并且x到y的最短路径经过你，且你们三个人之间互相到达的最小距离最大。
然后，假设你和$x$的距离为$a$,你和$y$的距离为$b$。
如果你走向x，杀死他后再返回杀死$y$，那么你走到路程为$max((a-k)/2,0)+max((b-k)/2,0)$
待着不动的话，结果为$max(max(a-k,0),max(b-k,0)) $
当a,b均小于k:都为$0$。√
当$a$或$b$小于$k$(一个):化简为
走向：$(a-k)/2$
不动： $a-k$
于是这个可以特判（??
不，（详细见后文）
$a,b$均大于$k$：
走向：$(a-k)/2+(b-k)/2=(a+b)/2-k$
不动： $max(a-k,b-k)=max(a,b)-k$ (这里出问题了？？？
不，其实没有
因为我们要走到的标准位置上，$a=b$或者$abs(a-b)=1$
证毕。
代码：
1 | #include<bits/stdc++.h> |
本文迁移自洛谷原文。
首先，我们可以先选择题目，再把剩下不要的让家长拿走。这一定是最优的。
然后就是个基础的背包。dp[i][j]表示考虑带第i个题目时，花费了j个时间的最大毒瘤值。
为了最后的计算，还要记录一下路径。
最后通过记录的路径求出选了那些题目，然后贪心的从大到小排序，选前k个*2即可。
1 | #include<bits/stdc++.h> |
本文迁移自洛谷原文。
这题线段树、珂朵莉树的题解都有了，我来个分块吧/cy
分块维护每一个块内的状况，如果遇到整块涂色则打上标记，可以将时间复杂度保持在$O(n\sqrt{n})$
1 | #include<bits/stdc++.h> |
本文迁移自洛谷原文。
没有python题解？我来水一发
直接暴力枚举有多少门得了两分，一个一个判断即可
1 | n,k=map(int,input().split()) |
本文迁移自洛谷原文。
自己的题，怎么能不写题解呢？
考察点：构图
我们可以新建$n$个点:$n+1 \dots2n$
第$i$个点表示$i-n$这个数
对于所有的$a_i$，将i与所有是$a_i$的约数的平方数的平方根所对应的节点号连一条边，权值为这个平方根
这样就可以转换成一个图论问题了！
也就是说，对于这张图，选出最大数量的点，使得两两之间不能由权值大于$x$的边相连。
我们很容易就可以发现， 在一个由权值大于$x$所组成的联通快中，最多只能选择一个。
所以跑$n$边dfs就可以了！
注意点1:
由于有$2 \times 10^5$个点和询问，所以裸的$O(nm)$是过不了的
通过打表可以发现，有很大一部分询问的答案是相同的
最多只需要查找$\sqrt{max{a_i}}=200$次即可。
所以只需要找到这个临界值就可以了
2.如何O($b_i^{\frac{1}{3}}$)求出$c_i$?
1 | res=1;i=1 |
为什么这段代码是正确的？
假设 $last_b=p*q$
因为所有$\le b_i^{\frac{1}{3}}$的 因数都已经被while除完了
所以$p,q$一定为两个挺大的，互质的数
所以只要特判一下$p,q$是否相等即可
std:
1 | #include<bits/stdc++.h> |
本文迁移自洛谷原文。
在1:43时A掉了这一题，成功翻盘，rank34
题解：
贪心+dp
首先我们可以发现，如果一个城堡是可以被守卫的，那么，我们就会尽可能的让他往后被守卫。
为什么呢？
因为，如果在前面就守卫了，也许就会影响到后面的关卡过不去。而到了最后，如果你再不守卫的话，那么就没有机会了。但是如果到最后再守卫，造成的代价与之前一样，但是可以让他有更多的机会去进攻。
dp:
令dp[i][j]表示考虑到第i个城堡时，剩余了j个人时的最大成果。
1 | inline void solve(){ |