看到网上有许多快速排序和快速选择的代码，但是相当一部分都有些错误，这里放一下自己的写法
快速排序模板题：https://www.luogu.com.cn/problem/P1177
快速选择模板题：https://vjudge.net/problem/POJ-2388
#include <cstdio>#include <cstdlib>#include <algorithm>using namespace std;const int maxn = 1e6 + 5;int n, a[maxn];void kth_element(int * l,
链接标题
复习最小路径覆盖
最小路径覆盖是指对于给定的DAG，用最少的路径将其所有点覆盖，路径不相交。最小路径覆盖建图如下：
变式1：最小链覆盖
用最少的路径将其所有点覆盖，路径可以相交
做法：使用floyd传递闭包重连边，然后进行最小路径覆盖
变式2：最长反链
指选择最多的点，使得两两之间不能互相到达
做法：对偶问题：最长反链等于最小链覆盖
本题中发现球是依次加入的，如果有两个球和为完全平方数那么小的向大的连接单向边，一个柱子就相当于一条路径。那么可以知道K" role="presentation" style="position: relative;"&
https://ac.nowcoder.com/acm/contest/7502/J
题目大意：
定义串
S1=[1]Sm=Sm−1+[m]+Sm−1" role="presentation" style="width: 100%; position: relative;">S1=[1]Sm=Sm−1+[m]+Sm−1S1=[1]Sm=Sm−1+[m]+Sm−1 S^1=[1]\\
S^m=S^{m-1}+[m]+S^{m-1}
其中′+′" role="presentation"
https://ac.nowcoder.com/acm/contest/7502/G
题目大意：
给定一个长度为n" role="presentation" style="position: relative;">nnn数组，每一次可以进行如下操作：
1、将数组划分为前后两段
2、将这两段分别翻转
问最后可能得到多少种数组？
多组数据
Σn≤2×106" role="presentation" style="position: relative;">Σn≤2×106Σn≤2×106\Sigma
传送门
题意：计算σ0(i3)" role="presentation" style="position: relative;">σ0(i3)σ0(i3)\sigma_0(i^3)的前缀和
以前雅礼集训的时候就听说过这题，好像是洲阁筛板子？
但是如今世道不同了，Min_25" role="presentation" style="position: relative;">Min_25Min_25Min\_25筛可以把这种东西吊起来筛！
当p∈Prime,f(pc)=3c+1" role="present
传送门
题意：计算σ0(ik)\sigma_0(i^k)的前缀和
一道牛逼题目，Min_25Min\_25筛写的很简短。
当p∈Prime,f(pc)=ck+1p\in Prime,f(p^c)=ck+1
且当p∈Prime,f(p)=k+1p\in Prime,f(p)=k+1
又因为前缀和∑ni=1k+1=n(k+1)\sum^n_{i=1}k+1=n(k+1)可以O(1)O(1)
直接Min_25Min\_25筛就行了，复杂度O(1011)O(10^{11})能过。
#include<cstdio>#include<algorithm>#
A - Colorful Subsequence
简化版题意：输入一个字符串，输出每种字母的个数+1" role="presentation" style="position: relative;">+1+1+1的乘积的结果−1" role="presentation" style="position: relative;">−1−1-1。 |S|≤105" role="presentation" style="position: relative;">|S|≤105|S|≤105|S| \le 10^5
题解：按照题意模拟就
题目描述
给你一棵n个点的树，每一个点有个颜色ci" role="presentation" style="position: relative;">cicic_i。定义一种颜色的树是：把该颜色的点两两路径上的点和边都拿出来构成的图形。你可以选出k" role="presentation" style="position: relative;">kkk种颜色来，求：有多少种方案可以使每种颜色交集产生的树非空。对k∈[1,m]" role="presentation" style="position: relative;">k∈[1,m]k∈[1,m]k
传送门
题解：
考虑怎么做这道题。
首先发现性质：
改变次数=2×总操作数−答案中′1′的个数" role="presentation">改变次数=2×总操作数−答案中′1′的个数改变次数
GTW likes tree
Time Limit: 7000/3500 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 191 Accepted Submission(s): 38
Problem Description
GTW has a tree of n nodes, in which m nodes are special nodes. The value of node i is vi.
Dis(x,y) is defined as
Rockdu's Blog