考试策略

T1 不可做,T2 不可做,T3 不可做……

今天考试看到题目第一句话就是:“凸包是什么”,第二句话是:“Day3 是什么”,后来经 WY 大佬指示才发现是 “NOIp” 模拟,注意,只有 “p” 是小写啊!

由于 T1 的暴力容易写一些,所以先写了 T1,然后写了 T2 的暴力。

结果今天只考了 60 分就 Rank1 了……T3 所有人都爆 0……

T1

期望得分: 40 实际得分:40

题目描述

在不存在 (所以我们今天考了场假试?) 的 noip day3 里小 w 见到了一堆堆的谜题。
比如这题为什么会叫共轭?
他并不知道答案。
有 n 堆谜题,每堆有 a i 个,小 w 每次从剩下的谜题中选择一个,然后把所在的那一堆谜题全部丢掉。
小 w 期望多少次后丢掉第一堆?

数据范围

对于 20% 的数据,$n \leq 10$
对于 40% 的数据,$n \leq 1000$
对于另外 20% 的数据,$a_i=1$
对于 100% 的数据 $n \leq 10^5 ,1 \leq a_i \leq 10^9$

题目分析

首先对于 $n \leq 10$,我们可以暴力搜出每一种丢掉方式和发生这种方式的概率,以此算期望。

对于 $a_i=1$的情况,设 f(x) 表示还剩下 x 堆的时候丢掉第一堆的期望,显然 $f(x)=\frac{1}{x}+\frac{x-1}{x}(f(x-1)+1)$

于是我们有了 40 分。

你会发现 40 分做法很优美 个鬼啊 ,然而 100 分算法也很容易…… 我们可以单独算除了 1 以外某一堆对期望的贡献,会发现任何一堆,如果它在第一堆被丢掉之前被丢掉,带来的丢掉次数是 1,而它在第一堆被丢掉之前被丢掉的概率是 $\frac{a_i}{a_i+a_1}$,所以…… 代码见下……

所以到底是为什么这道题没有人做出来啊喂,看来我们的期望都白学了……

代码

 #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+10;
