n很小，直接爆搜+剪枝

class Solution {
public:

    int n, k;
    vector<int>  sum;
    int ans = INT_MAX;

    void dfs(vector<int>& jobs, int u, int group){
        int h = *max_element(sum.begin(), sum.end());
        if (h >= ans)   return;
        if (u == n){
           ans = h;
           return;
        }

        for (int i = 0; i<group; i++){
            sum[i] += jobs[u];
            dfs(jobs, u + 1, group);
            sum[i] -= jobs[u];
        }
        if (group >= k) return;

        sum[group] += jobs[u];
        dfs(jobs, u + 1, group + 1);
        sum[group] -= jobs[u];
    }
    int minimumTimeRequired(vector<int>& jobs, int _k) {
        n = jobs.size(), k = _k;
        sum.resize(k, 0);
        sort(jobs.begin(), jobs.end()); reverse(jobs.begin(), jobs.end());
        dfs(jobs, 0, 0);
        return ans;
    }
};

枚举序列的前两个位数字，再用dfs递归判断字符串接下来的数字是否等于A+B。要注意字符串转INT的边界情况。

const int N = 210;
class Solution {
public:

    vector<int> ans;
    int n;
    int len_max = to_string(INT_MAX).length();

    int getVal(string &str, int start, int end){
        int len = end - start + 1;
        if (end > str.size() || len > len_max)   return -1;
        if (len > 1 && str[start] == '0')   return -1;

        auto ret = stol(str.substr(start, len));
        if (ret > INT_MAX) return -1;
        return (int) ret;
    }

    bool dfs(string &S, int start, int last, long goal){
        if (start == n)
            return true;

        int end = to_string(goal).length() + start - 1;
        int x = getVal(S, start, end);
        if (x == goal){
            ans.push_back(x);
            if (dfs(S, end+1, x, (long)last + x)) return true;
            ans.pop_back();
        }
        return false;
    }

    vector<int> splitIntoFibonacci(string S) {
        n = S.size();

        ans.resize(2);
        for (int i =1; i<n; i++){
            int a = getVal(S, 0, i-1);
            if (a == -1)    break;
            for (int j = i; j<n; j++){
                int b = getVal(S, i, j);
                if (b == -1)    break;
                ans[0] = a, ans[1] = b;
                if (dfs(S, j+1, b, (long) a + b))
                    return ans;
            }
        }
        return {};
    }
};

前导

几乎和并查集的代码是一模一样的， 因为增加了一项输出连通块数量的操作，所以要再原来的代码上加上一些东西

这就要求我们在面试或者比赛的时候随机应变，但是核心知识点是不会变的，也就是模板也不会变太多，只要把核心理解了，就能让我们举一反三

增加内容

我们使用一个size[]数组来存储树的大小，有三个需要注意的问题

1. size[]初始化
2. if(find(a) == find(b)) continue;含义
3. size[find(b)] += size[find(a)] 和 p[find(a)] = find(b)的先后位置

解答

1：因为一开始是一个个单独的节点，并没有形成树化结构，所以我们初始化为1就可以了

2：如果a,b已经连在一起了，就不用在加了，再相加的话就相当于多加了一遍，所以跳出循环就可以了

3：注意：一定要size[find(b)] += size[find(a)]在前，p[find(a)] = find(b)在后

如果p[find(a)] = find(b)在前的话，再次寻找根节点会找到b，这样的话就是size[find(b)] + size[find(b)]
而不是size[find(b)] + size[find(a)]

代码

import java.util.Scanner;

public class Main{
    static int N = 100010;
    static int[] p = new int[N];         //储存当前节点的父节点
    static int[] size = new int[N];      //储存树的大小

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int m = in.nextInt();

        for(int i = 1; i <= n; i ++){
            p[i] = i;
            size[i] = 1;
        } 

        while(m-- > 0)
        {
            String str = in.next();
            int a = in.nextInt();

            if(str.equals("C"))
            {
                int b = in.nextInt();
                if(find(a) == find(b)) continue;     //如果a,b已经连在一起了，就不用在加了
                size[find(b)] += size[find(a)];      //把根节点的大小加在一起
                p[find(a)] = find(b);                //注意：这条语句要在最后，如果在前面的话，再寻找根节点都会找到b
            } 
            else if(str.equals("Q1"))
            {
                int b = in.nextInt();
                if(find(a) == find(b)) System.out.println("Yes");
                else System.out.println("No");
            }
            else if(str.equals("Q2"))
            {
                System.out.println(size[find(a)]);
            }
        }
    }

    private static int find(int x){                  //用于寻找根节点
        if(x != p[x]) p[x] = find(p[x]);
        return p[x];
    }
}

//这里的r需要用double，用flaot会出现精度错误

#include<cstdio>
#include<iostream>

using namespace std;

int main(){
    double r;
    cin>>r;
    printf("A=%.4f",3.14159*r*r);
    return 0;
}

题目描述

从 1~n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。

1≤n≤15

样例

输入样例：
3
输出样例：

3
2
2 3
1
1 3
1 2
1 2 3

C++ 代码

#include<iostream>

using namespace std;

int n;
int st[25];//枚举每位状态:0没考虑，1选，2不选；
void dfs(int u){

    if(u>n){

        for(int i=1;i<=n;i++)
        if(st[i]==1)cout<<i<<" ";
        cout<<endl;
        return ;
    }


    //分枝
    st[u]=2;//不选
    dfs(u+1);
    st[u]=0;

    st[u]=1;//选
    dfs(u+1);
    st[u]=0;


    return;


}

int main(){
    cin>>n;
    dfs(1);



    return 0;
}

算法解析

