满足如下条件的序列 X（序列中元素被标号为 1、2、3…m）被称为“加成序列”：
- X[1]=1
- X[m]=n
- X[1]<X[2]<…<X[m−1]<X[m]
- 对于每个 k（2≤k≤m）都存在两个整数 i 和 j （1≤i,j≤k−1，i 和 j 可相等），使得 X[k]=X[i]+X[j]。
你的任务是：给定一个整数 n，找出符合上述条件的长度 m 最小的“加成序列”。
如果有多个满足要求的答案，只需要找出任意一个可行解。
输入格式
输入包含多组测试用例。
每组测试用例占据一行，包含一个整数 n。
当输入为单行的 0 时，表示输入结束。
输出格式
对于每个测试用例，输出一个满足需求的整数序列，数字之间用空格隔开。
每个输出占一行。
数据范围
1≤n≤100
输入样例：
5 7 12 15 77 0输出样例：
1 2 4 5 1 2 4 6 7 1 2 4 8 12 1 2 4 5 10 15 1 2 4 8 9 17 34 68 77import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class Main { static int N=200,id=1,id1=1,n,m; static int a[]=new int[N]; static BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { String line; while(!(line=br.readLine()).equals("0")){ n=Integer.parseInt(line); if(n==1){ bw.write(1+"\n"); continue; } a[1]=1; for (int m = 2; m <= n; m++) { // a[m]=n;f[n]=true; if(dfs(2,m,n,1)){ break; } // a[m]=0;f[n]=false; } } bw.flush(); br.close(); bw.close(); } static boolean dfs(int k,int m,int n,int maxz) throws IOException { if(k==m){ for (int i = 1; i < m; i++) { for (int j = 1; j < m; j++) { if(a[i]+a[j]==n){ StringBuilder stringBuilder=new StringBuilder(); for (int g = 1; g < m; g++) { stringBuilder.append(a[g]+" "); } stringBuilder.append(n+""); bw.write(stringBuilder.toString()+"\n"); bw.flush(); return true; } } } return false; } for (int i = k-1; i > 0; i--) { for (int j = k-1; j >0; j--) { if(a[i]+a[j]>maxz && a[i]+a[j]<n){ a[k]=a[i]+a[j]; if(dfs(k+1, m,n,a[k]))return true; a[k]=0; } } } return false; } }送礼物
达达帮翰翰给女生送礼物，翰翰一共准备了 N 个礼物，其中第 i 个礼物的重量是 G[i]。
达达的力气很大，他一次可以搬动重量之和不超过 W 的任意多个物品。
达达希望一次搬掉尽量重的一些物品，请你告诉达达在他的力气范围内一次性能搬动的最大重量是多少。
输入格式
第一行两个整数，分别代表 W 和 N。
以后 N 行，每行一个非负整数表示 G[i]。
输出格式
仅一个整数，表示达达在他的力气范围内一次性能搬动的最大重量。
数据范围
1≤N≤46,
1≤W≤231−1,
0≤G[i]≤231−1
输入样例：
20 5 7 5 4 18 1输出样例：
19import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Arrays; import java.util.StringTokenizer; public class Main { static int N=200,id=1,id1=1,n,m,k,cnt; static long w,res=0; static long weight[]=new long[1<<24]; static long a[]=new long[N]; // static int group[]=new int[N]; static BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer st=new StringTokenizer(br.readLine()); w=Long.parseLong(st.nextToken()); n=Integer.parseInt(st.nextToken()); for (int i = 0; i < n; i++) { a[i]=Integer.parseInt(br.readLine()); } //动态规划求解会超出应int的范围，而且时间复杂度太高 //所以可以写一个递归版的动态规划 //但是如果我们暴力的去求解一到n，那这样必然会超时 //我们可以先暴力的枚举1~n/2 然后再去暴力的枚举后半部分 //当后半部分枚举完之后 我们可以2分前半部分的结果 //从而找到最终的最大值 k=n/2; dfs1(0,0); //排序加去重 Arrays.sort(weight,0,cnt); unique(); dfs2(k,0); bw.write(res+""); bw.flush(); br.close(); bw.close(); } static void unique(){ int cur=1; for (int i = 1; i < cnt; i++) { if(weight[i]!=weight[i-1]){ weight[cur++]=weight[i]; } } cnt=cur; } static void dfs2(int u,long s){ if(u==n){ int l=0,r=cnt-1; while(l<r){ int mid=(l+r+1)>>1; if(s+weight[mid]<=w){ l=mid; }else{ r=mid-1; } } res=Math.max(res, s+weight[l]); return; } if(s+a[u]<=w)dfs2(u+1, s+a[u]); dfs2(u+1, s); } static void dfs1(int u,long s){//枚举到第u件物品了,总和为s if(u==k){ weight[cnt++]=s; return; } if(s+a[u]<=w)dfs1(u+1, s+a[u]); dfs1(u+1, s); } }排书
给定 n 本书，编号为 1∼n。
在初始状态下，书是任意排列的。
在每一次操作中，可以抽取其中连续的一段，再把这段插入到其他某个位置。
我们的目标状态是把书按照 1∼n 的顺序依次排列。
求最少需要多少次操作。
输入格式
第一行包含整数 T，表示共有 T 组测试数据。
每组数据包含两行，第一行为整数 n，表示书的数量。
第二行为 n 个整数，表示 1∼n 的一种任意排列。
同行数之间用空格隔开。
输出格式
每组数据输出一个最少操作次数。
如果最少操作次数大于或等于 5 次，则输出5 or more。
每个结果占一行。
数据范围
1≤n≤15
输入样例：
3 6 1 3 4 6 2 5 5 5 4 3 2 1 10 6 8 5 3 4 7 2 9 1 10输出样例：
2 3 5 or more解题思路:
1. 操作分析与搜索框架
每次操作可以抽取任意长度的连续一段，插入到任意位置。这样一次操作会改变序列的局部顺序，可能同时修正多处错位。
直接暴力搜索状态空间会爆炸，但观察到最少操作次数被限制在很小的范围（≤4≤4 才需要精确值），所以可以采用迭代加深（IDDFS）配合启发式估价（A），即IDA算法。
我们从深度上限max_depth = 0开始，每次max_depth++，在 DFS 中一旦当前深度 + 估价函数值 > 上限就立即回溯，直到找到解或上限达到 5 停止。
2. 估价函数的设计
估价函数需要给出“从当前状态到目标状态至少还需要多少步”。
一次剪切插入操作最多能同时修正多少处“不连续”的错误？
考察相邻关系：若排列中
a[i] + 1 == a[i+1]，则这一对是“正确的后继”，否则是“错误的后继”。目标状态有 n−1n−1 对正确的后继（1→2,2→3,…,n−1→n1→2,2→3,…,n−1→n）。
一次剪切插入操作最多能改变3 个位置的后继关系：被剪切段的前后、插入点的前后。因此最多可以修复 3 个错误后继。
设当前排列的错误后继个数为
cnt，则最少还需要⌈cnt/3⌉⌈cnt/3⌉ 步。这就是启发式下界。
实际编码时，f() = cnt / 3即可，当cnt=0时自然为 0。
3. 剪枝与搜索策略
为了避免重复搜索对称操作，可以规定：只将抽取段向后移动。因为把 A 段移动到 B 之前，等价于把 B 段移动到 A 之后，所以只枚举“把段插入到更后面的位置”就能覆盖所有情况。
具体枚举方式：
枚举抽取段的长度
len（1∼n−11∼n−1 或 1∼n1∼n）。枚举抽取的起始位置
l，得到区间[l, r]（r = l+len-1）。枚举插入位置
k（k在r之后），表示将该段插入到原来第k个元素之后（即r+1 \sim k这些元素整体前移，然后跟上原[l, r]段）。
这样生成的每个新状态都是唯一的，且不会遗漏任何本质不同的操作。
递归前备份当前序列到数组na[depth]，递归结束后恢复，保证回溯正确。
4. 终止条件
若
check()成立（即序列完全有序），返回成功。若
depth + f() > max_depth，立即剪枝返回失败。若
max_depth >= 5仍未找到解，直接输出5 or more。
5. 时间复杂度
n≤15n≤15，深度上限最多为 4。
分枝数：对于每个状态，长度有 O(n)O(n) 种，起点 O(n)O(n)，插入点 O(n)O(n)，总约 O(n3)O(n3)，但加上启发式剪枝后实际访问的状态数非常少，完全可以通过。
import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Main { static int N=20,id=1,id1=1,n,m,k,cnt,t; static long w,res=0; static int na[][]=new int[5][N];//记录递归过程中的a 方便恢复现场 static int a[]=new int[N]; // static int group[]=new int[N]; static BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { t=Integer.parseInt(br.readLine()); //StringTokenizer st=new StringTokenizer(br.readLine()); for (int i = 0; i < t; i++) { n=Integer.parseInt(br.readLine()); StringTokenizer st=new StringTokenizer(br.readLine()); for (int j = 0; j < n; j++) { a[j]=Integer.parseInt(st.nextToken()); } int depth=0; while(depth<5 && !dfs(0,depth))depth++; if(depth<5){ bw.write(depth+"\n"); }else{ bw.write("5 or more\n"); } } bw.flush(); br.close(); bw.close(); } static boolean check(){ for (int i = 0; i+1 < n; i++) { if(a[i]+1!=a[i+1])return false; } return true; } static int f(){ //每次最多修复3对相邻的关系 int sum=0; for (int i = 0; i+1 < n; i++) { if(a[i]+1!=a[i+1])sum++; } if(sum==0)return 0; return sum/3+1;//最少需要操作这么多次 } static boolean dfs(int depth,int maxdepth){ if(depth+f()>maxdepth)return false;//f是一个预估函数 if(check())return true; for (int len = 1; len < n; len++) { //把A段放在B之后 和 B段放在A之前是一样的 所以统一向后放 for (int l = 0; l < n; l++) { int r=l+len-1; //把l-r这一段放在k的后面 System.arraycopy(a, 0, na[depth], 0, n); for (int k = r+1; k < n; k++) { //先把r+1 到k 移到l开始的位置 再添加l-r的值 int y=l; for (int i = r+1; i <= k; i++) { a[y++]=na[depth][i]; } for (int i = l; i <= r; i++) { a[y++]=na[depth][i]; } if(dfs(depth+1, maxdepth))return true; System.arraycopy(na[depth], 0, a, 0, n);//恢复现场 } } } return false; } }回转游戏
如下图所示，有一个#形的棋盘，上面有 1,2,3 三种数字各 8 个。
给定 8 种操作，分别为图中的 A∼H。
这些操作会按照图中字母和箭头所指明的方向，把一条长为 7 的序列循环移动 1 个单位。
例如下图最左边的#形棋盘执行操作 A 后，会变为下图中间的#形棋盘，再执行操作 C 后会变成下图最右边的#形棋盘。
给定一个初始状态，请使用最少的操作次数，使#形棋盘最中间的 8 个格子里的数字相同。
输入格式
输入包含多组测试用例。
每个测试用例占一行，包含 24 个数字，表示将初始棋盘中的每一个位置的数字，按整体从上到下，同行从左到右的顺序依次列出。
输入样例中的第一个测试用例，对应上图最左边棋盘的初始状态。
当输入只包含一个 0 的行时，表示输入终止。
输出格式
每个测试用例输出占两行。
第一行包含所有移动步骤，每步移动用大写字母 A∼H 中的一个表示，字母之间没有空格，如果不需要移动则输出No moves needed。
第二行包含一个整数，表示移动完成后，中间 8 个格子里的数字。
如果有多种方案，则输出字典序最小的解决方案。
输入样例：
1 1 1 1 3 2 3 2 3 1 3 2 2 3 1 2 2 2 3 1 2 1 3 3 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 0输出样例：
AC 2 DDHH 2import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Main { static int N=20,id=1,id1=1,n,m,k,cnt,t; static long w,res=0; /* 一 二 0 1 2 3 八 4 5 6 7 8 9 10 三 11 12 七 13 14 15 16 17 18 19 四 20 21 22 23 六 五 */ static int a[][]={ {0,2,6,11,15,20,22},{1,3,8,12,17,21,23},{10,9,8,7,6,5,4}, {19,18,17,16,15,14,13},{23,21,17,12,8,3,1},{22,20,15,11,6,2,0}, {13,14,15,16,17,18,19},{4,5,6,7,8,9,10} }; static int center[]={6,7,8,11,12,15,16,17};//中心几个点的就是坐标 static int opposite[]={5,4,7,6,1,0,3,2};//存相互抵消的操作 比如说a和b static int q[]=new int[24]; static int path[]=new int[100]; static BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { //t=Integer.parseInt(br.readLine()); //StringTokenizer st=new StringTokenizer(br.readLine()); String line; while(!(line=br.readLine()).equals("0")){ StringTokenizer st=new StringTokenizer(line); for (int i = 0; i < 24; i++) { q[i]=Integer.parseInt(st.nextToken()); } int depth=0; while(!dfs(0,depth,-1))depth++; if(depth==0){ bw.write("No moves needed\n"); bw.write(q[6]+"\n"); continue; } StringBuilder stringBuilder=new StringBuilder(); for (int i = 0; i < depth; i++) { stringBuilder.append((char)(path[i]+'A')); } bw.write(stringBuilder.toString()+"\n"); bw.write(q[6]+"\n"); } bw.flush(); br.close(); bw.close(); } static int f(){ int sum[]=new int[4]; for (int i = 0; i < 8; i++) { sum[q[center[i]]]++; } //每次移动我会最多会移进来一个新的数 //先统计中间的那几个点次数最多的数是多少 然后用八减去这个值，就是预估值你好 int cnt=0; for (int i = 1; i < 4; i++) {//只有1~3这几个数字 cnt=Math.max(cnt, sum[i]); } return 8-cnt; } static void operate(int u){ //每次操作都相当于是将第一个移到最后，然后把剩下的前移 int t=q[a[u][0]]; for (int i = 1; i < 7; i++) { q[a[u][i-1]]=q[a[u][i]]; } q[a[u][6]]=t; } static boolean dfs(int depth,int maxdepth,int last){ if(depth+f()>maxdepth)return false; if(f()==0)return true; for (int i = 0; i < 8; i++) { if(opposite[i]==last)continue; operate(i); path[depth]=i; if(dfs(depth+1, maxdepth, i))return true; operate(opposite[i]);//恢复现场 } return false; } }