double ans=1;int n,a[N];
int main()
{
    freopen("conjugate.in","r",stdin);
    freopen("conjugate.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    for(int i=2;i<=n;++i) ans+=a[i]*1.0/(a[1]+a[i]);
    printf("%.12lf\n",ans);
    return 0;
}

T2

期望得分:40 实际得分:20(然而是题目的锅)

题目描述

小 w 有一个由 0、1、2 构成的序列。
他可以每次选一个序列中的数,把它移动到序列中任意一个位置。
要用最少多少次可以让 0 和 1 不相邻?
为了考验你的真实水平,小 w 决定使用多组数据。

数据范围

对于 20% 的数据,每个 $n \leq 10$
对于 40% 的数据,每个 $n \leq 100$
对于另外 20% 的数据,保证只有一个 2
对于 100% 的数据,保证 $\sum n \leq 5000$

暴力分析

对于 20% 保证只有一个 2 的数据,组成的序列里只要既有 1 又有 0(当然要判断 0 或 1 只有一个的情况),那么一定是 2 放在某个位置,一边全是 0 一边全是 1。所以枚举 2 放的位置,把某一边的 1 全部挪到另一边,把另一边的 0 全部挪过了即可。

对于 20% 的 $n \leq 10$,我们可以使用迭代加深搜索。由于每一次移动最多只有三个数字的 “前面数字” 会发生改变(挪动的数,挪动的数后面的数,挪动的数到新位置后其后面的数),所以我们令 h() 表示 “前面数字” 不符合要求的情况,然后设 maxd 为当前最大层数,d 为当前层数,当 $h()+3d>maxd$时可以剪枝。不过这样还是扩展了很多无用状态,由于可能会有 500 组数据,这样还是拿不到 20 分。于是我们需要用哈希来判重。

于是我花了两个小时打好了一个价值 20 分的迭代 A 星加哈希剪枝优化的深搜,结果这个迭代 A 星加哈希剪枝优化的深搜没有给我带来 20 分,因为出题人并没有说无解输出-1 但是有无解的情况并且要输出-1,于是我白打了这个迭代 A 星加哈希剪枝优化的深搜。

暴力代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
int n,T,ans,t1,t0,j2,j0,j1,kl;
int a[5005],vis[200000][6];
int h() {//(伪)估价函数
    int re=0;
    for(int i=2;i<=n;++i)
        if(a[i]==1&&a[i-1]==0) ++re;
        else if(a[i]==0&&a[i-1]==1) ++re;
    return re;
}
int has() {//哈希
    int t=1,i,re=0;
    for(i=1;i<=n;++i)
        re+=t*a[i],t*=3;
    return re;
}
int dfs(int d,int maxd) {//深搜的正文
    int i,j,k,t,kl=h(),b[12],kk;
    if(kl+3*d>maxd*3) return 0;
    if(!kl)return 1;
    kk=has();if(vis[kk][d]){return 0;}vis[kk][d]=1;
    for(i=1;i<=n;++i) b[i]=a[i];
    for(i=1;i<=n;++i) {
        t=0;
        for(j=1;j<=n;++j)if(j!=i) a[++t]=b[j];
        a[n]=b[i];
        for(j=n;j>=1;--j) {
            if(dfs(d+1,maxd)) {
                for(k=1;k<=n;++k) a[k]=b[k];
                return 1;
            }
            if(j==1) break;
            swap(a[j],a[j-1]);
        }
    }
    for(i=1;i<=n;++i) a[i]=b[i];
    return 0;
}
int main()
{
    freopen("conjunct.in","r",stdin);
    freopen("conjunct.out","w",stdout);
    int i,bj;T=read();
    while(T--) {
        n=read();
        for(i=1;i<=n;++i) a[i]=read();
        if(n<=10) {
            bj=0;
            for(i=0;i<=n/2;++i) {
                memset(vis,0,sizeof(vis));
                if(dfs(0,i)){printf("%d\n",i);bj=1;break;}
            }
            if(!bj)puts("-1");
        }
        else {//对于只有一个 2 的情况的暴力
            t1=t0=j0=j1=0;ans=1e7;
            for(i=1;i<=n;++i)
                if(a[i]==1) ++t1;
                else if(a[i]==0) ++t0;
                else j2=i;
            if(!t1||!t0){ puts("0");continue;}
            for(i=0;i<=n;++i) {
                if(j2==i) continue;
                if(a[i]==1&&i!=0) ++j1;
                else if(a[i]==0&&i!=0)++j0;
                kl=min(j1+t0-j0,j0+t1-j1);
                if(j2!=i+1) ++kl;
                ans=min(ans,kl);
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}

正解分析

好的那么问题来了:正解是什么?

正解是 dp(我花了大约两个半小时来看懂正解 QAQ)。

首先我们可以发现,我们移动数的过程可以看作是不动原序列与最终序列的 lcs,然后把其他数都动一次。因此我们只要在原序列里选出一段最长的符合要求的子序列(注意此处的 “子序列” 并不一定是在原序列中截取的连续的一段)即可。

什么叫符合要求?显然最珍贵的资源是 2,选出一个子序列后,对于 2 的需求量就求出来啦(子序列里的 2 的数量+子序列里相邻的 0 和 1 的数量),而对于 2 的需求量不超过原序列里 2 的数量的子序列就是符合要求的…… 所以我们需要记录子序列上一个选择的数是什么……

等等!还没完!假如对于一个既有 0 又有 1 并且只有一个 2 的序列,我选出了一个这样的序列:1 1 2 1 1 剩下的 0 往什么地方放啊???所以这样的子序列显然也是不符合要求的。因此我们还需要记录两个东西:d0 和 d1,分别表示当前选出的子序列中有没有可以放一段 0 的地方,有没有可以放一段 1 的地方。

好的,得到状态后我们继续分析实现代码。

1. 如果整个序列没有 1 或者没有 0,可以直接输出 “1”

2. 如果整个序列没有 2,可以直接输出无解的 “-1”

3. 接下来,我们需要两个状态:f(i,d0,d1) 和 g(x,i,d0,d1),其中 f 是一个临时数组,g 是永久的。g 的含义:子序列的末尾是 x,子序列已经带来了 i 的对 2 的需求量,子序列是否留给 0 和 1 位置(d0 和 d1),这样一个状态下选出的最长子序列长度。而 f 的含义中 i,d0,d1 同 g 中的 i,d0,d1,不过 f 是临时的(具体含义等下讲)

4. 现在我们看一看状态转移方程:

for(i=0;i<=2;++i) for(j=0;j<=n;++j)
    g[i][j][0][0]=g[i][j][1][0]=g[i][j][0][1]=g[i][j][1][1]=-inf;
g[2][0][0][0]=0;//可以假装子序列最开头有一个 2(因为开头放什么都没问题)
//一些变量的意思:tot 是原序列中 2 的数量,ans 是最长序列的长度(要去求)
for(i=1;i<=n;++i) {
    for(j=0;j<=tot;++j) f[j][0][0]=f[j][0][1]=f[j][1][0]=f[j][1][1]=-inf;
    //f: 一个临时的 dp 数组,表示的含义见上,并且 f 储存的那个子序列末尾一定是 a[i]
    for(las=0;las<=2;++las)
        for(j=0;j<=tot&&j<=i-1;++j)
        for(d0=0;d0<=1;++d0) for(d1=0;d1<=1;++d1) {
        D0=d0||(a[i]==0),D1=d1||(a[i]==1);
        if(las==2&&a[i]==2) D0=D1=1;
          //如果子序列中出现了两个连续的 2,那么下划线处可以放一个给 0 的区间和一个给 1 的区间:_2_2
        if((a[i]^las)==1||(a[i]==2)) //需要一个 2
            f[j+1][D0][D1]=max(f[j+1][D0][D1],g[las][j][d0][d1]+1);
        else f[j][D0][D1]=max(f[j][D0][D1],g[las][j][d0][d1]+1);//不一定需要一个新的 2
    }
    for(j=0;j<=i&&j<=tot;++j)//更新 g 数组
        for(d0=0;d0<=1;++d0) for(d1=0;d1<=1;++d1)
            g[a[i]][j][d0][d1]=max(g[a[i]][j][d0][d1],f[j][d0][d1]);
   //以下是答案统计部分
    for(j=0;j<=tot;++j) ans=max(ans,max(f[j][0][0],f[j][1][1]));
    for(j=0;j<=tot-1;++j) ans=max(ans,max(f[j][1][0],f[j][0][1]));
    if(a[i]==2) ans=max(ans,max(f[tot][0][1],f[tot][1][0]));
  //如果已经 “用掉了” 所有的 2(所有的 2 被需求),并且给 0 或给 1 的区间有一个没有留出来,除非末尾是 2(f 表示的序列末尾是 a[i] 啊)的时候,可以在末尾新添一个区间放 0 或 1,否则这个子序列就是不合要求的。
}

正解代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
const int N=5050,inf=1e6+5;
int T,n,t1,t0,tot,ans;
int a[N],g[3][N][2][2],f[N][2][2];
//g[x][i][d0][d1]: 末尾是 x,子序列需要 i 个 2, 有无放 1 和 0 的区间选出的最长子序列长度(不必须选择当前数)
//f[i][d0][d1] 子序列需要 i 个 2,有无放 1 和 0 的区间时选出的最长子序列长度(必须选择当前数)
void work() {
    int i,j,d0,d1,D0,D1,las;ans=0;
    for(i=0;i<=2;++i) for(j=0;j<=n;++j)
        g[i][j][0][0]=g[i][j][1][0]=g[i][j][0][1]=g[i][j][1][1]=-inf;
    g[2][0][0][0]=0;
    for(i=1;i<=n;++i) {
        for(j=0;j<=tot;++j) f[j][0][0]=f[j][0][1]=f[j][1][0]=f[j][1][1]=-inf;
        for(las=0;las<=2;++las)
            for(j=0;j<=tot&&j<=i-1;++j)
            for(d0=0;d0<=1;++d0) for(d1=0;d1<=1;++d1) {
            D0=d0||(a[i]==0),D1=d1||(a[i]==1);
            if(las==2&&a[i]==2) D0=D1=1;
            if((a[i]^las)==1||(a[i]==2)) 
                f[j+1][D0][D1]=max(f[j+1][D0][D1],g[las][j][d0][d1]+1);
            else f[j][D0][D1]=max(f[j][D0][D1],g[las][j][d0][d1]+1);
        }
        for(j=0;j<=i&&j<=tot;++j)
            for(d0=0;d0<=1;++d0) for(d1=0;d1<=1;++d1)
                g[a[i]][j][d0][d1]=max(g[a[i]][j][d0][d1],f[j][d0][d1]);
        for(j=0;j<=tot;++j) ans=max(ans,max(f[j][0][0],f[j][1][1]));
        for(j=0;j<=tot-1;++j) ans=max(ans,max(f[j][1][0],f[j][0][1]));
        if(a[i]==2) ans=max(ans,max(f[tot][0][1],f[tot][1][0]));
    }
    printf("%d\n",n-ans);
}
int main()
{
    freopen("conjunct.in","r",stdin);
    freopen("conjunct.out","w",stdout);
    T=read();
    while(T--) {
        n=read();t0=t1=tot=0;
        for(int i=1;i<=n;++i)
            a[i]=read(),t0+=(a[i]==0),t1+=(a[i]==1),tot+=(a[i]==2);
        if(!t0||!t1){puts("0");continue;}
        if(!tot){puts("-1");continue;}
        work();
    }
    return 0;
}

T3

期望得分: 0.4 实际得分:0

题目描述

听说 noip 不会考几何 (那你还考?),所以当 Day3 出现了一道几何题的时候,小 w 的内心是崩溃的。
有 n 个三维空间里的点,每个点有 p i 的概率出现,求期望意义下凸包上有多少个点。
一个点不在凸包上,当且仅当存在一个四面体严格包含了这个点。

数据范围

对于 20% 的数据,保证 $n \leq 15$
对于 40% 的数据,保证 $n \leq 30$
对于另外 20% 的数据,保证 $p_i=1$
对于 100% 的数据,保证 $n \leq 50$,保证任意三点不共线,任意四点不共面

题目分析

我不会凸包……

更不会三维凸包……

我好弱啊……

另外所有人这题都爆 0 了……

吾不言,吾不言……

分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

发表评论

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