求第
小数
1
2
3
4
5
6
7
8
9
10
11
12
13
| int find_mid(int l,int r, int k){
int mid=(l+r)/2;
int i=l,j=r;
int pivot=a[mid];
while(i<=j){
while(a[i]<pivot)i++;
while(a[j]>pivot)j--;
if(i<=j)swap(a[i++],a[j--]);
}
if(k<=j)return find_mid(l,j,k);
else if(i<=k)return find_mid(i,r,k);
else return a[j+1];
}
|
用快排的思想即可, 与快排不同的是, 只需要对一个子区间递归调用即可.
这里根据产生的下标做具体分析: 当交换结束后, 将 分成了三个区间: - 区间上的数都小于等于 pivot - 区间上的数都大于等于 pivot
因此如果 , 则第 小的数在区间 上; 如果 , 则第 小的数在区间 上, 否则说明 pivot 就是第 小的数, 且 pivot 在序列中的下标一定为
.
下面是数据 6 9 7 5 2 4 1 10 第一轮变换的结果:
1
2
3
4
| 6 9 7 5 2 4 1 10
1 9 7 5 2 4 6 10
1 4 7 5 2 9 6 10
1 4 2 5 7 9 6 10
|
P2949
优先队列priority_queue默认大根堆, 如果要实现小根堆:
1
| priority_queue<int,vector<int>, greater<int>>q;
|
优先队列的元素为 pair<int,int> 时,
入队的排序依据为第一个元素.
结构体入队时, 通过重载实现比较方式:
1
2
3
4
5
6
7
| typedef struct _foo{
int a,b;
friend bool operator > (_foo x,_foo y){
return x.b < y.b;
}
}foo;
priority_queue<foo>q;
|
LOJ10001
https://loj.ac/p/10001
暴力可过, 先假设每个点都种即 ans=n,
然后从头到尾扫描一遍, 如果不种不违反约束条件(不会导致某个区间的树不够)就
ans--, .
更快的方法是差分约束, 考虑前缀和, 约束条件可以转化为 的形式.
(没学过, 有时间再学)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e3,maxn2=3e4;
int sug[maxn+5][3];
int num[maxn+5];
int main(){
int n,h,ans=0;
cin>>n>>h;
for(int i=0;i<h;i++){
cin>>sug[i][0]>>sug[i][1]>>sug[i][2];
num[i]=sug[i][1]-sug[i][0]+1;
}
ans=n;
for(int k=1;k<=n;k++){
int flag=0;
for(int i=0;i<h;i++){
if(k>=sug[i][0]&&k<=sug[i][1]&&num[i]==sug[i][2]){
flag=1;
break;
}
}
if(!flag){
ans--;
for(int i=0;i<h;i++){
if(k>=sug[i][0]&&k<=sug[i][1]){
num[i]--;
}
}
}
}
cout<<ans;
return 0;
}
|
LOJ10002
首先考虑每个圆能够覆盖的区间,
用勾股定理将问题转化为从若干区间中选择最少的能覆盖给定区间的区间.
接着按照右端点排序, 从左到右进行覆盖, 记录当前能覆盖到的区间的右端点
crt, 在剩下的区间中选择左端点小于 crt
的且右端点最大的区间即可, 当不存在这样的区间或者最大的区间右端点小于
L 时输出 -1.
注意涉及到比较和运算的变量都要设置为浮点型.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| double crt=0;
int flag=0;
if(arr[0].r<L){
cout<<-1<<endl;
}
else{
while (crt<L){
flag=0;
for(int i=0;i<k;i++){
if(!isv[i]&&arr[i].l<crt){
isv[i]=1;
ans++;
crt=arr[i].r;
flag=1;
break;
}
}
if(!flag){
cout<<-1<<endl;
is_out=1;
break;
}
}
if(!is_out)
cout<<ans<<endl;
}
|
P2158
找到满足 的
的对数, 最后结果乘2加上 即可,
显然是转化为欧拉函数的前缀和, 最终答案为
用线性筛求积性函数即可, . 当
时, 设 ,
.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| int phi[N],p[N],isv[N],cnt=0,n;
void Euler(){
isv[1]=phi[1]=1;
for(int i=2;i<=n;i++){
if(!isv[i]){
p[++cnt]=i;
phi[i]=i-1;
}
for(int j=1;j<=cnt&&i*p[j]<=n;j++){
isv[i*p[j]]=1;
if(i%p[j]!=0){
phi[i*p[j]]=phi[i]*phi[p[j]];
}
else{
phi[i*p[j]]=phi[i]*p[j];
break;
}
}
}
}
|
好像也可以用莫比乌斯反演求 , 这里是个更一般的题.
不会做.
