B - Boxes（思维）
最多只需问一次。开箱顺序一定是根据代价从小到大开的。当你开箱到某个位置i，i之后的球都是同色，那么你一定能知道剩余球的情况，可以提前结束。因此答案就是
(sumlimits_{i< n}({ m P(位置i之后都同色)} imes cost_i))。
其中(cost_i)代表代价排好序后到(i)的前缀和。在位置(i)，有(frac{1}{2})概率和下一个位置不同色，(i)之后的位置有((frac{1}{2})^{n-i-1})概率与最后一个位置同色，故
({ m P(位置i之后都同色)}=frac{1}{2} imes (frac{1}{2})^{n-i-1}=(frac{1}{2})^{n-i})
直接递推求即可。时间复杂度O(n)
最后要与不问的情况取一个最小值。
#include <bits/stdc++.h>
#define endl '
'
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mp make_pair
#define seteps(N) fixed << setprecision(N)
typedef long long ll;
using namespace std;
/*-----------------------------------------------------------------*/
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
#define INF 0x3f3f3f3f
const int N = 1e5 + 10;
const int M = 1e9 + 7;
const double eps = 1e-5;
double cost[N];
double dp[N];
int main() {
IOS;
int n;
double c;
cin >> n >> c;
double p = 0.5;
for(int i = 1; i <= n; i++) {
cin >> cost[i];
}
sort(cost + 1, cost + 1 + n);
for(int i = 1; i <= n; i++) {
cost[i] += cost[i - 1];
}
double ans = 0;
for(int i = n - 1; i >= 1; i--) {
ans += p * cost[i];
p *= 0.5;
}
cout << seteps(10) << min(cost[n], ans + c) << endl;
}
D - Double String（dp）
设(dp1[i][j])代表A[1...i]和B[1...j]相等子序列的对数，可得递推式
- (dp1[i][j]=dp1[i-1][j]+dp1[i][j-1]-dp[i-1][j-1])
- 当A[i]==B[i]时，额外有(dp1[i][j]=1+dp[i-1][j-1])
设(dp2[i][j])代表从{1, 2, ..., i} 和 {1, 2, ..., j}中取出长度相同的序列的对数，等价于所有字符相等的(dp1)，即
(dp2[i][j]=1+dp2[i-1][j]+dp2[i][j-1])
枚举(i)，(j)，当(A[i]<B[j])时，贡献为((dp[i-1][j-1]+1) imes(dp[n-i][m-j]+1))
#include <bits/stdc++.h>
#define endl '
'
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mp make_pair
#define seteps(N) fixed << setprecision(N)
typedef long long ll;
using namespace std;
/*-----------------------------------------------------------------*/
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
#define INF 0x3f3f3f3f
const int N = 5e3 + 10;
const int M = 1e9 + 7;
const double eps = 1e-5;
char s1[N], s2[N];
int dp1[N][N];
int dp2[N][N];
int main() {
IOS;
cin >> s1 + 1 >> s2 + 1;
int n, m;
n = strlen(s1 + 1), m = strlen(s2 + 1);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(s1[i] == s2[j]) {
dp1[i][j]++;
dp1[i][j] = (dp1[i][j] + dp1[i - 1][j - 1]) % M;
}
dp2[i][j]++;
dp1[i][j] = (dp1[i][j] + dp1[i][j - 1]) % M;
dp1[i][j] = (dp1[i][j] + dp1[i - 1][j]) % M;
dp1[i][j] = (dp1[i][j] - dp1[i - 1][j - 1]) % M;
dp2[i][j] = (dp2[i][j] + dp2[i][j - 1]) % M;
dp2[i][j] = (dp2[i][j] + dp2[i - 1][j]) % M;
}
}
// cout << dp1[n][m] << endl;
ll ans = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(s1[i] < s2[j]) {
ans = (ans + 1ll * (dp1[i - 1][j - 1] + 1) * (dp2[n - i][m - j] + 1) % M) % M;
}
}
}
cout << (ans % M + M) % M << endl;
}
King of Range
用双端队列维护最大值和最小值，每次插入一个数后从两个队列的队头弹出差值大于k的位置（因为差值递增），累计统计答案即可。
#include <bits/stdc++.h>
#define endl '
'
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mp make_pair
#define seteps(N) fixed << setprecision(N)
typedef long long ll;
using namespace std;
/*-----------------------------------------------------------------*/
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
#define INF 0x3f3f3f3f
const int N = 3e5 + 10;
const double eps = 1e-5;
typedef pair<int, int> PII;
int arr[N];
PII mx[N], mi[N];
int s1, t1, s2, t2;
int main() {
IOS;
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> arr[i];
}
while(m--) {
s1 = t1 = 0;
s2 = t2 = 0;
int k;
cin >> k;
ll ans = 0;
int cnt = 0;
for(int i = 1; i <= n; i++) {
int cnt1 = 1, cnt2 = 1;
while(s1 != t1 && mx[t1 - 1].first <= arr[i]) cnt1 += mx[t1 - 1].second, t1--;
while(s2 != t2 && mi[t2 - 1].first >= arr[i]) cnt2 += mi[t2 - 1].second, t2--;
mx[t1++] = {arr[i], cnt1};
mi[t2++] = {arr[i], cnt2};
while(s1 != t1 && s2 != t2 && mx[s1].first - mi[s2].first > k) {
if(mx[s1].second > mi[s2].second) {
mx[s1].second -= mi[s2].second;
cnt += mi[s2].second;
s2++;
} else {
mi[s2].second -= mx[s1].second;
cnt += mx[s1].second;
s1++;
if(!mi[s2].second) s2++;
}
}
ans += cnt;
}
cout << ans << endl;
}
}