这道题的思路很好想，可以明显看出来可以用区间合并做，只要你学过区间合并，就肯定能想起来

温馨提示：区间合并是在算法基础课的第一章的最后一道题中

扩展题：区间合并

算法思想

1：把数组按照左端点从小到大的顺序排序

2：维护一个区间，和下一个区间进行对比，会分为三种情况

• 第一种：当前的区间完全被上一个区间所覆盖，这个时候我们就不用管，直接跳过就可以了
• 第二种：当前的区间比上一个区间的长度长，这个时候我们就更新右端点为长的内一个
• 第三种：当前的区间左端点大于上一个区间的右端点；此时的话，我们维护的区间要从上一个更新到当前的区间，因为上一个区间的长度已经达到最长了
• 

代码

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Comparator;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);

        int L = in.nextInt();
        int m = in.nextInt();

        List<int[]> list = new ArrayList<>();      //初始化
        for(int i = 0; i < m; i ++)
        {
            int l = in.nextInt();
            int r = in.nextInt();
            list.add(new int[]{l,r});
        }

        list.sort(new Comparator<int[]>(){        //按照左端点进行排序
            @Override
            public int compare(int[] a, int[] b){
                return a[0] - b[0];
            }
        });

        List<int[]> arr = new ArrayList<>();

        int l = Integer.MIN_VALUE;
        int r = Integer.MIN_VALUE;
        for(int[] a : list)                       //分为三种情况
        {
            if(a[0] > r){                         //第三种情况,有了新区间以后，把旧区间顶到arr中去
                if(l != Integer.MIN_VALUE) arr.add(new int[]{l,r});
                l = a[0];
                r = a[1];
            }else{
                r = Math.max(r,a[1]);             //第一二种情况，比较右区间的大小，取最大就行
            }
        }

        if(l != Integer.MIN_VALUE) arr.add(new int[]{l,r}); //把最后一个区间单独加到新数组中去,因为已经没有新区间可顶了

        int res = 0;
        for(int[] p : arr){
            res += (p[1] - p[0] + 1);             //每个区间的长度是l - r + 1
        }

        System.out.print(L + 1 - res);            //因为是从0~500，所以有500+1个数
    }
}

代码

/*
 * Project: 0x17_二叉堆
 * File Created:Friday, January 15th 2021, 7:29:20 pm
 * Author: Bug-Free
 * Problem:AcWing 147. 数据备份
 */
#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 100006;

struct L {
    int d, prv, nxt, th;
} p[N];

struct H {
    int D, tp;
} h[N];

int tot = 0;

void up(int i) {
    while (i > 1) {
        if (h[i].D < h[i >> 1].D) {
            swap(h[i], h[i >> 1]);
            swap(p[h[i].tp].th, p[h[i >> 1].tp].th);
            i >>= 1;
        } else {
            return;
        }
    }
}

void down(int i) {
    int ii = i << 1;
    while (ii <= tot) {
        if (ii < tot && h[ii].D > h[ii + 1].D) {
            ++ii;
        }
        if (h[ii].D < h[i].D) {
            swap(h[ii], h[i]);
            swap(p[h[ii].tp].th, p[h[i].tp].th);
            i = ii;
            ii = i << 1;
        } else {
            return;
        }
    }
}

void DeL(int i) {
    p[p[i].prv].nxt = p[i].nxt;
    p[p[i].nxt].prv = p[i].prv;
}

void DeH(int i) {
    if (i == --tot + 1) {
        return;
    }
    swap(h[i], h[tot + 1]);
    swap(p[h[i].tp].th, p[h[tot + 1].tp].th);
    up(i);
    down(i);
}

int main() {
    int n, k, pre;
    cin >> n >> k >> pre;
    for (int i = 1; i < n; i++) {
        int w;
        cin >> w;
        p[i].d = w - pre;
        p[i].prv = i - 1;
        p[i].nxt = i + 1;
        p[i].th = ++tot;
        pre = w;
        h[tot].D = p[i].d;
        h[tot].tp = i;
        up(tot);
    }
    int ans = 0;
    for (int i = 1; i <= k; i++) {
        ans += h[1].D;
        if (!p[h[1].tp].prv || p[h[1].tp].nxt == n) {
            if (!p[h[1].tp].prv) {
                DeH(p[p[h[1].tp].nxt].th);
                DeL(p[h[1].tp].nxt);
            } else {
                DeH(p[p[h[1].tp].prv].th);
                DeL(p[h[1].tp].prv);
            }
            DeL(h[1].tp);
            DeH(1);
        } else {
            int tp0 = h[1].tp;
            h[1].D = p[p[h[1].tp].prv].d + p[p[h[1].tp].nxt].d - p[h[1].tp].d;
            p[h[1].tp].d = h[1].D;
            down(1);
            DeH(p[p[tp0].prv].th);
            DeH(p[p[tp0].nxt].th);
            DeL(p[tp0].prv);
            DeL(p[tp0].nxt);
        }
    }
    cout << ans << endl;
    return 0;
}

#include<iostream>

using namespace std;

int main(){
    int a,b;
   cin>> a>> b;
   cout<<a+b<<endl;
   return 0;
}

#include <iostream>
using namespace std;
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    int a[n+5] = {0};
    for(int i=0;i<m;i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        for(int j=x;j<=y;j++)
        a[j] = 1;
    }
    int ans = 0;
    for(int i=0;i<=n;i++)
    if(!a[i]) ans++;
    printf("%d",ans);
    return 0;
}

#include<iostream>

using namespace std;

int main(){

    int a,b,c,d;

    cin>>a>>b>>c>>d;

    cout<<"DIFERENCA ="<<" "<<a*b-c*d <<endl;

    return 0;
}