悲剧的一天

---

这次考试很可恶，题目很可恶，但是最可恶的是偏偏再我感冒的时候考这种恶心的题，结果做地一塌糊涂。

T1 pf

题目来源：未知

题意：用 n 个不同的数组成一个长 p 的序列，要求任意两个相同的数之间至少要有 m 个数。求排列方案数。

考场思路：（我揉了揉卫生纸，屏幕默默地滚动了几下）

思路 1：可以考虑把所有可能的方案数减去与两种要求矛盾的方案数，即 “容斥原理”。

思路 2：可以考虑使用动态规划，若 f[i][j] 表示序列中前 i 个数用前 j 种给定数字有几种方案，那么

\begin{equation}
f[i][j]+=f[i-1][j-1];
\end{equation}
\begin{equation}
f[i][j]+=f[i-1][j]*(j-m);
\end{equation}

(1) 式为用新的数字，(2) 式为用原有的数字，不与中间 m 个重复。f[i][j] 的递推有一定范围限制，详见代码。

最后,f[p][n] 表示长度为 p 的序列用排列好的 n 种数字的方案数，所以我们需要将 f[p][n] 乘上 n!。

#include <iostream>
#include <cstdio>

#define MD 1000000007

using namespace std;

typedef long long ll;
int n,m,p;
ll f[10001];

void input(){scanf("%d%d%d",&n,&m,&p);}

int main()
{
    freopen("pf.in","r",stdin),freopen("pf.out","w",stdout);
    input();
    f[1]=1;
    for(int i=2;i<=p;i++)
        for(int j=n;j>=1;j--)
            if(j-m>=0)f[j]=(f[j-1]+(f[j]*(j-m))%MD)%MD;
            else f[j]=(f[j-1])%MD;
    for(int i=1;i<=n;i++)f[n]=f[n]*i%MD;
    cout<<f[n]<<endl;
    return 0;
}

---

T2 guard

题目来源：CodeVS1997

题意：（请过目）

打开了黑魔法师 calashock 的大门，队员们在迷宫般的路上漫无目的地搜寻着关押 demo 的监狱的所在地。突然，眼前一道亮光闪过。“我，nandemo，是黑魔法圣殿的守卫者。如果你能通过我的挑战，那么你可以带走黑魔法圣殿的地图……” 瞬间，队员们被传送到了一个擂台上，最初身边有一个容量为 k 的包包。
擂台赛一共有 m 项挑战，各项挑战依次进行。第 i 项挑战有一个属性 ai，如果，表示这次挑战成功后可以再获得一个容量为 ai 的包包；如果 ai=-1，则表示这次挑战成功后可以得到一个大小为 1 的地图残片。地图残片必须装在包包里才能带出擂台，包包没有必要全部装满，但是队员们必须把获得的所有的地图残片都带走（没有得到的不用考虑，只需要完成所有 n 项挑战后背包容量足够容纳地图残片即可），才能拼出完整的地图。并且他们至少要挑战成功次 l 才能离开擂台。
队员们一筹莫展之时，善良的守卫者 nandemo 帮忙预估出了每项挑战成功的概率，其中第项挑战成功的概率为 pi/100。现在，请你帮忙预测一下，队员们能够带上他们获得的地图残片离开擂台的概率。

考场思路：简单的概率 Dp，用 f[i][j][k] 表示前 i 场赢 j 场背包容量为 k 时的获胜概率，由于背包容量大于 200 是没有意义的，所以逆推时赢了也不给他 200 以上背包，输了再扣，但是上个厕所估计是忘了这回事，于是 k 开到 100000，用滚动数组加上一堆很邪门的判断和优化水过了（数据太水了，没有容量很大的情况）

思路：就是考场思路的前半部分。

给出考场代码吧，懒得改了。

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

#define MNS 201

using namespace std;

double f1[201][100000];
double f2[201][100000];
int nowf;
double p[300];
int a[300];
int n,l,k;
int totv,minv,mxv;


void input()
{
    scanf("%d%d%d",&n,&l,&k);
    for(int i=1;i<=n;i++)scanf("%lf",&p[i]);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),totv+=max(a[i],0),minv+=min(0,a[i]),mxv=max(mxv,a[i]);
    mxv+=abs(k);
    minv-=abs(k);
}

void init()
{
    for(int i=l;i<=n;i++)
        for(int j=0;j<=200;j++)
            f1[i][j+MNS]=1.0;
}

