西北大学集训队选拔赛(重现赛)
A.坐飞机
代码:
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; int n, t; int a[maxn], b[maxn]; int p[maxn]; int main() { scanf("%d%d", &n, &t); for(int i = 1; i <= n; i ++) { scanf("%d%d", &a[i], &b[i]); } for(int i = 2; i <= n; i ++) { p[i - 1] = a[i] - b[i - 1] + 1; } n --; sort(p + 1, p + n + 1); int ans = 0; for(int i = 1; i <= n; i ++) { if(t >= p[i]) { ans ++; t -= p[i]; } } printf("%d ", ans); return 0; }
B.饱和式救援
代码:
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; int n, m, k; double x[maxn]; double dp[2100][2100]; int main() { scanf("%d%d%d", &n, &m, &k); for(int i = 1; i <= m; i ++) x[i] = 1.0; for(int i = 1; i <= n; i ++) { int a; double p; scanf("%d%lf", &a, &p); x[a] = x[a] * (1.0 - p); } for(int i = 1; i <= m; i ++) x[i] = 1.0 - x[i]; dp[1][1] = x[1]; dp[1][0] = 1.0 - x[1]; for(int i = 2; i <= m; i ++) { dp[i][0] = dp[i - 1][0] * (1.0 - x[i]); for(int j = 1; j <= i; j ++) { dp[i][j] = dp[i - 1][j] * (1.0 - x[i]) + dp[i - 1][j - 1] * x[i]; } } double ans = 0.0; for(int j = k; j <= m; j ++) { ans += dp[m][j]; } printf("%.3f ", ans); return 0; }