1. 【华为】20240717_1_文件系统

描述
对于一个文件系统，第一行输入所有的父目录名称，第二行输入所有的子目录/文件名称，第三行输入待查询的文件或目录名称。对于查询的目录或文件名，如果存在子目录或文件，需要按输入的顺序，按层级输出所有的子目录和文件。“/”表示根目录，没有父目录。

输入描述

第一行是一个由所有的父目录名称组成的字符串，按空格分开。第二行是对应父目录的所有子目录或文件名组成的字符串，按空格分开。第三行是查询的文件名或目录名。

输出描述

按输入的顺序逐层输出所有的子目录和文件，包括查询的目录/文件本身

import sys
from collections import deque

def main() :
    parents = input().strip().split() 
    subdir = input().strip().split() 
    target = input().strip()
    n = len(parents)
    q = [target]
    out = []
    while q :
        cur = q[0] 
        q = q[1:] 
        for i in range(n):
            if parents[i] == cur :
                q.append(subdir[i]) 
        out.append(cur)
    print(' '.join(out))

if __name__ == '__main__' :
    main() 

1. 【华为】20240717_3_旅游体验次数

描述
小红有一笔旅游预算，旅游地点有若干组项目，每个项目有自己的价格和体验次数，求在当前预算下最多能体验的次数。预算和价格都是50的倍数。

输入描述

第一行输入总预算和k。

之后K行输入每个项目的花费和能体验的项目次数。

输出描述

在当前预算下最多能体验的次数。

import sys 
from collections import defaultdict 

def main() :
    input = sys.stdin.read().strip().split() 
    ptr = 0 
    C = int(input[ptr]) // 50 
    ptr += 1 
    lines = int(input[ptr]) 
    ptr += 1 
    mapper = defaultdict(int)
    for _ in range(lines) :
        c = int(input[ptr]) // 50 
        ptr += 1 
        cnt = int(input[ptr])
        ptr += 1 
        mapper[c] += cnt 
    # print(mapper) 
    new_cost = []
    new_cnt = []
    # 现在将mapper中的kv进行拆分
    for k , v in mapper.items() :
        # k -> cost ; v -> cnt 
        i = 1 
        while i <= v : 
            v -= i 
            new_cost.append(i * k)
            new_cnt.append(i)
            i <<= 1
        if v : 
            new_cost.append(v * k)
            new_cnt.append(v)
    n = len(new_cost)
    dp = [0] * (C+10)
    for i in range(n) :
        j = C 
        while j >= new_cost[i] :
            dp[j] = max(dp[j] , dp[j-new_cost[i]] + new_cnt[i]) 
            j -= 1
    print(dp[C])







if __name__ == '__main__' :
    main() 

'''
首先读入所有的cost cnt对
预处理 cost和C除以50 
然后收集cost相同的  将cnt汇总

基于汇总后的cost:cnt对,进行二进制拆分
得到new_cost  new_cnt 

基于二进制拆分 进行滚动数组的01背包

'''

1. 【华为】20240717_2_软件依赖查询

描述

一组n个软件和k（k < (n*(n - 1)/2)）个依赖关系,若干组查询，查询两个软件的前者是否是后者的直接依赖或间接依赖。（对于[a,b]判断a是否是b的前驱节点）

输入描述

第一行输入两个正整数n和d ，代表软件的个数和依赖关系。后面d行输入相应的依赖关系。下一行输入一个正整数q，代表查询的组数。之后q行输入相应的查询。

输出描述

第一行输出q。之后q行每行输出一个正整数，如果是依赖关系，输出1，否则输出0。

#include<bits/stdc++.h>
using namespace std ;

const int N = 1010 ;

bitset <N> d[N] ;
int n , m , q ;

void Floyd(){
    for(int k = 0 ; k < n ; k ++ ){
        for (int i = 0 ; i < n ;i ++ ) {
            if (d[i][k]) {
                d[i] |= d[k] ;
            }
        }
    }
}

int main(){
    scanf("%d%d" , &n,&m) ;
    for(int i = 0 ; i < n ; i ++) {
        d[i][i]= 1;
    }
    for (int i = 0 ; i < m ; i ++ ) {
        int a , b ;
        scanf("%d%d" , &a, &b) ;
        d[a][b] = 1 ;
    }
    Floyd() ;
    int q ;
    cin >> q ;
    printf("%d\n" , q) ;
    for (int i = 0 ; i < q ; i ++) {
        int a , b ;
        scanf("%d%d" , &a,&b) ;
        if (d[a][b]) {
            printf("1\n" ) ;
        }else {
            printf("0\n") ;
        }
    }
}