当前位置: 代码迷 >> 综合 >> CF739E Gosha is hunting —— WQS二分 套 WQS二分
  详细解决方案

CF739E Gosha is hunting —— WQS二分 套 WQS二分

热度:77   发布时间:2024-01-09 10:42:49.0

题目链接:点我啊╭(╯^╰)╮

题目大意:

     n n n 个神奇宝贝, a a a 个宝贝球、 b b b 个超级球
    宝贝球抓到第 i i i 个神奇宝贝的概率为 p i , p_i, pi?, 超级球为 u i u_i ui?
    求最大期望个数

解题思路:

    很明显 n 3 n^3 n3 d p dp dp 很蠢
    考虑到这里 恰好用 b b b 个超级球 的要求
    则可以用套用 W Q S WQS WQS 二分
    求最大期望,则图形为上凸包
    注意由于 d p dp dp 值为 d o u b l e double double ,所以枚举的斜率也必须为 d o u b l e double double
    时间复杂度: O ( n 2 l o g n ) O(n^2logn) O(n2logn)


    定睛一看发现 a a a b b b 都是同样的要求
    所以两者可以用 W Q S WQS WQS 二分优化
    时间复杂度: O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)


    第一次感觉对二分一无所知。。。。
    这里套用两个二分的时候,精度要加倍
    而且判别的方式要特别注意
    我 c h e c k check check 的满足需求是 n u m [ n ] < = a / b num[n] <= a / b num[n]<=a/b
    如果二分的边界判断不准确,是个很费脑的bug。。。
    有以下两种写法是可以正确处理到答案的:

double l1 = 0, r1 = 1.0, mid1, l2, r2, mid2;
while(r1 - l1 >= 0) {		// r1 - l1 > -epsmid1 = (l1 + r1) / 2;l2 = 0, r2 = 1.0;while(r2 - l2 >= 0){	// r2 - l2 > -epsmid2 = (l2 + r2) / 2;if(ck(mid1, mid2, 2)) r2 = mid2 - eps;	else l2 = mid2 + eps;		}if(ck(mid1, l2, 1)) r1 = mid1 - eps;	else l1 = mid1 + eps;	
}
ck(l1, l2, 1);
printf("%.5lf\n", dp[n] + l1 * a + l2 * b);

或者

double l1 = 0, r1 = 1.0, mid1, l2, r2, mid2;
while(r1 - l1 > eps) {		mid1 = (l1 + r1) / 2;l2 = 0, r2 = 1.0;while(r2 - l2 > eps){	mid2 = (l2 + r2) / 2;if(ck(mid1, mid2, 2)) r2 = mid2;else l2 = mid2;		}if(ck(mid1, r2, 1)) r1 = mid1;	else l1 = mid1;	
}
ck(r1, r2, 1);
printf("%.5lf\n", dp[n] + l1 * a + l2 * b);

一个 W Q S WQS WQS二分

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
const int maxn = 2e3 + 5;
const double eps = 1e-8;
int n, a, b, num[maxn][maxn];
double p[maxn], q[maxn], dp[maxn][maxn];bool ck(double x) {double tmp;for(int i=1; i<=n; i++) {for(int j=0; j<=a; j++) {dp[i][j] = dp[i-1][j], num[i][j] = num[i-1][j];tmp = dp[i-1][j] + q[i] - x;if(tmp>dp[i][j] || (tmp==dp[i][j] && num[i-1][j]+1<num[i][j])) {dp[i][j] = tmp; num[i][j] = num[i-1][j] + 1;}if(j==0) continue;tmp = dp[i-1][j-1] + p[i];if(tmp>dp[i][j] || (tmp==dp[i][j] && num[i-1][j-1]<num[i][j])) {dp[i][j] = tmp; num[i][j] = num[i-1][j-1];}tmp = dp[i-1][j-1] + p[i] + q[i] - p[i]*q[i] - x;if(tmp>dp[i][j] || (tmp==dp[i][j] && num[i-1][j-1]+1<num[i][j])) {dp[i][j] = tmp; num[i][j] = num[i-1][j-1] + 1;}}}return num[n][a] <= b;
}signed main() {scanf("%d%d%d", &n, &a, &b);for(int i=1; i<=n; i++) scanf("%lf", p+i);for(int i=1; i<=n; i++) scanf("%lf", q+i);double l = 0, r = 1.0, mid;while(r - l >= 0) {		// r - l > epsmid = (l + r) / 2;if(ck(mid)) r = mid - eps;	// r = midelse l = mid + eps;			// l = mid}ck(l);printf("%.4f\n", dp[n][a] + 1.0 * l * b);
}

W Q S WQS WQS二分 套 W Q S WQS WQS二分

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
const int maxn = 2e3 + 5;
const double eps = 1e-10;
int n, a, b, num1[maxn], num2[maxn];
double p[maxn], q[maxn], dp[maxn];bool ck(double x, double y, int op) {double tmp;for(int i=1; i<=n; i++){dp[i] = dp[i-1], num1[i] = num1[i-1], num2[i] = num2[i-1];tmp = dp[i-1] + p[i] - x;if(tmp > dp[i]){dp[i] = tmp, num1[i] = num1[i-1] + 1, num2[i] = num2[i-1];}tmp = dp[i-1] + q[i] - y;if(tmp > dp[i]){dp[i] = tmp, num1[i] = num1[i-1], num2[i] = num2[i-1] + 1;}tmp = dp[i-1] + p[i] + q[i] - p[i] * q[i] - x - y;if(tmp > dp[i]){dp[i] = tmp, num1[i] = num1[i-1] + 1, num2[i] = num2[i-1] + 1;}}if(op == 1) return num1[n] <= a;else return num2[n] <= b;
}signed main() {scanf("%d%d%d", &n, &a, &b);for(int i=1; i<=n; i++) scanf("%lf", p+i);for(int i=1; i<=n; i++) scanf("%lf", q+i);double l1 = 0, r1 = 1.0, mid1, l2, r2, mid2;while(r1 - l1 > eps) {		mid1 = (l1 + r1) / 2;l2 = 0, r2 = 1.0;while(r2 - l2 > eps){	mid2 = (l2 + r2) / 2;if(ck(mid1, mid2, 2)) r2 = mid2;else l2 = mid2;		}if(ck(mid1, r2, 1)) r1 = mid1;	else l1 = mid1;	}ck(r1, r2, 1);printf("%.5lf\n", dp[n] + r1 * a + r2 * b);
}