阿里巴巴笔试 3.17
第一题
t组数据
n副牌 每副m张 求每一组选一张，使得和为k，有多少种情况？
第二题---这个代码过70%
n个零件 m个冲突
每一个零件有对应的时间空间优化a[i],b[i]
m个冲突关系，使得零件之间不能一起选
求，每个零件和其他所有零件组合的开销的总最小值。
5 3
-1 3
2 4
1 1
3 5
2 2
1 4
2 3
3 5
4 14 4 16 10
-1 3
2 4
1 1
3 5
2 2
1 4
2 3
3 5
4 14 4 16 10
/ 本题为考试单行多行输入输出规范示例，无需提交，不计分。
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
// static int ans = 0;
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int T = cin.nextInt();
List<Integer> res = new ArrayList<>();
for(int i=0;i<T;i++){
int n = cin.nextInt();
int m = cin.nextInt();
int k = cin.nextInt();
// get_ans(n, m, k);
res.add(get_ans(n, m, k));
}
for (int i=0;i<T;i++){
System.out.println(res.get(i));
}
}
public static int get_ans(int n, int m, int k){
int res = 0;
long [][]dp = new long[n+1][k+1];
for(int j=1;j<=m && j<=k;j++){
dp[1][j] = 1;
// System.out.println(1 + " " + j + " " + dp[1][j]);
}
for(int i=2;i<=n;i++){
for(int j=i;j<=k;j++){
for(int c = 1;c<=m;c++){
if(j - c < 1)
break;
dp[i][j] += dp[i-1][j-c];
// System.out.println(i + " " + j + " " + dp[i][j]);
}
}
}
return (int)(dp[n][k] % 1000000007);
}
// 本题为考试单行多行输入输出规范示例，无需提交，不计分。
import java.util.*;
public class Main {
// static int ans = 0;
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int m = cin.nextInt();
List<Integer> lint = new ArrayList<>();
int []a = new int[n+1];
int []b = new int[n+1];
for(int i=1;i<=n;i++){
a[i] = cin.nextInt();
b[i] = cin.nextInt();
}
char [][]relation = new char[n+1][n+1];
for (int i=0;i<m;i++){
int x = cin.nextInt();
int y = cin.nextInt();
relation[x][y] = '1';
relation[y][x] = '1';
}
int res;
for(int i=1;i<=n;i++){
res = 0;
for(int j=1;j<=n;j++){
if (i == j || relation[i][j] == '1')
continue;
res += Math.min(a[i]+b[j], a[j] + b[i]);
}
lint.add(res);
}
for (int i=0;i<lint.size();i++){
System.out.print(lint.get(i) + " ");
}
}
}
