每一种物品有一份额和体量,有P/Q的票房价值会爆炸

迎接待上访问~原版的书文出处——博客园-zhouzhendong

题目:

欢迎访问~原来的书文出处——博客园-zhouzhendong

去天涯论坛看该题解


1. 中位数

去网易看该题解


难题传送门 – 洛谷2973


【难题讲述】

题材传送门 – BZOJ1076


题意归纳

  有N个城市,M条双向道路组成的地图,城市标号为1到N。“西瓜炸弹”放在1号都市,保障城市1起码连接着三个任何都市。“西瓜炸弹”有P/Q的几率会爆炸,每一趟进入其它城市时,爆炸的可能率一样。假如它从未爆炸,它会随机的挑选一条道路到另1个城池去,对于近期都聚会场地连接的每一条道路都有雷同的恐怕被选中。对于给定的地图,求每一个城市“西瓜炸弹”爆炸的概率。


给定C个不等物品,每一个物品有一份量和体积,保障各个物品的重量不平等。从中选出N个物品,在容积不超越F的景观下,使得选出的物品的轻重的中位数最大。所谓中位数,就是排序后高居最中间的份量,比如3,8,9,7,5的中位数是7。

题意回顾

  有n个东西,k次扔出来。每回等可能率扔出里面二个。

  你能够拿这么些事物,不过有标准,得在得到钦命东西之后再拿,不然白拿。

  获得3个东西,会获得其权值。能够是负数。


 

题解

  通过概率关系创设方程:

  其中in[j]表示节点j的出度。

  图片 1

  然后高斯消元跑一跑就能够了。


【输入格式】

题解

  状压dp跑一发。

  一起头想写正着dp的,因为自己以为这么听挺不难想的。

  可是网上的大腕都说是倒着的。于是小编倒着了。

  方程是这般的:

  dp[i][j]代表扔出来i次之后,状态为j,在那事后方可拿走的最大受益。

  dp[i][j]=(∑F[k])/n

  F[k]分三种情状。假诺在状态j的情状下得以取k,那么F[k]
= max(dp[i+1][j],dp[i+1][j | (1<<k)] + v[k])

    否则F[k] = dp[i+1][j]

  依据意义,最终输出dp[0][0]即可。


 

代码

#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int N=300+5;
const double Eps=1e-9;
int n,m,P,Q,cnt[N];
bool g[N][N];
double p,a[N][N],x[N];
void Gauss(){
    int row=n,col=n,k,c;
    for (k=c=1;k<=row,c<=col;k++,c++){
        int Mk=k;
        for (int i=k+1;i<=row;i++)
            if (fabs(a[Mk][c])<fabs(a[i][c]))
                Mk=i;
        if (fabs(a[Mk][c])<Eps){
            k--;
            continue;
        }
        if (k!=Mk)
            for (int i=c;i<=col+1;i++)
                swap(a[k][i],a[Mk][i]);
        for (int i=k+1;i<=row;i++)
            for (int j=col+1;j>=c;j--)
                a[i][j]=a[i][j]-a[k][j]*a[i][c]/a[k][c];
    }
    memset(x,0,sizeof x);
    for (int i=k;i>=1;i--){
        x[i]=a[i][n+1];
        for (int j=i+1;j<=n;j++)
            x[i]-=a[i][j]*x[j];
        x[i]/=a[i][i];
    }
}
int main(){
    scanf("%d%d%d%d",&n,&m,&P,&Q);
    p=double(P)/double(Q);
    memset(g,0,sizeof g);
    memset(cnt,0,sizeof cnt);
    for (int i=1,a,b;i<=m;i++){
        scanf("%d%d",&a,&b);
        g[a][b]=g[b][a]=1;
        cnt[a]++,cnt[b]++;
    }
    memset(a,0,sizeof a);
    a[1][n+1]=p;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++){
            if (i==j){
                a[i][j]=1;
                continue;
            }
            if (!g[i][j])
                continue;
            double del=(1.0-p)/double(cnt[j]);
            a[i][j]-=del;
        }
    Gauss();
    for (int i=1;i<=n;i++)
        if (fabs(x[i])<Eps)
            x[i]=0;
    for (int i=1;i<=n;i++)
        printf("%.9lf\n",x[i]);
    return 0;
}

  

先是行:四个用空格分开的整数:N,C和F。1 ≤ N ≤ 一九九九9,N ≤ C ≤ 105

代码

#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
const int N=15+5,M=100+5,S=(1<<15)+5;
int n,m,v[N],pre[N];
double dp[M][S];
int main(){
    scanf("%d%d",&m,&n);
    memset(pre,0,sizeof pre);
    for (int i=0,p;i<n;i++){
        scanf("%d",&v[i]);
        while (scanf("%d",&p)&&p!=0)
            pre[i]|=1<<(p-1);
    }
    for (int i=m-1;i>=0;i--)
        for (int j=0;j<(1<<n);j++){
            dp[i][j]=0;
            for (int k=0;k<n;k++)
                if ((pre[k]&j)==pre[k])
                    dp[i][j]+=max(dp[i+1][j],dp[i+1][j|(1<<k)]+v[k]);
                else
                    dp[i][j]+=dp[i+1][j];
            dp[i][j]/=n;
        }
    printf("%.6lf",dp[0][0]);
    return 0;
}

 

,0 ≤ F ≤ 2 × 109

第②行到C + 1行:每行有七个用空格分开的平头。第三个数是这几个物品的重量Wi,第贰个数是其一物品的体量Qi。

【输出格式】

首先行:二个整数,表示能够获得的最大中位数,假诺F装不下任何N个物品,则输出-1。

【输入样例】

3 5 70

30 25

50 21

20 20

5 18

35 30

【输出样例】

35

【样例解释】

慎选重量为 5, 35, 50 的物料,中位数为 35,体量18 + 30 + 21 = 69,小于70。

【数据范围】

    40%的数据,1 ≤ N≤ C ≤200

100%的数据,1 ≤ N ≤ 19999,N ≤ C ≤ 105,0 ≤ F ≤ 2 × 109,0 ≤ Qi≤ 105,0 ≤ Wi≤ 2 × 109。保证n为奇数。

 

 

2. 爆炸

【难题讲述】

 有N个城市,M条双向道路组成的地图,城市里发布的标准号为1到N。“西瓜炸弹”放在1号都市,保证城市1至少连接着三个其余都市。“西瓜炸弹”有P/Q的票房价值会爆炸,每一趟进入别的城市时,爆炸的可能率一样。假设它没有爆炸,它会随机的选拔一条道路到另1个都市去,对于当前都聚会地方连接的每一条道路都有相同的只怕性被入选。对于给定的地形图,求每种城市“西瓜炸弹”爆炸的几率。

比如说,假诺唯有七个都市1和2,它们被一条道路连接起来。最初步“西瓜炸弹”放在城市1,每一回进入城市它都有二分一的或然性爆炸: 

1 — 2

大家就有以下或然的路径(当中最终一项是终止城市,即“西瓜炸弹”爆炸并污染该城市): 

1: 1 
2: 1-2 
3: 1-2-1 
4: 1-2-1-2 
5: 1-2-1-2-1 
etc. 

为了找出“西瓜炸弹”在城市1放炮的恐怕,大家得以把第二 、三 、5…种途径出现的可能率加起来(在那一个例子中即把具有奇数路径出现的恐怕性加起来)。 
对此第k种途径出现的大概为(二分之一)^k:在通过前k-3回时,炸弹相对不会在城池1爆裂(每三遍的可能率为1 – 八分之四 = 八分之四),然后最终在城市1放炮(可能率为百分之五十)。 

由此,在都会1爆裂的也许便是 八分之四 + (二分之一)^3 + (一半)^5 + … ,把那么些数都加起来就分外2 / 3,约为0.666666667。 
据此在城池2爆裂的只怕就是三分之一,约为0.333333333。

【输入格式】

第二行:八个被空格分隔整数:N,M,P和Q 

第②..M+1行:第i行描述了多少个空格分隔的平头:A_j 和 B_j(表示城市A_j与B_j相连)

【输出格式】

第一..N行:第i作为贰个小数,表示第i个城市 “西瓜炸弹”爆炸的概率。至少要精确到10^-6才有效。

【输入样例1】

2 1 1 2 
1 2

【输出样例1】

0.666666667 
0.333333333

【输入样例2】

3 2 1 3

1 2

3 2

【输出样例2】

0.466666667

0.400000000

0.133333333

【数据范围】

20%  2<=N<=25 , 1<=M<=100

100% 2 <= N <= 300 ,1 <= M <= 44850 ,1 <= P <= 1,000,000,1 <= Q <= 1,000,000

 

3.行列划分

 

【题目叙述】

给定三个行列{An},现在,须求把那几个行列划分成K个子类别,使得各类子体系包蕴的数的个数不少于2,并且依旧非升,要么非降。你的天职就是求出K的细小值。

 

【输入文件】

输入第①行贰个正整数N,表示类别长度,接下去N行,第i行代表成分Ai-1

 

【输出文件】

借使不能分开这一个队列,输出一个数0;不然输出K。

 

【样例输入1】

6

12

33

97

18

15

33

 

【样例输出1】

2

【样例输入2】

1

88

【样例输出2】

0

【样例输入3】

4

77

22

22

11

【样例输出3】

1

【数据规模】

对于30%的数据,1<=N<=10;

对于100%的数据,1<=N<=25,1<=Ai<=100;

 

 题解:

一:依照体量排序

1.预甩卖前i小、大的体量的物料的份量拿n/1个的微小重量

然后1个个枚举过去,看看是或不是成立

至于预处理就用贰个堆好了

二:高斯消元+可能率dp

自然想要简单的dp+收敛,没有想到数据那么坑。。。

(其实根据自由的可能率大概能够过p/q>0.02的动静吧)

正解:高斯高校+可能率

列出n个方程,解n个数字,正是高斯消元

三:迭代深搜

枚举有多少个能够,然后遵照类似与导弹拦截的贪心方法做贪心

代码:

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=200005;
int f[N],d[N],l,a[N],b[N],n,m,F;
long long f1[N],f2[N];
void up(int x)
{
    if (x==1)return;
    if (d[x]>d[x/2])
     {
         swap(d[x],d[x/2]);
         up(x/2);
     }
}
void down(int x)
{
    int i=x;
    if (x*2<=l&&d[x]<d[x*2])i=x*2;
    if (x*2<l&&d[i]<d[x*2+1])i=x*2+1;
    if (i!=x)
     {
         swap(d[x],d[i]);
         down(i);
     }
}
int cmp(int x,int y)
{
    return a[x]<a[y];
}
int main()
{
    freopen("finance.in","r",stdin);
    freopen("finance.out","w",stdout); 
    scanf("%d%d%d",&n,&m,&F);
    for (int i=1;i<=m;i++)scanf("%d%d",&a[i],&b[i]),f[i]=i;
    sort(f+1,f+m+1,cmp);
    for (int i=1;i<=n/2;i++)d[i]=b[f[i]],f1[i]=f1[i-1]+b[f[i]];
    l=n/2;
    for (int i=1;i<=n/2;i++)up(i);
    for (int i=n/2+1;i<=m;i++)
     {
         if (b[f[i]]>=d[1])
          {
              f1[i]=f1[i-1];
              continue;
          }
         f1[i]=f1[i-1]+b[f[i]]-d[1]; 
         d[1]=b[f[i]];
        down(1); 
     }
    memset(d,0,sizeof d);
    for (int i=m;i>m-n/2;i--)d[m-i+1]=b[f[i]],f2[i]=f2[i+1]+b[f[i]];
    for (int i=1;i<=n/2;i++)up(i);    
    for (int i=m-n/2;i;i--)
     {
         if (b[f[i]]>=d[1])
          {
              f2[i]=f2[i+1];
              continue;
          }
         f2[i]=f2[i+1]+b[f[i]]-d[1]; 
         d[1]=b[f[i]];
        down(1);          
     }  
    for (int i=m-n/2;i>n/2;i--)
     if (F>=f1[i-1]+f2[i+1]+b[f[i]])
      {
          printf("%d",a[f[i]]);
          return 0;
      }
    puts("-1");
    return 0;  
} 

#include <bits/stdc++.h>
using namespace std;
typedef double ld;
const int N=305;
const ld eps=1e-15;
int n,m,mp[N][N],du[N];
ld f[N][N],sum,P,Q;
int main()
{
    freopen("dotp.in","r",stdin);
    freopen("dotp.out","w",stdout);
    scanf("%d%d%lf%lf",&n,&m,&P,&Q);
    for(int i=1,x,y;i<=m;i++)
     {
        scanf("%d%d",&x,&y);
        mp[x][y]++;mp[y][x]++;
        du[x]++;du[y]++;
     }
    f[1][n+1]=1;
    for(int i=1;i<=n;i++)
     {
        f[i][i]=1;
        for(int j=1;j<=n;j++)
         if(mp[i][j])f[i][j]+=((ld)P/Q-1)/du[j]*mp[i][j];
     }
    for(int i=1;i<=n;i++)
     {
        int t=i;
        for(int j=i;j<=n;j++)
         if(fabs(f[j][i])>eps)t=j;
        for(int j=1;j<=n+1;j++)swap(f[i][j],f[t][j]);
        for(int j=1;j<=n;j++)
         if(j!=i&&fabs(f[j][i])>eps)
          {
            ld t=f[j][i]/f[i][i];
            for(int k=1;k<=n+1;k++)f[j][k]-=f[i][k]*t;
          }
     }
    for(int i=1;i<=n;i++)sum+=(f[i][i]=f[i][n+1]/f[i][i]);
    for(int i=1;i<=n;i++)printf("%.9lf\n",(double)(f[i][i]/sum+eps));
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=30;
int a[N][N],b[N][N],A,B,ans[N],x[N],dep,n;
void DFS(int u)
{
    if (A+B>dep)return;
    if (u>n)
     {
        for (int i=1;i<=A;i++)
         if (*a[i]<2)return;
        for (int i=1;i<=B;i++)
         if (*b[i]<2)return;
        printf("%d\n",dep);
        exit(0);
     }
    int v=0;
    for (int i=1;i<=A;i++)
     if (a[i][*a[i]]<=x[u]&&(!v||a[v][*a[v]]<a[i][*a[i]]))v=i;
    if (!v)
     {
        ++A;
        a[A][++*a[A]]=x[u];
        ans[u]=A;
        DFS(u+1);
        --*a[A--];
     }
    else
     {
        a[v][++*a[v]]=x[u];
        ans[u]=v;
        DFS(u+1);
        --*a[v];
     }
    v=0;
    for (int i=1;i<=B;i++)
     if (b[i][*b[i]]>=x[u]&&(!v||b[v][*b[v]]>b[i][*b[i]]))v=i;
    if (!v)
     {
        ++B;
        b[B][++*b[B]]=x[u];
        ans[u]=dep+1-B;
        DFS(u+1);
        --*b[B--];
     }
    else
     {
        b[v][++*b[v]]=x[u];
        ans[u]=dep+1-v;
        DFS(u+1);
        --*b[v];
     }
}
int main()
{
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;i++)scanf("%d",&x[i]);
    for (dep=1;dep*2<=n;dep++)
      {
        memset(a,0,sizeof a);
        memset(b,0,sizeof b);
        A=B=0;
        DFS(1);
     }
    puts("0");    
    return 0;
}

 

相关文章