jzoj2018.7.6【2018提高組】模拟B組

1.二分圖計數

10

#include <cstdio>
#include <cstring>

using namespace std;

const int q[18]={,,,,,,,,,,,,,,,,,};
const long long N=;
int n,m,g,d[],e[],a[],h[]; 
long long ans,b;
long long f[];
long long s,ss;

void work(int tot){ 
    int bz=;
    s=tot;
    f[tot+]=;
    for (int i=tot;i>=;i--)
        f[i]=f[i+]*(m-i+);
    b=f[]%N;
    for (int i=;i<=d[];i++) h[i]=d[i];
    for (int i=;i<=d[];i++){
        ss=;
        for (int j=;j<=d[];j++)
            ss+=(s-h[j])*d[j],h[j]=(s-h[j])*d[j];
        if (bz) b-=(ss/i)*f[i]; else b+=(ss/i)*f[i];
        bz^=;b%=N;s=ss;
    }
    if (d[]==) b-=f[]*tot;
    if (d[]==) b--;
}

void dfs(int i,int k,long long c){
    if (i>n){
        if (k) work(k),ans=(ans+(b%N)*(c%N))%N;
        return;
    }
    dfs(i+,k,c);
    for (int j=;j<=d[];j++)
        if (e[j]==a[i]) {g=j;break;}
    if (g) d[g]++; else d[++d[]]++,e[d[]]=a[i];
    dfs(i+,k+,c+q[i-1]);
    if (g) d[g]--,g=; else e[d[]]=e[],d[d[]--]=;
}

int main(){
//  freopen("bipartite.in","r",stdin);
//  freopen("bipartite.out","w",stdout);
    scanf("%d%d",&n,&m);
    memset(e,,sizeof(e));
    for (int i=;i<=n;i++)
        scanf("%d",&a[i]);
    dfs(,,);
    printf("%lld",ans);
}
           

2.撲克遊戲

100

=合并果子

=貪心，每次找最小的兩個相加計入答案，删去這兩個，把這兩個的和加入

#include <cstdio>
#include <cstring>

using namespace std;

int n,a[],ans;

void down(int x,int n){
    while (x*<n){
        int p=x*;
        if (a[x]>a[p]||a[x]>a[p+]){
            if (a[p+]<a[p]&&p+<=n) p++;
            int t=a[x];
            a[x]=a[p];a[p]=t;
        }
        x=p;
    }
}

int main(){
    scanf("%d",&n);
    memset(a,,sizeof(a));
    for (int i=;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for (int i=n;i>=;i--) down(i,n);
    for (int i=n;i>=;i--){
        int p;
        if (a[]<a[]) p=; else p=;       
        ans+=a[p]+a[];
        a[p]+=a[];
        a[]=a[i];
        a[i]=a[];
        down(p,i-);
        down(,i-);
    }
    printf("%d",ans);
}
           

3.表白

100

二分+dp

二分答案，dp判斷可行性

科學的題解：

那麼我們二分t 之後可以得到每個人的兩個參數Q1i-C1i*t 以及Q2i-C2i*t，采取最科學合理的方式安排人手即可。對于小資料我們可以采用O(N^3)的動态規劃，即f[i][j][k] 表示前i 個人中挑了j 個人到第一隊，挑了k個人到第二隊，轉移方程是顯而易見的。

對于100%的大資料我們需要分析觀察資料，我們發現，對N1+N2個人，我們隻考慮如何安排這些人時，我們一定可以按照他們的(Q1i-C1i*t)-(Q2i-C2i*t)排序之後進行選擇。同樣的，我們對N個人先進行排序之後，用f[i][j] 表示前i 個人取了j 個進第一隊，用g[i][j] 表示後i 個人取了j 個進第二隊，最後用f[i][N1] +g[N-i][N2]來更新答案即可。另外注

意精度誤差就可以了。

被精度誤差卡了一會，發現讀入時不要用小數讀

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

const double e=;
int q1[],c1[],q2[],c2[];
double l,r,mid;
int n,n1,n2,bz[];
struct node{
    double a1,a2,a3;
}a[];
double f[][],g[][];

bool comp(node a,node b){
    return a.a3>b.a3;
}

bool work(double k){
    for (int i=;i<=n;i++){
        a[i].a1=(double)q1[i]-c1[i]*k;
        a[i].a2=(double)q2[i]-c2[i]*k;
        a[i].a3=a[i].a1-a[i].a2;
    }
    sort(a+,a++n,comp);   
    memset(f,,sizeof(f));
    memset(g,,sizeof(g));
    g[][]=;f[][]=;
    for (int i=;i<=n;i++){
        g[i][]=;
        for (int j=;j<=min(n1,i);j++)
            g[i][j]=max(g[i-][j],g[i-][j-]+a[i].a1);
    }
    for (int i=n;i>=;i--)
    {
        f[n-i+][]=;
        for (int j=;j<=min(n-i+,n2);j++)
            f[n-i+][j]=max(f[n-i][j],f[n-i][j-]+a[i].a2);
    }
    for (int i=n1;i<=n-n2;i++)
    if (g[i][n1]+f[n-i][n2]>=) return true;
    return false;
}

int main(){
    scanf("%d%d%d",&n,&n1,&n2);
    for (int i=;i<=n;i++){
        scanf("%d%d%d%d",&q1[i],&c1[i],&q2[i],&c2[i]);
    }
    l=,r=;
    while (l+e<r){
        mid=(l+r)/;
        if (work(mid)) l=mid;
                else r=mid-e;
    }
    printf("%.6f",l);
}