void work()
{
    for(int i=n-1;i>=0;i--)
    {
        for(int j=i;j>=0;j--)
        {
            for(int v=200;v>=minv;v--)
            {
                if(nowf==1)
                    f2[j][v+MNS]=((100-p[i+1])/100)*f1[j][v+MNS]+(p[i+1]/100)*f1[j+1][min(v+a[i+1],200)+MNS];
                else
                    f1[j][v+MNS]=((100-p[i+1])/100)*f2[j][v+MNS]+(p[i+1]/100)*f2[j+1][min(v+a[i+1],200)+MNS];
            }
        }
        nowf=3-nowf;
    }
    if(nowf==1)printf("%.6f\n",f1[0][k+MNS]);
    else printf("%.6f\n",f2[0][k+MNS]);
}

int main()
{
    nowf=1;
    freopen("guard.in","r",stdin),freopen("guard.out","w",stdout);
    input();
    init();
    work();
    return 0;
}

---

T3 hamilton

来源：CodeForces11D

题意：哈密顿回路计数

考场思路：暴力 50 分 ($O(n!)$)

思路：状压DP，($O(n^2*2^n)$), 若f[k][i]表示从点集k中编号最小的点出发经过所有k中的点到达i点的简单路径条数，那么枚举：任意的i,j满足:i∈k,(i,j)∈E，j>=min{x,x∈k}, 那么如果 j 为 k 中编号最小的点，那么对 ans+=f[k][i], 如果 j∉k, 那么 f[k∪{j}][j]+=f[k][i], 只需要按照 k 中点的数量的递增顺序枚举 k 的所有情况即可。最后由于每个环正着反着都计数了一遍，且二元环也计数了一遍，所以减去二元环数除以二。

↓超级不压行大发

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <iostream>

#define MX 25

using namespace std;

typedef long long ll;

int mp[MX][MX];
int fst[MX],nxt[MX*MX*2],u[MX*MX*2],v[MX*MX*2],lnum=-1;
ll f[6000000][MX];
int n,m;
ll ans;

void addeg(int nu,int nv)
{
    lnum++;
    nxt[lnum]=fst[nu];
    fst[nu]=lnum;
    u[lnum]=nu;
    v[lnum]=nv;
}

void input()
{
    memset(fst,0xff,sizeof(fst));
    int a,b;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&a,&b);
        addeg(a,b);
        addeg(b,a);
        mp[a][b]=mp[b][a]=1;
    }
}

void sch(int nowset,int top,int now,int dep,int first)
{
    if(dep==top+1)
    {
        for(int i=first; i<=n; i++)
        {
            if(nowset&(1<<i))
            {
                for(int j=fst[i]; j>=0; j=nxt[j])
                {
                    if(v[j]>=first)
                    {
                        if((nowset&(1<<v[j]))==0)f[nowset|(1<<v[j])][v[j]]+=f[nowset][i];
                        else if(v[j]==first)ans+=f[nowset][i];
                    }
                }
            }
        }
        return ;
    }
    for(int i=now;i<=n;i++)
    {
        sch(nowset|(1<<i),top,i+1,dep+1,min(first,i));
    }
}

int main()
{
    freopen("hamilton.in","r",stdin),freopen("hamilton.out","w",stdout);
    for(int i=1;i<=20;i++)f[(1<<i)][i]=1;
    input();
    for(int i=1;i<=n;i++)sch(0,i,1,1,99);
    cout<<(ans-m)/2<<endl;
    return 0;
}

---

T4 cg

来源：CodeVS4654

题意：给定非负序列，选取一些元素使没有任意 k 个元素相连，使元素和最大

考场思路：Dp 骗几分吧，好歹是 $O(nk)$的。虽然发现用线段树维护区间最大值可以做，但是懒得打了。

思路：问题转化成：每隔 k 个至少选 1 个元素，选的和最小

所以可以用单调队列优化。队列左边的比右边的先进来，值更小，每次维护队列单调性，队列最左端的就是可以选的最小值。

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

using namespace std;

typedef long long ll;

ll src[100002],tot;
ll f[100002];
int q[100002],n,k;

void input()
{
    scanf("%I64d%I64d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%I64d",&src[i]),tot+=src[i];
}

void work()
{
    int l=1,r=1;
    q[r]=0;
    for(int i=1;i<=n+1;i++)
    {
        f[i]=f[q[l]]+src[i];
        while(f[i]<f[q[r]]&&l<=r)r--;
        q[++r]=i;
        while(q[r]-q[l]>k&&l<=r)l++;
    }
    cout<<tot-f[n+1]<<endl;
}

int main()
{
    freopen("cg.in","r",stdin),freopen("cg.out","w",stdout);
    input();
    work();
    return 0;
}