拼多多算法笔试全解析

#include <bits/stdc++.h> using namespace std; int main(){     int n;cin>>n;     vector<pair<int, int>> v(n);     for(int i = 0;i<n;i++){         scanf("%d",&v[i].first);     }     int l = 0;     for(int i = 0;i<n;i++){         scanf("%d",&v[i].second);         l+=v[i].second;     }     sort(v.begin(), v.end());     vector<int> dp(l+10,0);     int sum = 0;     int ans = 0;     for(int i = 0;i<n;i++){         for(int j = sum;j>=0;j--){             if(v[i].second*7>=j){                 dp[j+v[i].second] = max(dp[j+v[i].second],dp[j]+1);             }             ans = max(ans,dp[j+v[i].second]);         }         sum+=v[i].second;     }     cout<<ans<<endl; } 第四题ac

#include <bits/stdc++.h> using namespace std; int main(){     int n,m;cin>>n>>m;     vector<int> v(n+1);     for(int i = 0;i<n;i++){         scanf("%d",&v[i+1]);     }     vector<vector<int>> vv(n+1);     vector<int> cnt(n+1,0);     int val1,val2;     for(int i = 0;i<m;i++){         scanf("%d %d",&val1,&val2);         vv[val1].push_back(val2);         cnt[val2]++;     }     priority_queue<pair<int, int>,vector<pair<int, int>>,greater<>> pq;     for(int i = 1;i<=n;i++){         if(cnt[i]==0){             pq.push({v[i],i});         }     }     vector<int> ans(n+1);     int k = 1;     while (!pq.empty()) {         int val = pq.top().second;         pq.pop();         ans[k++]=val;         for(int i = 0;i<vv[val].size();i++){             int x = vv[val][i];             cnt[x]--;             if(cnt[x]==0){                 pq.push({v[x],x});             }         }     }     for(int i = 1;i<=n;i++){         cout<<ans[i]<<" ";     } } 第三题

第三题 from collections import defaultdict import heapq class Node(object): def __init__(self,time,l,index): self.time = time self.l = l self.index = index def __lt__(self, other): if self.time < other.time: return True elif self.time == other.time: return self.index < other.index else: return False N,M = map(int, input().split()) times = list(map(int, input().split())) d = defaultdict(set) l = [] #heapq.heapify(l) for i in range(M): tmp = list(map(int, input().split())) for e in tmp[:-1]: d[tmp[-1]].add(e) for i in range(N): #print(times[i], d[i+1],i+1) heapq.heappush(l,Node(times[i], d[i+1], i+1)) res = [] while len(l) > 0: tmp = [] node = None while len(l) > 0: node = heapq.heappop(l) if len(node.l) > 0: tmp.append(node) else: res.append(node.index) break for e in tmp: heapq.heappush(l, e) if node != None: for i in range(len(l)): if node.index in l[i].l: l[i].l.remove(node.index) for e in res: print(e, end=" ")

第二题 from collections import defaultdict words = input().split() N = len(words) d = defaultdict(int) head = defaultdict(set) for e in words: head[e[0]].add(e[-1]) tmp = e[0] + e[-1] d[tmp] += 1 res = False def fun(startC, word, num): global res if num == 0: res = True return if res == True: return for c in head[word[1]]: if num == 1 and c != startC: continue tmp = word[1] + c if d[tmp] > 0: d[tmp] -= 1 fun(startC, tmp, num - 1) d[tmp] += 1 tmp = words[0][0] + words[0][-1] d[tmp] -= 1 fun(words[0][0],tmp,N-1) if res: print("true") else: print("false")

#include <bits/stdc++.h> using namespace std; bool dfs(vector<vector<int>>& v,int n,int cur,int x){     if(cur==n+1) return true;     bool ans = false;     for(int i = 0;i<v[x].size();i++){         ans|=dfs(v, n, cur+1, v[x][i]);     }     return ans; } int main(){     vector<vector<int>> v(26);     string str;     int n = 0;     int start = 0;     vector<int> v1(26,0);     vector<int> v2(26,0);     while(cin>>str){         v[str[0]-'A'].push_back(str.back()-'A');         v1[str[0]-'A']++;         v2[str.back()-'A']++;         start = str[0]-'A';         n++;     }     for(int i = 0;i<26;i++){         if(v1[i]!=v2[i]){             cout<<"false"<<endl;             exit(0);         }     }     if(dfs(v,n, 0, start)){         cout<<"true"<<endl;     }else{         cout<<"false"<<endl;     } } 第二题

第二题直接统计每个串的开头和结尾字符不就行嘛（逃

我也贴一下自己的代码吧~第一题 A = list(map(int, input().split())) B = list(map(int, input().split())) A.append(float("inf")) A.insert(0,-float("inf")) index = 1 for i in range(1,len(A)): if A[i] <= A[i-1]: index = i break res = -float("inf") for i in range(len(B)): if B[i] < A[index+1] and res < B[i] and B[i] > A[index-1]: res = B[i] if res == -float("inf"): index -= 1 for i in range(len(B)): if B[i] < A[index + 1] and res < B[i] and B[i] > A[index - 1]: res = B[i] if res == -float("inf"): print("NO") else: A[index] = res for e in range(1, len(A) - 1): print(A[e], end=" ") else: A[index] = res for e in range(1,len(A)-1): print(A[e],end=" ")

第四题 dp，同95%不知道哪个数据有问题

看了阁下的思路一下子就明白第三题怎么做了，我好菜。。。

第四题和第二题的思路不是一样吗

大佬就是大佬