9.26腾讯客户端笔试题
1.二叉树去重
map标记一下,遇到相同的就删除,fa -> left / fa -> right,赋值为NULL 感觉题目有点问题,[1,3,2*,2+] 按题意来说,应该删除2*,代码写成删除2+,(2*应该比2+更右),不过也通过了
2.找平方
#include <bits/stdc++.h> using namespace std; #define ll long long const int N = 1e5 + 2; ll a[N]; unordered_map<ll,int>mp; int n,cnt = 0; int main() { freopen("test.in","r",stdin); scanf("%d",&n); for(int i = 1; i <= n; ++ i) { ll x; scanf("%lld",&x); mp[x] = true; a[i] = x; if(x == 1) ++ cnt; } if(cnt >= 2){ cout << 1 << " " << 1 << "\n"; return 0; } for(int i = 1;i <= n; ++ i){ if(a[i] != 1 && mp[a[i] * a[i]]){ cout << a[i] << " " << a[i] * a[i] << endl; return 0; } } puts("-1"); return 0; }3.序列最大值最小值和
#include <bits/stdc++.h> using namespace std; #define ll long long const int N = 1e5 + 2; ll a[N]; ll ans = 0; int n; const ll mod = 1e9 + 7; vector<int>v; int main() { // freopen("test.in","r",stdin); scanf("%d",&n); for(int i = 1; i <= n; ++ i) scanf("%d",a + i); sort(a + 1,a + n + 1); ll tmp = 1; for(int i = 1;i <= n; ++ i){ ans = (ans + tmp * a[i] % mod) % mod; tmp = (tmp * 2) % mod; } reverse(a + 1,a + n + 1); tmp = 1; for(int i = 1;i <= n; ++ i){ ans = (ans + tmp * a[i] % mod) % mod; tmp = (tmp * 2) % mod; } printf("%lld\n",ans); return 0; }4.二分+贪心 贪得略有问题,先手应该是尽量不杀死,时间不够没实现 通过70%
#include <bits/stdc++.h> using namespace std; #define ll long long const int N = 1e5 + 2; int a[N],b[N]; ll ans = 0; int n,m; int del[N],add[N]; bool check(int res) { multiset<int>st; multiset<int>mst; for(int i = 1; i <= res; ++ i) st.insert(b[i]); for(int i = 1; i <= n; ++ i) mst.insert(a[i]); // cout << "debug" << endl; // for(auto x : mst) { // cout << x << endl; // } while(mst.size()) { int sz = st.size(); if(sz == 0) return false; auto it = mst.upper_bound(sz); if(it == mst.end()) -- it; int mx = *it; if(mx > sz) { mst.erase(mst.find(mx)); mst.insert(mx - sz); } else { if(mst.size() == 0) return true; auto it = mst.begin(); int d = (*it); mst.erase(mst.find(d)); } int tot = mst.size(); if(tot == 0) return true; del[0] = 0; add[0] = 0; for(auto x : st) { if(tot == 0) break; if(x <= tot) { del[++ del[0]] = x; tot -= x; } else { del[++ del[0]] = x; add[++ add[0]] = x - tot; tot = 0; } } for(int i = 1; i <= del[0]; ++ i) st.erase(st.find(del[i])); for(int i = 1; i <= add[0]; ++ i) st.insert(add[i]); } return true; } int main() { // freopen("test.in","r",stdin); scanf("%d %d",&n,&m); for(int i = 1; i <= n; ++ i) scanf("%d",a + i); for(int i = 1; i <= m; ++ i) scanf("%d",b + i); // sort(b + 1,b + n + 1,[&](int x,int y) { // return x > y; // }); int l = 1,r = m,ans = -1; while(l <= r) { int mid = (l + r) / 2; if(check(mid)) { ans = mid; r = mid - 1; } else l = mid + 1; } printf("%d\n",ans); return 0; }5.四个数异或 按位算贡献,只有奇数个1有贡献,也就是选出1或3个1,其余的全0
#include <bits/stdc++.h> using namespace std; #define ll long long const int N = 1e5 + 2; int n; ll inv[N],fac[N],cnt[N]; const ll mod = 1e9 + 7; ll C(ll x,ll y){ if(x < y) return 0ll; return fac[x] * inv[y] % mod * inv[x - y] % mod; } ll mod_pow(ll a,ll b){ ll res = 1; while(b){ if(b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1; } return res; } int main() { freopen("test.in","r",stdin); scanf("%d",&n); fac[0] = inv[0] = 1; for(int i = 1;i <= n; ++ i) fac[i] = fac[i - 1] * i % mod; for(int i = 1;i <= n; ++ i) inv[i] = mod_pow(fac[i],mod - 2); for(int i = 1; i <= n; ++ i) { ll x; scanf("%lld",&x); for(int j = 0;j <= 30; ++ j){ if((x >> j) & 1) ++ cnt[j]; } } ll tmp = 1,ans = 0; for(int i = 0;i <= 30; ++ i){ ans = (ans + (tmp * (C(cnt[i],1) * C(n - cnt[i],3) % mod + C(cnt[i],3) * C(n - cnt[i],1) % mod) % mod) % mod)% mod; tmp = tmp * 2 % mod; } printf("%lld\n",ans); return 0; }
END.