总结

题单（问题 A11A15/B11B14）

二分、搜索

很多题可以用二分之外的方法解决，B14的优化非常巧妙，值得记录

A11 - Binary Search 1

如果想用 vector 但是又想从下标为 1 开始记录，访问头迭代器时用 a.begin()+1

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 表达式的格式

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

小数二分

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 表达式写递归函数的格式

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");
}