总结
题单（问题 A11~A15/B11~B14）
二分、搜索
很多题可以用二分之外的方法解决，B14的优化非常巧妙，值得记录
A11 - Binary Search 1
如果想用 vector 但是又想从下标为 1 开始记录，访问头迭代器时用 a.begin()+1
1
2
3
4
5
6
7
8
9
10
| void solve()
{
int n;cin>>n;
int x;cin>>x;
vector<int> a(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
}
cout<<lower_bound(a.begin()+1,a.end(),x)-a.begin()<<"\n";
}
|
A12 - Printer
主要回顾 Lambda 表达式的格式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| void solve()
{
int n,k;
cin>>n>>k;
vector<int> a(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
}
auto check=[&](int mid)->bool{
int sum=0;
for(int i=1;i<=n;i++){
sum+=mid/a[i];
}
return sum>=k;
};
int l=1,r=1e9;
while(l<r){
int mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<l<<"\n";
}
|
B12 - Equation
小数二分
1
2
3
4
5
6
7
8
9
10
11
12
| void solve()
{
int n;cin>>n;
double l=0,r=100;
while(l+0.0001<r){
double mid=(l+r)/2;
if(mid*mid*mid+mid>=n){
r=mid;
}else l=mid+0.0001;
}
cout<<l<<"\n";
}
|
B14 - Another Subset Sum
题意
从大小为 $n$ 的数组 $a$ 中取任意个数，问是否能使取出数的和等于 $k$
$n_{max}=30$，$k_{max}=10^8$，$a$中任意元素$_{max}=10^8$
idea
初看会有两种思路，$dp$ 与 $dfs$，两者的复杂度分别为$O(nk)$、$O(2^n)$，都无法通过
这里的技巧是把大小为 30 的数组分成两个大小为 15 的数组 $a$ 与 $b$ ，
利用 $dfs$ 把 $a$ 可能得到的结果存在一个 $map$ 中，
然后对 $b$ 中做 $dfs$ ，判断其中是否存在一种值，与 $map$ 中的结果相加等于 $k$
总时间复杂度为 $2\cdot O(2^{n/2})$
同时还有 Lambda 表达式写递归函数的格式
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
35
36
37
38
| void solve()
{
int n,k;
cin>>n>>k;
vector<int> a(1),b(1);
for(int i=1;i<=n/2;i++){
int x;cin>>x;
a.push_back(x);
}
for(int i=n/2+1;i<=n;i++){
int x;cin>>x;
b.push_back(x);
}
int n1=a.size(),n2=b.size();
bool ok=0;
unordered_map<int,int> mp;
//function<void(int,int)>，void为返回值，(int,int)为形参表
function<void(int,int)> dfs1=[&](int i,int sum)->void{
mp[sum]++;
if(i==n1+1) return ;
dfs1(i+1,sum+a[i]);
dfs1(i+1,sum);
};
dfs1(1,0);
function<void(int,int)> dfs2=[&](int i,int sum)->void{
if(mp[k-sum]>0){
ok=1;
return ;
}
if(i==n2+1) return ;
dfs2(i+1,sum+b[i]);
dfs2(i+1,sum);
};
dfs2(1,0);
cout<<(ok?"Yes\n":"No\n");
}
|