最后一题写搓了。不应该这样背包，过了50%
第一题
/*
给了一棵树，节点最多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;
} 第四题
update：这题数据水了，当时过了，就没管那么多。
对于x[i]<=mid && y[i]>=mid的，如果cnt*2>=n，那么取x[i],否则取mid，对于其他的取x[i]即可，对于
x[i]>mid的，因为他会增加cnt的个数，所以应该先按照左端点从大到小排序，这样优先选择了更多>=mid的数字，可以减少在
中间部分，选择更多的x[i]，而不是mid，使得总和S尽可能小。
代码已更新
/*
n个人，总共有w元，每个人要得到的钱数量在x和y之间，求让分配后，中位数最大值是多少
n<=1e5
w<=1e14
∑x[i]<=w<=∑y[i]
* @Author: 7QQQQQQQ
* @IDE: vscode
* @Date: 2021-03-21 20:23:00
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+50;
ll n,w;
struct node{
ll x,y;
friend bool operator<(node a,node b){
if(a.x!=b.x) return a.x>b.x;
return a.y>b.y;
}
}a[N];
bool check(ll mid){
ll S=0;
int cnt=0;
for(int i=1;i<=n;i++){
if(a[i].x<=mid && a[i].y>=mid){
if(cnt*2<n) S+=mid,cnt++;
else S+=a[i].x;
}
else{
S+=a[i].x;
if(a[i].x>=mid) ++cnt;
}
}
return S<=w && cnt*2>=n;
}
int main(){
cin>>n>>w;
ll R=0;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y;
R=max(R,a[i].y+1);
}
sort(a+1,a+n+1);
ll L=0;
while(L+1<R){
ll mid=L+R>>1;
if(check(mid)) L=mid;
else R=mid;
}
cout<<L;
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;
} 
全部评论
(11) 回帖