花了几天时间才做完一套试题，挺慢，不过收获不小，写一下自己的解题思路。试题链接
双核处理
一种双核CPU的两个核能够同时的处理任务，现在有n个已知数据量的任务需要交给CPU处理，假设已知CPU的每个核1秒可以处理1kb，每个核同时只能处理一项任务。n个任务可以按照任意顺序放入CPU进行处理，现在需要设计一个方案让CPU处理完这批任务所需的时间最少，求这个最小的时间。
输入描述:
输入包括两行：
第一行为整数n(1 ≤ n ≤ 50)
第二行为n个整数length[i](1024 ≤ length[i] ≤ 4194304)，表示每个任务的长度为length[i]kb，每个数均为1024的倍数。
输出描述:
输出一个整数，表示最少需要处理的时间
输入例子1:
5
3072 3072 7168 3072 1024
输出例子1:
9216
解题思路
一个cpu处理n1个任务所用时间为t1，当t1最接近(sum/2)时，
此时t2也最接近(sum/2)，完成任务所需最小时间就是t1、t2中的最小值。
也就是说只要求出一个cpu所处理任务即可。
现在的目标是：在(sum/2)时间内，能完成的最多任务。也就是背包问题了
public class MultiKernel {
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
int []arr=new int[n];
int sum=0;
for(int i=0;i<n;i++) {
arr[i] = scanner.nextInt()>>9;
sum+=arr[i];
}
//先排序
Arrays.sort(arr);
System.out.print(concurent2(arr,sum)<<9);
}
/*
dep[i]表示时间为i时能完成的最多任务重量(时间)。
dep[j]=max(dep[j],dep[j-t[i]]+t[i])表示找出选择第i个任务和不选第i个任务时的最大值。
*/
public static int concurent2(int[] arr,int sum){
//java语言特性，全为0
int []dep=new int[sum/2+1];
dep[0]=0;
int n=arr.length;
int i,j;
for(i=0;i<n;i++){
for(j=sum/2;j>=arr[i];j--){
dep[j]=Math.max(dep[j],dep[j-arr[i]]+arr[i]);
}
}
//找出两个cpu中所用时间最长的。这就是最长时间000
return Math.max(sum-dep[sum/2],dep[sum/2]);
}
}
结果
赶去公司
终于到周末啦！小易走在市区的街道上准备找朋友聚会，突然服务器发来警报,小易需要立即回公司修复这个紧急bug。假设市区是一个无限大的区域，每条街道假设坐标是(X，Y)，小易当前在(0，0)街道，办公室在(gx,gy)街道上。小易周围有多个出租车打车点，小易赶去办公室有两种选择，一种就是走路去公司，另外一种就是走到一个出租车打车点，然后从打车点的位置坐出租车去公司。每次移动到相邻的街道(横向或者纵向)走路将会花费walkTime时间，打车将花费taxiTime时间。小易需要尽快赶到公司去，现在小易想知道他最快需要花费多少时间去公司。
输入描述:
输入数据包括五行:
第一行为周围出租车打车点的个数n(1 ≤ n ≤ 50)
第二行为每个出租车打车点的横坐标tX[i] (-10000 ≤ tX[i] ≤ 10000)
第三行为每个出租车打车点的纵坐标tY[i] (-10000 ≤ tY[i] ≤ 10000)
第四行为办公室坐标gx,gy(-10000 ≤ gx,gy ≤ 10000),以空格分隔
第五行为走路时间walkTime(1 ≤ walkTime ≤ 1000)和taxiTime(1 ≤ taxiTime ≤ 1000),以空格分隔
输出描述:
输出一个整数表示，小易最快能赶到办公室的时间
输入例子1:
2
-2 -2
0 -2
-4 -2
15 3
输出例子1:
42
解题思路
这道题初看时是一道关于图的回溯问题，但是看一下数值范围就会发现如果是回溯的话肯定会超时。再仔细阅读发现这题很简单。
(X1,Y1)和(X2,Y2)的最短距离就是abs(X1-X2)+abs(Y1-Y2)
找出完全步行的最短时间再和先到停车点再到公司的最短时间比较，找到最小的即可
public class GotoCompany {
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
int x[]=new int[n];
int y[]=new int[n];
int gX,gY,walkTime,taxiTime;
int i,j;
for(i=0;i<n;i++){
x[i]=scanner.nextInt();
}
for(i=0;i<n;i++){
y[i]=scanner.nextInt();
}
gX=scanner.nextInt();
gY=scanner.nextInt();
walkTime=scanner.nextInt();
taxiTime=scanner.nextInt();
//完全步行所用时间
int minTime=(Math.abs(gX)+Math.abs(gY))*walkTime;
int curTime;
for(i=0;i<n;i++){
curTime=0;
//走到停车点所用时间
curTime+=walkTime*(Math.abs(x[i])+Math.abs(y[i]));
//加上从停车点到公司时间
curTime+=taxiTime*(Math.abs(gX-x[i])+Math.abs(gY-y[i]));
//比较
minTime=curTime<minTime?curTime:minTime;
}
System.out.print(minTime);
}
}
结果
调整队形
在幼儿园有n个小朋友排列为一个队伍，从左到右一个挨着一个编号为(0~n-1)。其中有一些是男生，有一些是女生，男生用'B'表示，女生用'G'表示。小朋友们都很顽皮，当一个男生挨着的是女生的时候就会发生矛盾。作为幼儿园的老师，你需要让男生挨着女生或者女生挨着男生的情况最少。你只能在原队形上进行调整，每次调整只能让相邻的两个小朋友交换位置，现在需要尽快完成队伍调整，你需要计算出最少需要调整多少次可以让上述情况最少。例如：
GGBBG -> GGBGB -> GGGBB
这样就使之前的两处男女相邻变为一处相邻，需要调整队形2次
输入描述:
输入数据包括一个长度为n且只包含G和B的字符串.n不超过50.
输出描述:
输出一个整数，表示最少需要的调整队伍的次数
输入例子1:
GGBBG
输出例子1:
2
解题思路
目的就是进行划分,从某一点开始左侧全为'G'(或'B'),右侧全为'B'(或'G').
在这里一个重要的规律是:将两个数arr[i] arrj交换,需要的交换次数是(j-i+1).
那么类似于快速排序中的hoare划分,循环将最左侧的'G'(或'B')与最右侧的'B'(或'G')交换,直到相交.这样就能得到一个划分.
取决于'G'和'B'的数目和位置,可能存在两种:1、'G'在左侧 2、'G'在右侧
为了方便我尝试分别将'G'放在左侧和右侧，再比较两者中交换次数较小者。
import java.util.Arrays;
import java.util.Scanner;
public class AdjustArray {
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
char[] arr= scanner.nextLine().toCharArray();
int n=arr.length;
int i,j;
int min=Integer.MAX_VALUE;
int curMin;
i=-1;
j=n;
curMin=0;
//复制数组
char[]temp= Arrays.copyOf(arr,arr.length);
//左侧全为'B'
while(i<j){
while(i<n-1&&temp[++i]=='G');
while(j>0&&temp[--j]=='B');
if(i<j) {
swap(temp, i, j);
curMin += (j - i);
}
}
min=curMin<min?curMin:min;
curMin=0;
i=-1;
j=n;
//左侧全为'G'
while(i<j){
while(i<n-1&&arr[++i]=='B');
while(j>0&&arr[--j]=='G');
if(i<j) {
swap(arr,i,j);
curMin += (j - i);
}
}
//比较找出最小值
min=curMin<min?curMin:min;
System.out.print(min);
}
public static void swap(char[] arr,int i,int j){
char temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
结果
消除重复元素
小易有一个长度为n序列，小易想移除掉里面的重复元素，但是小易想是对于每种元素保留最后出现的那个。小易遇到了困难,希望你来帮助他。
输入描述:
输入包括两行：
第一行为序列长度n(1 ≤ n ≤ 50)
第二行为n个数sequence[i](1 ≤ sequence[i] ≤ 1000)，以空格分隔
输出描述:
输出消除重复元素之后的序列，以空格分隔，行末无空格
输入例子1:
9
100 100 100 99 99 99 100 100 100
输出例子1:
99 100
解题思路
很简单，从后向前，使用set过滤，最后输出时也是从后向前。
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Q4 {
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
int []arr=new int[n];
int i,j;
for(i=0;i<n;i++){
arr[i]=scanner.nextInt();
}
Set<Integer> set=new HashSet<>();
int []res=new int[n];
j=0;
for(i=n-1;i>=0;i--){
if(!set.contains(arr[i])){
set.add(arr[i]);
res[j++]=arr[i];
}
}
for(j-=1;j>=0;j--){
System.out.print(res[j]);
if(j!=0)
System.out.print(" ");
}
}
}
结果
魔力手环
小易拥有一个拥有魔力的手环上面有n个数字(构成一个环),当这个魔力手环每次使用魔力的时候就会发生一种奇特的变化：每个数字会变成自己跟后面一个数字的和(最后一个数字的后面一个数字是第一个),一旦某个位置的数字大于等于100就马上对100取模(比如某个位置变为103,就会自动变为3).现在给出这个魔力手环的构成，请你计算出使用k次魔力之后魔力手环的状态。
输入描述:
输入数据包括两行：
第一行为两个整数n(2 ≤ n ≤ 50)和k(1 ≤ k ≤ 2000000000),以空格分隔
第二行为魔力手环初始的n个数，以空格分隔。范围都在0至99.
输出描述:
输出魔力手环使用k次之后的状态，以空格分隔，行末无空格。
输入例子1:
3 2
1 2 3
输出例子1:
8 9 7
解题思路
看到这道题首先想到的时循环x次后会回到初始状态，更巧的是我测试用70、80、90带入结果符合我的设想（只能说自己用来测试的数据太巧了），最后看了别人的解答才知道要用矩阵快速乘来计算。
以A={{1},{2},{3}}这个3行1列的矩阵为例，B={{1,0,1},{1,1,0},{0,1,1}}(这个矩阵要从列来看)对它进行一次操作相当于
A*B
要对A进行k次操作相当于
A*B^k
最后结合霍纳法则对B^k的计算进行简化
import java.util.Scanner;
public class MagicBand {
//使用矩阵快速乘思想
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
int k=scanner.nextInt();
int[][]arr=new int[1][n];
for(int i=0;i<n;i++)
arr[0][i]=scanner.nextInt();
//初始化系数矩阵，要从列看
int [][]mul=new int[n][n];
for(int i=0;i<n;i++){
mul[i][i]=1;
if(i<n-1){
mul[i+1][i]=1;
}else{
mul[0][i]=1;
}
}
//根据霍纳法则简化
while(k>0){
if(k%2==1)
arr=multi(arr,mul);
mul=multi(mul,mul);
k>>=1;
}
for(int i=0;i<n;i++){
System.out.print(arr[0][i]);
if(i!=n-1)
System.out.print(" ");
}
}
//矩阵相乘，通用版本
public static int[][] multi(int[][]a,int[][]b){
int row=a.length;
int n=a[0].length;
int col=b[0].length;
int [][]c=new int[row][col];
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
c[i][j]=0;
for(int k=0;k<n;k++){
//优化，可以节省一次乘法
if(a[i][k]==0||b[k][j]==0)
continue;
c[i][j]+=a[i][k]*b[k][j];
//注意不能超过100
if(c[i][j]>=100)
c[i][j]%=100;
}
}
}
return c;
}
/*
!!!!!!
下面是我使用自己的循环x次后会回到初始状态的思想做的，是错的，而且效率很低，引以为戒
*/
public static void resolve(int[]arr,int k,int[]origin){
final int n=arr.length;
int i,j;
int head=0;
boolean flag=true;
for(i=0;i<k;i++){
for(j=0;j<n;j++){
if(j==0){
head=(arr[0]+arr[1])%100;
}else{
arr[j]=(arr[j]+arr[(j+1)%n])%100;
}
}
if(head>1000000){
for(int p=0;p<n;p++)
arr[p]%=100;
}
arr[0]=head;
if(flag&&circle(origin,arr)){
k-=(i+1);
k%=(i+1)*n;
//注意这里结束后在外层循环i会自增所以需要再减去1
i=-1;
flag=false;
}
}
}
public static boolean circle(int[]origin,int[]copyofArr){
final int n=origin.length;
for(int i=0;i<n;i++){
if(i!=n-1){
if(origin[i]!=copyofArr[i+1])
return false;
}else{
if(origin[n-1]!=copyofArr[0])
return false;
}
}
return true;
}
}
结果
工作安排
现在有n位工程师和6项工作(编号为0至5)，现在给出每个人能够胜任的工作序号表(用一个字符串表示，比如：045，表示某位工程师能够胜任0号，4号，5号工作)。现在需要进行工作安排，每位工程师只能被安排到自己能够胜任的工作当中去，两位工程师不能安排到同一项工作当中去。如果两种工作安排中有一个人被安排在的工作序号不一样就被视为不同的工作安排，现在需要计算出有多少种不同工作安排计划。
输入描述:
输入数据有n+1行：
第一行为工程师人数n(1 ≤ n ≤ 6)
接下来的n行，每行一个字符串表示第i(1 ≤ i ≤ n)个人能够胜任的工作(字符串不一定等长的)
输出描述:
输出一个整数，表示有多少种不同的工作安排方案
输入例子1:
6
012345
012345
012345
012345
012345
012345
输出例子1:
720
解题思路
先理解下面：
- 每个工程师有且只有一项工作
- 不必所有工作都需要被做
很不幸最初我理解的是，所有工作必须被做，每个工程师可以有任意项工作。。
这道题很适合用回溯法解决。(仍然是看过解析才懂)
import java.util.*;
public class WorkArrangement {
//只要每个工程师有事做就行，不必每项任务都有人做
static int count=0;
Set<Integer> s = new HashSet<>(Arrays.asList(0,1,2,3,4,5));
static final int N=6;
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
//第i个工程师能做第j件工作
char [][]worker=new char[n][];
scanner.nextLine();
for(int i=0;i<n;i++){
worker[i]=scanner.nextLine().toCharArray();
}
backreverse(worker,0,new HashSet<Character>());
System.out.print(count);
}
public static void backreverse(char[][] worker,int index,HashSet<Character> set){
//如果已经全部安排，说明成功
if(index>=worker.length){
count++;
return;
}
char[] work=worker[index];
for(int i=0;i<work.length;i++){
if(!set.contains(work[i])){
//把这项工作记录下来说明已分配
set.add(work[i]);
//为下一位工程师分配
backreverse(worker,index+1,set);
//移除，为这个工程师分配下一个任务的情况
set.remove(work[i]);
}
}
}
}
结果
集合
小易最近在数学课上学习到了集合的概念,集合有三个特征：1.确定性 2.互异性 3.无序性.
小易的老师给了小易这样一个集合：
S = { p/q | w ≤ p ≤ x, y ≤ q ≤ z }
需要根据给定的w，x，y，z,求出集合中一共有多少个元素。小易才学习了集合还解决不了这个复杂的问题,需要你来帮助他。
输入描述:
输入包括一行：
一共4个整数分别是w(1 ≤ w ≤ x)，x(1 ≤ x ≤ 100)，y(1 ≤ y ≤ z)，z(1 ≤ z ≤ 100).以空格分隔
输出描述:
输出集合中元素的个数
输入例子1:
1 10 1 1
输出例子1:
10
解题思路
唯一要注意的是它没有限定结果是整数，所以要以double型存储和计算
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class CollectionNumber {
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
int w,x,y,z;
w=scanner.nextInt();
x=scanner.nextInt();
y=scanner.nextInt();
z=scanner.nextInt();
Set<Double> set=new HashSet<>();
for(int i=w;i<=x;i++){
for(int j=y;j<=z;j++){
double temp=i/(double)j;
set.add(temp);
}
}
System.out.print(set.size());
}
}
结果
奇怪的表达式求值
常规的表达式求值，我们都会根据计算的优先级来计算。比如*/的优先级就高于+-。但是小易所生活的世界的表达式规则很简单，从左往右依次计算即可，而且小易所在的世界没有除法，意味着表达式中没有/，只有(+, - 和 *)。现在给出一个表达式，需要你帮忙计算出小易所在的世界这个表达式的值为多少
输入描述:
输入为一行字符串，即一个表达式。其中运算符只有-,+,*。参与计算的数字只有0~9.
保证表达式都是合法的，排列规则如样例所示。
输出描述:
输出一个数，即表达式的值
输入例子1:
3+5*7
输出例子1:
56
解题思路
同样很简单，直接看代码
public class Calculate {
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
char[] arr=scanner.nextLine().toCharArray();
int i=0;
Set<Character> operator=new HashSet<>(Arrays.asList('0','1','2','3','4','5','6','7','8','9'));
int left=0;
char oper;
int right;
while(operator.contains(arr[i])){
left+=left*10+(arr[i]-'0');
i++;
}
while(i<arr.length){
right=0;
oper=arr[i++];
while(i<arr.length&&operator.contains(arr[i])){
right+=right*10+(arr[i]-'0');
i++;
}
left=cal(left,oper,right);
}
System.out.print(left);
}
public static int cal(int left,char oper,int right){
int result=0;
switch (oper){
case '+':
result=left+right;
break;
case '-':
result=left-right;
break;
case '*':
result=left*right;
break;
}
return result;
}
}
涂棋盘
小易有一块n*n的棋盘，棋盘的每一个格子都为黑色或者白色，小易现在要用他喜欢的红色去涂画棋盘。小易会找出棋盘中某一列中拥有相同颜色的最大的区域去涂画，帮助小易算算他会涂画多少个棋格。
输入描述:
输入数据包括n+1行：
第一行为一个整数n(1 ≤ n ≤ 50),即棋盘的大小
接下来的n行每行一个字符串表示第i行棋盘的颜色，'W'表示白色，'B'表示黑色
输出描述:
输出小易会涂画的区域大小
输入例子1:
3
BWW
BBB
BWB
输出例子1:
3
解题思路
对每一列进行计算，找出最长的。
public class MaxArea {
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
scanner.nextLine();
boolean[][] table=new boolean[n][n];
int i,j;
//白1黑0
for(i=0;i<n;i++){
char []arr=scanner.nextLine().toCharArray();
for(j=0;j<n;j++){
if(arr[j]=='B'){
table[i][j]=false;
}else{
table[i][j]=true;
}
}
}
int max=0;
boolean flag;
int curMax;
for(j=0;j<n;j++){
flag=table[0][j];
curMax=1;
for(i=1;i<n;i++){
if(table[i][j]==flag){
curMax++;
}else{
curMax=1;
flag=!flag;
}
max=(curMax>max)?curMax:max;
}
}
System.out.print(max);
}
}
结果
小易记单词
小易参与了一个记单词的小游戏。游戏开始系统提供了m个不同的单词，小易记忆一段时间之后需要在纸上写出他记住的单词。小易一共写出了n个他能记住的单词，如果小易写出的单词是在系统提供的，将获得这个单词长度的平方的分数。注意小易写出的单词可能重复，但是对于每个正确的单词只能计分一次。
输入描述:
输入数据包括三行：
第一行为两个整数n(1 ≤ n ≤ 50)和m(1 ≤ m ≤ 50)。以空格分隔
第二行为n个字符串，表示小易能记住的单词，以空格分隔，每个单词的长度小于等于50。
第三行为m个字符串，系统提供的单词，以空格分隔，每个单词的长度小于等于50。
输出描述:
输出一个整数表示小易能获得的分数
输入例子1:
3 4
apple orange strawberry
strawberry orange grapefruit watermelon
输出例子1:
136
解题思路
只要对小易的输入进行过滤就行了
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
//注意数据的读取
public class RememberVocaly {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n=scanner.nextInt();
int m=scanner.nextInt();
ArrayList<String> sysArr=new ArrayList<>();
ArrayList<String> yiArr=new ArrayList<>();
int i=0,j=0;
while(scanner.hasNext()){
String s=scanner.next();
//对小易的输入要进行过滤
if(i<n){
if(!yiArr.contains(s)){
yiArr.add(s);
}
i++;
}else{
sysArr.add(s);
j++;
if(j==m)
break;
}
}
scanner.close();
int score=0;
for(i=0;i<yiArr.size();i++){
String sa=yiArr.get(i);
if(sysArr.contains(sa)){
int len=sa.length();
score+=len*len;
}
}
System.out.print(score);
}
}
结果
堆砖块
小易有n块砖块，每一块砖块有一个高度。小易希望利用这些砖块堆砌两座相同高度的塔。为了让问题简单，砖块堆砌就是简单的高度相加，某一块砖只能使用在一座塔中一次。小易现在让能够堆砌出来的两座塔的高度尽量高，小易能否完成呢。
输入描述:
输入包括两行：
第一行为整数n(1 ≤ n ≤ 50)，即一共有n块砖块
第二行为n个整数，表示每一块砖块的高度height[i] (1 ≤ height[i] ≤ 500000)
输出描述:
如果小易能堆砌出两座高度相同的塔，输出最高能拼凑的高度，如果不能则输出-1.
保证答案不大于500000。
输入例子1:
3
2 3 5
输出例子1:
5
解题思路
这题和双核处理那道题挺像的，当时这里并不需要用到所有的砖块，自己尝试了依次减去砖块并用剩余砖块进行背包处理，只能通过90%。最终又看了解析(哭)。
它是用动态规划解决的！！
dp[i][j]表示用前i个砖块，高低塔高度差为j时，低塔的高度
dp[i][j]为以下中的最大值
1、dp[i-1][j+weigh[i]]+weigh[i] 第i块砖块放在低塔后低塔高度仍然低于高塔。
2、dp[i-1][high-j]+high-j 第i块砖块放在低塔后低塔高度高于高塔
3、dp[i-1][j-weigh[i]] 第i块砖块放在高塔
4、dp[i][j] 不放
可以看出只用到了dp[i]和dp[i-1],因此可以用=两个数组代替二位数组减少内存
2示意
public class Q11 {
static int sum;
static int[] height;
public static void main(String[]args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
height = new int[n];
sum = 0;
for (int i = 0; i < n; i++) {
height[i] = scanner.nextInt();
sum += height[i];
}
Arrays.sort(height);
int []dp=new int[sum +1];
Arrays.fill(dp,Integer.MIN_VALUE);
dp[0]=0;
for(int i=1;i<=n;i++){
int []temp=new int[sum+1];
int high=height[i-1];
Arrays.fill(temp,Integer.MIN_VALUE);
for(int j=0;j<=sum;j++){
//根据j、high的大小差距可以过滤一种情况
//向高塔放
if(j>high){
temp[j]=Math.max(temp[j],dp[j-high]);
}
if(j<=high){//向低塔放，放后低塔变高塔
temp[j]= Math.max(temp[j],dp[high-j]+high-j);
}
//向低塔放，放后低塔仍旧是低塔
if(j+high<=sum){
temp[j]=Math.max(temp[j],dp[j+high]+high);
}
//不放
temp[j]=Math.max(temp[j],dp[j]);
}
dp=temp;
}
if(dp[0]>0){
System.out.print(dp[0]);
}else{
System.out.print(-1);
}
}
//自己的方法，超时
/* public static int tryBuild(int[]arr,int sum){
//使用数组的子序列构建
int max=-1;
if(arr.length>1) {
int[][] arrs=new int[arr.length][arr.length-1];
for (int i = 0; i < arr.length; i++) {
int m=0;
for(int j=0;j<arrs[i].length;j++,m++){
if(j==i)
m++;
arrs[i][j]=arr[m];
}
max = findMax(sum - arr[i],arrs[i] );
if (max != -1) {
return max;
}
}
//子数组的新一轮循环
for(int i=0;i<arr.length;i++){
int diff=sum-arr[i];
if(diff> Q11.sum /2)
max=tryBuild(arrs[i],sum-arr[i]);
if(max!=-1)
return max;
}
}
return -1;
}
public static int findMax(int sum,int[]arr){
int max=-1;
if(sum%2!=0)
return max;
int[] dep = new int[sum / 2 + 1];
dep[0] = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = sum / 2; j >= arr[i]; j--) {
dep[j] = Math.max(dep[j], dep[j - arr[i]] + arr[i]);
}
}
// dfs(0,sum/2,dep,arr);
if (dep[sum / 2] == (sum / 2)) {
max=sum/2;
}
return max;
}
public static int dfs(int i,int j,int[] dp,int[] arr){
if(dp[j]>0)
return dp[j];
int res;
if(i==arr.length){
res=0;
}else if(j<arr[i]){
res=dfs(i+1,j,dp,arr);
}else{
res=Math.max(dfs(i+1,j,dp,arr),dfs(i+1,j-arr[i],dp,arr)+arr[i]);
}
return dp[j]=res;
}
*/
}
结果
分饼干
易老师购买了一盒饼干，盒子中一共有k块饼干，但是数字k有些数位变得模糊了，看不清楚数字具体是多少了。易老师需要你帮忙把这k块饼干平分给n个小朋友，易老师保证这盒饼干能平分给n个小朋友。现在你需要计算出k有多少种可能的数值
输入描述:
输入包括两行：
第一行为盒子上的数值k，模糊的数位用X表示，长度小于18(可能有多个模糊的数位)
第二行为小朋友的人数n
输出描述:
输出k可能的数值种数，保证至少为1
输入例子1:
9999999999999X
3
输出例子1:
4
解题思路
暴力法超时.同样使用动态规划
dp[i][j]表示前i个数字余数为j时可能的数值种数
dp[0][0]=1 没有数字且余数为0只有一种可能
状态转移方程为
dp[i][(j*10+k)%n]+=dp[i][j]
import java.util.Scanner;
public class Q12 {
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
String s=scanner.nextLine();
int n=scanner.nextInt();
long []dp=new long[n];
dp[0]=1;
for(int i=1;i<=s.length();i++){
long []temp= new long[n];
char c=s.charAt(i-1);
for(int j=0;j<n;j++){
for(int k=0;k<10;k++){
if(c=='X'||(c=='0'+k)){
temp[(j*10+k)%n]+=dp[j];
}
}
}
dp=temp;
}
System.out.print(dp[0]);
}
}
网友评论