9.26腾讯客户端笔试题

map标记一下，遇到相同的就删除，fa -> left / fa -> right，赋值为NULL

感觉题目有点问题，[1,3,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;
}

#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;
}

#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;
}

#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;
}