第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-645 加法分解

#include<stdio.h>
#include<malloc.h>
int sum = 0;
void a(int n, int count, int *p){
  int i;
  if(n==0){
    printf("%d=", sum);
    for(i=0;i<count;i++)
      if(i==count-1)
        printf("%d\n", p[i]);
      else
        printf("%d+", p[i]);
    return;
  }
  for(i=1;i<=n;i++){
    p[count] = i;
    a(n-i, count+1, p);
  }
  return;
}
void b(int n, int count, int *p){
  int i;
  if(n==0){
    printf("%d=", sum);
    for(i=0;i<count;i++)
      if(i==count-1)
        printf("%d\n", p[i]);
      else
        printf("%d+", p[i]);
    return;
  } 
  int k = count>0 ? p[count-1] : 1;
  for(i=k;i<=n;i++){
    p[count] = i;
    b(n-i, count+1, p);
  }
  return;
}
int main(){
  int n, m;
  scanf("%d%d", &n, &m);
  if(n<=15){
    sum = n;
    int *p = (int*)malloc(sizeof(int)*n);
    if(m==1)
      a(n, 0, p);
    else if(m==2)
      b(n, 0, p);
  }
  return 0;
}

#include<iostream>
using namespace std;
int sum = 0;
void dfs1(int n,int count,int*p)
{
  if(n==0)
  {
    cout<<sum<<"=";
    for(int i=0;i<count;i++)
      if(i==count-1)
        cout<<p[i]<<endl;
      else
        cout<<p[i]<<"+";
    return;
  }
  for(int i=1;i<=n;i++)
  {
    p[count]=i;
    dfs1(n-i,count+1,p);
  }
  return;
}
void dfs2(int n,int count,int*p)
{
  if(n==0)
  {
    cout<<sum<<"=";
    for(int i=0;i<count;i++)
      if(i==count-1)
        cout<<p[i]<<endl;
      else
        cout<<p[i]<<"+";
    return;
  }
  int k = count>0 ? p[count-1] : 1;
  for(int i=k;i<=n;i++)
  {
    p[count] = i;
    dfs2(n-i,count+1,p);
  }
}
int main()
{
  int n,m;
  cin>>n>>m;
  sum = n;
  int* p = new int[n];
  if(m==1)
    dfs1(n,0,p);
  else if(m==2)
    dfs2(n,0,p);
  return 0;
}

import java.io.*;
import java.util.*;
 
public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] split = br.readLine().split(" ");
    int n = Integer.parseInt(split[0]);
    int flag = Integer.parseInt(split[1]);
    Temp645 obj = new Temp645(n, flag);
    obj.dfs();
    System.out.println(obj.builder);
  }
}
class Temp645{
  int n;//待分解数
  int flag;//分解类型
  int sum = 0;//单前总和
  List<Integer> list = new ArrayList<>();//存储实时分解项
  StringBuilder builder = new StringBuilder();//存储最终答案
  List<List<Integer>> listAll = new ArrayList<>();//存储类型2的不重复集合项
  
  public Temp645(int n, int flag) {
    this.n = n;
    this.flag = flag;
  }
  
  public void dfs() {//由于分解个数无要求，不传“step”参数
    if(sum >= n) {//当前和大于n时，直接返回，等于时作进一步处理
      if(sum == n) {
        if(flag == 1) {
          print1();
        }else {
          print2();
        }
        return;
      }else {
        return;
      }
    }
    for(int i = 1; i <= n; i++) {
      if(sum < n) {//当前和比目标和小时才累加，大于时，不处理
        sum += i;
        list.add(i);//存放实时分解项
        dfs();
        sum -= i;//回溯
        list.remove(list.size() - 1);
      }
    }
  }
  
  private void print1() {//将此时list中的分解项作格式化处理，并拼接至builder
    builder.append(n + "=");
    for(int i = 0; i < list.size() - 1; i++) {
      builder.append(list.get(i) + "+");
    }
    builder.append(list.get(list.size() - 1) + "\n");//最后一项无加号
  }
  
  private void print2() {//主要实现对储存集合的集合的去重处理
    int []arr = new int[list.size()];//将原list中值拷贝到arr中
    for(int i = 0; i < list.size(); i++) {
      arr[i] = list.get(i);
    }
    Arrays.sort(arr);//排序
    for(int i = 0; i < listAll.size(); i++) {//遍历存放集合的集合
      List<Integer> temp = listAll.get(i);
      int j = 0;
      for(j = 0; j < temp.size(); j++) {
        if(temp.get(j) != arr[j]) {//当有一项不同时，则证明此时的两集合不同，进行下一集合比较
          break;
        }
      }
      if(j == temp.size()) {//表示当前两集合元素完全相同
        return;//直接返回，不添加到去重集合和builder
      }
    }
    List<Integer> list2 = new ArrayList<>();//将排好序的arr转化至集合
    for(int i = 0; i < arr.length; i++) {
      list2.add(arr[i]);
    }
    listAll.add(list2);//添加至去重集合
    print1();//将此集合拼接至builder
  }
}

def f1(s):
    if s == n:
        print(str(n) + "=" + "+".join(alist))
        return
    for i in range(n - s):
        alist.append(str(i + 1))
        f1(s + i + 1)
        alist.pop()
def f2(u, s):
    if s == n:
        print(str(n) + "=" + "+".join(alist))
        return
    for i in range(u, n - s):
        alist.append(str(i + 1))
        f2(i, s + i + 1)
        alist.pop()
        
alist = []
n, m= map(int, input().split())
if m == 1:
    f1(0)
else:
    f2(0, 0)