暑假刷题第16天--7/28

143. 最大异或对 - AcWing题库（字典树）

#include<iostream>
using namespace std;
const int N=100005;
int a[N];
int nex[10000007][2],cnt;
void insert(int x){int p=0;for(int i=30;i>=0;i--){int u=x>>i&1;if(!nex[p][u])nex[p][u]=++cnt;p=nex[p][u];}
}
int find(int x){int p=0;int ans=0;for(int i=30;i>=0;i--){int u=x>>i&1;if(nex[p][!u]){ans=ans*2+1;p=nex[p][!u];}else {p=nex[p][u];ans=ans*2;}}return ans; 
}
int main(){int n;cin>>n;for(int i=0;i<n;i++){cin>>a[i];insert(a[i]);}int ans=0;for(int i=0;i<n;i++){ans=max(ans,find(a[i]));}cout<<ans<<endl;
} 

144. 最长异或值路径 - AcWing题库(前面一题变形--两题都要重点学习)

#include<iostream>
#include<cstring>
using namespace std;
const int N=100005,M=2e5+5;
int nex[320*N][2],cnt;
int d[N];//根节点到i 
int ne[M],w[M],e[M],h[N],idx;
void add(int a,int b,int c){e[idx]=b;ne[idx]=h[a];w[idx]=c;h[a]=idx++;
}
void insert(int x){int p=0;for(int i=30;i>=0;i--){int u=x>>i&1;if(!nex[p][u])nex[p][u]=++cnt;p=nex[p][u];}
}
int find(int x){int p=0;int ans=0;for(int i=30;i>=0;i--){int u=x>>i&1;if(nex[p][!u]){ans=ans*2+1;p=nex[p][!u];}else {p=nex[p][u];ans=ans*2;}}return ans; 
}
void dfs(int x,int fa,int sum){d[x]=sum;for(int i=h[x];~i;i=ne[i]){int j=e[i];if(j!=fa){dfs(j,x,sum^w[i]);}}
}
int main(){int n;cin>>n;memset(h,-1,sizeof(h));for(int i=0;i<n-1;i++){int x,y,z;cin>>x>>y>>z;add(x,y,z);add(y,x,z);}dfs(0,-1,0);for(int i=0;i<n;i++){insert(d[i]);}int ans=0;for(int i=0;i<n;i++){ans=max(ans,find(d[i]));}cout<<ans<<endl;
} 

Problem - C - Codeforces

#include<iostream>
#include<cstring>
using namespace std;
const int N=200005;
long long  a[N];
void solve(){long long n,k;cin>>n>>k;for(int i=0;i<n;i++)cin>>a[i];long long j=0,ans=1;while(k--) {while(j<n&&a[j]<=ans+j)j++;ans+=j;}cout<<ans<<endl;
}
int main(){int t;cin>>t;while(t--){solve();}
} 

Problem - B - Codeforces

#include<iostream>
#include<cstring>
using namespace std;
const int N=100005;
int a[N];
int n,k;
int check(int mid){int c=n,b=mid,a;for(int i=1;i<=k-2;i++){if(b>c)return 0;a=c-b;c=b;b=a;}if(b>c)return 0;return 1;
}
int check1(int mid){int c=n,b=mid,a;for(int i=1;i<=k-2;i++){if(b>c)return 1;a=c-b;c=b;b=a;}if(b>c)return 1;return 0;
}
void solve(){cin>>n>>k;if(k>=30){cout<<0<<endl;return;}int ans=0;for(int i=n/2-1;i<=n;i++){if(check(i))ans++;}cout<<ans<<endl;
}
int main(){int t;cin>>t;while(t--){solve();}
} 

145. 超市 - AcWing题库(优先队列+贪心)--并查集解法待补

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=10004;
typedef pair<int,int>PII;
PII  a[N];
int main(){int n;while(cin>>n){priority_queue<int,vector<int>,greater<int> >q;for(int i=0;i<n;i++){cin>>a[i].second>>a[i].first;}sort(a,a+n);int t=1;for(int i=0;i<n;i++){if(q.empty()||t<=a[i].first){t++;q.push(a[i].second);} else {if(a[i].second>q.top()){q.pop();q.push(a[i].second);}}}long long ans=0;while(!q.empty()){ans+=q.top();q.pop();}cout<<ans<<endl;}
}