H 牛牛看云
求上述式， ai <= 1000, n <= 1e6
思路： 1. 注意到𝑛 ≤ 106而𝑎 𝑖 ≤ 1000，可以看到𝑎[𝑖]范围很小，或者说极 限数据下会有大量重复的值出现，我们想想怎么利用这一点 2. 记cnt[𝑖]表示𝑖出现的次数，枚举(𝑖,𝑗)对儿（共10^6种） 3. 不同情况直接相乘, 特殊处理相同情况
求贡献：
- i == j
- 自身 + 握手原则（n + n * (n - 1) / 2)
- i != j
- 直接相乘（cnt[i] * cnt[j]）
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; }
I B站与各唱各的
题意：n个人，m句话，每人都可以选择唱与不唱。某句话都没人唱，或都唱了算这句话唱失败，否则是唱成功。求成功唱出的句子数尽可能多的数量。
思路： • 首先注意到句子与句子之间没有办法互相影响，因此答案是一句话的期望乘以𝑚； • 由于无法交流，每个人在唱每句时唯一的策略就是随机以𝑝𝑖的概率决定唱或不唱这一句 • 又由于𝑛个人之间没有区别，所以不同人的概率一定是相等的，记为𝑝； • 因此，唱失败的概率是𝑝^𝑛 + (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; }
J 小朋友做游戏
a个安静小朋友，b个不安分小朋友，选出n个围成圈。规定两个不安分的不能手拉手。每个小朋友有幸福值，求出最大值。
思路： 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; } }
