2022-10-24总结

Medals

Description

你有 $N$ 个朋友，他们会来你家玩，第 $i$ 个人 $1 \sim A_i$ 天来玩，然后 $A_i+1 \sim 2A_i$ 天不来，然后 $2A_i+1 \sim 3A_i2$ 又会来，以此类推。

每天你会选一个来玩的人，给他颁个奖，如果没人来玩，你就不颁奖。

你要给每个人都颁 $K$ 个奖，问至少需要多少天。

Input

$N$ $K$

$A_1, A_2, \cdots, A_n$

Output

答案

Hint

$N \le 18, K \le 10^5, A_i \le 10^5$

Solution

天数的上界是 $2NK$，然后可以二分，用网络流 check，然而跑不动。

我们可以拆点看成二分图匹配问题，然后利用霍尔定理判断，进行一个超集和的统计。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int A = 1e5+10;
 
int n, k;
int a[20];
int t[1<<18];
int st[3*18*A];
 
bool check(int mid);
 
#define pos(i) (1<<(i-1))
 
int main()
{
    cin >> n >> k;
    const int up = 5*n*k;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        for(int j = 1; j <= 3*n*k; j++)
            if(!(((j-1)/a[i])&1)) st[j] |= pos(i);
    }
     
    int l = n*k, r = 5*n*k, mid;
    while(l < r)
    {
        mid = (l+r)>>1;
        if(check(mid))
            r = mid;
        else
            l = mid+1;
    }
    cout << l << "\n";
}
bool check(int mid)
{
    memset(t, 0, sizeof(t));
    for(int i = 1; i <= mid; i++)
        t[(1<<n)-1]++,
        t[((1<<n)-1)-st[i]]--;
     
    for(int i = 1; i <= n; i++)
        for(int j = 0; j < (1<<n); j++)
            if(j&pos(i)) t[j-pos(i)] += t[j];
     
    for(int i = 1; i < (1<<n); i++)
        if(t[i] < k*__builtin_popcount(i))
            return false;
    return true;
}

Google Code Jam

Description

一场考试的时间为 $T$ ，有 $n$ 道题，每道题都可以花 $t1_i$ 的时间获得 $s1_i$ 的暴力分，并且可以在打完暴力后再花 $t2_i$ 的时间多获得 $s2_i$ 的分，但有 $p_i$ 的概率写挂正解，写挂可以不提交。求最大期望得分以及最大期望得分下的最小期望罚时（这里罚时定义为最后一次提交代码的时间）。

Input

第一行输入两个整数 $n$ 和 $T$。
接下来 $n$ 行每行五个数 $s1_i,s2_i,t1_i,t2_i,p_i$，其中 $s1_i,s2_i,t1_i,t2_i$ 为整数，$p_i$ 为浮点数。

Output

输出一行两个实数，绝对或相对误差小于 $10^{-9}$ 算作正确。

Hint

$1 \le n \le 1000, 1 \le T \le 1560, t1_i,t2_i \le 1560, s1_i,s2_i \le 10^9, 0 \le p_i \le 1$ 且 $p_i$ 最多有 $6$ 为小数。

Solution

设 $f_i$ 为花费时间为 $i$ 时最大期望得分，$g_i$ 为最小期望罚时。

首先因为罚时的存在，所以每道题必定时先打暴力再打正解，然后因为正解打挂了可以不交，所以两道题顺序不一样的话期望罚时也不一样，我们可以列个式子排序一下就行，然后最大期望得分可以直接背包。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
 
typedef long double ldb;
const int N = 2005;
 
struct node {
    int a, b, s, t;
    ldb p;
};
 
int n, t;
node x[N];
ldb f[N], g[N];
 
bool equal(ldb a, ldb b)
{
    return abs(a-b) <= 1e-9;
}
bool ldb_less(ldb a, ldb b)
{
    return !equal(a, b) and a < b;
}
 
int main()
{
    cin >> n >> t;
    for(int i = 1; i <= n; i++)
    {
        cin >> x[i].a >> x[i].b >> x[i].s >> x[i].t >> x[i].p;
        x[i].p = 1-x[i].p;
    }
     
    sort(x+1, x+n+1, [](node a, node b){
        return (1-a.p)*a.t/a.p < (1-b.p)*b.t/b.p;
    });
     
    fill(f+1, f+t+1, -1);
     
     
    for(int i = 1; i <= n; i++)
    {
        for(int j = t; j >= x[i].s; j--)
        {
            ldb now = f[j-x[i].s]+x[i].a;
            if(equal(f[j], now))
                g[j] = min(g[j], g[j-x[i].s]+x[i].s);
            else if(now > f[j])
            {
                f[j] = now;
                g[j] = g[j-x[i].s]+x[i].s;
            }
             
            if(j >= x[i].s+x[i].t)
            {
                ldb tmp = f[j-x[i].s-x[i].t] + x[i].a + x[i].p*x[i].b;
                if(equal(tmp, f[j]))
                    g[j] = min(g[j], (g[j-x[i].s-x[i].t]+x[i].s)*(1-x[i].p) + j*x[i].p);
                else if(tmp > f[j])
                {
                    f[j] = tmp;
                    g[j] = (g[j-x[i].s-x[i].t]+x[i].s)*(1-x[i].p) + j*x[i].p;
                }
            }
        }
    }
     
    ldb ans = 0, mint = 0;
    for(int i = 0; i <= t; i++)
    {
        if(equal(f[i], ans))
            mint = min(mint, g[i]);
        else if(f[i] > ans)
            ans = f[i], mint = g[i];
    }
     
    printf("%.10Lf %.10Lf", ans, mint);
     
}