牛客寒假算法基础集训营1下

思路：
1. 注意到𝑛 ≤ 106而𝑎 𝑖 ≤ 1000，可以看到𝑎[𝑖]范围很小，或者说极
限数据下会有大量重复的值出现，我们想想怎么利用这一点
2. 记cnt[𝑖]表示𝑖出现的次数，枚举(𝑖,𝑗)对儿（共10^6种）
3. 不同情况直接相乘, 特殊处理相同情况

void solve() {
  cin >> n;
    vi cnt(1001);
    rep(i, 0, n) {
        int x; cin >> x;
        cnt[x]++;
    }
    int ans = 0;
    rep(i, 0, 1001) {
        rep(j, i, 1001) {
            int add;
            if(i == j) add = cnt[i] + cnt[i] * (cnt[i] - 1) / 2;
            else add = cnt[i] * cnt[j];
            ans = ans + add * abs(i + j - 1000);
        }
    }
    cout << ans << endl;
}

思路：
   • 首先注意到句子与句子之间没有办法互相影响，因此答案是一句话的期望乘以𝑚；
   • 由于无法交流，每个人在唱每句时唯一的策略就是随机以𝑝𝑖的概率决定唱或不唱这一句
   • 又由于𝑛个人之间没有区别，所以不同人的概率一定是相等的，记为𝑝；
     • 因此，唱失败的概率是𝑝^𝑛 + (1 − 𝑝)^𝑛，求其最小值得𝑝 = 1/2，

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
ll qmi(ll a, ll k) {
    ll res = 1ll;
    while(k) {
        if(k & 1) res = res * a % mod;
        a = a * a % mod;
        k >>= 1;
    }
    return res % mod;
}
int main() {
    ll t; cin >> t;
    while(t--) {
        ll n, m; cin >> n >> m;
        int x = qmi(2, n - 1);
        cout << m * (1ll + mod - 1ll * qmi(x, mod - 2)) % mod << endl;
    }
    return 0;
}

思路：
1. 先将两种小朋友的幸福度分别按从大到小排序，记为A和B数组
2. 那么最优的方案一定是从A和B中各选一个前缀
3. 贪

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N],b[N];
bool cmp(int a,int b) {
    return a > b;
}
signed main()
{
    int t; cin >> t;
    while(t--)
    {
        long long A , B , n;
        cin >> A >> B >> n;
        for(int i = 1; i <= A ; i ++) cin>>a[i];
        for(int i = 1; i <= B ; i ++) cin>>b[i];
        sort(a + 1, a + 1 + A , cmp);
        sort(b + 1, b + 1 + B , cmp);
        for(int i = 1 ; i <= A ; i ++)  a[i] = a[i - 1] + a[i];
        for(int i = 1 ; i <= B ; i ++)  b[i] = b[i - 1] + b[i];
        int ans = -1;
        for(int i = 1; i <= A ; i ++)
            if(n <= 2 * i && n - i <= B && i <= n)
                ans = max(ans , a[i] + b[n - i]);
        cout << ans << endl;
    }
}