2019牛客多校第10场

Myth丶恋晨 2023-10-11 09:16 14阅读 0赞

A：01概率退背包，这是赛后看题解补的，概率的背包和普通的背包有点不太一样，但思想还是差不多的

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

/*
    n张牌带权值ai随机洗牌，然后抽牌
    将每次抽到的ai累计到sum，可以重复抽牌，也可以停止
    如果最后sum在区间（a,b]则胜利，反之失败
    问获胜概率
    
    先考虑该问题的弱化版：从n张牌里选出点数总和在(a,b]区间的概率
    用一个二维的背包可以解决dp[k,i,j]表示前k张牌选i张点数和为j的概率
    dp[k][i][j]=dp[k-1][i][j](第k张牌不选的情况)+dp[k-1][i-1][j-x[k]]*i/(n-i+1)
    (选择第k张牌的情况：从之前选的i张里选一张，总共有i种策略，其位置用k代替，在剩下n-i+1张牌里选k的概率是1/(n-i+1)) 
    
    再来考虑这道题的情况，和弱化版不同之处在于：当前k-1张牌的和>a时，第k张牌是不同用取的
    所以我们先假设第k张牌不选，前k-1张牌的点数总和范围就是(a-x,min(a,b-x)) 
    那么前k-1张牌怎么取是无所谓的，所以我们枚举最后一张牌选idx，除了这张牌之外的牌求一次背包dp，dp[i][j]表示除了idx，选i张牌凑出j的概率 
    
    转化为每种情况的概率对答案的贡献
    用f[k][i][j]表示在n张牌中选i张，凑出分数j的概率，显然是个背包问题
    f[k][i][j]=f[k-1][i][j]+f[k-1][i-1][j-x[k]]*i/(n-i+1);
    意义为在前k-1个中取i张牌凑出分数j的概率+在k-1个中取i-1张牌凑出分数j-x[k]的概率
    最后*i/(n-i+1)是因为在剩下n-i+1张牌中抽到k的概率是1/(n-i+1)，在i张牌里抽i-1的情况有i种
    
    枚举最后一张抽的牌idx，抽完这张牌获胜的要求是之前的点数为（a-x,min(a,b-x)),
    dp[i][j]表示除了牌idx，在剩余的牌中抽的i张凑出j分的概率
    显然有dp[i][j]=f[n-1][i][j]，每个dp[i][j]对答案的贡献是dp[i][j]/(n-i)
    意义是先取了i张牌凑出点数j，然后最后一张取idx的概率是1/(n-i)，所以每种状态的贡献要*1/(n-i)
        
    计算复杂度：外层枚举每一张不选的牌，内层O(n^3)求f，O(n^2)求dp[i][j]的贡献，O(n^4)TLE
    考虑到在n张牌中不选一张牌，可用01退背包，即先预处理选没有不选的情况下的f，然后枚举删掉一张牌的影响即可
    这样计算f的复杂度降到O(n^2),
    设当前不取牌k，dp[i][j]=f[n][i][j]-dp[i-1][j-x[k]]*i/(n-i+1)
    意义是无限制的概率-留着位置让k被选中的总概率，即在i张牌中任意挑一张不选，凑成体积j-x[k]的总概率*第i张牌选到k的概率（1/n-i+1） 
    */
    #include<bits/stdc++.h>
    using namespace std;
    #define maxn 505
    typedef double db;
    db f[2][maxn][maxn],dp[maxn][maxn];
    int n,a,b,x[maxn];
    
    int main(){
        cin>>n>>a>>b;
        for(int i=1;i<=n;i++)scanf("%d",&x[i]);
        f[0][0][0]=1;int cur=0;
        for(int k=1;k<=n;k++){
            cur^=1;
            for(int i=0;i<=k;i++)
                for(int j=0;j<=b;j++){
                    f[cur][i][j]=f[cur^1][i][j];//不选第k张 
                    if(i>0 && j>=x[k])//选第k张 
                        f[cur][i][j]+=f[cur^1][i-1][j-x[k]]*i/(n-i+1); 
                }
        }
        //f[cur][i][j]就是前n张选i张凑j的概率
        //枚举每张不选的idx，进行退背包,求总概率
        db ans=0; 
        for(int idx=1;idx<=n;idx++){
            memset(dp,0,sizeof dp);
            for(int i=0;i<n;i++)//除idx外选i张
                for(int j=0;j<=b;j++){
         //凑出体积b 
                    dp[i][j]=f[cur][i][j]; 
                    if(i>0 && j>=x[idx])
                        dp[i][j]-=dp[i-1][j-x[idx]]*i/(n-i+1);
                }
            int L=max(0,a-x[idx]+1),R=min(a,b-x[idx]);//求点数在这个范围的概率和 
            for(int i=0;i<n;i++)
                for(int j=L;j<=R;j++)
                    ans+=dp[i][j]/(n-i);//剩下的n-i张牌翻到idx的概率为1/(n-i) 
        }
        printf("%.10lf\n",ans);
        return 0;
    }

B：斐波那契数列

D:大数ex\_crt

E:希尔伯特排序，分形法

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    #define maxn 1000005
    #define ll long long
    struct Node{ll x,y,id;}p[maxn];
    ll n,k;
     
    long long f(int n, int x, int y) {
        if (n == 0) return 1;
        int m = 1 << (n - 1);
        if (x <= m && y <= m)return f(n - 1, y, x);
        if (x > m && y <= m) return 3LL * m * m + f(n - 1, m-y+ 1, m * 2 - x + 1);
        if (x <= m && y > m)return 1LL * m * m + f(n - 1, x, y - m);
        if (x > m && y > m)return 2LL * m * m + f(n - 1, x - m, y - m);
    }
    int cmp(Node &a,Node &b){
         return a.id<b.id;}
    int main(){
        cin>>n>>k;
        for(int i=1;i<=n;i++){
            scanf("%lld%lld",&p[i].x,&p[i].y);
            swap(p[i].x,p[i].y);
            p[i].id=f(k,p[i].x,p[i].y);
        }
        sort(p+1,p+1+n,cmp);
        for(int i=1;i<=n;i++){
            swap(p[i].x,p[i].y);
            cout<<p[i].x<<" "<<p[i].y<<endl;
        }
    }

