前言

题目地址： http://acm.suse.edu.cn/contest.php?cid=1081

A.半数集问题；

题目：
给定一个自然数n，由n开始可以依次产生半数集set(n)中的数如下：
(1) n∈set(n)；
(2) 在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；
(3) 按此规则进行处理，直到不能再添加自然数为止。
例如，set(6)={6,16,26,126,36,136}。半数集set(6)中有6个元素。注意，半数集是多重集。对于给定的自然数n，计算半数集set(n)中的元素。
分析：

  • 首先理解题意，在最开始的num左边加上一个数，这个数 x 必须满足 x <= last / 2(上一个x)
  • 会不会存在重复的情况？答案是YES,但是这道题服务器没有对应样例，所以可以不用考虑，但是还是要简单说一下：
    • 当 n = 24 时 他的下一个状态就是[1, 12], 而我如果选择2进行拼接，那么2的下一个状态就是1， 与我第一个状态选择12就会与之重叠， 所以我们最好使用set将所有的答案全部存储一下，最后再 for 遍历打印所以的就可以了
  • 解题思路：
    1. 可以使用递归，当满足last = 1时结束递归，
    2. 也可以使用队列，将所有的第一个状态push到queue中，然后使用bfs模板进行以此遍历即可

代码：

#include <iostream>
#include <set>
#include <cmath>
using namespace std;
int n;
// 使用字母
int t(int l, int r) {
    int len = 0, m = r;
    while (m) {
        len ++;
        m /= 10;
    }
    l *= pow(10, len);
    return l + r; // 拼接字符串
} // 时间复杂度 o(logn)
// 使用字符串
string st(string l, int r) {
  return "" + r + l;
}// 时间复杂度o(1)
void dfs(int n, int u) {
    if (u <= 1) return;
    for (int i = 1; i <= u / 2; i ++ ) {
        cout << i << "" << n << endl;
        dfs(t(i, n), i);
    }
} // 复杂度o(nlogn + nlogn) = o(nlogn) => 对于每一层的宽度小于等于n, 一共有logn层（每次折半）
 
int main() {
    scanf("%d", &n);
    cout << n << endl;
    dfs(n, n);
    return 0; 
}

/* 去重
void dfs1(int n, int u) {
  if (u <= 1) return;
  for (int i = 1; i <= u / 2; i ++ ) {
    int ne = t(i, n);
    set.insert(ne);
    dfs1(ne, i);
  }
}
for (auto i : set) {
  cout << i << endl;
}
*/

B.幂乘问题

快速求a^n次方

#include <iostream>
using namespace std;

int ans, n, a;
// 可以记录次数
int c(int a, int n) {
  if (n == 1) return a; 
  if (n & 1) {
    ans += 2;
    int t = c(a, n / 2);
    return t * t * 2;
  } else {
    ans ++;
    int t = c(a, n / 2);
    return t * t;
  }
} // 递归求幂=> o(logn)

// for快速幂 o(logn) 无法记录次数
int d(int a, int n) {
  int res = 1;
  while (n) {
    if (n & 1) res *= a;
    a *= a;
    n >>= 1;
  }
  return res;
} 
 
int main() {
  
  scanf("%d%d", &a, &n);
  int res = c(a, n);
  cout << res << endl << ans << endl;
  cout << d(a, n) << endl;
  return 0;
}

C: 活动安排问题

这个是一个非常典型的场所活动问题， 要求选择尽可能多的活动，并打印出来，
贪心问题，问题是如何去贪？优先选择进行时长短的，还是选最先开始的，还是选最早结束的？
显然，我们可以以此证明：

  1. 如果选择时长短的，那么有些活动结束时间晚，在后面的位置，而在前面的活动明显先选他，照时长排序的话，会导致这个活动前面的都选不了。
  2. 优先选择最先开始的，有第一场就直接从白天开到晚上，而中间小段时间的就选不了了。
  3. 优先选择最早结束的，如果优先选择最早结束的，那么后面的只要在他结束后开始就可以被选到，在第一次选择的时候，因为按照结束时间排序，对于2-4, 3-4, 我都无所谓，只要选择其中一个为答案第一个就可以了,因为前面几个选择的代价都不会影响到后续的选择。

代码如下：

#include <iostream>
#include <algorithm>
 
using namespace std;
const int N = 1e5 + 10;
int n;
struct node {
  int l, r, id;
  bool operator<(const node& t)const {
    return r < t.r;
  }
}a[N]; 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) {
        scanf("%d%d", &a[i].l, &a[i].r);
        a[i].id = i;
    }
    sort(a, a + n);
    int res = 0;
    for (int i = 1; i < n; i ++ ) {
        if (a[i].l >= a[res].r) {
            cout << a[i].id << " ";
            res = i;
        }
    }
    cout << endl;
    return 0;
}

D.SP2

求[l, r]中所有的质数，并打印出来

这里有非常多种方法，但是我建议使用比较简单的方法就行了：
但是要注意数据范围，此题的数据范围到了1e9， 非常接近int的最大值了，所以为了保险建议开long long，但是int也行
首先输入l, r， 然后for(int i = l; i <= r; i ++ ) if (check(i)) printf("%d,",i);就可以了
主要是对check(int x)的编写，而对于本题来说check函数就是判断x是否为质数的函数

那么我们就有非常多种方法了：

  1. 暴力判断质数， 从[2, x - 1]里面去找x的因数，没找到就返回true，找到了说明x不是质数返回false;
    bool check(int x) {
      if (x <= 1) return false;
      for (int i = 2; i < x; i ++ ) {
        if (x % i == 0) return false;
      }
      return true;
    }
  2. 对于暴力判断质数来说，他的复杂度为O(n),如果说要查询非常多次呢？那么明显有点力不从心了。所以我们就要对这个暴力判断质数
    首先要举例说明一下；
    判断16是不是质数 -> 2 8, 4 4, 8 2
    判断24是不是质数 -> 2     12, 3 8, 4 6, 6 4, 8 3, 12 2
    判断23是不是质数 -> 2, 3, …., 22
    从第一个和第二个样例中，我们明显可以看见有重复的查询，那么是从哪儿开始重复的呢？
    设i = [2, x - 1], 如果i是x的因子，那么对应的另外一个就是x/i
    令 i = x/ i => i^2 = x => i = [2, √x],到了这里我们就已经推出了对于判断单个质数的最优解是[2, √x]
    *翻译成代码：
    bool check(int x) {
      for (int i = 2; i <= sqrt(x); i ++ ) {
        if (x % i == 0) return false;
      }
      return true;
    }
    当然，对于上面这份代码还不是最优解，因为他还使用了一个函数sqrt(int x)求根，所以还可以进一步优化
    bool check(int x) {
      for (int i = 2; i * i <= x; i ++ ) {
        if (x % i == 0) return false;
      }
      return true;
    }

    E. 俄式乘法

    使用俄式乘法计算n*m;

暴力枚举就可以了

long long mul(long long x, long long y) {
    long long sum = 0;
    while (x > 1) {
        if (x % 2 == 1) sum += y;
        y *= 2;
        x /= 2;
    }
    sum += y;
    return sum;
}
 
int main() {
    scanf("%lld%lld", &x, &y);
    cout << mul(x, y) << endl;
//  cout << x * y;
     
     
    return 0;
}

F.投资问题

m元钱，投资n个项目。效益函数fi(x)，表示第i个项目投x元的效益，i=1，2，…，n。求如何分配每个项目的钱数使得总效益最大？实例：5万元，投资给4个项目，效益函数：

输入m, n， 求投资方案数

最开始的时候我还以为是动态规划求最大收益，做了接近半小时结果一看不是求最大收益，而是求有多少中投资的方案
真的谢谢您

#include <iostream>
using namespace std;
 
const int N = 1e3 + 10;
int dp[N][N];
int n, m;
int dfs(int u, int sum) {
    // 到了倒数第二层的时候，最后一层的可选数为总的可选数减去之前选了的总数再加一
    if (u == n - 1) {
        // cout << u << " - " << sum << " -> " << m - sum + 1 << endl;
        return m - sum + 1;
    }
    // 没有到最后一层，那么我就去变量你当前状态的所有下一个可行状态
    // 可行范围[0, m - sum] =>(m - sum - 0 + 1)个可行状态
    int res = 0;
    for (int i = 0; i <= m - sum; i ++ ) res += dfs(u + 1, sum + i);
    // cout << u << " - " << sum << " -> " << res << endl;
    // 将他的所有子状态的可选方案返回给父状态
    return res;
}
 
int main() {
//  int n, m;
    scanf("%d%d", &m, &n);
    // 如果层数大于1， 那么就深搜, 否则直接打印 m + 1
    if (n > 1) cout << dfs(1, 0) << endl;
    else cout << m + 1 << endl;
    return 0; 
}

附上此题动态规划求最大收益代码：有兴趣可以看看

#include <iostream>
#include <algorithm>
using namespace std;
int n,m;
const int N = 1e3 + 10;
 
int dp[N][N];
int f[N][N];
 
int main()
{
    cin >> n >> m;
     
    for (int i = 0; i <= m; i ++ )
        for (int j = 1; j <= n; j ++ )
            cin >> f[j][i];
     
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            for (int k = 0; k <= j; k ++ )
                dp[i][j] = max(dp[i][j],dp[i - 1][j - k] + f[i][k]);
    
    cout << dp[n][m] << endl;
    return 0;
}