首页 > 阿里巴巴笔试 3.17
头像
天青se等烟雨
编辑于 2021-04-02 14:23
+ 关注

阿里巴巴笔试 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
 / 本题为考试单行多行输入输出规范示例,无需提交,不计分。
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) + " ");
        }
    }
}




全部评论

(5) 回帖
加载中...
话题 回帖

推荐话题

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