F：数据结构（加速dp？）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
     
    using namespace std;
     
    #define maxn 500005
     
    int r,n,x[maxn],y[maxn];
     
    int cnt[maxn],a[maxn];//?y[i]???????
     
    vector<int> v[maxn];//??x???y??
     
    template<typename T>
     
    inline void rd(T&x){
     
        x=0;int f=1;char ch=getchar();
     
        while(ch<'0' ||ch>'9'){ if(ch=='-')f=-1; ch=getchar(); }
     
        while(ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
     
        x*=f;
     
    }
     
       
     
    #define lson l,m,rt<<1
     
    #define rson m+1,r,rt<<1|1
     
    int seg[maxn<<2];
     
    void pushup(int rt){
     
        seg[rt]=max(seg[rt<<1],seg[rt<<1|1]);
     
    }
     
    void build(int l, int r, int rt) {
     
      if (l == r) {
     
        seg[rt] = a[l];
     
        return;
     
      }
     
      int m = l + r >> 1;
     
      build(lson);
     
      build(rson);
     
      pushup(rt);
     
    }
     
    void update(int p, int x,int l,int r,int rt) {
     
      if (l == r) {
     
        seg[rt] += x;
     
        return;
     
      }
     
      int m = l + r >> 1;
     
      if (p <= m)
     
        update(p,x,lson);
     
      else
     
        update(p,x,rson);
     
      pushup(rt);
     
    }
     
      
     
    int main(){
     
        //freopen("2.txt","r",stdin);
     
        rd(n);rd(r);
     
        int xMax=0,yMax=0;
     
        for(int i=1;i<=n;i++){
     
            rd(x[i]);rd(y[i]);
     
            x[i]++,y[i]++;
     
            xMax=max(xMax,x[i]);
     
            yMax=max(yMax,y[i]);
     
            v[x[i]].push_back(y[i]);
     
            cnt[y[i]]++;
     
        }
     
        for(int i=1;i<=yMax;i++){
     
            a[i]=cnt[i];
     
            if(i+r<=xMax)a[i]+=cnt[i+r];
     
            if(i+2*r<=xMax)a[i]+=cnt[i+2*r];
     
        }
     
        build(1,yMax,1);//?????a[i]
     
           
     
               
     
        int ans=0;
     
        for(int xx=1;xx<=xMax;xx++){
     
             
     
            int sum=v[xx].size()/*+v[xx+r].size()+v[xx+2*r].size()*/;//x????
     
            for(int j=0;j<v[xx].size();++j){
         //???1?x????
     
                int yy=v[xx][j];
     
                update(yy,-1,1,yMax,1);
     
                if(yy>r)
     
                    update(yy-r,-1,1,yMax,1);
     
                if(yy>2*r)
     
                    update(yy-2*r,-1,1,yMax,1);    
     
            }
     
            if(xx+r<=xMax){
     
                sum+=v[xx+r].size();
     
                for(int j=0;j<v[xx+r].size();++j){
         //???2?x????
     
                    int yy=v[xx+r][j];
     
                    update(yy,-1,1,yMax,1);
     
                    if(yy>r)
     
                        update(yy-r,-1,1,yMax,1);
     
                    if(yy>2*r)
     
                        update(yy-2*r,-1,1,yMax,1);    
     
                }
     
            }
     
            if(xx+2*r<=xMax){
     
                sum+=v[xx+r*2].size();
     
                for(int j=0;j<v[xx+2*r].size();++j){
         //???3?x????
     
                    int yy=v[xx+2*r][j];
     
                    update(yy,-1,1,yMax,1);
     
                    if(yy>r)
     
                        update(yy-r,-1,1,yMax,1);
     
                    if(yy>2*r)
     
                        update(yy-2*r,-1,1,yMax,1);    
     
                }
     
            }
     
            sum+=seg[1];
     
            for(int j=0;j<v[xx].size();++j){
         //???1?x????
     
                int yy=v[xx][j];
     
                update(yy,1,1,yMax,1);
     
                if(yy>r)
     
                    update(yy-r,1,1,yMax,1);
     
                if(yy>2*r)
     
                    update(yy-2*r,1,1,yMax,1);     
     
            }
     
            if(xx+r<=xMax){
     
                for(int j=0;j<v[xx+r].size();++j){
         //???2?x????
     
                    int yy=v[xx+r][j];
     
                    update(yy,1,1,yMax,1);
     
                    if(yy>r)
     
                        update(yy-r,1,1,yMax,1);
     
                    if(yy>2*r)
     
                        update(yy-2*r,1,1,yMax,1);     
     
                }
     
            }
     
            if(xx+2*r<=xMax){
     
                for(int j=0;j<v[xx+2*r].size();++j){
         //???3?x????
     
                    int yy=v[xx+2*r][j];
     
                    update(yy,1,1,yMax,1);
     
                    if(yy>r)
     
                        update(yy-r,1,1,yMax,1);
     
                    if(yy>2*r)
     
                        update(yy-2*r,1,1,yMax,1);     
     
                }
     
            }
     
            ans=max(ans,sum);
     
        }
     
        cout<<ans<<endl;
     
    }

H:同构图

J：斜率优化（分治）加速dp，待补

转载于:https://www.cnblogs.com/zsben991126/p/11372255.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif