//唔,这次被虐的有点惨啊/(ㄒoㄒ)/~~

T1 pf

听说可以动归做?
真神奇,这不是数论题么。。。

我考场搞了两个半小时搞了个容斥原理做出来了。(心好累,人家kb随便乱搞了一下就93分。。。)

首先要明白,斐波那契完全用不上,就是来装逼吓人的。。。
直接用$i$代替$fib[i]$就行了。。。

首先,如果不需要你每个元素都至少用一次的话:序列的第一位有$n$种选择,第二位有$n-1$种选择,第三位有$n-2$中选择…第$m+1$位有$n-m$种选择,第$m+2$位依然是有$n-m$种选择,后面的也都是这样的,所以方案数是:
$n\times (n-1)\times (n-2)\times … \times (n-m) \times {(n-m)}^{p-m-1}$
也就是
$n!\div {(n-m)}!\times {(n-m)}^{p-m}$

但是这样子,可能某种元素没用。。。
所以我们要排除有的元素没用的方案。

如果是有1个元素没用的话:序列的第一位有$n-1$种选择,第二位有$n-2$种选择,第三位有$n-3$种选择,第$m+1$位有$n-m-1$种选择,第$m+2$位依然是有$n-m-1$种选择,后面的也都是这样的,所以方案数是:
$(n-1)\times (n-2)\times … \times (n-m-1) \times {(n-m-1)}^{p-m-1}$
也就是
$(n-1)!\div {(n-m-1)}!\times {(n-m-1)}^{p-m}$
然后有$n$种元素,选择其中的一个不选,有$n$种选法,所以方案数一共有:
$n!\div {(n-m-1)}!\times {(n-m-1)}^{p-m}$

这样拿上面那个$n!\div {(n-m)}!\times {(n-m)}^{p-m}$再减去这个$n!\div {(n-m-1)}!\times {(n-m-1)}^{p-m}$。。。

你就发现得到的结果比答案小了。。。

这是为什么呢?
因为你减掉了的这个1个元素不选的方案中,还包含了2个元素不选的啊!
所以我们得把2个元素不选的加上去。。。
然而这样你又把3个元素不选的多加了(本来要减去的)。。。
所以我们又要把3个元素不选的减去。。。
然后4个不选的又多减了。。。
一直这样下去,还有完吗?
当然有完——一共就n个元素啊!

所以我们就给出答案了。。。

$i$个元素不选的方案数显然是:
${C_n^i}\times (n-i)!\times (n-m-i)^{p-m}\div (n-m-i)!$
当$i$为奇数时,答案减去$i$对应的方案数;
当$i$为偶数时,答案加上$i$对应的方案数。

$\{i|0\leq i< n\}$

用杨辉三角算组合数,记得取模,而且取模记得处理负数(加上模数再取模)

代码:


#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
static const LL mod=1000000007;
LL c[1005][1005],ans,tot,n,m,p;
int main()
{
    freopen("pf.in","r",stdin),freopen("pf.out","w",stdout);
    for(LL i=1;i<=1000;i++)c[i][0]=c[i][i]=1,c[i][1]=i;
    for(LL i=3;i<=1000;i++)
        for(LL j=2;j<i;j++)
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
    scanf("%lld%lld%lld",&n,&m,&p);
    for(LL i=0;i<n;i++)
    {
        tot=c[n][i];
        for(LL j=n-i;j>n-m-i;j--)tot=(tot*j)%mod;
        for(LL j=1;j<=p-m;j++)tot=(tot*(n-m-i))%mod;
        if(!tot)break;
        if(i&1)ans=(ans-tot+mod)%mod;else ans=(ans+tot)%mod;
    }
    printf("%lld\n",ans);
    return 0;
}

T2 guard

唔,概率dp。。。
考场原地蒙圈。。。

设$f(i,j,x)$为当前比了$i$场,背包容量为$j$,赢了$x$场的概率。
$f(i,j,x)=f(i-1,j,x)\times (1.0-p[i])+f(i-1,j-a[i],x-1)\times p[i]$

因为一共只有200场,所以背包容量>200是没有意义的,每次容量对200min/max一下就行了。
还有$0\leqslant j\leqslant 400$,当$j>=200$时表示背包还有$400-j$的空余容量,当$j< 200$时表示有$200-j$个残片没装。

代码:


#include <bits/stdc++.h>
using namespace std;
int n,l,k,arr[205];
double p[205],f[205][405][205],ans;
int main()
{
    freopen("guard.in","r",stdin),freopen("guard.out","w",stdout);
    scanf("%d%d%d",&n,&l,&k),k=min(k,n);
    for(int i=1;i<=n;i++)scanf("%lf",&p[i]),p[i]/=100.0;
    for(int i=1;i<=n;i++)scanf("%d",&arr[i]);
    f[0][k+200][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=400;j++)
            for(int x=0;x<=i;x++)
                f[i][j][x]=f[i-1][j][x]*(1.0-p[i])+f[i-1][max(j-arr[i],0)][x-1]*p[i];
    for(int i=200;i<=400;i++)
        for(int j=l;j<=n;j++)
            ans+=f[n][i][j];
    printf("%.6lf",ans);
    return 0;
}

T3 hamilton

考场打了个5维floyd。。。
要交的时候改成了输出0。。。
得10分。。。
后来发现五维floyd可以拿30。。。

思路:状压dp
设$f(i,s)$为从节点$i$出发,访问状态为$s$时的简单环个数。
状态:二进制下,$s$的第$k$位为1表示节点$k$被访问过了,为0表示没访问过。
为防止重复计算,我们让$i$为状态$s$中编号最小的节点。
然后因为从一个节点扩展,环的双向都走过了,所以答案要除以二输出。

时间1s,最后一个点5s。。。下面提供两个优化方法(优化后第9个点0.2s,第10个点1.2s,原本是第9个点1.2秒,第10个点5.7秒)。

  1. 用low_bit函数计算状态$s$中编号最小的节点——先预处理处$log2(2^i)$的值,每次获得最小节点编号则:$log2(low\_ bit(s))$。

  2. 预处理出状态$s$中被访问的节点个数($s$二进制下数字1的个数),递推实现即可

代码:


#include <bits/stdc++.h>
using namespace std;
static const int maxs=20;
typedef long long LL;
int n,m,lg[1<<maxs],cnt[1<<maxs];
bool book[maxs][maxs];
LL f[maxs][1<<maxs],ans;
int main()
{
    freopen("hamilton.in","r",stdin),freopen("hamilton.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)for(int j=0;j<(1<<i);j++)cnt[j|(1<<i)]=cnt[j]+1;
    for(int i=0;i<n;i++)lg[1<<i]=i;
    for(int i=1,a,b;i<=m;i++)scanf("%d%d",&a,&b),a--,b--,book[a][b]=book[b][a]=1;
    for(int i=0;i<n;i++)f[i][1<<i]=1;
    for(int s=1;s<(1<<n);s++)
    {
        int i=lg[s&(-s)];
        for(int j=i;j<n;j++)
            if((s&(1<<j))&&f[j][s])
            {
                for(int k=i;k<n;k++)
                {
                    int ns=s|(1<<k);
                    if(book[j][k]&&!(s&(1<<k)))
                    {
                        f[k][ns]+=f[j][s];
                        if(book[i][k]&&cnt[ns]>=3)ans+=f[j][s];
                    }
                }
            }
    }
    printf("%lld\n",ans>>1);
    return 0;
}

T4 cg

唔,动态规划的单调队列优化。。。
设$f(i)$为前$i$头牛的最小价值。
$f(i)=max\{f(j)|i-k\leqslant j\leqslant i-1\}$
用单调队列维护:$max\{f(j)|i-k\leqslant j\leqslant i-1\}$

代码:


#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> pll;
LL n,k,arr[100005],sum,minn=LLONG_MAX,f[100005],qf,qt;
pll que[100005];
int main()
{
    freopen("cg.in","r",stdin),freopen("cg.out","w",stdout);
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++)scanf("%lld",&arr[i]),sum+=arr[i];
    f[0]=0,que[qt++]=(pll){0,0};
    for(int i=1;i<=n;i++)
    {
        f[i]=que[qf].first+arr[i];
        while(que[qt-1].first>f[i]&&qf<qt)qt--;
        que[qt++]=(pll){f[i],i};
        while(i-que[qf].second>k&&qf<qt)qf++;
    }
    for(int i=n-k;i<=n;i++)minn=min(minn,f[i]);
    printf("%lld\n",sum-minn);
    return 0;
}

分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *