字节笔试后端AK（9月24日）

T2 用map装最小堆，二分+排序模拟一下即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;

int a[N], b[N];

void solve(){
    int n, q;
    cin >> n >> q;
    map<int, priority_queue<int>> mp;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i) cin >> b[i];
    for(int i = 1; i <= n; ++i){
        mp[a[i]].push(b[i]);
    }
    ll ans = 0;
    while(q--){
        int x;
        cin >> x;
        auto it = mp.upper_bound(x);
        if(it != mp.begin()){
            it = prev(it);
            int val = it->second.top();
            ans += val;
            it->second.pop();
            it->second.push(val / 2);
        }
    }
    cout << ans << '\n';
}

int main(){
    solve();
    return 0;
}

T3 用前缀和计算经过每个房屋的次数，然后比较 pre[i]*b[i] 和 a[i] 的大小，贪心取小的即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define lowbit(x) x & (-x)
const int N = 2e5 + 10, mod = 1e9 + 7, inf = 1e9;

int a[N], b[N], p[N], pre[N];

void solve(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> p[i];
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i) cin >> b[i];
    int x = 1;
    p[n + 1] = n + 1;
    for(int i = 1; i <= n; ++i){
        pre[min(x, p[i])]++;
        pre[max(x, p[i]) + 1]--;
        if(p[i + 1] > p[i])
            x = p[i] + 1;
        else
            x = p[i] - 1;
    }
    pre[x]++, pre[n + 1]--;
    for(int i = 1; i <= n; ++i) pre[i] += pre[i - 1];
    ll ans = 0;
    for(int i = 1; i <= n; ++i){
        if(a[i] > (ll)b[i] * pre[i]){
            ans += (ll)b[i] * pre[i];
        }else ans += a[i];
    }
    cout << ans << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	int t = 1;
    while(t--){
        solve();
    }
	return 0;
}

T4 将横向和竖向分开考虑，选取LR的时候枚举LR的数量，利用组合数计算一下放在不同位置的所有可能情况，UD也是一样的，最后乘起来就行了

#include<iostream>
#include<vector>
using namespace std;
#define ll long long
const ll mod = 1e9 + 7;
ll bp(ll a, ll b, ll m) {
	a %= m;
	ll res = 1;
	while (b > 0) {
		if (b & 1) res = res * a % m;
		a = a * a % m;
		b >>= 1;
	}
	return res;
}
ll func(ll x, ll y)
{
	if (x > y)
		swap(x, y);
	ll cnt = 1;
	ll tmp1 = 1 , tmp2 = 1;
	for (int i = 0; i <= x; i++)
	{
		tmp2 *= y - i;
		tmp2 %= mod;
		tmp2 *= bp(i + 1,mod-2,mod);
		tmp2 %= mod;

		tmp1 *= x - i;
		tmp1 %= mod;
		tmp1 *= bp(i + 1, mod - 2, mod);
		tmp1 %= mod;

		cnt = (cnt + tmp1*tmp2) % mod;
	}
	return cnt;
}

int main()
{
	string s;
	cin >> s;
	ll L = 0,  R = 0 , U = 0, D = 0;
	for (int i = 0; i < s.size(); i++)
	{
		L += s[i] == 'L';
		R += s[i] == 'R';
		U += s[i] == 'U';
		D += s[i] == 'D';
	}
	ll ans = func(L, R)* func(U, D);
	ans = (ans - 1 + mod) % mod;
	cout << ans % mod;
}