3.21腾讯笔试题(过了4+0.5)

/*
    给了一棵树，节点最多1000个，1000次查询，问从根到这个数字x都经过了哪些节点。  保证结点数字唯一

*/
/**
 * struct ListNode {
 * int val;
 * struct ListNode *next;
 * ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
/**
 * struct TreeNode {
 * int val;
 * struct TreeNode *left;
 * struct TreeNode *right;
 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 你需要返回m个指针，第i个指针指向一条链，表示第i个问题的答案
     * @param root TreeNode类 指向链表树的根
     * @param b int整型vector 表示每个问题是什么
     * @return ListNode类vector
     */
    int fa[1005];
    void dfs(TreeNode* root,int f){
        if(!root) return ;
        fa[root->val]=f;
        dfs(root->left,root->val);
        dfs(root->right,root->val);
        
    }
    vector<ListNode*> solve(TreeNode* root, vector<int>& b) {
        vector<ListNode*> ans;
        dfs(root,root->val);
        for(auto &X:b){
            vector<int> now;
            int x=X;
            while(fa[x]!=x){
                now.push_back(x);
                x=fa[x];
            }
            now.push_back(x);
            reverse(now.begin(),now.end());
            ListNode* head=new ListNode(now[0]);
            ListNode* H=head;
            for(int i=1;i<now.size();i++){
                H->next=new ListNode(now[i]);
                H=H->next;
            }
            ans.push_back(head);
        }
        return ans;
        
    }
};
	

		
	

/*
    一个数字n，三种操作，n=n-1，偶数可以n=n/2，三的倍数可以n=n/3
    问变成1最小操作次数
     1<=n<=1e9
     
 * @Author: 7QQQQQQQ
 * @IDE: vscode
 * @Date: 2021-03-21 20:00:29
 */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+50;

int main(){
    int T;cin>>T;
    while(T--){
        map<int,int> vis;
        int n;cin>>n;
        queue<int> que;
        que.push(n);
        vis[n]=1;
        while(!que.empty()){
            int x=que.front();
            que.pop();
            if(x==1) break;
            if(!vis[x-1]){
                vis[x-1]=vis[x]+1;
                que.push(x-1);
            }
            if(x%2==0 && !vis[x/2]){
                vis[x/2]=vis[x]+1;
                que.push(x/2);
            }
            if(x%3==0 && !vis[x/3]){
                vis[x/3]=vis[x]+1;
                que.push(x/3);
            }
        }
        cout<<vis[1]<<endl;
    }
    return 0;
}

/*
    给了n个数字，然后q次查询，每次查询给了若干个数组，求这些数组合并后的第k小
    范围都是1e5

 * @Author: 7QQQQQQQ
 * @IDE: vscode
 * @Date: 2021-03-21 20:14:53
 */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+50;
vector<int> e[N];
int cnt[N];
int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>cnt[i];
        for(int j=1;j<=cnt[i];j++){
            int x;cin>>x;
            e[i].push_back(x);
        }
        sort(e[i].begin(),e[i].end());
    }
    int Q;cin>>Q;
    while(Q--){
        int num;cin>>num;
        vector<int> query;
        for(int i=0;i<num;i++){
            int x;cin>>x;
            query.push_back(x);
        }
        int K;cin>>K;
        int L=0,R=1e9;
        while(L+1<R){
            int mid=L+R>>1;
            int sum=0;
            for(int i=0;i<num;i++){
                int j=query[i];
                sum+=lower_bound(e[j].begin(),e[j].end(),mid)-e[j].begin();
            }
            if(sum<K) L=mid;
            else R=mid;
        }
        cout<<L<<endl;
    }
    return 0;
}

/*
    n个物品，每个物品有自己的价值，现在让选择物品，使得选择的物品价值是m的倍数，输出最少要丢弃的价值
    1<=n<=1e5
    1<=m<=100
    
 * @Author: 7QQQQQQQ
 * @IDE: vscode
 * @Date: 2021-03-21 20:30:44
 */

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+50;
ll a[N],b[N],dp[N*10];
int main(){
    int T;cin>>T;
    while(T--){
        int n,m;cin>>n>>m;
        ll SUM=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            SUM+=a[i];
            b[i]=a[i]%m;
        }
        if(SUM%m==0){
            cout<<0<<endl;
            continue;
        }
        for(int i=1;i<=m;i++){
            dp[i]=1e18;
        }
        ll ans=1e18,NOT=0;
        for(int i=1;i<=n;i++){
            if(b[i]==0) continue;
            NOT+=a[i];
            if(a[i]%m==SUM%m) ans=min(ans,a[i]);
            for(int j=m;j>=b[i];j--){
                dp[j]=min(dp[j],dp[j-b[i]]+a[i]);
                if(dp[j]%m==SUM%m) ans=min(ans,dp[j]);
            }
        }
        if(ans==(ll)(1e18)) ans=NOT;
        cout<<ans<<endl;
        
    }
    return 0;
}